Cryptology ePrint Archive: Report 2020/518

Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings

Muhammed F. Esgin and Ngoc Khanh Nguyen and Gregor Seiler

Abstract: We propose a lattice-based zero-knowledge proof system for exactly proving knowledge of a ternary solution $\vec{s} \in \{-1,0,1\}^n$ to a linear equation $A\vec{s}=\vec{u}$ over $\mathbb{Z}_q$, which improves upon the protocol by Bootle, Lyubashevsky and Seiler (CRYPTO 2019) by producing proofs that are shorter by a factor of $7.5$.

At the core lies a technique that utilizes the module-homomorphic BDLOP commitment scheme (SCN 2018) over the fully splitting cyclotomic ring $\mathbb{Z}_q[X]/(X^d + 1)$ to prove scalar products with the NTT vector of a secret polynomial.

Category / Keywords: cryptographic protocols / lattice-based, zero-knowledge, commitments

Date: received 4 May 2020, last revised 26 May 2020

Contact author: gseiler at inf ethz ch

Available format(s): PDF | BibTeX Citation

Version: 20200526:090809 (All versions of this report)

Short URL: ia.cr/2020/518


[ Cryptology ePrint archive ]