Black-box non-black-box zero knowledge
Black-box non-black-box zero knowledge
复制标题
黑盒非黑盒零知识
DOI：
10.1145/2591796.2591879
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Ivan Visconti
中科院分区：
文献类型：
--
作者：
Vipul Goyal;R. Ostrovsky;Alessandra Scafuro;Ivan Visconti
受理论和实践兴趣的动机，设计只有黑框访问原语的加密协议的具有挑战性的任务在过去十年中产生了各种突破。尽管结果如此积极，尽管如今，但即使在恒定的回合中，我们也知道安全的两方和多方计算的黑盒结构，但在密码学中，仍然存在一些批判性的构造，这些结构需要非常需要非黑色的盒子来使用原始盒，以便为了以便使用原始框以便以便以便使用原始盒子。安全地实现一些基本任务。因此，对黑盒和非布莱克盒结构之间差距的研究仍然包括主要的开放问题。在这项工作中，我们在填补上述空白方面取得了进步。我们考虑了用于计算的黑框构造的情况，即使播放器的输入的大小也仍然隐藏。我们展示了如何承担一串任意大小的字符串并在字符串的位上证明语句。承诺和证明都是简洁的，隐藏输入大小，并以黑框方式使用标准原语。我们通过提供可扩展的默克树的黑盒结构来实现这一结果，该树依赖于Ishai等人的“头部MPC”范式的新颖使用。 [Stoc 2007]。我们通过为NP提供了第一个黑盒恒定公共核心知识论点来展示新技术的力量。为了实现这一结果，我们使用了Barak [Focs 2001]引入的非Black-box模拟技术，这是Ben-Sasson等人引入的接近pcp。 [STOC 2004]，加上我们一路上构建的黑盒公共场所证人无法区分的普遍论据。
Motivated by theoretical and practical interest, 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 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 blackbox 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 nonblack-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.