In the paper we prove that all but at most x/A(x) positive integers n ≤ x can be completely factored in deterministic polynomial time C(x), querying the prime decomposition exponent oracle at most D(x) times. The functions A(x), C(x) and D(x) have the polynomial growth (of log x) at infinity.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
G. Miller in his seminal paper from the mid 1970s has proven that the problem of factoring integers reduces to computing Euler’s totient function Φ under the Extended Riemann Hypothesis. We show, unconditionally, that such a deterministic polynomial reduction exists for a large class of integers.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In the paper we investigate the set of odd, squarefree positive integers n that can be factored completely in polynomial timeO(log6+ε n), given the prime decomposition of orders ordnb for b ≤ logη n, (η > 2), which is closely related to DLPC problem. We prove that the number of n ≤ x that may not be factored in deterministic time O(log6+εn), is at most (η - 2)-1x(log x)-c(η-2), for some c > 0 and arbitrary ε > 0.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W artykule analizujemy wyzwania dla polskiej kryptologii XXI wieku ze szczególnym uwzględnieniem potrzeb narodowej kryptologii i roli, jaką spełniają w niej wybrane dziedziny matematyki, takie jak teoria liczb i geometria algebraiczna. W szczególności pokreślono rolę i bezpieczeństwo kryptosystemów bazujących na iloczynach dwuliniowych, a także problemy złożoności obliczeniowej ważnych dla kryptologii algorytmów deterministycznych. Wskazano na znaczenie funkcji typu L we współczesnej kryptografii i kryptoanalizie.
EN
In this paper we analyze the challenges for the twenty-first century Polish cryptology with special emphasis on the needs of the national cryptology and the role they perform in the selected areas of mathematics such as number theory and algebraic geometry. In particular, westress the role and security of bilinear based cryptosystems, as well as the problems of computational complexity of deterministic algorithms important for cryptology. We pointed out the importance of L-functions in modern cryptography and cryptoanalysis.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In the paper we present the design of new digital signature protocol with the secretly hidden warning in the Gap Diffie-Hellman group. The proposed scheme is the extended Id based protocol applying the idea of Schnorr signature and the subliminal channel defined by Simmons.
PL
W pracy przedstawiono projekt nowego protokołu cyfrowego podpisu z ukrytym ostrzeżeniem wykorzystujący grupę DiffiegoHellmana z luką obliczeniowo-decyzyjną. Proponowany schemat jest oparty na rozszerzonym protokole podpisu bazującego na tożsamości i wykorzystuje schemat C. P Schnorra i ideę kanału podprogowego zainicjowaną przez G. Simmonsa.
We present a digital signature scheme with secretly embedded warning. The embedded warning is a protection mechanism in case of restraint or blackmail. Extending ordinary digital signatures we propose schemes where a signer, approached by a powerful adversary that demands handing over a signing key, can disclose his private key. In our solution the signer is able to generate a feigned key indistinguishable from the genuine one. Then such a key can be used to embed a special warning message within a signature to indicate coercion. Such warnings can be transferred via subliminal channel to some trusted authority.
Artykuł prezentuje interdyscyplinarną perspektywę metod uwierzytelniania stosowanych we współczesnej gospodarce elektronicznej. Prezentowane są aspekty informatyczne kryminalistyczne prawne a także etyczne związane z systemami uwierzytelniania ze szczególnym uwzględnieniem metod biometrycznych. Analizowane są systemy uwierzytelniania wykorzystujące różne charakterystyki biometryczne. Zaakcentowany został także wymiar kryptograficzny metod uwierzytelniania oraz istotne problemy zarządzania tożsamością cyfrową. Podajemy szereg przypadków użycia analizując dokładniej system paszportu biometrycznego i rozwiązanie stosowane aktualnie w Polsce.
EN
The article presents the interdisciplinary perspective of authentication methods in the context of the current ecommerce development. The presented aspects deal with such domains as computer science, forensic science, legal science, biometry, ethics and cryptography. The authentication systems based on the various biometric characteristics are investigated. The cryptographic approach related to the management of the digital identity is presented. As a case study we consider the system of biometric passport used currently in Poland.
In the paper we present a simple threshold decryption system based on the RSA cryptosystem. Our model avoids the application of the Shamir secret sharing protocol and is based only on the Chinese reminder theorem. The flexibility in the threshold level is attained due to the suitable preparation of the input data. The second part of the article describes a modification of the basic model, which admits the sender's impact on the choice of the real receiver's group.
In the paper the ID-based digital signatures with signer's protection in case of the private key compromising is investigated. The proposed protocols have two main ingredients. First is the application of the credential system for the suitable verification key approval. Second is the application of the subliminal channel together with the interactive generation of the secret key, to obtain the increased resistance of the system against the powerful adversary. The particular interest was turned towards the significance of the deniable encryption in creation of the corresponding protocols.
10
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this paper we propose and prove the security of the new cryptographic primitive called the Anonymous Signer Verifiable Encrypted Signature (ASVES), joining the idea of the group signature and the verifiable encrypted signature. It satisfies the traditional requirements of the group signature (unforgeability, anonymity, unlinkability, traceability) and the opacity condition known from the verifiable encrypted signatures. The corresponding scheme may be applied for the fair exchange protocols. Our construction is based on bilinear pairings, defined in the Gap Diffie-Hellman groups.
We propose the Weil Pairing based threshold flexible signature scheme for dynamic group. The protocol applies the simple additive secret sharing device. Its security is based on the computational Diffie-Hellman problem in the gap Diffie-Hellman groups. The computation of the Weil pairing is the crucial point of our proposition. We have managed to avoid the random numbers generation in the corresponding Miller’s algorithm without an essential increase in the computational cost. The system is particularly interesting when the threshold size is small in relation to the group cardinality.
The work presents a new signature scheme, called the multi-threshold signature, which generalizes the concept of multisignature and threshold signature. This scheme protects the anonymity of signers in a way the group signature does - in exceptional circumstances the identities of signers may be revealed. Due to the new party - completer, in our scheme the threshold size may vary together with the message to be signed. The presented scheme is based on the RSA signature standard, however other signature standards might be applied to it as well.
Artykuł przedstawia nową metodę zabezpieczania baz danych - szyfrowanie z zastosowaniem technik kryptografii progowej. Dzięki temu możliwe jest zminimalizowanie zagrożenia, jakim są ataki napastników wewnętrznych (np. pracowników posiadających dostęp do bazy), gdyż wymagana jest współpraca kilku osób przy odszyfrowywaniu (czyli odczycie) danych. Jest to o tyle ważne, iż obecne systemy zabezpieczeń nie zapewniają takiej ochrony. Opisane w pracy, oparte na RSA i CRT, deszyfrowanie ze zmiennym progiem oferuje pełną elastyczność progu (liczba osób, które muszą współpracować przy deszyfrowaniu) - może on być ustalany osobno dla każdych danych. Sprawia to, iż możliwe jest dokładne dopasowanie poziomu zabezpieczeń do indywidualnych potrzeb. Pierwsza część artykułu wprowadza podstawowe pojęcia z zakresu matematyki (CRT) i kryptografii (RSA i kryptografia progowa), a także zawiera opis podstawowego modelu (jego elementy składowe oraz zastosowane algorytmy szyfrowania i deszyfrowania). W drugiej części artykułu opisano modyfikacje modelu - wprowadzono pojęcia filtrów (ograniczających dostęp do danych podgrupom użytkowników) oraz grup kluczowych (składających się z osób, z których przynajmniej jedna musi brać udział w deszyfrowaniu, by proces ten zakończył się powodzeniem). W drugiej części opisano też dwie sytuacje, w których można zastosować przedstawiony model. Zawarty tam został także przykład liczbowy, ilustrujący poprawność przedstawionych algorytmów.
EN
The works presents a new way of securing the database - dynamic threshold decryption of the encrypted data in the database. It helps to minimize the risk created by the "inside attackers" (e.g. corrupted employees having an access to the database) by requiring of users cooperation in the process of decryption (reading) of data from the database. The currently used database systems are not equipped with this kind of protection. Any single corrupted user with a password can decrypt and steal critical data from the system. In the presented model, the users are equipped merely with the suitable shares. Decryption of data requires the specifi ed number of these shares, so the group of the corrupted users must be large enough to steal the crucial data. This minimal number of shares required for decryption is called "the threshold level". In the "traditional" threshold cryptosystems the threshold level is fixed in advance and cannot be changed (unless the process of the generation of the new shares is executed). Therefore all the messages require the same number of shares needed for the decryption process. The presented model offers the full flexibility of the threshold level. It may vary together with the data to be encrypted. It is important since some data may require higher level of secrecy (protection) than the others. First part of the article gives the mathematical background - it contains the basic information about the RSA cryptosystem, the Chinese reminder theorem and dynamic threshold decryption. It presents the general system model (participants, initial conditions and the algorithms used). Second part describes the possible modifications which make the presented model more secure and practical. It contains also the mathematical example simulating the work (and correctness of the system).
We present a new cryptographic primitive blackmail warning, signature scheme. In distinction to the ordinary signature it allows the signer to include in the signature the additional information whether it was voluntary or forced. The protocol based on veriably encrypted signature in the Gap Diffie-Hellman group is provably secure in the random oracle model. It may be applied for the fair exchange and signing rights designation protocols.
PL
Prezentujemy nowe pojęcie podpisu z ostrzeżeniem o wymuszeniu. W odróżnieniu od zwykłego podpisu pozwala podpisującemu na przekazanie dodatkowej informacji czy podpis został złożony dobrowolnie. Pokażemy dwa protokoły implementujące powyższą funkcjonalność, oba oparte na werykowalnie zaszyfrowanym podpisie w grupie Diego-Hellmana. Mogą one znaleźć zastosowanie np. przy sprawiedliwej wymianie. Ścisły dowód bezpieczeństwa przedstawiony jest w modelu z losową wyrocznią (random oracle model).
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.