## CryptoDB

### Helger Lipmaa

#### Publications

**Year**

**Venue**

**Title**

2023

ASIACRYPT

On Black-Box Knowledge-Sound Commit-And-Prove SNARKs
Abstract

Gentry and Wichs proved that adaptively sound SNARGs for hard languages need non-falsifiable assumptions. Lipmaa and Pavlyk claimed Gentry-Wichs is tight by constructing a non-adaptively sound zk-SNARG FANA for NP from falsifiable assumptions. We show that FANA is flawed. We define and construct a fully algebraic $F$-position-binding vector commitment scheme VCF. We construct a concretely efficient commit-and-prove zk-SNARK Punic, a version of FANA with an additional VCF commitment to the witness. Punic satisfies semi-adaptive black-box $G$-knowledge-soundness, a new natural knowledge-soundness notion for commit-and-prove SNARKs. We use a new proof technique to achieve global consistency using a functional somewhere-extractable commitment scheme to extract vector commitment's local proofs.

2023

TCC

Algebraic Group Model with Oblivious Sampling
Abstract

In the algebraic group model (AGM), an adversary has to return with each group element a linear representation with respect to input group elements. In many groups, it is easy to sample group elements obliviously without knowing such linear representations. Since the AGM does not model this, it can be used to prove the security of spurious knowledge assumptions. We propose AGM with oblivious sampling (AGMOS), a variant of the AGM where the adversary has additional access to an oracle that allows sampling group elements obliviously from some distribution. We separate AGM and AGMOS by classifying the family of ``total knowledge-of-exponent'' assumptions, showing that while they are all secure in the AGM (even insecure ones), most are not secure in the AGMOS if the DL holds. We show that many known AGM reductions go through also in the AGMOS, assuming a novel falsifiable assumption $\TOFR$. We prove that $\TOFR$ is secure in a version of GGM with oblivious sampling.

2022

ASIACRYPT

Counting Vampires: From Univariate Sumcheck to Updatable ZK-SNARK
📺
Abstract

We propose a univariate sumcheck argument $\mathfrak{Count}$ of essentially
optimal communication efficiency of one group element. While the previously
most efficient univariate sumcheck argument of Aurora is based on polynomial
commitments, $\mathfrak{Count}$ is based on inner-product commitments. We
use $\mathfrak{Count}$ to construct a new pairing-based updatable and
universal zk-SNARK $\mathfrak{Vampire}$ with the shortest known argument
length (four group and two finite field elements) for $\mathsf{NP}$. In addition,
$\mathfrak{Vampire}$ uses the aggregated polynomial commitment scheme of
Boneh et al.

2022

PKC

A Unified Framework for Non-Universal SNARKs
Abstract

We propose a general framework for non-universal SNARKs. It contains (1) knowledge-sound and non-black-box any-simulation-extractable (ASE), (2) zero-knowledge and subversion-zero knowledge SNARKs for the well-known QAP, SAP, QSP, and QSP constraint languages that all by design have \emph{relatively} simple security proofs. The knowledge-sound zero-knowledge SNARK is similar to Groth's SNARK from EUROCRYPT 2016, except having fewer trapdoors, while the ASE subversion-zero knowledge SNARK relies on few additional conditions. We prove security in a weaker, more realistic version of the algebraic group model. We characterize SAP, SSP, and QSP in terms of QAP; this allows one to use a SNARK for QAP directly for other languages. Our results allow us to construct a family of SNARKs for different languages and with different security properties following the same proof template. Some of the new SNARKs are more efficient than prior ones. In other cases, the new SNARKs cover gaps in the landscape, e.g., there was no previous ASE or Sub-ZK SNARK for SSP or QSP.

2021

ASIACRYPT

Verifiably-Extractable OWFs and Their Applications to Subversion Zero-Knowledge
📺
Abstract

An extractable one-way function (EOWF), introduced by Canetti and Dakdouk (ICALP 2008) and generalized by Bitansky et al. (SIAM Journal on Computing vol. 45), is an OWF that allows for efficient extraction of a preimage for the function.
We study (generalized) EOWFs that have a public image verification algorithm.
We call such OWFs verifiably-extractable and show that several previously known constructions satisfy this notion.
We study how such OWFs relate to subversion zero-knowledge (Sub-ZK) NIZKs by using them to generically construct a Sub-ZK NIZK from a NIZK satisfying certain additional properties, and conversely show how to obtain them from any Sub-ZK NIZK.
Prior to our work, the Sub-ZK property of NIZKs was achieved using concrete knowledge assumptions.

2021

ASIACRYPT

Efficient NIZKs for Algebraic Sets
📺
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.

2021

ASIACRYPT

Gentry-Wichs Is Tight: A Falsifiable Non-Adaptively Sound SNARG
📺
Abstract

By the impossibility result of Gentry and Wichs, non-falsifiable assumptions are needed to construct (even non-zero-knowledge) adaptively sound succinct non-interactive arguments (SNARGs) for hard languages. It is important to understand whether this impossibility result is tight. While it is known how to construct adaptively sound non-succinct non-interactive arguments for $\mathsf{NP}$ from falsifiable assumptions, adaptively sound SNARGs for $\mathsf{NP}$ from non-falsifiable assumptions, and adaptively sound SNARGs for $\mathsf{P}$ from falsifiable assumptions, there are no known non-adaptively sound SNARGs for $\mathsf{NP}$ from falsifiable assumptions. We show that Gentry-Wichs is tight by constructing the latter. In addition, we prove it is non-adaptively knowledge-sound in the algebraic group model and Sub-ZK (i.e., zero-knowledge even if the CRS is subverted) under a non-falsifiable assumption.

2021

JOFC

On Subversion-Resistant SNARKs
Abstract

While NIZK arguments in the CRS model are widely studied, the question of what happens when the CRS is subverted has received little attention. In ASIACRYPT 2016, Bellare, Fuchsbauer, and Scafuro showed the first negative and positive results, proving also that it is impossible to achieve subversion soundness and (even non-subversion) zero knowledge at the same time. On the positive side, they constructed a sound and subversion-zero knowledge (Sub-ZK) non-succinct NIZK argument for NP. We consider the practically very relevant case of zk-SNARKs. We make Groth’s zk-SNARK for Circuit-SAT from EUROCRYPT 2016 computationally knowledge-sound and perfectly composable Sub-ZK with minimal changes. We only require the CRS trapdoor to be extractable and the CRS to be publicly verifiable. To achieve the latter, we add some new elements to the CRS and construct an efficient CRS verification algorithm. We also provide a definitional framework for knowledge-sound and Sub-ZK SNARKs.

2020

PKC

On QA-NIZK in the BPK Model
📺
Abstract

Recently, Bellare et al. defined subversion-resistance (security in the case the CRS creator may be malicious) for NIZK. In particular, a Sub-ZK NIZK is zero-knowledge, even in the case of subverted CRS. We study Sub-ZK QA-NIZKs, where the CRS can depend on the language parameter. First, we observe that subversion zero-knowledge (Sub-ZK) in the CRS model corresponds to no-auxiliary-string non-black-box NIZK in the Bare Public Key model, and hence, the use of non-black-box techniques is needed to obtain Sub-ZK. Second, we give a precise definition of Sub-ZK QA-NIZKs that are (knowledge-)sound if the language parameter but not the CRS is subverted and zero-knowledge even if both are subverted. Third, we prove that the most efficient known QA-NIZK for linear subspaces by Kiltz and Wee is Sub-ZK under a new knowledge assumption that by itself is secure in (a weaker version of) the algebraic group model. Depending on the parameter setting, it is (knowledge-)sound under different non-falsifiable assumptions, some of which do not belong to the family of knowledge assumptions.

2020

ASIACRYPT

Succinct Functional Commitment for a Large Class of Arithmetic Circuits
📺
Abstract

A succinct functional commitment (SFC) scheme for a circuit class $\mathbf{CC}$ enables, for any circuit $\mathcal{C}\in \mathbf{CC}$, the committer to first succinctly commit to a vector $\vec{\alpha}$, and later succinctly open the commitment to $\mathcal{C} (\vec{\alpha}, \vec{\beta})$, where the verifier chooses $\vec{\beta}$ at the time of opening. Unfortunately, SFC commitment schemes are known only for severely limited function classes like the class of inner products. By making non-black-box use of SNARK-construction techniques, we propose a SFC scheme for the large class of semi-sparse polynomials. The new SFC scheme can be used to, say, efficiently (1) implement sparse polynomials, and (2) aggregate various interesting SFC (e.g., vector commitment and polynomial commitment) schemes. The new scheme is evaluation-binding under a new instantiation of the computational uber-assumption. We provide a thorough analysis of the new assumption.

2013

ASIACRYPT

#### Program Committees

- Crypto 2024
- Eurocrypt 2022
- PKC 2020
- Asiacrypt 2020
- PKC 2019
- Asiacrypt 2019
- Asiacrypt 2018
- Eurocrypt 2010
- Eurocrypt 2006
- FSE 2003

#### Coauthors

- Behzad Abdolmaleki (3)
- Andris Ambainis (1)
- Karim Baghery (1)
- Fabrice Benhamouda (1)
- Florian Bourse (1)
- Ahto Buldas (2)
- Geoffroy Couteau (1)
- Philippe Dumas (1)
- Prastudy Fauzi (3)
- Jens Groth (1)
- Markus Jakobsson (1)
- Aggelos Kiayias (1)
- Peeter Laud (1)
- Sven Laur (1)
- Shiho Moriai (1)
- Arne Tobias Ødegaard (2)
- Roberto Parisella (2)
- Kateryna Pavlyk (2)
- Berry Schoenmakers (1)
- Janno Siim (6)
- Johan Wallén (1)
- Jan Willemson (1)
- Michał Zając (7)