Paper 2024/1401
New Techniques for Preimage Sampling: Improved NIZKs and More from LWE
Abstract
Recent constructions of vector commitments and non-interactive zero-knowledge (NIZK) proofs from LWE implicitly solve the following shifted multi-preimage sampling problem: given matrices and targets , sample a shift and short preimages such that for all . In this work, we introduce a new technique for sampling together with a succinct public trapdoor for solving the multi-preimage sampling problem with respect to . This enables the following applications:
* We provide a dual-mode instantiation of the hidden-bits model (and by correspondence, a dual-mode NIZK proof for
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2025
- Keywords
- latticespreimage samplingnon-interactive zero-knowledgeNIZKvector commitment
- Contact author(s)
-
bwaters @ cs utexas edu
wee @ di ens fr
dwu4 @ cs utexas edu - History
- 2025-04-05: revised
- 2024-09-07: received
- See all versions
- Short URL
- https://ia.cr/2024/1401
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1401, author = {Brent Waters and Hoeteck Wee and David J. Wu}, title = {New Techniques for Preimage Sampling: Improved {NIZKs} and More from {LWE}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1401}, year = {2024}, url = {https://eprint.iacr.org/2024/1401} }