IACR News item: 25 July 2014
Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, Eran Tromer
ePrint Reportnon-interactive computationally-sound proofs where the verifier\'s
work is essentially independent of the complexity of the NP
nondeterministic verifier) has been an intriguing question for the
past two decades. Other than CS proofs in the random oracle model
[Micali, FOCS \'94], the only existing candidate construction is
based on an elaborate assumption that is tailored to a specific
protocol [Di Crescenzo and Lipmaa, CiE \'08].
We formulate a general and relatively natural notion of an
\\emph{extractable collision-resistant hash function (ECRH)} and show
that, if ECRHs exist, then a modified version of Di Crescenzo and
Lipmaa\'s protocol is a succinct non-interactive argument for
NP. Furthermore, the modified protocol is actually a succinct
non-interactive \\emph{adaptive argument of knowledge (SNARK).} We
then propose several candidate constructions for ECRHs and
relaxations thereof.
We demonstrate the applicability of SNARKs to various forms of delegation of computation, to succinct non-interactive zero knowledge arguments, and to succinct two-party secure computation. Finally, we show that SNARKs essentially imply the existence of ECRHs, thus demonstrating the necessity of the assumption.
Going beyond $\\ECRH$s, we formulate the notion of {\\em extractable
one-way functions ($\\EOWF$s)}. Assuming the existence of a natural
variant of $\\EOWF$s, we construct a $2$-message
selective-opening-attack secure commitment scheme and a 3-round
zero-knowledge argument of knowledge. Furthermore, if the $\\EOWF$s are
concurrently extractable, the 3-round zero-knowledge protocol is also
concurrent zero-knowledge.
Our constructions circumvent previous black-box impossibility
results regarding these protocols by relying on $\\EOWF$s as the non-black-box component in the security reductions.
Additional news items may be found on the IACR news page.