SMILE: Set Membership from Ideal Lattices with Applications to Ring Signatures and Confidential Transactions
Metadata only
Date
2021Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
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. Show more
Publication status
publishedExternal links
Book title
Advances in Cryptology – CRYPTO 2021Journal / series
Lecture Notes in Computer ScienceVolume
Pages / Article No.
Publisher
SpringerEvent
More
Show all metadata
ETH Bibliography
yes
Altmetrics