„Subtractive Sets over Cyclotomic Rings: Limits of Schnorr-like Arguments over Lattices“ erscheint auf der CRYPTO 2021
Das Paper „Subtractive Sets over Cyclotomic Rings: Limits of Schnorr-like Arguments over Lattices“ von Russell W. F. Lai in Zusammenarbeit mit Martin R. Albrecht erscheint auf dem IEEE International Symposium on Information Theory 2021.
Unten stehend finden Sie die Kurzfassung des Papers in englischer Sprache.
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(\lambda) 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(\lambda). 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.