In The Second Theory of Cryptography Conference (TCC 2005), Boneh, Goh, and Nissim proposed a new structure of bilinear groups that have a composite order and a new cryptosystem which is intractable on a decisional problem over the subgroup in such structure [BGN05]. Their proposal, which referred to as the BGN cryptosystem by researchers, receive much attention and is quickly followed by two publications in CRYPTO'05 [BI05, OI05].
The BGN cryptosystem is a dual homomorphic public-key cryptosystem that enables the evaluation of 2-DNF (disjunctive normal form) formulas on ciphertexts. In their work, Boneh et. al. also presented three applications, namely private information retrieval with reduced computational complexity, an e-voting system without non-interactive zero knowledge proofs, and a protocol for universally verifiable computation. Few number of works also produced from the BGN public-key system, include non-interactive zero-knowledge proof (NIZK), obfuscated ciphertext mixing, and signature.
In this thesis, the author performs in-depth study of the BGN public-key cryptosystem and existing literatures on its applications. The author observes two properties of BGN, namely the indistinguishability of the BGN ciphertexts of sum and product of two messages, and the verifiability of elements from composite prime subgroups in BGN settings. The author further proposes three new applications of BGN, namely the protocols for authentication, oblivious transfer, and proof-of-visit respectively.
Blum integers (BL), which has extensively been used in the domain of cryptography, are integers with form p , where p and q are di#erent primes both 3 mod 4 and k 1 and k 2 are odd integers. These integers can be divided two types: 1) M = pq, 2) M = p at least one of k 1 and k 2 is greater than 1.
It's essential on algorithm design of designated confirmer signatures to construct proofs satisfying security requirements such as unforgetablility, non-transferability, invisibility and zero-knowledge. A designated confirmer signature protocol (RSA-DCSV) is proposed, based on RSA encryption and signature schemes in forms of RSA extended modular computations. Proofs for a designated verifier are considered. Security analysis on RSA-DCSV is also addressed.
A protocol for zero-knowledge proofs of identity based on ElGamal on conic is proposed in this paper. The solution to a hard puzzle is divided into two parts, and the P (prover) provides one of them according to the V (verifier) 's random bit. The eavesdropper cannot obtain any useful knowledge about the P (prover) 's identity during the process of authentication. No adversary in this protocol can cheat each other or get the privacy of each other. The security of this protocol relies on the discrete logarithm problem on conic over finite fields. Compared with those identification protocols implemented on elliptic, these kinds of identification protocols implemented on conic can be designed and implemented easier. Corresponding to the simple version, a parallel version is presented subsequently. The characteristic of ZKp and security of the simple version is proved. The trait of our identification protocol is given. We also analyzed the "soundness ", the "completeness ", before analyzed the amount of computation in the protocol. A simple solution considering t/sub timeout/ is proposed to prevent a potential leak of our protocol. Some problems need to be solved in the future is brought forward at the end of this paper.
Subliminal channel is proposed by Simmons, he showed a method that a message authentication without secrecy channel transferring secret message. Subsequently, subliminal channel is implemented in ElGamal, DSA which based on the difficulty of discrete logarithms. Zero-knowledge proof is an important tool in cryptology, a digital signature scheme based on zero-knowledge proof or “cut and chose” is regarded as resist subliminal channel. The possibility of constructing subliminal channel in these digital signature scheme is analyzed, the security and application of subliminal channel is discussed also.
This paper proposed a protocol for zero-knowledge proof of identity based on ElGamal on conic. It is more appropriate than the traditional identity protocol in distributed environment without trusted third parties. The security of this protocol relies on the discrete logarithm problem on conic over finite fields. Compared with those identification protocols implemented on elliptic curve, this protocol can be designed and implemented easier. And compared with that security lies on disassemble a large number, it runs faster. Corresponding to the simple version, a parallel version is presented subsequently. The characteristic of ZKp and security of the simple version is proved. The "soundness", "completeness", and amount of computation are also analyzed. A simple solution considering t/sub timeout/ is proposed to prevent a potential leak of our protocol.
In this paper we propos eas imple PVSS scheme based on the homomorphic properties of Paillier' se ncryption scheme. This ne ws cheme is the first known PVSS scheme based on the decisional composite residuosity assumption. The verification process in this scheme is much simpler than in the other known schemes. Furthermore, in our proposal, verification is made non-interactive without using th eF iat-Shamir technique or an ya dditional Zero Knowledge proof.
A new threshold digital signature using the research result about the digital signature with zero knowledge proof was proposed in this paper. The security of this algorithm is based on large number of factorizations and security of RSA. The scheme doesn’t need to invert any elements in any structure, and then no algebraic extension is needed for any structure. It is useful for the information security.
A zero-knowledge proof of identity protocol on conic is proposed in this paper.The security of this protocol is based on the discrete logarithm problem on conic over finite fields.These kinds of identity protocols can be designed and implemented easier than those on elliptic curve,and faster than those based on discrete logarithm.Security and feasibility are discussed.A simple solution is proposed to a potential leak of this protocol.
We propose an approach using elliptic curve-based zero-knowledge proofs in e-commerce applications. We demonstrate that using elliptic curved-based zero-knowledge proofs provide privacy and more security than other existing techniques. The improvement of security is due to the complexity of solving the discrete logarithm problem over elliptic curves.
Ma and Chen proposed a new authenticated encryption scheme with public verifiability. This scheme requires less computational costs and communication overheads than the conventional signature-then-encryption approaches. In this letter, we show that the Ma-Chen scheme does not satisfy three security properties: unforgeability, confidentiality and non-repudiation. Introduction: For electronical commercial applications, evidence of possession of documents is especially important. A digital signature is analogous to an ordinary hand-written signature and establishes both of signer authenticity and data integrity assurance. However, it is necessary to keep commercial documents confident to protect the privacy of users in many applications. One simple way to implement such authenticated encryption scheme is to sign and encrypt message separately, first-sign-then-encrypt or first-encrypt-then-sign. This way perhaps results in separation of signature and ciphertext. Other way is to combine signature and encryption together in order to reduce the amount of computational cost and communication overheads. In 1997, Zheng proposed two new combined schemes [1], called signcryption scheme, in which message encryption and digital signature are simultaneously fulfilled in a logically single step. Besides some security shortcomings [2, 3], the Zheng schemes are not efficient as a zero-knowledge proof is required in its non-repudiation protocol. Recently, Ma and Chen proposed a new authenticated encryption scheme with public verifiability [4]. They claimed that their scheme is as efficient as the Zheng signcryption schemes with respect to both computational costs and communication overheads. In addition, their scheme has an efficient non-repudiation procedure without using a zero-knowledge proof protocol. Ma and Chen further claimed that their scheme satisfy three security properties: unforgeability, confidentiality and non-repudiation. In this letter, we would show the Ma-Chen scheme is not only erroneous but also insecure. The honest receiver cannot convince the judge that the valid signature is signed by the true signer, while the dishonest receiver can deceive the judge into believing the forged signature of any message. Moreover, if the scheme is adapted for the case of a long message, it cannot withstand the known plaintext-ciphertext attack. Belief review of the Ma-Chen scheme: Initially, two large primes p and q with q|(p – 1) and an element g ∈ Zp of order q are computed by a trusted third party (TTP for short) and are authenticated to each user. Each user i ∈{A, B} chooses a secret key xi∈ Zqand computes his public key yi = i x g mod p. He publishes yi which is 1 of 4 Tuesday , September 09, 2003
Based on the zero-knowledge proof protocol a new forward-secure digital signature scheme is proposed. The scheme is proven to be forward secure based on the hardness of factoring,discrete logarithm and quadric remain problems in the random oracle model.
Zero-knowledge interactive proof is a useful tool for designing identification and digital signature schemes. We propose a new interactive proof based identification and signature scheme.
With increasing demands for internet security, the demand for distribution of public key certificates and certificate authorities spreads. This brings up the new problem of public key validation. This problem can arise in different contexts and can be adressed in some of them using novel zero knowledge protocols, while in other contexts it can be only poorly solved. The purpose of this paper is to give an overview of the topic of key validation and to discuss the possible solutions to the different instances in which it appears. We also present a new zero knowledge protocol for correctness of an RSA public exponent and a simple protocol (not zero-knowledge) for primality of a discrete logarithm. We use the latter to give a proof protocol (not zero knowledge) that an RSA key is the product of strong primes These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Let n be a large composite number. Without factoring n, the computation of a 2 t (mod n)given a, t with gcd(a# n) = 1 and t!n can be done in t squarings modulo n.For t n (e.g., n?2 1024 and t!2 100 ), no lower complexity than t squarings is known to fulfill this task. Rivest et al suggested to use such constructions as good candidates for realising timed-release crypto problems. We argue the necessity for a zero-knowledge proof of the correctness of such constructions and propose the first practically efficient protocol for a realisation. Our protocol proves, in log 2 t standard crypto operations, the correctness of (a e ) 2 t (mod n) with respect to a e where e is an RSA encryption exponent. With such a proof, a Timed-release Encryption of a message M can be given as a 2 t M (mod n) with the assertion that the correct decryption of the RSA ciphertext M e (mod n) can be obtained by performing t squarings modulo n starting from a. Timed-release RSA signatures can be constructed analogously. Keywords Timed-release cryptography, Time-lock puzzles, Non-parallelisability, Efficient zero-knowledge protocols. 1