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.
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.
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.
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.
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 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.
Zero knowledge sets is a new cryptographic primary in- troduced by Micali, Rabin, and Kilian in FOCS 2003. It is intensively investigated recently. However all schemes follow the basic frame by Micali et al. That is, the schemes employ Merkle tree as basic frame and mercurial com- mitments as commitment units to nodes of the tree. The proof for any query constitutes of an authentication chain. We propose in this paper a new algebraic scheme that is completely different from all existing schemes. The new scheme is computationally secure under standard assump- tion: Strong RSA assumption. It employs neither mercurial commitments nor tree frame as all previous schemes did. In fact, the prover (also as the committer) in our construc- tion commits the desired set without trapdoor information, which is another important difference from the previous ap- proaches.
Although the semi-honest model is reasonable in some cases, it is unrealistic to assume that adversaries will al- ways follow the protocols exactly. In particular, malicious adversaries could deviate arbitrarily from their prescribed protocols. Clearly, protocols that can withstand malicious adversaries provide more security. However, there is an ob- vious 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 perfor- mance and security in privacy-preserving distributed data mining algorithms in the two models. In order to make a realistic comparison, we enhance commonly used subpro- tocols 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.