Welcome to the resource topic for 2021/1251
Title:
Efficient NIZKs for Algebraic Sets
Authors: Geoffroy Couteau, Helger Lipmaa, Roberto Parisella, 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.
ePrint: https://eprint.iacr.org/2021/1251
Talk: https://www.youtube.com/watch?v=v4RCFA9mJgk
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .