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

Abstract

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 afore-mentioned work. For example, a transaction with two inputs and two outputs, where each input is hidden among 2(15) other accounts, requires approximately 30KB in our protocol.