International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Muhammed F. Esgin
Ngoc Khanh Nguyen
Gregor Seiler
Download:
DOI: 10.1007/978-3-030-64834-3_9
Search ePrint
Search Google
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.
Video from ASIACRYPT 2020
BibTeX
@article{asiacrypt-2020-30647,
  title={Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  publisher={Springer},
  doi={10.1007/978-3-030-64834-3_9},
  author={Muhammed F. Esgin and Ngoc Khanh Nguyen and Gregor Seiler},
  year=2020
}