Welcome to the resource topic for 2024/1401
Title:
New Techniques for Preimage Sampling: Improved NIZKs and More from LWE
Authors: Brent Waters, Hoeteck Wee, David J. Wu
Abstract:Recent constructions of vector commitments and noninteractive zeroknowledge (NIZK) proofs from LWE implicitly solve the following /shifted multipreimage sampling problem/: given matrices \mathbf{A}_1, \ldots, \mathbf{A}_\ell \in \mathbb{Z}_q^{n \times m} and targets \mathbf{t}_1, \ldots, \mathbf{t}_\ell \in \mathbb{Z}_q^n, sample a shift \mathbf{c} \in \mathbb{Z}_q^n and short preimages \boldsymbol{\pi}_1, \ldots, \boldsymbol{\pi}_\ell \in \mathbb{Z}_q^m such that \mathbf{A}_i \boldsymbol{\pi}_i = \mathbf{t}_i + \mathbf{c} for all i \in [\ell]. In this work, we introduce a new technique for sampling \mathbf{A}_1, \ldots, \mathbf{A}_\ell together with a succinct public trapdoor for solving the multipreimage sampling problem with respect to \mathbf{A}_1, \ldots, \mathbf{A}_\ell. This enables the following applications:

We provide a dualmode instantiation of the hiddenbits model (and by correspondence, a dualmode NIZK proof for NP) with (1) a linearsize common reference string (CRS); (2) a transparent setup in hiding mode (which yields statistical NIZK arguments); and (3) hardness from LWE with a polynomial modulustonoise ratio. This improves upon the work of Waters (STOC 2024) which required a quadraticsize structured reference string (in both modes) and LWE with a superpolynomial modulustonoise ratio.

We give a statisticallyhiding vector commitment with transparent setup and polylogarithmicsize CRS, commitments, and openings from SIS. This simultaneously improves upon the vector commitment schemes of de Castro and Peikert (EUROCRYPT 2023) as well as Wee and Wu (EUROCRYPT 2023).
At a conceptual level, our work provides a unified view of recent latticebased vector commitments and hiddenbits model NIZKs through the lens of the shifted multipreimage sampling problem.
ePrint: https://eprint.iacr.org/2024/1401
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .