### Efficient Set Membership Proofs using MPC-in-the-Head

Aarushi Goel, Matthew Green, Mathias Hall-Andersen, and Gabriel Kaptchuk

##### 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, {\em i.e.} $\mathcal{R}(w,x)=1$ and $x$ is a member of a public set $\{x_1, \ldots, x_\ell\}$. 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.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.Privacy Enhancing Technologies Symposium 2022
Keywords
Zero-knowledgeRing SignaturesSet MembershipConfidential Transactions
Contact author(s)
aarushig @ cs jhu edu
mgreen @ cs jhu edu
ma @ cs au dk
kaptchuk @ bu edu
History
2021-12-22: last of 4 revisions
See all versions
Short URL
https://ia.cr/2021/1656

CC BY

BibTeX

@misc{cryptoeprint:2021/1656,
author = {Aarushi Goel and Matthew Green and Mathias Hall-Andersen and Gabriel Kaptchuk},
title = {Efficient Set Membership Proofs using MPC-in-the-Head},
howpublished = {Cryptology ePrint Archive, Paper 2021/1656},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1656}},
url = {https://eprint.iacr.org/2021/1656}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.