Paper 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.
Note: Fixed typos + revised grammatical and structural errors.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. INDOCRYPT 2025
- DOI
- 10.1007/978-3-032-13301-4_6
- Keywords
- LatticesZero-Knowledge ProtocolCommit-and-proveHint-MLWERejection sampling
- Contact author(s)
-
antoine douteau @ unicaen fr
adeline roux-langlois @ cnrs fr - History
- 2026-04-29: revised
- 2025-12-12: received
- See all versions
- Short URL
- https://ia.cr/2025/2239
- License
-
CC BY
BibTeX
@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}
}
