We present a protocol for verification of ``no such entry'' replies from databases. We introduce a new cryptographic primitive as the underlying structure, the keyed hash tree, which is an extension of Merkle's hash tree. We compare our scheme to Buldas et al.'s Undeniable Attesters and Micali et al.'s Zero Knowledge Sets.
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.
We show new lower bounds and impossibility results for general (possibly non-black-box) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: 1. There does not exist a two-round zero-knowledge proof system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero knowledge, by Goldreich and Oren (J. Cryptology, 1994) was only for the case of auxiliary-input zero-knowledge proofs and arguments. 2. There does not exist a constant-round zero-knowledge strong proof or argument of knowledge (as defined by Goldreich (2001)) for a nontrivial language. 3. There does not exist a constant-round public-coin proof system for a nontrivial language that is resettable zero knowledge. This result also extends to bounded-resettable zero knowledge, in which the number of resets is a priori bounded by a polynomial in the input length and prover-to-verifier communication.
The concept of zero-knowledge (ZK) has become of fundamental importance in cryptography. However, in a setting where entities are modeled by quantum computers, classical arguments for proving ZK fail to hold since, in the quantum setting, the concept of rewinding is not generally applicable. Moreover, known classical techniques that avoid rewinding have various shortcomings in the quantum setting.<br /> <br />We propose new techniques for building <em>quantum</em> zero-knowledge (QZK) protocols, which remain secure even under (active) quantum attacks. We obtain computational QZK proofs and perfect QZK arguments for any NP language in the common reference string model. This is based on a general method converting an important class of classical honest-verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical protocols if the underlying HVZK proof is efficient. These are the first proof protocols enjoying these properties, in particular the first to achieve perfect QZK.<br /> <br />As part of our construction, we propose a general framework for building unconditionally hiding (trapdoor) string commitment schemes, secure against quantum attacks, as well as concrete instantiations based on specific (believed to be) hard problems. This is of independent interest, as these are the first unconditionally hiding string commitment schemes withstanding quantum attacks.<br /> <br />Finally, we give a partial answer to the question whether QZK is possible in the plain model. We propose a new notion of QZK, <em>non-oblivious verifier</em> QZK, which is strictly stronger than honest-verifier QZK but weaker than full QZK, and we show that this notion can be achieved by means of efficient (quantum) protocols.
We show that every language in NP has a (black-box) concurrent zero-knowledge proof system using O/spl tilde/(log n) rounds of interaction. The number of rounds in our protocol is optimal, in the sense that any language outside BPP requires at least /spl Omega//spl tilde/(log n) rounds of interaction in order to be proved in black-box concurrent zero-knowledge. The zero-knowledge property of our main protocol is proved under the assumption that there exists a collection of claw free functions. Assuming only the existence of one-way functions, we show the existence of O/spl tilde/(log n)-round concurrent zero-knowledge arguments for all languages in NP.
We introduce the notion of non-malleable non-interactive zero-knowledge (NIZK) proof systems. We show how to transform any ordinary NIZK proof system into one that has strong non-malleability properties. We then show that the elegant encryption scheme of Naor and Yung (1990) can be made secure against the strongest form of chosen-ciphertext attack by using a non-malleable NIZK proof instead of a standard NIZK proof. Our encryption scheme is simple to describe and works in the standard cryptographic model under, general assumptions. The encryption scheme can be realized assuming the existence of trapdoor permutations.
This thesis is written for the Swedish degree Licentiate ofScience, Teknisk Licentiat.It is a university degree, between that of master andthat of doctor.The main focus of the thesis is on the construction ofsecure protocols for comparing the underlying plain-texts inElGamal encryptions. The protocols make use of the malleabilityof the ElGamal encryption scheme. More specifically they usethe multiplicative homomorphic property of ElGamal.We present fully verifiable protocols for both thetwo-party setting and the multi-party setting. These protocolsare built on sub-protocols, which are specially constructed tofit the present setting. We also present full proofs forcompleteness, soundness, and zero-knowledge for all the givenprotocols, in the random oracle model.
We consider the basic cryptographic primitive known as zero-knowledge proofs on committed bits. In this primitive, a prover P commits to a set of bits, and then at a later time convinces a verifier V that some property /spl Pscr/ holds for a subset of these bits. It is known how to implement this primitive based on an ordinary bit-committal primitive, but the standard implementations involve a great deal of interaction between the prover and the verifier. We introduce new implementations that require markedly less interaction. We implement bounded-interaction proofs on committed bits, generalizing a model of A. De Micali et al. (1988). For all security parameters, our implementations require only a lg/sup 2/ (n) overhead over the best known circuit-based interactive implementations; for sufficiently large security parameters this gap drops to a lg(n) factor.>
The authors solve the two major open problems associated with noninteractive zero-knowledge proofs: how to enable polynomially many provers to prove in writing polynomially many theorems based on the basis of a single random string, and how to construct such proofs under general (rather than number-theoretic) assumptions. The constructions can be used in cryptographic applications in which the prover is restricted to polynomial time, and they are much simpler than earlier (and less capable) proposals.>
We describe efficient constructions for various cryptographic primitives in private-key as well as public-key cryptography. Our main results are two new constructions of pseudo-random functions. We prove the pseudo-randomness of one construction under the assumption that factoring (Blum integers) is hard while the other construction is pseudo-random if the decisional version of the Diffie--Hellman assumption holds. Computing the value of our functions at any given point involves two subset products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in TC 0 (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates). This fact has several interesting applications. The simple algebraic structure of the functions implies additional features such as a zero-knowledge proof for statements of the form " y = f s ( x )" and " y ≠ f s ( x )" given a commitment to a key s of a pseudo-random function f s .
A zap is a 2‐round, public coin witness‐indistinguishable protocol in which the first round, consisting of a message from the verifier to the prover, can be fixed “once and for all” and applied to any instance. We present a zap for every language in NP, based on the existence of noninteractive zero‐knowledge proofs in the shared random string model. The zap is in the standard model and hence requires no common guaranteed random string. We present several applications for zaps, including 3‐round concurrent zero‐knowledge and 2‐round concurrent deniable authentication, in the timing model of Dwork, Naor, and Sahai [J. ACM, 51 (2004), pp. 851–898], using moderately hard functions. We also characterize the existence of zaps in terms of a primitive called verifiable pseudorandom bit generators.
In this paper we examine the role of Identification Protocols in the field of Cryptography. Firstly, the rationale behind the need for Identification Protocols is discussed. Secondly, we examine, in detail, challenge-response protocols, based upon zero-knowledge proofs, that form a subset of Identification Protocols in general. Thirdly, the mathematical tools necessary for the understanding of how these protocols work is given. Finally, we discuss four main Identification Protocols: Fiat-Shamir, Feige-Fiat-Shamir, Schnorr and Guillou- Quisquater. This discussion includes the theory, practical examples and the security aspects of each protocol.
Vanesa Daza, Javier Herranz, Carles Padró, Germán Sáez
In [16], Naor, Pinkas and Reingold introduced schemes in which some groups of servers distribute keys among a set of users in a distributed way. They gave some specic proposals both in the unconditional and in the computational security framework. Their computationally secure scheme is based on the Decisional DiÆe-Hellman Assumption. This model assumes secure communication between users and servers. Furthermore it requires users to do some expensive computations in order to obtain a key. In this paper we modify the model introduced in [16], requiring au-thenticated channels instead of assuming the existence of secure channels. Our model makes the user&apos;s computations easier, because most compu-tations of the protocol are carried out by servers, keeping to a more re-alistic situation. We propose a basic scheme, that makes use of ElGamal cryptosystem, and that ts in with this model in the case of a passive ad-versary. We then add zero-knowledge proofs and veriable secret sharing to prevent from the action of an active adversary. We consider general structures (not only the threshold ones) for those subsets of servers that can provide a key to a user and for those tolerated subsets of servers that can be corrupted by the adversary. We nd necessary combinatorial conditions on these structures in order to provide security to our scheme. 1
Abstract. Artin’s braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced in [2, 3, 18] (see also [22]). A variety of key agreement protocols based on braids have been described, but few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible implementations, involving normal forms or an alternative braid algorithm, called handle reduction, which can achieve good efficiency under specific requirements. 1.
The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain constant-round zero-knowledge proofs and proofs of knowledge (for NP), one had to allow simulators and knowledge-extractors to run in time which is only polynomial on the average (i.e., expected polynomial time). Whether or not allowing expected polynomial-time is necessary for obtaining constant-round zero-knowledge proofs and proofs of knowledge, has been posed as an important open question. This question is interesting not only for its theoretical ramifications, but also because expected polynomial time simulation is not closed under composition. Therefore, in some cases security is not maintained when a protocol that utilizes expected polynomial time simulation (or extraction) is used as a part of a larger protocol.A partial answer to the question of the necessity (or non-necessity) of expected polynomial-time was provided recently by Barak, who gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) polynomial-time simulator. His was also the first protocol that is not black-box zero-knowledge. That is, the simulator in his protocol utilizes the description of the code of the verifier in an essential way.In this paper, we completely resolve the question of expected polynomial-time in zero-knowledge arguments and arguments of knowledge. First, we show that there exist constant-round zero-knowledge arguments of knowledge with strict polynomial-time extractors. As in the simulator of Barak's zero-knowledge protocol, the extractor for our proof of knowledge is not black-box and uses the code of the prover in an essential way.On the negative side, we show that non-black-box techniques are essential to both strict polynomial-time simulation and extraction. That is, we show that no constant-round zero-knowledge argument (or proof) can have a strict polynomial-time black-box simulator. Similarly, we show that no constant-round zero-knowledge argument (or proof) of knowledge can have a strict polynomial-time black-box knowledge extractor. Thus, for constant-round black-box zero-knowledge arguments (resp., arguments of knowledge), it is imperative that the simulator (resp., extractor) be allowed to run in expected polynomial-time.