Efficient Set Membership Proofs using MPC-in-the-Head
Efficient Set Membership Proofs using MPC-in-the-Head
复制标题
DOI：
10.2478/popets-2022-0047
复制
发表时间：
2022-03
影响因子：
--
通讯作者：
Aarushi Goel;M. Green;Mathias Hall-Andersen;Gabriel Kaptchuk
中科院分区：
文献类型：
--
作者：
Aarushi Goel;M. Green;Mathias Hall-Andersen;Gabriel Kaptchuk
摘要集合成员证明是隐私保护系统中非常重要的一部分。这些证明允许证明者证明与公共集合的秘密元素x相对应的见证w的知识，使得它们共同满足给定的NP关系，即，n（w，x）= 1并且x是公共集合{x1，. . .，x {\displaystyle x {\displaystyle x}}。这使得证明者的身份保持隐藏，例如。环签名和加密货币的机密交易。在这项工作中，我们开发了一种新的技术，用于有效地添加到任何基于零知识协议（Ishai等人[STOC'07]）的MPC中的头的集合成员资格证明。我们将我们的技术集成到Katz等人[CCS'18]的最先进的后量子安全零知识协议的开源实现中。我们发现，使用我们的技术来构造环签名会导致签名（仅基于对称密钥原语）比基于相同假设的最先进技术小5到10倍。我们还表明，我们的技术可以用来有效地构建后量子安全RingCT从对称密钥原语。
Abstract Set membership proofs are an invaluable part of privacy preserving systems. These proofs allow a prover to demonstrate knowledge of a witness w corresponding to a secret element x of a public set, such that they jointly satisfy a given NP relation, i.e. ℛ(w, x) = 1 and x is a member of a public set {x1, . . . , x𝓁}. This allows the identity of the prover to remain hidden, eg. ring signatures and confidential transactions in cryptocurrencies. In this work, we develop a new technique for efficiently adding logarithmic-sized set membership proofs to any MPC-in-the-head based zero-knowledge protocol (Ishai et al. [STOC’07]). We integrate our technique into an open source implementation of the state-of-the-art, post quantum secure zero-knowledge protocol of Katz et al. [CCS’18].We find that using our techniques to construct ring signatures results in signatures (based only on symmetric key primitives) that are between 5 and 10 times smaller than state-of-the-art techniques based on the same assumptions. We also show that our techniques can be used to efficiently construct post-quantum secure RingCT from only symmetric key primitives.