Paper 2021/1251

Efficient NIZKs for Algebraic Sets

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


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.

Note: Published in Asiacrypt 2021. This version includes additional references, all proofs, and several appendices03 October 2021: Replaced some [?] with missing references 08.01.2022: Minor revision. The conference version had several small typos but also a more global inconsistency about the notation of tensor products. We corrected it in this update.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in Asiacrypt 2021
Algebraic branching programsalgebraic languagesalgebraic setsNIZKpairing-based cryptographySPHFzero knowledge
Contact author(s)
couteau @ irif fr
helger lipmaa @ gmail com
robertoparisella @ hotmail it
arne tobias @ gmail com
2022-01-08: last of 2 revisions
2021-09-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Geoffroy Couteau and Helger Lipmaa and Roberto Parisella and Arne Tobias Ødegaard},
      title = {Efficient NIZKs for Algebraic Sets},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1251},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.