Cryptology ePrint Archive: Report 2019/445

Lattice-based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications

Muhammed F. Esgin and Ron Steinfeld and Joseph K. Liu and 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.

Category / Keywords: cryptographic protocols / lattice-based cryptography, zero-knowledge proof, CRT packing, ring signature, one-out-of-many proof, range proof, set membership proof

Original Publication (with major differences): IACR-CRYPTO-2019

Date: received 1 May 2019

Contact author: muhammed esgin at monash edu

Available format(s): PDF | BibTeX Citation

Note: Full version of the paper.

Version: 20190508:185936 (All versions of this report)

Short URL: ia.cr/2019/445


[ Cryptology ePrint archive ]