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
Most of the cryptographic work in privacy-preserving distributed data mining deals with semi-honest adversaries, which are assumed to follow the prescribed protocol but try to infer private information using the messages they receive during the protocol. Although the semi-honest model is reasonable in some cases, it is unrealistic to assume that adversaries will always follow the protocols exactly. In particular, malicious adversaries could deviate arbitrarily from their prescribed protocols. Secure protocols that are developed against malicious adversaries require utilisation of complex techniques. Clearly, protocols that can withstand malicious adversaries provide more security. However, there is an obvious trade-off: protocols that are secure against malicious adversaries are generally more expensive than those secure against semi-honest adversaries only. In this paper, our goal is to make an analysis of trade-offs between performance and security in privacy-preserving distributed data mining algorithms in the two models. In order to make a realistic comparison, we enhance commonly used subprotocols that are secure in the semi-honest model with zero knowledge proofs to be secure in the malicious model. We compare the performance of these protocols in both models.
Chunming Tang, Dingyi Pei, Xiao Feng Wang, Zhuojun Liu
A delegateable signature scheme(DSS)which was first introduced by Barak is mainly based on the non-interactive zero-knowledge proof(NIZK)for preventing the signing verifier from telling which witness(i.e.,restricted subset)is being used. However,the scheme is not significantly efficient due to the difficulty of constructing NIZK.We first show that a non-interactive witness indistinguishable(NIWI)proof sys- tem and a non-interactive witness hiding(NIWH)proof system are easier and more efficient proof models than NIZK in some cases.Furthermore,the witnesses em- ployed in these two protocols(NIWI and NIWT)cannot also be distinguished by the verifiers.Combined with theÎŁ-protocol,we then construct NIWI and NIWH proofs for any NP statement under the existence of one-way functions and show that each proof is different from those under the existence of trapdoor permutations.Finally,based on our NIWI and NIWH proofs,we construct delegateable signature schemes under the existence of one-way functions,which are more efficient than Barak's scheme under the existence of trapdoor permutations.
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.
In this paper we have formulated an online voting framework which ensures that the voter is able to vote in a public environment without his vote being eavesdropped on by a neighbor i.e. his vote becomes known to his neighbor or a third party when he marks his choice on a particular candidate. We also give a model for secure online voting system using zero knowledge proof and other cryptographic schemes encompassing the voting process of the user and the backend process of servers and the tallying and display of results and verification by the user of the vote cast by him at a later stage.
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.
Endre Bangerter, Jan Camenisch, Stephan Krenn, AhmadâReza Sadeghi · 5 authors
Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic building blocks of many practical cryptographic applications such as identification schemes, group signatures, and secure multiparty computation. Currently, first applications that essentially rely on ZK-POKs are being deployed in the real world. The most prominent example is Direct Anonymous Attestation (DAA), which was adopted by the Trusted Computing Group (TCG) and implemented as one of the functionalities of the cryptographic chip Trusted Platform Module (TPM). Implementing systems using ZK-PoK turns out to be challenging, since ZK-PoK are, loosely speaking, significantly more complex than standard crypto primitives, such as encryption and signature schemes. As a result, implementation cycles of ZK-PoK are time-consuming and error-prone, in particular for developers with minor or no cryptographic skills. To overcome these challenges, we have designed and implemented a compiler with corresponding languages that given a high-level ZK-PoK protocol specification automatically generates a sound implementation of this. The output is given in form of -protocols, which are the most efficient protocols for ZK-PoK currently known. Our compiler translates ZK-PoK protocol specifications, written in a high-level protocol description language, into Java code or \LaTeX\ documentation of the protocol. The compiler is based on a unified theoretical framework that encompasses a large number of existing ZK-PoK techniques. Within this framework we present a new efficient ZK-PoK protocol for exponentiation homomorphisms in hidden order groups. Our protocol overcomes several limitations of the existing proof techniques.
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.
This paper proposes RSA-based zero-knowledge proof watermark verification protocols.It can tackle the problem of disclosing sensitive information.In the protocols,the public key encryption are used to encrypt the watermark and the watermarked data of the watermark embedding locations,the open verification of copyright watermarking is achieved through estimating the relativity of them.Furthermore,the authors research how to resist cheat-attack,and propose the way that prover and verifier can only communicate with each other to resist this attack.
Advanced Steganography and Watermarking Techniques
Non-interactive zero-knowledge (NIZK) proofs can be an extremely powerful tool, allowing one to prove a statement in a single message without revealing any information besides the truth of the statement. Blum et al. showed that NIZK proof systems exist for all languages in NP. However, in practice, NIZK proofs are rarely used, because existing protocols are extremely inefficient. Here we examine some useful languages for which we can give efficient proof system.
We define two useful building blocks: one for proving that a message has been signed, and a second for proving that a value has been chosen according to a pseudorandom function. We give applications of these building blocks to anonymous credential systems, to electronic cash, and to the design of other efficient NIZK proofs systems.
The abstraction of cryptographic operations by term algebras, called DolevâYao models, is essential in almost all tool-supported methods for proving security protocols. Recently significant progress was made in proving that DolevâYao models offering the core cryptographic operations such as encrypt ion and digital signatures can be sound with respect to actual cryptographic realizations and security definitions. Recent work, however, has started to extend DolevâYao models to more sophisticated operations with unique security features. Zero-knowledge proofs arguably constitute the most amazing such extension. In this paper, we first identify which additional properties a cryptographic (non-interactive) zero-knowledge proof needs to fulfill in order to serve as a computationally sound implementation of symbolic (DolevâYao style) zero-knowledge proofs; this leads to the novel definition of a symbolically-sound zero-knowledge proof system. We prove that even in the presence of arbitrary active adversaries, such proof systems constitute computationally sound implementations of symbolic zero-knowledge proofs. This yields the first computational soundness result for symbolic zero-knowledge proofs and the first such result against fully active adversaries of DolevâYao models that go beyond the core cryptographic operations.
The abstraction of cryptographic operations by term algebras, called Dolev-Yao models, is essential in almost all tool-supported methods for proving security protocols. Recently significant progress was made in proving that Dolev-Yao models offering the core cryptographic operations such as encryption and digital signatures can be sound with respect to actual cryptographic realizations and security definitions. Recent work, however, has started to extend Dolev-Yao models to more sophisticated operations with unique security features. Zero-knowledge proofs arguably constitute the most amazing such extension. In this paper, we first identify which additional properties a cryptographic zero-knowledge proof needs to fulfill in order to serve as a computationally sound implementation of symbolic (Dolev-Yao style) zero-knowledge proofs; this leads to the novel definition of a symbolically-sound zero-knowledge proof system. We prove that even in the presence of arbitrary active adversaries, such proof systems constitute computationally sound implementations of symbolic zero-knowledge proofs. This yields the first computational soundness result for symbolic zero-knowledge proofs and the first such result against fully active adversaries of Dolev-Yao models that go beyond the core cryptographic operations.