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 non-interactive zero-knowledge (NIZK) proofs from LWE implicitly solve the following /shifted multi-preimage 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 multi-preimage sampling problem with respect to \mathbf{A}_1, \ldots, \mathbf{A}_\ell. 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 NP) with (1) a linear-size common reference string (CRS); (2) a transparent setup in hiding mode (which yields statistical NIZK arguments); and (3) hardness from LWE with a polynomial modulus-to-noise ratio. This improves upon the work of Waters (STOC 2024) which required a quadratic-size structured reference string (in both modes) and LWE with a super-polynomial modulus-to-noise ratio.
-
We give a statistically-hiding vector commitment with transparent setup and polylogarithmic-size 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 lattice-based vector commitments and hidden-bits model NIZKs through the lens of the shifted multi-preimage 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 .