Public-key cryptography is a key technology for making the Internet and other IT infrastructures secure. The security of the established public-key cryptosystems relies on the difficulty of factoring large composite integers or computing discrete logarithms. However, it is unclear whether these computational problems remain intractable in the future. For example, Shor showed in 1994 that quantum computers can be used to factor integers and to compute discrete logarithms in polynomial time. It is therefore necessary to develop alternative public-key cryptosystems which do not rely on the difficulty of factoring or computing discrete logarithms and which are secure even against quantum computer attacks. We call such cryptosystems quantum-immune. To prove the security of these quantum-immune cryptosystems, appropriate security models have to be used. Since quantum computers are able to solve problems in polynomial time which are supposed to be intractable for classical computers, the existing security models are inadequate in the presence of quantum adversaries. Therefore, new security models have to be developed to capture quantum adversaries. Properties of these new security models have to be investigated. On a more practical level, the quantum-immune cryptosystems have to be implemented in a way that they can seamlessly replace established cryptosystems. The implementations have to be efficient and suitable for resource-constrained devices. They must easily integrate into existing public-key infrastructures. This thesis contributes to both the theory and practice of quantum-immune cryptography, addressing the above-mentioned challenges. In the theoretical part, we concentrate on the quantum zero-knowledge property of interactive proof systems. We show for the first time that the quantum statistical, perfect, and computational zero-knowledge properties are preserved under sequential composition of interactive proof systems. In the practical part, we provide implementations of the most important quantum-immune cryptosystems. We present efficiency improvements of some of the alternative cryptosystems. The implementations are very efficient and easily integrate into existing public-key infrastructures. We present comprehensive timings that show that the alternative cryptosystems are competitive or even superior compared to established cryptosystems. Finally, we present a new cryptographic API that is particularly well-suited for resource-constrained devices like mobile phones and PDAs. With this API, the alternative cryptosystems can also be used with these devices.
Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the “trusted-party paradigm,” where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to “emulating” the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an ideal functionality. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their “unstable” nature, does not seem to be an easy task. In this paper we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of canonical ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure. In our framework, the constituent functionalities of a task can be derived either directly or, following a translation strategy we introduce, from existing game-based definitions; such definitions have in many cases captured desired individual properties of cryptographic tasks, albeit in less adversarial settings. Our translation methodology entails a sequence of steps that systematically derive a corresponding canonical functionality given a game-based definition, effectively “lifting” the game-based definition to its composition-safe version. We showcase our methodology by applying it to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to “debug” previous definitions and pinpoint their shortcomings.
Abstract. In this paper we consider the problem of increasing the number of possible challenge values from 2 to s in various zero-knowledge cut and choose protocols. First we discuss doing this for graph isomorphism protocol. Then we show how increasing this number improves efficiency of protocols for double discrete logarithm and e-th root of discrete logarithm which are potentially very useful tools for constructing complex cryptographic protocols. The practical improvement given by our paper is 2-4 times in terms of both time complexity and transcript size. 1
This paper presents a new zero knowledge protocol for knowledge of (A,x,y),which is based on Cramer-shoup encryptionfrom linear assumption. Compared with reference,this protocol has one more parameter.
Oblivious transfer, first introduced by Rabin, is one of the basic building blocks of cryp-tographic protocols. In an oblivious transfer (or more exactly, in its 1-out-of-2 variant), one party known as the sender has a pair of messages and the other party known as the receiver obtains one of them. Somewhat paradoxically, the receiver obtains exactly one of the messages (and learns nothing of the other), and the sender does not know which of the messages the receiver obtained. Due to its importance as a building block for secure protocols, the efficiency of oblivious transfer protocols has been extensively studied. However, to date, there are almost no known oblivious transfer protocols that are secure in the presence of malicious adversaries under the real/ideal model simulation paradigm (without using general zero-knowledge proofs). Thus, efficient protocols that reach this level of security are of great interest. In this paper we present efficient oblivious transfer protocols that are secure according to the ideal/real model simulation paradigm. We achieve constructions under the DDH, Nth residuosity and quadratic residuosity assumptions, as well as under the assumption that homomorphic encryption exists. 1
Recently, at Crypto 2008, Boneh, Halevi, Hamburg, and Ostrovsky (BHHO) solved the longstanding open problem of “circular encryption,” by presenting a public key encryption scheme and proving that it is semantically secure against key dependent chosen plaintext attack (KDMCPA security) under standard assumptions (and without resorting to random oracles). However, they left as an open problem that of designing an encryption scheme that simultaneously provides security against both key dependent chosen plaintext and adaptive chosen ciphertext attack (KDM-CCA2 security). In this paper, we solve this problem. First, we show that by applying the Naor-Yung “double encryption” paradigm, one can combine any KDM-CPA secure scheme with any (ordinary) CCA2 secure scheme, along with an appropriate non-interactive zero-knowledge proof, to obtain a KDM-CCA2 secure scheme. Second, we give a concrete instantiation that makes use the above KDM-CPA secure scheme of BHHO, along with a generalization of the Cramer-Shoup CCA2 secure encryption scheme, and recently developed pairing-based NIZK proof systems. This instantiation increases the complexity of the BHHO scheme by just a small constant factor.
This paper presents a protocol aiming at proving that an encryption system contains structural weaknesses without disclosing any information on those weaknesses. A verifier can check in a polynomial time that a given property of the cipher system output has been effectively realized. This property has been chosen by the prover in such a way that it cannot been achieved by known attacks or exhaustive search but only if the prover indeed knows some undisclosed weaknesses that may effectively endanger the cryptosystem security. This protocol has been denoted zero-knowledge-like proof of cryptanalysis. In this paper, we apply this protocol to the Bluetooth core encryption algorithm E0, used in many mobile environments and thus we suggest that its security can seriously be put into question.
The batch verification technique of Bellare et al. is extended to verification of several frequently employed zero-knowledge proofs. The new techniques are correct, sound, efficient, and can be widely applied. Specific applications are discussed in detail, including batch ZK proof and verification of validity of encryption (or reencryption) and batch ZK proof and verification of validity of decryption. Considerable efficiency improvements are gained in these two applications without compromising security. As a result, efficiency of the practical cryptographic systems (such as mix networks) based on these two applications is dramatically improved.
An interactive-PCP (say, for the membership x ∈ L) is a proof that can be verified by reading only one of its bits, with the help of a very short interactive-proof. We show that for membership in some languages L, there are interactive-PCPs that are significantly shorter than the known (non-interactive) PCPs for these languages. Our main result is that the satisfiability of a constant depth Boolean formula Φ(z1, . . . , zk) of size n (over the gates ∧,∨, ⊕,¬) can be proved by an interactive-PCP of size poly(k), followed by a short interactive proof of communication complexity polylog(n). That is, we obtain interactivePCPs of size polynomial in the size of the witness. This compares to the known (non-interactive) PCPs that are of size polynomial in the size of the instance. By reductions, this result extends to many other central NP languages (e.g., SAT, k-clique, Vertex-Cover, etc.). More generally, we show that the satisfiability of Vn i=1[Φi(z1, . . . , zk) = 0], where each Φi(z1, . . . , zk) is an arithmetic formula of size n (say, over GF[2]) that computes a polynomial of degree d, can be proved by an interactive-PCP of size poly(k, d), followed by a short interactive proof of communication complexity poly(d, log n). We give many cryptographic applications and motivations for our results. In particular, we show the following: 1. The satisfiability of a constant depth formula Φ(z1, . . . , zk) of size n (as above) has an interactive zero-knowledge proof of communication complexity poly(k) (rather than poly(n))1 . As before, this result extends to many other central NP languages. This zero-knowledge proof has some additional desired properties that will be elaborated on in the body of the paper. 2. Alice can commit to a Boolean formula Λ of size m, by a message of size poly(m), and later on prove to Bob any N statements of the form Λ(x1) = z1, . . . ,Λ(xN ) = zN by a zero-knowledge proof of communication complexity poly(m, log N). Moreover, if Λ is a constant depth Boolean formula then the zero-knowledge proof has communication complexity poly(log m, log N). We further motivate this application in the body of the paper.
Abstract. Statistical zero-knowledge (SZK) properties play an important role in designing cryptographic protocols that enforce honest behavior while maintaining privacy. This paper presents a novel approach for verifying SZK properties, using recently developed techniques based on approximate simulation relations. We formulate statistical indistinguishability as an implementation relation in the Task-PIOA framework, which allows us to express computational restrictions. The implementation relation is then proven using approximate simulation relations. This technique separates proof obligations into two categories: those requiring probabilistic reasoning, as well as those that do not. The latter is a good candidate for mechanization. We illustrate the general method by verifying the SZK property of the well-known identification protocol proposed by Girault, Poupard and Stern. ⋆ Supported by the MURI project:DARPA/AFOSR MURI F49620-02-1-0325 grant. 1
Zero-knowledge proof is a protocol, and ElGamal's digital signature is widely applied. Gives a GMR module of zero-knowledge proof about ElGamal's digital signature which has little computation, high reliability, and easy to implement.
The use of quantum correlations to attack security protocols is an important research line deserving growing attention. An important class of cryptographic protocols used as building blocks for several other more complex protocols is zero-knowledge proof systems. One of the properties that zero-knowledge proof systems are assumed to satisfy is that it is impossible for the verifier to show to a third party that he has interacted with the prover (impossibility of transferring proofs). Herein, it is shown how Bell pairs, together with tamper-proofing, can be used to break the impossibility of transferring proofs for an important class of zero-knowledge proof systems.
A zero-knowledge proof(ZKP) is a powerful tool which can be used and already be used for many cryptographic applications.But for the completeness property and the soundness property the existing zero-knowledge proofs are iterative in nature.The multiple communication rounds makes ZKPs unsuitable in practice.In this thesis,propose a new ZKP protocol which runs in one-round while ensure the completeness property and the soundness property.On the other hand,extend ZKPs to elliptic curves.At last,proposed a necessary condition which was needed by constructing a one-round zero-knowledge proofs protocol.