Portal de Periódicos da CAPES

Subtractive Sets over Cyclotomic Rings

2021; Springer Science+Business Media; Linguagem: Inglês

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

1611-3349

M. Albrecht, Russell W. F. Lai,

Complexity and Algorithms in Graphs

We study when (dual) Vandermonde systems of the form $$\mathbf {V} _T^{{(\intercal )}} \cdot \mathbf {z} = s\cdot \mathbf {w}$$ admit a solution $$\mathbf {z}$$ over a ring $$\mathcal {R}$$ , where $$\mathbf {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 = \textsf {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 $$\mathbf {A} \cdot \mathbf {x} = s \cdot \mathbf {y} \bmod q$$ with O(1/n) knowledge error, and $$s = 1$$ in case $$p = \textsf {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 $$\varOmega (\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.