Paper 2020/518 Original: eprint.iacr.org/2020/518 ↗
Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings
Abstract
We propose a very fast 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 $8$. 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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2020-11-10: last updated
- 2020-05-05: published
- Short URL
- https://ia.cr/2020/518
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2020/518,
author = {Muhammed F. Esgin and Ngoc Khanh Nguyen and Gregor Seiler},
title = {Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/518},
year = {2020},
url = {https://eprint.iacr.org/2020/518}
}