## CryptoDB

### Georg Fuchsbauer

#### Affiliation: Rennes University, FR

#### Publications

**Year**

**Venue**

**Title**

2019

PKC

Adaptively Secure Proxy Re-encryption
Abstract

A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key
$$pk'$$
. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under
$$pk'$$
without having to know the underlying message, while transformations from
$$pk'$$
to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.All existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in , rendering the result meaningless already for moderate .Jafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.Our results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).

2019

EUROCRYPT

Aggregate Cash Systems: A Cryptographic Investigation of Mimblewimble
📺
Abstract

Mimblewimble is an electronic cash system proposed by an anonymous author in 2016. It combines several privacy-enhancing techniques initially envisioned for Bitcoin, such as Confidential Transactions (Maxwell, 2015), non-interactive merging of transactions (Saxena, Misra, Dhar, 2014), and cut-through of transaction inputs and outputs (Maxwell, 2013). As a remarkable consequence, coins can be deleted once they have been spent while maintaining public verifiability of the ledger, which is not possible in Bitcoin. This results in tremendous space savings for the ledger and efficiency gains for new users, who must verify their view of the system.In this paper, we provide a provable-security analysis for Mimblewimble. We give a precise syntax and formal security definitions for an abstraction of Mimblewimble that we call an aggregate cash system. We then formally prove the security of Mimblewimble in this definitional framework. Our results imply in particular that two natural instantiations (with Pedersen commitments and Schnorr or BLS signatures) are provably secure against inflation and coin theft under standard assumptions.

2018

CRYPTO

The Algebraic Group Model and its Applications
📺
Abstract

One of the most important and successful tools for assessing hardness assumptions in cryptography is the Generic Group Model (GGM). Over the past two decades, numerous assumptions and protocols have been analyzed within this model. While a proof in the GGM can certainly provide some measure of confidence in an assumption, its scope is rather limited since it does not capture group-specific algorithms that make use of the representation of the group.To overcome this limitation, we propose the Algebraic Group Model (AGM), a model that lies in between the Standard Model and the GGM. It is the first restricted model of computation covering group-specific algorithms yet allowing to derive simple and meaningful security statements. To prove its usefulness, we show that several important assumptions, among them the Computational Diffie-Hellman, the Strong Diffie-Hellman, and the interactive LRSW assumptions, are equivalent to the Discrete Logarithm (DLog) assumption in the AGM. On the more practical side, we prove tight security reductions for two important schemes in the AGM to DLog or a variant thereof: the BLS signature scheme and Groth’s zero-knowledge SNARK (EUROCRYPT 2016), which is the most efficient SNARK for which only a proof in the GGM was known. Our proofs are quite simple and therefore less prone to subtle errors than those in the GGM.Moreover, in combination with known lower bounds on the Discrete Logarithm assumption in the GGM, our results can be used to derive lower bounds for all the above-mentioned results in the GGM.

2018

PKC

Subversion-Zero-Knowledge SNARKs
Abstract

Subversion zero knowledge for non-interactive proof systems demands that zero knowledge (ZK) be maintained even when the common reference string (CRS) is chosen maliciously. SNARKs are proof systems with succinct proofs, which are at the core of the cryptocurrency Zcash, whose anonymity relies on ZK-SNARKs; they are also used for ZK contingent payments in Bitcoin.We show that under a plausible hardness assumption, the most efficient SNARK schemes proposed in the literature, including the one underlying Zcash and contingent payments, satisfy subversion ZK or can be made to at very little cost. In particular, we prove subversion ZK of the original SNARKs by Gennaro et al. and the almost optimal construction by Groth; for the Pinocchio scheme implemented in libsnark we show that it suffices to add 4 group elements to the CRS. We also argue informally that Zcash is anonymous even if its parameters were set up maliciously.

2018

PKC

Weakly Secure Equivalence-Class Signatures from Standard Assumptions
Abstract

Structure-preserving signatures on equivalence classes, or equivalence-class signatures for short (EQS), are signature schemes defined over bilinear groups whose messages are vectors of group elements. Signatures are perfectly randomizable and given a signature on a vector, anyone can derive a signature on any multiple of the vector; EQS thus sign projective equivalence classes. Applications of EQS include the first constant-size anonymous attribute-based credentials, efficient round-optimal blind signatures without random oracles and efficient access-control encryption.To date, the only existing instantiation of EQS is proven secure in the generic-group model. In this work we show that by relaxing the definition of unforgeability, which makes it efficiently verifiable, we can construct EQS from standard assumptions, namely the Matrix-Diffie-Hellman assumptions. We then show that our unforgeability notion is sufficient for most applications.

2010

EPRINT

Batch Groth-Sahai
Abstract

In 2008, Groth and Sahai proposed a general methodology for constructing non-interactive zero-knowledge (and witness-indistinguishable) proofs in bilinear groups. While avoiding expensive NP-reductions, these proof systems are still inefficient due to a number of pairing computations required for verification. We apply recent techniques of batch verification to the Groth-Sahai proof systems and manage to improve significantly the complexity of proof verification. We give explicit batch verification formulas for generic Groth-Sahai equations (whose cost is less than a tenth of the original) and also for specific popular protocols relying on their methodology (namely Groth's group signatures and Belenkiy-Chase-Kohlweiss-Lysyanskaya's P-signatures).

2010

EPRINT

Fair Blind Signatures without Random Oracles
Abstract

A fair blind signature is a blind signature with revocable anonymity and unlinkability, i.e., an authority can link an issuing session to the resulting signature and trace a signature to the user who requested it. In this paper we first revisit the security model for fair blind signatures given by Hufschmitt and Traor\'e in 2007. We then give the first practical fair blind signature scheme with a security proof in the standard model. Our scheme satisfies a stronger variant of the Hufschmitt-Traor\'e model.

2010

EPRINT

Commuting Signatures and Verifiable Encryption and an Application to Non-Interactively Delegatable Credentials
Abstract

Verifiable encryption allows to encrypt a signature and prove that the plaintext is valid. We introduce a new primitive called commuting signature that extends verifiable encryption in multiple ways: a signer can encrypt both signature and message and prove validity; more importantly, given a ciphertext, a signer can create a verifiably encrypted signature on the encrypted message; thus signing and encrypting commute. We instantiate commuting signatures using the proof system by Groth and Sahai (EUROCRYPT '08) and the automorphic signatures by Fuchsbauer (ePrint report 2009/320). As an application, we give an instantiation of delegatable anonymous credentials, a powerful primitive introduced by Belenkiy et al. (CRYPTO '09). Our instantiation is arguably simpler than theirs and it is the first to provide non-interactive issuing and delegation, which is a standard requirement for non-anonymous credentials. Moreover, the size of our credentials and the cost of verification are less than half of those of the only previous construction, and efficiency of issuing and delegation is increased even more significantly. All our constructions are proved secure in the standard model.

2008

EPRINT

Anonymous Consecutive Delegation of Signing Rights: Unifying Group and Proxy Signatures
Abstract

We define a general model for consecutive delegations of signing rights with the following properties: The delegatee actually signing and all intermediate delegators remain anonymous. As for group signatures, in case of misuse, a special authority can open signatures to reveal the chain of delegations and the signer's identity. The scheme satisfies a strong notion of non-frameability generalizing the one for dynamic group signatures. We give formal definitions of security and show them to be satisfiable by constructing an instantiation proven secure under general assumptions in the standard model. Our primitive is a proper generalization of both group signatures and proxy signatures and can be regarded as non-frameable dynamic hierarchical group signatures.

2008

EPRINT

Efficient Rational Secret Sharing in the Standard Communication Model
Abstract

We propose a new methodology for rational secret sharing leading to various instantiations that are simple and efficient in terms of computation, share size, and round complexity. Our protocols do not require physical assumptions or simultaneous channels, and can even be run over asynchronous, point-to-point networks.
Of additional interest, we propose new equilibrium notions for this setting (namely, computational versions of strict Nash equilibrium and stability with respect to trembles), show relations between them, and prove that our protocols satisfy them.

2008

EPRINT

Encrypting Proofs on Pairings and Its Application to Anonymity for Signatures
Abstract

We give a generic methodology to unlinkably anonymize cryptographic schemes in bilinear groups using the Boneh-Goh-Nissim cryptosystem and NIZK proofs in the line of Groth, Ostrovsky and Sahai.
We illustrate our techniques by presenting the first instantiation of anonymous proxy signatures, a recent primitive unifying the functionalities and strong security notions of group and proxy signatures. To construct our scheme, we introduce various efficient NIZK and witness-indistinguishable proofs, and a relaxed version of simulation soundness.

#### Program Committees

- Crypto 2018
- Eurocrypt 2018
- PKC 2017
- Asiacrypt 2017
- Eurocrypt 2016
- Asiacrypt 2016
- PKC 2015
- PKC 2012

#### Coauthors

- Masayuki Abe (2)
- Hamza Abusalah (1)
- Joël Alwen (1)
- Foteini Baldimtsi (1)
- Abhishek Banerjee (2)
- Mihir Bellare (2)
- Olivier Blazy (2)
- Melissa Chase (1)
- Véronique Cortier (1)
- Dana Dachman-Soled (1)
- David Galindo (1)
- Romain Gay (2)
- Peter Gaži (1)
- Jens Groth (2)
- Christian Hanser (2)
- Kristiyan Haralambiev (2)
- Felix Heuer (1)
- Malika Izabachène (1)
- Zahra Jafargholi (1)
- Amandine Jambert (1)
- Chethan Kamath (1)
- Jonathan Katz (2)
- Eike Kiltz (2)
- Karen Klein (1)
- Markulf Kohlweiss (1)
- Momchil Konstantinov (2)
- Lucas Kowalczyk (1)
- Albert Kwon (1)
- Éric Levieil (1)
- Julian Loss (1)
- Payman Mohassel (1)
- David Naccache (2)
- Adam O'Neill (1)
- Miyako Ohkubo (2)
- Claudio Orlandi (1)
- Michele Orrù (1)
- Sunoo Park (1)
- Chris Peikert (2)
- Krzysztof Pietrzak (9)
- David Pointcheval (3)
- Vanishree Rao (2)
- Alessandra Scafuro (1)
- Yannick Seurin (1)
- Hervé Sibert (1)
- Daniel Slamanig (2)
- Sophie Stevens (2)
- Damien Vergnaud (3)