Rejection-Free Framework of Zero-Knowledge Proof Based on Hint-MLWE
摘要
Commit-and-prove zero-knowledge proofs are a generalized version of zero-knowledge protocols that permit proving relations over the committed elements in addition testifying to its 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 time execution 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.