Abstract. We construct resettably-sound resettable zero knowledge arguments for NP based on standard hardness assumption (the existence of claw-free permutations) in the plain model. This proves the simultaneous resettability conjecture posed by Barak et al. in [FOCS 2001]. Our construction, inspired by the paradigm for designing concurrent zero knowledge protocols, makes crucial use of a tool called instance-dependent resettably-sound resettable WI argument of knowledge (IDWIAOK (and a special-purpose variant), introduced recently by Deng and Lin in [Eurocrypt 2007]). Roughly speaking, for a NP statement of the form x0 ∨ x1, IDWIAOK is an argument for which resettable WI property holds when both x0 and x1 are YES instances, and resettably-sound argument of knowledge property holds when x0 is a NO instance. The heart of the simulator for our protocol is a new technique that allows us to embed the (non-black-box) straight-line simulation strategy in the (black-box) recursive rewinding simulation strategy. 1 The problem and our result It is well known that randomness is essential to zero knowledge proofs/arguments[17]. Moreover,
We will construct a perfectly hiding commitment in two rounds from any one-way permutation, which is a negation of this result that O(n/(log n)) rounds is the tight lower bound on the rounds complexity of perfectly hiding commitments from any one-way permutation. Based on our commitments, we will construct a computational zero-knowledge proof for any NP that achieves negligible error probability in 5 rounds of interaction, assuming only the existence of a one-way permutation.
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
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung
We investigate structural properties of interactive perfect zero-knowledge (PZK) proofs. Specifically, we look into the closure properties of PZK languages under monotone boolean formula composition. This gives rise to new protocol techniques. We show that interactive PZK for random self-reducible (RSR) (and for co-RSR) languages is closed under monotone boolean formula composition. Namely, we present PZK proofs for monotone boolean formulae whose atoms are statements about membership in a PZK language which is RSR (or whose complement is RSR). We also discuss extensions, recent applications, and generalizations of the techniques.
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
The interplay of randomness and computation is at the heart of modern Cryptography and plays a fundamental role in the design of algorithms and in the study of computation at large.Specifically, this interplay is pivotal to several intriguing notions of probabilistic proof systems (e.g., interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs), is the focal of the computational approach to randomness, and is essential for various types of sub-linear time algorithms.This essay provides a brief outline of these connections.
Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) introduced the notion of resettable zero-knowledge proofs, where the protocol must be zero-knowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the closely related notion of resettable soundness, where the soundness condition of the protocol must hold even if the cheating prover can reset the verifier to have multiple interactions with the same verifier's random tape. The main problem left open by this work was whether it is possible to have a single protocol that is simultaneously resettable zero knowledge and resettably sound. We resolve this question by constructing such a protocol. At the heart of our construction is a new non-black-box simulation strategy, which we believe to be of independent interest. This new strategy allows for simulators which "marry'' recursive rewinding techniques (common in the context of concurrent simulation) with non-black-box simulation. Previous non-black-box strategies led to exponential blowups in computational complexity in such circumstances, which our new strategy is able to avoid.
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.
It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are nonconstant-round. Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is a open problem. This paper focuses on the problem and give a positive answer by presenting two constructions of constant-round (black-box) zero-knowledge proofs of knowledge for the HC (Hamiltonian Cycle) problem. By the recent result of Katz, our second construction which relies on the existence of claw-free functions has optimal round complexity (5-round) assuming the polynomial hierarchy does not collapse.
In this paper, we give an efficient short constant-size group signature scheme that is secure in standard model based on strong Diffie-Hellman assumption. We achieve this result by combining a variant signature scheme of the one presented by Okamoto and non-interactive zero knowledge proof used by Boyen and Waters. Compared with the most efficient group signature scheme without random oracle, our scheme has a much shorter public key length and signature length, and needs less computation.
The concept of Zaps, two-round witness indistinguish- able proofs, was introduced by Dwork and Naor in 2000. They constructed Zaps based on non-interactive zero- knowledge proof. This left open the following problem: does there exist a non-interactive Zaps? Barak et al. and Groth et al. answered this question affirmatively under the assumption of the existence of Hitting Set Generators against co-nondeterministic circuits and Decisional Linear Assumption, respectively. In this paper, we will construct ef- ficient non-interactive Zaps under the existence of one-way function. In 2006, Chase and Lysyanskaya defined and con- structed signatures of knowledge based on non-interactive zero-knowledge proof. We prove that their signature is not secure and point out that they exist under the existence of trapdoor permutation. Feige and Shamir stated that digi- tal signature cannot be zero-knowledge(otherwise they are forgeable) and it can be witness hiding. In this paper, we will revise the definition of the signatures of knowledge by using witness hiding protocol and construct them under the existence of one-way function.