Cryptology ePrint Archive: Report 2020/1448
Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments
Vadim Lyubashevsky and Ngoc Khanh Nguyen and Gregor Seiler
Abstract: There has been a lot of recent progress in constructing efficient
zero-knowledge proofs for showing knowledge of an $\polvec s$ with small
coefficients satisfying $\pol A\polvec s=\polvec t$. For typical parameters,
the proof sizes have gone down from several megabytes to a bit under $50$KB
(Esgin et al., Asiacrypt 2020). These are now within an order of magnitude of
the sizes of lattice-based signatures, which themselves constitute proof
systems which demonstrate knowledge of something weaker than the
aforementioned equation. One can therefore see that this line of research is
approaching optimality. In this paper, we modify a key component of these
proofs, as well as apply several other tweaks, to achieve a further reduction
of around $30\%$ in the proof output size. We also show that this savings
propagates itself when these proofs are used in a general framework to
construct more complex protocols.
Category / Keywords: public-key cryptography / Lattices, Zero-Knowledge Proofs
Date: received 17 Nov 2020
Contact author: vad at zurich ibm com, nkn@zurich ibm com, gseiler@inf ethz ch
Available format(s): PDF | BibTeX Citation
Version: 20201119:094059 (All versions of this report)
Short URL: ia.cr/2020/1448
[ Cryptology ePrint archive ]