Paper 2021/564

SMILE: Set Membership from Ideal Lattices with Applications to Ring Signatures and Confidential Transactions

Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler


In a set membership proof, the public information consists of a set of elements and a commitment. The prover then produces a zero-knowledge proof showing that the commitment is indeed to some element from the set. This primitive is closely related to concepts like ring signatures and ``one-out-of-many'' proofs that underlie many anonymity and privacy protocols. The main result of this work is a new succinct lattice-based set membership proof whose size is logarithmic in the size of the set. We also give a transformation of our set membership proof to a ring signature scheme. The ring signature size is also logarithmic in the size of the public key set and has size $16$ KB for a set of $2^5$ elements, and $22$ KB for a set of size $2^{25}$. At an approximately $128$-bit security level, these outputs are between 1.5X and 7X smaller than the current state of the art succinct ring signatures of Beullens et al. (Asiacrypt 2020) and Esgin et al. (CCS 2019). We then show that our ring signature, combined with a few other techniques and optimizations, can be turned into a fairly efficient Monero-like confidential transaction system based on the MatRiCT framework of Esgin et al. (CCS 2019). With our new techniques, we are able to reduce the transaction proof size by factors of about 4X - 10X over the aforementioned work. For example, a transaction with two inputs and two outputs, where each input is hidden among $2^{15}$ other accounts, requires approximately $30$KB in our protocol.

Note: In submission.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2021
LatticesZero-Knowledge ProofsRing SignaturesBlockchain
Contact author(s)
vad @ zurich ibm com
nkn @ zurich ibm com
gseiler @ inf ethz ch
2022-05-20: last of 4 revisions
2021-05-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vadim Lyubashevsky and Ngoc Khanh Nguyen and Gregor Seiler},
      title = {SMILE: Set Membership from Ideal Lattices with Applications to Ring Signatures and Confidential Transactions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/564},
      year = {2021},
      doi = {10.1007/978-3-030-84245-1_21},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.