## CryptoDB

### Jens Groth

#### Affiliation: University College London

#### Publications

**Year**

**Venue**

**Title**

2018

CRYPTO

Updatable and Universal Common Reference Strings with Applications to zk-SNARKs
📺
Abstract

By design, existing (pre-processing) zk-SNARKs embed a secret trapdoor in a relation-dependent common reference strings (CRS). The trapdoor is exploited by a (hypothetical) simulator to prove the scheme is zero knowledge, and the secret-dependent structure facilitates a linear-size CRS and linear-time prover computation. If known by a real party, however, the trapdoor can be used to subvert the security of the system. The structured CRS that makes zk-SNARKs practical also makes deploying zk-SNARKS problematic, as it is difficult to argue why the trapdoor would not be available to the entity responsible for generating the CRS. Moreover, for pre-processing zk-SNARKs a new trusted CRS needs to be computed every time the relation is changed.In this paper, we address both issues by proposing a model where a number of users can update a universal CRS. The updatable CRS model guarantees security if at least one of the users updating the CRS is honest. We provide both a negative result, by showing that zk-SNARKs with private secret-dependent polynomials in the CRS cannot be updatable, and a positive result by constructing a zk-SNARK based on a CRS consisting only of secret-dependent monomials. The CRS is of quadratic size, is updatable, and is universal in the sense that it can be specialized into one or more relation-dependent CRS of linear size with linear-time prover computation.

2018

CRYPTO

Sub-linear Lattice-Based Zero-Knowledge Arguments for Arithmetic Circuits
📺
Abstract

We propose the first zero-knowledge argument with sub-linear communication complexity for arithmetic circuit satisfiability over a prime
$${p}$$
whose security is based on the hardness of the short integer solution (SIS) problem. For a circuit with
$${N}$$
gates, the communication complexity of our protocol is
$$O\left( \sqrt{{N}{\lambda }\log ^3{{N}}}\right) $$
, where
$${\lambda }$$
is the security parameter. A key component of our construction is a surprisingly simple zero-knowledge proof for pre-images of linear relations whose amortized communication complexity depends only logarithmically on the number of relations being proved. This latter protocol is a substantial improvement, both theoretically and in practice, over the previous results in this line of research of Damgård et al. (CRYPTO 2012), Baum et al. (CRYPTO 2016), Cramer et al. (EUROCRYPT 2017) and del Pino and Lyubashevsky (CRYPTO 2017), and we believe it to be of independent interest.

2018

PKC

Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials
Abstract

Bootle et al. (EUROCRYPT 2016) construct an extremely efficient zero-knowledge argument for arithmetic circuit satisfiability in the discrete logarithm setting. However, the argument does not treat relations involving commitments, and furthermore, for simple polynomial relations, the complex machinery employed is unnecessary.In this work, we give a framework for expressing simple relations between commitments and field elements, and present a zero-knowledge argument which, by contrast with Bootle et al., is constant-round and uses fewer group operations, in the case where the polynomials in the relation have low degree. Our method also directly yields a batch protocol, which allows many copies of the same relation to be proved and verified in a single argument more efficiently with only a square-root communication overhead in the number of copies.We instantiate our protocol with concrete polynomial relations to construct zero-knowledge arguments for membership proofs, polynomial evaluation proofs, and range proofs. Our work can be seen as a unified explanation of the underlying ideas of these protocols. In the instantiations of membership proofs and polynomial evaluation proofs, we also achieve better efficiency than the state of the art.

2018

ASIACRYPT

Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution
Abstract

There have been tremendous advances in reducing interaction, communication and verification time in zero-knowledge proofs but it remains an important challenge to make the prover efficient. We construct the first zero-knowledge proof of knowledge for the correct execution of a program on public and private inputs where the prover computation is nearly linear time. This saves a polylogarithmic factor in asymptotic performance compared to current state of the art proof systems.We use the TinyRAM model to capture general purpose processor computation. An instance consists of a TinyRAM program and public inputs. The witness consists of additional private inputs to the program. The prover can use our proof system to convince the verifier that the program terminates with the intended answer within given time and memory bounds. Our proof system has perfect completeness, statistical special honest verifier zero-knowledge, and computational knowledge soundness assuming linear-time computable collision-resistant hash functions exist. The main advantage of our new proof system is asymptotically efficient prover computation. The prover’s running time is only a superconstant factor larger than the program’s running time in an apples-to-apples comparison where the prover uses the same TinyRAM model. Our proof system is also efficient on the other performance parameters; the verifier’s running time and the communication are sublinear in the execution time of the program and we only use a log-logarithmic number of rounds.

2017

ASIACRYPT

2016

EUROCRYPT

2015

JOFC

2009

EPRINT

Homomorphic Trapdoor Commitments to Group Elements
Abstract

We present a homomorphic trapdoor commitment to group elements. In contrast, previous homomorphic trapdoor commitment schemes only allow the messages to be exponents. Our commitment scheme is length-reducing, we can make a short commitment to many group elements at once, and it is perfectly hiding and computationally binding. The construction is based on groups with a bilinear map and the binding property follows from the simultaneous triple pairing assumption. While the simultaneous triple pairing assumption is new, we demonstrate that it is implied by the well-known decision linear assumption.

2007

EPRINT

Fully Anonymous Group Signatures without Random Oracles
Abstract

We construct a new group signature scheme using bilinear groups. The group signature scheme is practical, both keys and group signatures consist of a constant number of group elements, and the scheme permits dynamic enrollment of new members. The scheme satisfies strong security requirements, in particular providing protection against key exposures and not relying on random oracles in the security proof.

2007

EPRINT

Efficient Non-interactive Proof Systems for Bilinear Groups
Abstract

Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as Circuit Satisfiability, causing an expensive blowup in the size of the statement when reducing it to a circuit. The contribution of this paper is a general methodology for constructing very simple and efficient non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs that work directly for groups with a bilinear map, without needing a reduction to Circuit Satisfiability.
Groups with bilinear maps have enjoyed tremendous success in the field of cryptography in recent years and have been used to construct a plethora of protocols. This paper provides non-interactive witness-indistinguishable proofs and non-interactive zero-knowledge proofs that can be used in connection with these protocols. Our goal is to spread the use of non-interactive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups.

2006

ASIACRYPT

2006

EPRINT

Cryptography in the Multi-string Model
Abstract

The common random string model permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. In this model, a trusted party generates a random string and gives it to all parties in the protocol. However, the introduction of such a third party should set alarm bells going off: Who is this trusted party? Why should we trust that the string is random? Even if the string is uniformly random, how do we know it does not leak private information to the trusted party? The very point of doing cryptography in the first place is to prevent us from trusting the wrong people with our secrets.
In this paper, we propose the more realistic multi-string model. Instead of having one trusted authority, we have several authorities that generate random strings. We do not trust any single authority, we only assume a majority of them generate the random string honestly. We demonstrate the use of this model for two fundamental cryptographic taks. We define non-interactive zero-knowledge in the multi-string model and construct NIZK proofs in the multi-string model. We also consider multi-party computation and show that any functionality can be securely realized in the multi-string model.

2005

EPRINT

A Verifiable Secret Shuffle of Homomorphic Encryptions
Abstract

We suggest an honest verifier zero-knowledge argument for the correctness of a shuffle of homomorphic encryptions. A shuffle consists of a rearrangement of the input ciphertexts and a re-encryption of them. One application of shuffles is to build mix-nets.
Our scheme is more efficient than previous schemes in terms of both communication and computational complexity. Indeed, the HVZK argument has a size that is independent of the actual cryptosystem being used and will typically be smaller than the size of the shuffle itself. Moreover, our scheme is well suited for the use of multi-exponentiation techniques and batch-verification.
Additionally, we suggest a more efficient honest verifier zero-knowledge argument for a commitment containing a permutation of a set of publicly known messages. We also suggest an honest verifier zero-knowledge argument for the correctness of a combined shuffle-and-decrypt operation that can be used in connection with decrypting mix-nets based on ElGamal encryption.
All our honest verifier zero-knowledge arguments can be turned into honest verifier zero-knowledge proofs. We use homomorphic commitments as an essential part of our schemes. When the commitment scheme is statistically hiding we obtain statistical honest verifier zero-knowledge arguments, when the commitment scheme is statistically binding we obtain computational honest verifier zero-knowledge proofs.

2005

EPRINT

Perfect Non-Interactive Zero Knowledge for NP
Abstract

Non-interactive zero-knowledge (NIZK) systems are fundamental cryptographic primitives used in many constructions, including CCA2-secure cryptosystems, digital signatures, and various cryptographic protocols. What makes them especially attractive, is that they work equally well in a concurrent setting, which is notoriously hard for interactive zero-knowledge protocols. However, while for interactive zero-knowledge we know how to construct statistical zero-knowledge argument systems for all NP languages, for non-interactive zero-knowledge, this problem remained open since the inception of NIZK in the late 1980's. Here we resolve two problems regarding NIZK:
- we construct the first perfect NIZK argument system for any NP language.
- we construct the first UC-secure NIZK protocols for any NP language in the presence of a dynamic/adaptive adversary.
While it was already known how to construct efficient prover computational NIZK proofs for any NP language, the known techniques yield large common reference strings and large NIZK proofs. As an additional implication of our techniques, we considerably reduce both the size of the common reference string and the size of the proofs.

2003

EPRINT

Non-interactive and Reusable Non-malleable Commitment Schemes
Abstract

We consider non-malleable (NM) and universally composable (UC)
commitmentschemes in the common reference string (CRS) model.
We show how to construct non-interac\-tive NM commitments that
remain non-malleable even if the adversary has access to an
arbitrary number of commitments from honest players - rather than
one, as in several previous schemes. We show this is a strictly
stronger security notion. Our construction is the first
non-interactive scheme achieving this that can be based
on the minimal assumption of existence of one-way
functions. But it can also be instantiated in a very efficient
version based on the strong RSA assumption. For UC commitments,
we show that existence of a UC commitment scheme in the CRS model
(interactive or not) implies key exchange and - for a uniform
reference string - even implies oblivious transfer. This indicates
that UC commitment is a strictly stronger primitive than NM. Finally,
we show that our strong RSA based construction can be used to improve
the most efficient known UC commitment scheme so it can work with
a CRS of size independent of the number of players, without loss of
efficiency.

2002

EPRINT

Evaluating Security of Voting Schemes in the Universal Composability Framework
Abstract

In the literature, voting protocols are considered secure if they satisfy requirements such as privacy, accuracy, robustness, etc. It can be time consuming to evaluate a voting protocol with respect to all these requirements and it is not clear that the list of known requirements is complete. Perhaps because of this many papers on electronic voting do not offer any security proof at all.
As a solution to this, we suggest evaluating voting schemes in the universal composability framework. We investigate the popular class of voting schemes based on homomorphic threshold encryption. It turns out that schemes in this class realize an ideal voting functionality that takes the votes as input and outputs the result. This ideal functionality corresponds closely to the well-known ballot box model used today in manual voting. Security properties such as privacy, accuracy and robustness now follow as easy corollaries. We note that some security requirements, for instance incoercibility, are not addressed by our solution.
Security holds in the random oracle model against a non-adaptive adversary. We show with a concrete example that the schemes are not secure against adaptive adversaries. We proceed to sketch how to make them secure against adaptive adversaries in the erasure model with virtually no loss of efficiency. We also sketch how to achieve security against adaptive adversaries in the erasure-free model.

#### Program Committees

- Asiacrypt 2018
- Eurocrypt 2018
- PKC 2017
- Asiacrypt 2016
- Crypto 2016
- Asiacrypt 2015
- Eurocrypt 2015
- TCC 2014
- PKC 2014
- Eurocrypt 2013
- PKC 2012
- Crypto 2012
- Eurocrypt 2012
- Asiacrypt 2011
- TCC 2010
- TCC 2009
- Asiacrypt 2009
- Crypto 2009
- TCC 2008
- PKC 2008
- Eurocrypt 2007

#### Coauthors

- Masayuki Abe (9)
- Carsten Baum (1)
- Stephanie Bayer (3)
- Jonathan Bootle (6)
- Andrea Cerulli (5)
- Pyrros Chaidos (3)
- Ivan Damgård (1)
- George Danezis (1)
- Rafael del Pino (1)
- Alex Escala (1)
- Cédric Fournet (1)
- Georg Fuchsbauer (2)
- Craig Gentry (1)
- Essam Ghadafi (3)
- Mohammad Hajiabadi (1)
- Kristiyan Haralambiev (3)
- Yuval Ishai (2)
- Sune K. Jakobsen (1)
- Sune Jakobsen (1)
- Aggelos Kiayias (1)
- Markulf Kohlweiss (3)
- Helger Lipmaa (1)
- Steve Lu (2)
- Vadim Lyubashevsky (1)
- Mary Maller (3)
- Sarah Meiklejohn (1)
- Ian Miers (1)
- Miyako Ohkubo (9)
- Rafail Ostrovsky (6)
- Chris Peikert (1)
- Christophe Petit (2)
- Amit Sahai (6)
- Adam Smith (1)
- Takeya Tango (1)
- Mehdi Tibouchi (4)