Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs
Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs
复制标题
DOI：
10.1007/978-3-642-11799-2_30
复制
发表时间：
2010-02
期刊：
影响因子：
--
通讯作者：
Benoît Libert;M. Yung
中科院分区：
文献类型：
--
作者：
Benoît Libert;M. Yung
零知识集的基本原语是由Micali、Rabin和Kilian(MRK)提出的，它允许证明者承诺一个秘密集，从而能够证明ASX∈SOR等语句。Chaseet等人证明了ZKS协议是由一种密码学原始的终端汞承诺所支持的。变化无常的承诺有两个承诺程序。在提交时，提交者可以选择不提交特定的消息，而是生成一个虚值，它将能够软打开任何消息，而不是完全打开它。另一方面，硬承诺很难或温和地只接受一种特定的信息。在2008年欧洲加密大会上，Catalano，Fiore和Messina(CFM)引入了一种名为陷阱门q-Mercurial承诺(QTMC)的扩展，它允许承诺一系列QMessages。这些QTMC方案很有趣，因为它们的开幕式是W.r.t.特定的向量位置可以很短(理想情况下，打开长度不应该依赖于q)，当这样的承诺与Arityq的Merkle树相结合时，这提供了具有更短证明的零知识集。CFM结构的显著特点是非成员资格的简短证明，因为它利用了具有短软开口的QTMC方案。一个悬而未决的问题是，硬空缺仍然有Sizeo(Q)，这使得成员资格的证明不像非成员资格的证明那样紧凑。在本文中，我们解决了这一公开问题，并描述了一种新的QTMC方案，其中沿位置方向的硬开口和短位置开口都具有恒定的大小。然后，我们展示了我们的方案如何服从于构造独立的零知识集(即，ZK防止对手将他们的集合与诚实证明者的集合关联，如Gennaro和Micali所定义的)。我们的解决方案也保留了这个重要原语的短证明性质。
Introduced by Micali, Rabin and Kilian (MRK), the basic primitive of zero-knowledge sets (ZKS) allows a prover to commit to a secret setSso as to be able to prove statements such asx∈Sor. Chaseet al.showed that ZKS protocols are underlain by a cryptographic primitive termedmercurial commitment. A (trapdoor) mercurial commitment has two commitment procedures. At committing time, the committer can choose not to commit to a specific message and rather generate a dummy value which it will be able to softly open to any message without being able to completely open it. Hard commitments, on the other hand, can be hardly or softly opened to only one specific message. At Eurocrypt 2008, Catalano, Fiore and Messina (CFM) introduced an extension called trapdoorq-mercurial commitment (qTMC), which allows committing to a vector ofqmessages. These qTMC schemes are interesting since their openings w.r.t. specific vector positions can be short (ideally, the opening length should not depend onq), which provides zero-knowledge sets with much shorter proofs when such a commitment is combined with a Merkle tree of arityq. The CFM construction notably features short proofs ofnon-membershipas it makes use of a qTMC scheme with short soft openings. A problem left open is that hard openings still have sizeO(q), which prevents proofs of membership from being as compact as those of non-membership. In this paper, we solve this open problem and describe a new qTMC scheme where hard and short position-wise openings, both, haveconstant size. We then show how our scheme is amenable to constructing independent zero-knowledge sets (i.e., ZKS’s that prevent adversaries from correlating their set to the sets of honest provers, as defined by Gennaro and Micali). Our solution retains the short proof property for this important primitive as well.