Constant-round adaptive zero-knowledge proofs for NP

Secure two-party computation allows two parties with private inputs to securely compute some function of their inputs, even in the presence of a malicious adversary. In this work, we revisit zero-knowledge proofs and focus on adaptive adversaries, which could corrupt an arbitrary number of parties a...

Full description

Saved in:
Bibliographic Details
Published in:Information sciences 2014-03, Vol.261, p.219-236
Main Authors: Zhang, Zongyang, Cao, Zhenfu, Zhu, Haojin
Format: Article
Language:English
Subjects:
Adaptive zero-knowledge proof
Instance-dependent commitments
Proofs of knowledge
Trapdoor commitments
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Secure two-party computation allows two parties with private inputs to securely compute some function of their inputs, even in the presence of a malicious adversary. In this work, we revisit zero-knowledge proofs and focus on adaptive adversaries, which could corrupt an arbitrary number of parties and adaptively determine who and when to corrupt during the computation phase. Previous constructions could realize adaptive zero-knowledge proofs for all languages in NP (Lindell and Zarosim TCC’09) at the cost of a high round-complexity, i.e., super-constant number of rounds. In this work, assuming the existence of constant-round statistically hiding commitment schemes, we build efficient adaptive zero-knowledge proofs for all languages in NP, which only require constant number of communication rounds. The system is also a proof of knowledge. The construction relies on an adaptive instance-dependent commitment scheme, and the proof of security requires only the use of black-box techniques and is presented according to the real/ideal simulation paradigm.
ISSN:0020-0255
1872-6291
DOI:10.1016/j.ins.2013.07.037