Paper 2021/202

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

Martin R. Albrecht and Russell W. F. Lai

Abstract

We study when (dual) Vandermonde systems of the form $V_T^{(⊺)}\cdot \overrightarrow{z}=s\cdot \overrightarrow{w}$ admit a solution $\overrightarrow{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 $$-subtractive sets $$ of size $$ poly over cyclotomic rings $$ for prime $$, we construct Schnorr-like lattice-based proofs of knowledge for the SIS relation $$ with $$ knowledge error, and $$ in case $$ 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 $$ relative to $$, which suggest that our Bulletproof-compatible protocols are optimal unless fundamentally new techniques are discovered. Noting that the knowledge error of lattice Bulletproofs is $$ for witnesses in $$ and subtractive set size $$, our result represents a barrier to practically efficient lattice-based succinct arguments in the Bulletproof framework. Beyond these main results, the concept of $$-subtractive sets bridges group-based threshold cryptography to lattice settings, which we demonstrate by relating it to distributed pseudorandom functions.