International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Vadim Lyubashevsky , IBM Research Europe - Zurich
Ngoc Khanh Nguyen , IBM Research Europe - Zurich & ETH Zurich
Gregor Seiler , IBM Research Europe - Zurich & ETH Zurich
Download:
DOI: 10.1007/978-3-030-84245-1_21 (login may be required)
Search ePrint
Search Google
Conference: CRYPTO 2021
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 transformations of our set membership proof to a ring signature scheme and to a confidential transaction payment system. 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.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31121,
  title={SMILE: Set Membership from Ideal Lattices with Applications to Ring Signatures and Confidential Transactions},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-84245-1_21},
  author={Vadim Lyubashevsky and Ngoc Khanh Nguyen and Gregor Seiler},
  year=2021
}