Paper 2018/773
Short Lattice-based One-out-of-Many Proofs and Applications to Ring Signatures
Muhammed F. Esgin and Ron Steinfeld and Amin Sakzad and Joseph K. Liu and Dongxi Liu
Abstract
In this work, we construct a short one-out-of-many proof from (Module-SIS) lattices, allowing one to prove knowledge of a secret associated with one of the public values in a set. The proof system follows 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 adapt the above discrete logarithm proof techniques to the lattice setting. To achieve our result, we introduce 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 lattice-based ring signature scheme. Our scheme offers post-quantum security and practical usability in cryptocurrencies and e-voting systems. Even for a very large ring size such as 1 billion, our ring signature size is only 4.5 MB for 100-bit security level compared to 166 MB in the best existing lattice-based result by Libert et al. (EUROCRYPT '16).
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- lattice-based cryptographyzero-knowledge proofring 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