Paper 2025/2239 Original: eprint.iacr.org/2025/2239 ↗

Rejection-Free Framework of Zero-Knowledge Proof Based on Hint-MLWE

Abstract

Commit-and-prove zero-knowledge proofs are generalized ver- sions of zero-knowledge protocols that permit proving relations over the committed elements in addition testifying the knowledge of the initial message. For example, the existing framework (LNP, Crypto22) allow a user to prove that the secret element committed satisfies quadratic relations with bounded norm ($\ell_2$ or $\ell_\infty$). Security of these frameworks, regarding the zero knowledge property, is mainly assumed by the use of rejection sampling introduced by Lyubashevsky (Asiacrypt09). The main problems with rejection sampling are non-constant execution time and the cost of protecting this step from side-channel attacks. Our contribution is a new framework of proof for zero-knowledge property that proves knowledge and quadratic relations over lattices without basing the security over rejection sampling. The security of our framework is based on the recent Hint-MLWE (KLSS, Crypto23) assumption. This variant of MLWE gives additional hints about the secret in addition to the original input, and is shown to be as hard as its associated MLWE instance when secrets follow discrete Gaussian distributions.