Cryptology ePrint Archive: Report 2014/390

Black-Box Non-Black-Box Zero Knowledge

Vipul Goyal and Rafail Ostrovsky and Alessandra Scafuro and Ivan Visconti

Abstract: Motivated by theoretical and practical interest, the challenging task of designing crypto- graphic 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 non-black-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 of the input of a player remains hidden. We show how to commit to a string of arbitrary size and to 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 a black-box way. We achieve such a result by giving a black-box construction of an extendable Merkle tree that relies on a novel use of the “MPC in the head” paradigm of Ishai et al. [STOC 2007]. We show the power of our new techniques by giving the first black-box constant-round public-coin zero knowledge argument for NP. To achieve this result we use the non-black-box simulation technique introduced by Barak [FOCS 2001], the PCP of Proximity introduced by Ben-Sasson et al. [STOC 2004], together with a black-box public-coin witness indistinguishable universal argument that we construct along the way. Additionally we show the first black-box construction of a generalization of zero-knowledge sets introduced by Micali et al. [FOCS 2003]. The generalization that we propose is a strengthening that requires both the size of the set and the size of the elements of the set to remain private.

Category / Keywords: foundations / Black-box Constructions, Non-black-box Simulation, Input-size hiding

Original Publication (with minor differences): STOC'14 ACM
DOI:
10.1145/2591796.2591879

Date: received 29 May 2014

Contact author: alescafu at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140530:122400 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]