Zero-Knowledge Sets With Short Proofs
Zero-Knowledge Sets With Short Proofs
复制标题
DOI：
10.1109/tit.2011.2112150
复制
发表时间：
2008-04
影响因子：
2.5
通讯作者：
D. Catalano;M. Raimondo;D. Fiore;Mariagrazia Messina
中科院分区：
文献类型：
--
作者：
D. Catalano;M. Raimondo;D. Fiore;Mariagrazia Messina
零知识集（ZKS），由Micali，Rabin和Kilian在2003年提出，允许证明者以一种方式提交一个秘密集合S，这样它可以在以后非交互地证明形式为x ∈ S（或x ∈ S）的陈述，而不会透露任何关于S的进一步信息（除了上面的包含/排除陈述所显式透露的信息之外），甚至不包括它的大小。后来，蔡斯通过引入一个优雅的新承诺变体，他们称之为（陷阱）善变承诺，抽象出了米卡利、拉宾和基利安的结构。使用这个原语，它显示了如何从各种假设（一般和数论）构建零知识集。本文介绍了陷阱q -mercurial承诺（\ssr qTMCs）的概念，mercurial承诺的概念，允许发送者提交到一个有序的序列，而不是一个单一的q消息。在前面的工作之后，它展示了如何从\ssr qTMC和抗冲突哈希函数构建ZKS。然后，它是一个有效的实现\ssr qTMCs，是安全的下，所谓的强Diffie赫尔曼（SDH）假设，数论猜想最近推出的Boneh和Boyen。使用这样的计划作为基本的构建块，它是获得的ZKS的建设，允许的证明，相对于最好的先前已知的实现要短得多。特别是，对于一个适当的参数选择，我们的证明是短33%的情况下，证明的成员资格，并缩短73%的情况下，证明的非成员资格。实验测试证实了实际的时间性能。
Zero knowledge sets (ZKS), introduced by Micali, Rabin, and Kilian in 2003, allow a prover to commit to a secret set S in a way such that it can later prove, non interactively, statements of the form x ∈ S (or x ∉ S), without revealing any further information (on top of what explicitly revealed by the inclusion/exclusion statements above) on S, not even its size. Later, Chase abstracted away the Micali, Rabin, and Kilian's construction by introducing an elegant new variant of commitments that they called (trapdoor) mercurial commitments. Using this primitive, it was shown how to construct zero knowledge sets from a variety of assumptions (both general and number theoretic). This paper introduces the notion of trapdoor q -mercurial commitments (\ssr qTMCs), a notion of mercurial commitment that allows the sender to commit to an ordered sequence of exactly q messages, rather than to a single one. Following the previous work, it is shown how to construct ZKS from \ssr qTMCs and collision resistant hash functions. Then, it is presented an efficient realization of \ssr qTMCs that is secure under the so called Strong Diffie Hellman (SDH) assumption, a number theoretic conjecture recently introduced by Boneh and Boyen. Using such scheme as basic building block, it is obtained a construction of ZKS that allows for proofs that are much shorter with respect to the best previously known implementations. In particular, for an appropriate choice of the parameters, our proofs are up to 33% shorter for the case of proofs of membership, and up to 73% shorter for the case of proofs of nonmembership. Experimental tests confirm practical time performances.