Home Publications Research Grants Inventions & Patents Awards Additional Research Activities Faculties & Institutions Research Areas

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

Albrecht MR, Lai RWF (2021)

---

Publication Type: Conference contribution

Publication year: 2021

Journal

Publisher: Springer Science and Business Media Deutschland GmbH

Book Volume: 12826 LNCS

Pages Range: 519-548

Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Event location: Virtual, Online

ISBN: 9783030842444

DOI: 10.1007/978-3-030-84245-1_18

Abstract

We study when (dual) Vandermonde systems of the form VT(⊺)·z=s·w admit a solution z over a ring R, where VT 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=Z[ζpℓ] for prime p, we construct Schnorr-like lattice-based proofs of knowledge for the SIS relation A·x=s·ymodq 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 lattice settings, which we demonstrate by relating it to distributed pseudorandom functions.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Albrecht, M.R., & Lai, R.W.F. (2021). Subtractive Sets over Cyclotomic Rings: Limits of Schnorr-Like Arguments over Lattices. In Tal Malkin, Chris Peikert (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 519-548). Virtual, Online: Springer Science and Business Media Deutschland GmbH.

MLA:

Albrecht, Martin R., and Russell W. F. Lai. "Subtractive Sets over Cyclotomic Rings: Limits of Schnorr-Like Arguments over Lattices." Proceedings of the 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual, Online Ed. Tal Malkin, Chris Peikert, Springer Science and Business Media Deutschland GmbH, 2021. 519-548.

BibTeX: Download