Lattice-based zero-knowledge proofs: new techniques for shorter and faster constructions and applications

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

34 Citations (Scopus)


We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree≥ 2, where the protocol achieves a negligible soundness error in a single execution, and thus performs signicantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree ≥ 2 have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P '18) and arithmetic circuit arguments (EUROCRYPT '16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case (k = 1) and a very specific quadratic case (k = 2), which are obtained as a special case of our technique.

Moreover, we introduce two speedup techniques for lattice-based ZKPs: a CRT-packing technique supporting "inter-slot" operations, and "NTTfriendly" tools that permit the use of fully-splitting rings. The former technique comes at almost no cost to the proof length, and the latter one barely increases it, which can be compensated for by tweaking the rejection sampling parameters while still having faster computation overall.

To illustrate the utility of our techniques, we show how to use them to build efficient relaxed proofs for important relations, namely proof of commitment to bits, one-out-of-many proof, range proof and set membership proof. Despite their relaxed nature, we further show how our proof systems can be used as building blocks for advanced cryptographic tools such as ring signatures.

Our ring signature achieves a dramatic improvement in length over all the existing proposals from lattices at the same security level. The computational evaluation also shows that our construction is highly likely to outperform all the relevant works in running times. Being efficient in both aspects, our ring signature is particularly suitable for both small-scale and large-scale applications such as cryptocurrencies and e-voting systems. No trusted setup is required for any of our proposals.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2019
Subtitle of host publication39th Annual International Cryptology Conference Santa Barbara, CA, USA, August 18–22, 2019 Proceedings, Part I
EditorsAlexandra Boldyreva, Daniele Micciancio
Place of PublicationCham Switzerland
Number of pages32
ISBN (Electronic)9783030269487
ISBN (Print)9783030269470
Publication statusPublished - 2019
EventAdvances in Cryptology 2019 - Santa Barbara, United States of America
Duration: 18 Aug 201922 Aug 2019
Conference number: 39th (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceAdvances in Cryptology 2019
Abbreviated titleCRYPTO 2019
Country/TerritoryUnited States of America
CitySanta Barbara
Internet address


  • CRT packing
  • Lattice-based cryptography
  • One-out-of-many proof
  • Range proof
  • Ring signature
  • Set membership proof
  • Zero-knowledge proof

Cite this