Short Lattice-based One-out-of-Many Proofs and Applications to Ring Signatures

Muhammed F.  Esgin; Ron Steinfeld; Amin Sakzad; Joseph K.  Liu; Dongxi Liu

Paper 2018/773

Short Lattice-based One-out-of-Many Proofs and Applications to Ring Signatures

Muhammed F. Esgin, Ron Steinfeld, Amin Sakzad, Joseph K. Liu, and Dongxi Liu

Abstract

In this work, we construct a short one-out-of-many proof from (module) lattices, allowing one to prove knowledge of a secret associated with one of the public values in a set. The proof system builds on a combination of ideas from the efficient proposals in the discrete logarithm setting by Groth and Kohlweiss (EUROCRYPT '15) and Bootle et al. (ESORICS '15), can have logarithmic communication complexity in the set size and does not require a trusted setup. Our work resolves an open problem mentioned by Libert et al. (EUROCRYPT '16) of how to efficiently extend the above discrete logarithm proof techniques to the lattice setting. To achieve our result, we introduce new technical tools for design and analysis of algebraic lattice-based zero-knowledge proofs, which may be of independent interest. Using our proof system as a building block, we design a short ring signature scheme, whose security relies on ``post-quantum'' lattice assumptions. Even for a very large ring size such as 1 billion, our ring signature size is only 3 MB for 128-bit security level compared to 216 MB in the best existing lattice-based result by Libert et al. (EUROCRYPT '16).

Note: The full version of the paper accepted to ACNS 2019.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. ACNS 2019
Keywords: lattice-based cryptography zero-knowledge proof one-out-of-many proof ring signature
Contact author(s): muhammed esgin @ monash edu
History: 2019-04-15: revised; 2018-08-27: received; See all versions
Short URL: https://ia.cr/2018/773
License: CC BY

BibTeX

@misc{cryptoeprint:2018/773,
      author = {Muhammed F.  Esgin and Ron Steinfeld and Amin Sakzad and Joseph K.  Liu and Dongxi Liu},
      title = {Short Lattice-based One-out-of-Many Proofs and Applications to Ring Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/773},
      year = {2018},
      url = {https://eprint.iacr.org/2018/773}
}