Paper 2025/2239

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

, Université Caen Normandie, ENSICAEN, CNRS, Normandie Univ, GREYC UMR 6072, F-14000 Caen, France

Adeline Roux-Langlois, Université Caen Normandie, ENSICAEN, CNRS, Normandie Univ, GREYC UMR 6072, F-14000 Caen, France

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.

Note: Fixed typos + revised grammatical and structural errors.

@misc{cryptoeprint:2025/2239,
      author = {Antoine Douteau and Adeline Roux-Langlois},
      title = {Rejection-Free Framework of Zero-Knowledge Proof Based on Hint-{MLWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2239},
      year = {2025},
      doi = {10.1007/978-3-032-13301-4_6},
      url = {https://eprint.iacr.org/2025/2239}
}