Black−Box Non −Black&$8722;Box Zero Knowledge
Vipul Goyal, Rafail Ostrovsky, Alessandra scafuro
Abstract:
Motivated by theoretical and practical intrest, the challenging task of designing cryptographic protocols having only black−box access to primitives has generated various breakthroughs in the last decade. Despite such positive results,even though nowadays we know black−box constructions for secure two−party and multi−party computation even in constant rounds, there still are in Cryptography several constructions that critically require non−black−box use of primitives in order to securely realize some fundamental tasks.As such, the study of the gap between black−box and nonblack−box constructions still includes major open questions.
In this work we make progress towards filling the above gap. We consider the case of black−box constructions for computations requiring that even the size the input of a player remains hidden. We show how to commit to a string of arbitrary size and prove statements over the bits of the string. Both the commitment and the proof are succinct, hide the input size and use standard primitives in black−box way. We achieve such results by giving a black−box construction of extendable Merkle tree that relies on a novel use of the “MPC in the head” paradigm of Ishai et al.[STOC2007].
We show the power if our new techniques by giving the first black−box constant−round public−coin zero knowledge argument for NP. To achieve this results black−box simulation technique introduced by Barak [FOCS 2001]. The PCP of Proximity introduced by Ben−Sasson et al.[STOC2004], together with a black−box public−coin witness indistinguishable universal argument that we construct along the way.
comment: STOC 2014 PP: 515−524
Fetch PDF file of the paper
| Back to Publications List |