## CryptoDB

### Jens Groth

#### Publications

**Year**

**Venue**

**Title**

2022

EUROCRYPT

On the security of ECDSA with additive key derivation and presignatures
📺
Abstract

Two common variations of ECDSA signatures are {\em additive key derivation}
and presignatures.
Additive key derivation is a simple mechanism for deriving many subkeys from a single master key, and is already widely used in cryptocurrency applications with the Hierarchical Deterministic Wallet mechanism standardized in Bitcoin Improvement Proposal 32 (BIP32).
Because of its linear nature, additive key derivation is also amenable to efficient implementation in the threshold setting.
With presignatures, the secret and public nonces used in the ECDSA signing algorithm are precomputed.
In the threshold setting, using presignatures along with other precomputed data allows for an extremely efficient "online phase" of the protocol.
Recent works have advocated for both of these variations, sometimes combined together.
However, somewhat surprisingly, we are aware of no prior security proof for additive key derivation, let alone for additive key derivation in combination with presignatures.
In this paper, we provide a thorough analysis of these variations, both in isolation and in combination.
Our analysis is in the generic group model (GGM).
Importantly, we do not modify ECDSA or weaken the standard notion of security in any way.
Of independent interest, we also present a version of the GGM that is specific to elliptic curves.
This EC-GGM better models some of the idiosyncrasies (such as the conversion function and malleability) of ECDSA.
In addition to this analysis, we report security weaknesses in these variations that apparently have not been previously reported.
For example, we show that when both variations are combined, there is a cube-root attack on ECDSA, which is much faster than the best known, square-root attack on plain ECDSA.
We also present two mitigations against these weaknesses: re-randomized presignatures and homogeneous key derivation.
Each of these mitigations is very lightweight, and when used in combination, the security is essentially the same as that of plain ECDSA (in the EC-GGM).

2020

TCC

Linear-Time Arguments with Sublinear Verification from Tensor Codes
📺
Abstract

Minimizing the computational cost of the prover is a central goal in the area of succinct arguments. In particular, it remains a challenging open problem to construct a succinct argument where the prover runs in linear time and the verifier runs in polylogarithmic time.
We make progress towards this goal by presenting a new linear-time probabilistic proof. For any fixed ? > 0, we construct an interactive oracle proof (IOP) that, when used for the satisfiability of an N-gate arithmetic circuit, has a prover that uses O(N) field operations and a verifier that uses O(N^?) field operations. The sublinear verifier time is achieved in the holographic setting for every circuit (the verifier has oracle access to a linear-size encoding of the circuit that is computable in linear time).
When combined with a linear-time collision-resistant hash function, our IOP immediately leads to an argument system where the prover performs O(N) field operations and hash computations, and the verifier performs O(N^?) field operations and hash computations (given a short digest of the N-gate circuit).

2020

JOFC

Foundations of Fully Dynamic Group Signatures
Abstract

Group signatures allow members of a group to anonymously sign on behalf of the group. Membership is administered by a designated group manager. The group manager can also reveal the identity of a signer if and when needed to enforce accountability and deter abuse. For group signatures to be applicable in practice, they need to support fully dynamic groups, i.e., users may join and leave at any time. Existing security definitions for fully dynamic group signatures are informal, have shortcomings, and are mutually incompatible. We fill the gap by providing a formal rigorous security model for fully dynamic group signatures. Our model is general and is not tailored toward a specific design paradigm and can therefore, as we show, be used to argue about the security of different existing constructions following different design paradigms. Our definitions are stringent and when possible incorporate protection against maliciously chosen keys. We consider both the case where the group management and tracing signatures are administered by the same authority, i.e., a single group manager, and also the case where those roles are administered by two separate authorities, i.e., a group manager and an opening authority. We also show that a specialization of our model captures existing models for static and partially dynamic schemes. In the process, we identify a subtle gap in the security achieved by group signatures using revocation lists. We show that in such schemes new members achieve a slightly weaker notion of traceability. The flexibility of our security model allows to capture such relaxation of traceability.

2019

JOFC

Efficient Fully Structure-Preserving Signatures and Shrinking Commitments
Abstract

In structure-preserving signatures, public keys, messages, and signatures are all collections of source group elements of some bilinear groups. In this paper, we introduce fully structure-preserving signature schemes, with the additional requirement that even secret keys are group elements. This strong property allows efficient non-interactive proofs of knowledge of the secret key, which is useful in designing cryptographic protocols under simulation-based security where online extraction of the secret key is needed. We present efficient constructions under simple standard assumptions and pursue even more efficient constructions with the extra property of randomizability based on the generic bilinear group model. An essential building block for our efficient standard model construction is a shrinking structure-preserving trapdoor commitment scheme, which is by itself an important primitive and of independent interest as it appears to contradict a known impossibility result that structure-preserving commitments cannot be shrinking. We argue that a relaxed binding property lets us circumvent the impossibility while still retaining the usefulness of the primitive in important applications as mentioned above.

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

2006

ASIACRYPT

#### 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 (8)
- Carsten Baum (1)
- Stephanie Bayer (2)
- Jonathan Bootle (7)
- Andrea Cerulli (5)
- Pyrros Chaidos (3)
- Alessandro Chiesa (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 (4)
- Helger Lipmaa (1)
- Steve Lu (2)
- Vadim Lyubashevsky (1)
- Mary Maller (3)
- Sarah Meiklejohn (1)
- Ian Miers (1)
- Miyako Ohkubo (8)
- Rafail Ostrovsky (4)
- Chris Peikert (1)
- Christophe Petit (1)
- Amit Sahai (4)
- Victor Shoup (1)
- Adam Smith (1)
- Takeya Tango (1)
- Mehdi Tibouchi (3)