## CryptoDB

### Paper: Subtractive Sets over Cyclotomic Rings: Limits of Schnorr-like Arguments over Lattices

Authors: Martin Albrecht , Royal Holloway, University of London Russell W. F. Lai , Chair of Applied Cryptography, Friedrich-Alexander-Universität Erlangen-Nürnberg DOI: 10.1007/978-3-030-84245-1_18 (login may be required) Search ePrint Search Google Slides CRYPTO 2021 We study when (dual) Vandermonde systems of the form V_T ⋅ z = s⋅w admit a solution z over a ring 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 R, with the property that if S is (s,t)-subtractive then the above (dual) Vandermonde systems defined by any t-subset T ⊆ S are solvable over R. The challenge is then to find large sets S while minimising (the norm of) s when given a ring R. By constructing families of (s,t)-subtractive sets S of size n = poly(λ) over cyclotomic rings R = ZZ[ζ_{p^ℓ}] for prime p, we construct Schnorr-like lattice-based proofs of knowledge for the SIS relation A ⋅ x = s ⋅ y mod 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 Ω(log k/n) for witnesses in 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 the lattice settings, which we demonstrate by relating it to distributed pseudorandom functions.
##### BibTeX
@inproceedings{crypto-2021-31093,
title={Subtractive Sets over Cyclotomic Rings: Limits of Schnorr-like Arguments over Lattices},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-84245-1_18},
author={Martin Albrecht and Russell W. F. Lai},
year=2021
}