Removing Complexity Assumptions from Concurrent Zero-Knowledge Proofs

Huijia Lin, Rafael Pass, Wei-Lung Dustin Tseng +1 more

Ning Ding, Dawu Gu

Divya Gupta, Amit Sahai

Ivan Damgård, Adriana López-Alt

Puwen Wei, Guoyan Zhang, Lijiang Zhang +1 more

This paper shows that the protocol presented by Goyal et al. can be further simplified for a one-way function, with the simplified protocol being more practical for the decisional Diffie-Hellman assumption. Goyal et al. provided a general transformation from any honest verifier statistical zero-knowledge argument to a concurrent statistical zero-knowledge argument. Their transformation relies only on the existence of one-way functions. For the simplified transformation, the witness indistinguishable proof of knowledge protocols in “parallel” not only plays the role of preamble but also removes some computational zero-knowledge proofs, which Goyal et al. used to prove the existence of the valid openings to the commitments. Therefore, although some computational zero-knowledge proofs are replaced with a weaker notion, the witness indistinguishable protocol, the proof of soundness can still go through.

Zhenfu Cao, Zongyang Zhang, Yunlei Zhao

A zero-knowledge protocol allows a prover to convince a verifier of the correctness of a statement without disclosing any other information to the verifier. It is a basic tool and widely used in many other cryptographic applications. However, when stand-alone zero-knowledge protocols are used in complex environments, e.g., the Internet, the basic properties may not be sufficient. This is why researchers considered security of zero-knowledge protocols under concurrent composition and manin-the-middle attacks. Moreover, it is very likely that an adversary might break computers that run the protocol and get internal information of the parties. It is thus necessary to take account of the security of zero-knowledge protocols when adaptive corruptions are allowed. Previous adaptively secure zero-knowledge protocols work either in a stand-alone setting, or in a concurrent setting with trusted setup assumptions. In this paper, we study adaptive security of zero-knowledge protocols under both concurrent self composition and man-in-the-middle attacks in the plain model (i.e., without any set-up assumptions). We provide a construction of adaptively secure concurrent non-malleable zero-knowledge proof/argument for every language in NP.