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^{{(\intercal)}} \cdot \vec{z} = s\cdot \vec{w}$ admit a solution $\vec{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 $(s,t)$-subtractive sets $S$ of size $n = $ poly 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 ${A} \cdot \vec{x} = s \cdot \vec{y} \bmod 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 \(\Omega(\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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in Crypto 2021
Keywords
Lattice-Based CryptographyLattice-based Zero Knowledge
Contact author(s)
martin albrecht @ royalholloway ac uk
russell lai @ cs fau de
History
2021-06-14: last of 2 revisions
2021-03-01: received
See all versions
Short URL
https://ia.cr/2021/202
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/202,
      author = {Martin R.  Albrecht and Russell W.  F.  Lai},
      title = {Subtractive Sets over Cyclotomic Rings: Limits of Schnorr-like Arguments over Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2021/202},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/202}},
      url = {https://eprint.iacr.org/2021/202}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.