Welcome to the resource topic for 2019/445
Title:
Lattice-based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications
Authors: Muhammed F. Esgin, Ron Steinfeld, Joseph K. Liu, Dongxi Liu
Abstract: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 k\ge 2, where the protocol achieves a negligible soundness error in a single execution, and thus performs significantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree k\ge 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 NTT-friendly’’ 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.
ePrint: https://eprint.iacr.org/2019/445
Talk: https://www.youtube.com/watch?v=p-louO6GdO8
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .