We propose a very fast lattice-based zero-knowledge proof system for exactly proving knowledge of a ternary solution s~→ ∈ { -1, 0, 1}~n to a linear equation As~→ = u~→ over 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 Z_q[X]/(X~d + 1) to prove scalar products with the NTT vector of a secret polynomial.
展开▼
