**Efficient NIZKs for Algebraic Sets**

*Geoffroy Couteau and Helger Lipmaa and Roberto Parisella and Arne Tobias Ødegaard*

**Abstract: **Significantly extending the framework of (Couteau and Hartmann, Crypto 2020), we propose a general methodology to construct NIZKs for showing that an encrypted vector $\vec{\chi}$ belongs to an algebraic set, i.e., is in the zero locus of an ideal $\mathscr{I}$ of a polynomial ring. In the case where $\mathscr{I}$ is principal, i.e., generated by a single polynomial $F$, we first construct a matrix that is a ``quasideterminantal representation'' of $F$ and then a NIZK argument to show that $F (\vec{\chi}) = 0$. This leads to compact NIZKs for general computational structures, such as polynomial-size algebraic branching programs. We extend the framework to the case where $\IDEAL$ is non-principal, obtaining efficient NIZKs for R1CS, arithmetic constraint satisfaction systems, and thus for $\mathsf{NP}$. As an independent result, we explicitly describe the corresponding language of ciphertexts as an algebraic language, with smaller parameters than in previous constructions that were based on the disjunction of algebraic languages. This results in an efficient GL-SPHF for algebraic branching programs.

**Category / Keywords: **cryptographic protocols / Algebraic branching programs, algebraic languages, algebraic sets, NIZK, pairing-based cryptography, SPHF, zero knowledge

**Original Publication**** (with minor differences): **IACR-ASIACRYPT-2021

**Date: **received 20 Sep 2021, last revised 3 Oct 2021

**Contact author: **couteau at irif fr, helger lipmaa at gmail com, robertoparisella at hotmail it, arne tobias at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **Published in Asiacrypt 2021. This version includes additional references, all proofs, and several appendices

03 October 2021: Replaced some [?] with missing references

**Version: **20211003:195938 (All versions of this report)

**Short URL: **ia.cr/2021/1251

[ Cryptology ePrint archive ]