In the past decade, pairing-based cryptography has emerged as an active area of research that gave rise to new algorithms, protocols, and primitives. These new techniques allowed researchers to achieve cryptographic schemes which had no known (or less efficient) counterparts in groups without bilinear pairings. In this dissertation, we introduce several schemes in which pairings play a central role in their construction. The results that we present in this dissertation stem from three papers which are respectively joint work with Rafail Ostrovsky, Amit Sahai, Hovav Shacham, and Brent Waters, with Jens Groth, and with Vipul Goyal, Amit Sahai, and Brent Waters.
In the dissertation, we present the first sequential aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a novel application of a signature scheme due to Waters. We review the definition of these signature variants and consider applications to secure routing and proxy signatures. We show how these are constructed using pairing-based cryptography.
Another scheme we present is a non-interactive verifiable shuffle. A shuffle is a permutation and re-encryption of a set of ciphertexts. Shuffles are used, for instance, in mix-nets for anonymous broadcast and voting. One way to make a shuffle verifiable is to give a zero-knowledge proof of correctness. All currently known practical zero-knowledge proofs for correctness of a shuffle rely on interaction. We give the first efficient non-interactive zero-knowledge proof for correctness of a shuffle based on pairings.
Finally, we consider the problem of accountability for PKGs in identity-based encryption. A well-known concern in the setting of identity-based encryption is that the PKG is all powerful and must be completely trusted. To mitigate this problem, the notion of Accountable Authority Identity-Based Encryption (A-IBE) was recently introduced by Goyal, who provided constructions to realize the notion of A-IBE only in the white-box and weak black-box models. In this dissertation, we present a resolution to the main open question left in Goyal's work by providing a construction of a fully black-box A-IBE system. We show how such a scheme can be securely realized from generic underlying primitives, then give a concrete realization of the scheme in any bilinear group where the Decisional Bilinear Diffie-Hellman assumption holds.
â-protocol is an important tool in cryptology field.In this paper,we will prove that any â-protocol has the following characters: â it is a witness hiding protocol if there exist at least two witnesses on R;âĄthere exists a â-protocol on any NP statement under the assumption of the existence of one-way permutation;â˘there exist â-protocols with computational zero-knowledge;âŁâ-protocol can be changed into a zero-knowledge proof.
Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as Circuit Satisfiability, causing an expensive blowup in the size of the statement when reducing it to a circuit. The contribution of this paper is a general methodology for constructing very simple and efficient non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs that work directly for groups with a bilinear map, without needing a reduction to Circuit Satisfiability. Groups with bilinear maps have enjoyed tremendous success in the field of cryptography in recent years and have been used to construct a plethora of protocols. This paper provides non-interactive witness-indistinguishable proofs and non-interactive zero-knowledge proofs that can be used in connection with these protocols. Our goal is to spread the use of non-interactive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups.
How to find efficient and secure member- ship revocation algorithms is one of the most important issues standing in the way of real-world applications of group signatures. In this paper, the proof of knowledge of divisibility is given and a novel membership revocation method in ACJT group signature scheme is proposed: the group manager issues the product E of the public keys of current members in the group, when a group member wants to sign, he should not only proves that he has a membership certificate, but also proves that the public key in his certificate divides exactly the public key product E with zero knowledge. The proposed method is efficient since the group manager only needs one division and one exponentiation when a group member is deleted, while the signing and verifying procedure are independent of the number of current group members and excluded members, as well as the original group public key and membership certificates needn't be changed.
Abstract Whether a recipient can prove a signature to others is of great importance. The function is just one reason that we call a signature âsignature â rather than others. In this paper, we point out that one popular signcryption signature convinces only the designated documentâs recipient that the signer deliberately signed the document. The designated recipient can check the validity of a given signcryptext but cannot prove it to others. We also improve it using the efficient technique developed in Schnorrâs signature instead of a zero-knowledge proof such that the receiver can check the validity of a given signcryptext and can prove it to a third party.
Abstract. We show an efficient secure two-party protocol, based on Yaoâs construction, which provides security against malicious adversaries. Yaoâs original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the âGMW compilerâ). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yaoâs protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilianâs reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1
The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier-Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.
This dissertation presents new constructions and security definitions related to three areas: authentication, cascadable and commutative crytpography, and private set operations. Existing works relevant to each of these areas fall into one of two categories: efficient solutions lacking formal proofs of security or provably-secure, but highly inefficient solutions. This work will bridge this gap by presenting new constructions and definitions that are both practical and provably-secure.
The first contribution in the area of efficient authentication is a provably-secure authentication protocol named HB+. The HB+ protocol is efficient enough to be implemented on extremely low-cost devices, or even by a patient human with a coin to flip. The security of HB+ is based on the hardness of a long-standing learning problem that is closely related to coding theory. HB+ is the first authentication protocol that is both practical for low-cost devices, like radio frequency identification (RFID) tags, and provably secure against active adversaries.
The second contribution of this work is a new framework for defining and proving the security of cascadable crypt osystems, specifically commutative cryptosystems. This new framework addresses a gap in existing security definitions that fail to handle cryptosystems where ciphertexts produced by cascadable encryption and decryption operations may contain some message-independent history. Several cryptosystems, including a new, practical commutative cryptosystem, are proven secure under this new framework.
Finally, a new and efficient private disjointness testing construction named HW is offered. Unlike previous constructions, HW is secure in the face of malicious parties, but without the need for random oracles or expensive zero-knowledge protocols. HW is as efficient as previous constructions and may be implemented using standard software libraries. The security of HW is based on a novel use of subgroup assumptions. These assumptions may prove useful in solving many other private set operation problems. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)
This article introduces new methodology for the design of two-party cryptographic protocols using Graph Theory tools. In this sense, several Oblivious Transfer and Bit Commitment algorithms are proposed as primitives in the design of more complex protocols. Special attention is paid to the strong identification problem through Zero Knowledge Proofs, and new solutions based on graphs are given.
Ma and Chen have proposed an authenticated encryption scheme with public verifiability. The scheme claims that the TTP can publicly verify the sender's signature without running a zero knowledge proof protocol. The problem in verification which causes the TTP to reject a valid signature with non-negligible probability is pointed out.
Theoretical computer science has found fertile ground in many areas of mathematics. The approach has been to consider classical problems through the prism of computational complexity, where the number of basic computational steps taken to solve a problem is the crucial qualitative parameter. This new approach has led to a sequence of advances, in setting and solving new mathematical challenges as well as in harnessing discrete mathematics to the task of solving real-world problems. In this talk, I will survey the development of modern cryptography -- the mathematics behind secret communications and protocols -- in this light. I will describe the complexity theoretic foundations underlying the cryptographic tasks of encryption, pseudo-randomness number generators and functions, zero knowledge interactive proofs, and multi-party secure protocols. I will attempt to highlight the paradigms and proof techniques which unify these foundations, and which have made their way into the mainstream of complexity theory.
In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical cryptography, and then move on to modern public-key cryptography. Particular attention is paid to cryptographic protocols and the problem of constructing key components of protocols such as one-way functions. A function is one-way if it is easy to compute, but hard to invert. We discuss the notion of one-way functions both in a cryptographic and in a complexity-theoretic setting. We also consider interactive proof systems and present some interesting zero-knowledge protocols. In a zero-knowledge protocol, one party can convince the other party of knowing some secret information without disclosing any bit of this information. Motivated by these protocols, we survey some complexity-theoretic results on interactive proof systems and related complexity classes.
An identification scheme based on a generator matrix of error-correcting codes over GF(q) is proposed, it is proved that the given protocol is a zero-knowledge interactive proof in the random oracle model, and it is shown that the scheme is secure when parameters are selected properly.
In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical cryptography, and then move on to modern public-key cryptography. Particular attention is paid to cryptographic protocols and the problem of constructing the key components of such protocols such as one-way functions. A function is one-way if it is easy to compute, but hard to invert. We discuss the notion of one-way functions both in a cryptographic and in a complexity-theoretic setting. We also consider interactive proof systems and present some interesting zero-knowledge protocols. In a zero-knowledge protocol one party can convince the other party of knowing some secret information without disclosing any bit of this information. Motivated by these protocols, we survey some complexity-theoretic results on interactive proof systems and related complexity classes.
An identification scheme based on a parity check matrix of error correcting codes over îF G(2)î was proposed in the paper âA New Paradigm for Public Key Identificationâ by J.Stern. The identification scheme of J.Stern is generalized in this paper, and a new identification scheme based on a parity check matrix of error correcting codes over îF G(q) (qî is a prime) is proposed. The limitation on the weight of mysterious datum îsî is changed into the limitation on the distribution of code elements of îsî. It is proved that the given protocol is a zero knowledge interactive proof in the random oracle model, and it is shown that the scheme is more secure than the scheme of J.Stern when parameters are selected properly.