International Association for Cryptologic Research

International Association
for Cryptologic Research


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

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
Presentation: Slides
Conference: CRYPTO 2021
Abstract: 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.
Video from CRYPTO 2021
  title={Subtractive Sets over Cyclotomic Rings: Limits of Schnorr-like Arguments over Lattices},
  author={Martin Albrecht and Russell W. F. Lai},