Welcome to the resource topic for 2021/202
Title:
Subtractive Sets over Cyclotomic Rings: Limits of Schnorr-like Arguments over Lattices
Authors: Martin R. Albrecht, Russell W. F. Lai
Abstract:We study when (dual) Vandermonde systems of the form {V}_T^{{(\intercal)}} \cdot \vec{z} = s\cdot \vec{w} admit a solution \vec{z} over a ring \mathcal{R}, where {V}_T is the Vandermonde matrix defined by a set T and where the “slack” s is a measure of the quality of solutions. To this end, we propose the notion of (s,t)-subtractive sets over a ring \mathcal{R}, with the property that if S is (s,t)-subtractive then the above (dual) Vandermonde systems defined by any t-subset T \subseteq S are solvable over \mathcal{R}. The challenge is then to find large sets S while minimising (the norm of) s when given a ring \mathcal{R}. By constructing families of (s,t)-subtractive sets S of size n = poly over cyclotomic rings \mathcal{R} = \mathbb{Z}[\zeta_{p^\ell}] for prime p, we construct Schnorr-like lattice-based proofs of knowledge for the SIS relation {A} \cdot \vec{x} = s \cdot \vec{y} \bmod q with O(1/n) knowledge error, and s = 1 in case p = poly. Our technique slots naturally into the lattice Bulletproof framework from Crypto’20, producing lattice-based succinct arguments for NP with better parameters. We then give matching impossibility results constraining n relative to s, which suggest that our Bulletproof-compatible protocols are optimal unless fundamentally new techniques are discovered. Noting that the knowledge error of lattice Bulletproofs is (\Omega(\log k/n)) for witnesses in (\mathcal{R}^k) and subtractive set size (n), our result represents a barrier to practically efficient lattice-based succinct arguments in the Bulletproof framework. Beyond these main results, the concept of (s,t)-subtractive sets bridges group-based threshold cryptography to lattice settings, which we demonstrate by relating it to distributed pseudorandom functions.
ePrint: https://eprint.iacr.org/2021/202
Talk: https://www.youtube.com/watch?v=wX9gnEcjSZI
Slides: https://iacr.org/submit/files/slides/2021/crypto/crypto2021/91/slides.pdf
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 .