CryptoDB
RoK, Paper, SISsors – Toolkit for Latticebased Succinct Arguments
Authors: 


Download:  
Conference:  ASIACRYPT 2024 
Abstract:  Latticebased succinct arguments allow to prove boundednorm satisfiability of relations, such as $f(\mathbf{s}) = \mathbf{t} \bmod q$ and $\\mathbf{s}\\leq \beta$, over specific cyclotomic rings $\mathcal{O}_\mathcal{K}$, with proof size polylogarithmic in the witness size. However, stateoftheart protocols require either 1) a superpolynomial size modulus $q$ due to a soundness gap in the security argument, or 2) a verifier which runs in time linear in the witness size. Furthermore, construction techniques often rely on specific choices of $\mathcal{K}$ which are not mutually compatible. In this work, we exhibit a diverse toolkit for constructing efficient latticebased succinct arguments: \begin{enumerate} \item We identify new subtractive sets for general cyclotomic fields $\mathcal{K}$ and their maximal real subfields $\mathcal{K}^+$, which are useful as challenge sets, e.g. in arguments for exact norm bounds. \item We construct modular, verifiersuccinct reductions of knowledge for the boundednorm satisfiability of structuredlinear/innerproduct relations, without any soundness gap, under the vanishing SIS assumption, over any $\mathcal{K}$ which admits polynomialsize subtractive sets. \item We propose a framework to use twisted trace maps, i.e. maps of the form $\tau(z) = \frac{1}{N} \cdot \mathsf{Trace}_{\mathcal{K}/\mathbb{Q}}( \alpha \cdot z )$, to embed $\mathcal{R}$innerproducts as $\mathcal{R}$innerproducts for some structured subrings $\mathcal{R} \subseteq \mathcal{O}_\mathcal{K}$ whenever the conductor has a squarefree odd part. \item We present a simple extension of our reductions of knowledge for proving the consistency between the coefficient embedding and the Chinese Remainder Transform (CRT) encoding of $\vec{s}$ over any cyclotomic field $\mathcal{K}$ with a smooth conductor, based on a succinct decomposition of the CRT map into automorphisms, and a new, simple succinct argument for proving automorphism relations. \end{enumerate} Combining all techniques, we obtain, for example, verifiersuccinct arguments for proving that $\vec{s}$ satisfying $f(\mathbf{s}) = \mathbf{t} \bmod q$ has binary coefficients, without soundness gap and with polynomialsize modulus $q$. 
BibTeX
@inproceedings{asiacrypt202434671, title={RoK, Paper, SISsors – Toolkit for Latticebased Succinct Arguments}, publisher={SpringerVerlag}, author={Michael Klooß and Russell W. F. Lai and Ngoc Khanh Nguyen and Michał Osadnik}, year=2024 }