## CryptoDB

### Dennis Hofheinz

#### Publications

**Year**

**Venue**

**Title**

2022

TCC

The Price of Verifiability: Lower Bounds for Verifiable Random Functions
Abstract

Verifiable random functions (VRFs) are a useful extension of pseudorandom functions for which it is possible to generate a proof that a certain image is indeed the correct function value (relative to a public verification key). Due to their strong soundness requirements on such proofs, VRFs are notoriously hard to construct, and existing constructions suffer either from complex proofs (for function images), or rely on complex and non-standard assumptions.
In this work, we attempt to explain this phenomenon. We show that for a large class of pairing-based VRFs, it is not possible to obtain short proofs and a reduction to a simple assumption simultaneously. Since the class of "consecutively verifiable" VRFs we consider contains in particular the VRF of Lysyanskaya and that of Dodis-Yampolskiy, our results explain the large proof size, resp. the complex assumption of these VRFs.

2021

ASIACRYPT

Onion Routing with Replies
📺
Abstract

Onion routing (OR) protocols are a crucial tool for providing anonymous internet communication. An OR protocol enables a user to anonymously send requests to a server. A fundamental problem of OR protocols is how to deal with replies: ideally, we would want the server to be able to send a reply back to the anonymous user without knowing or disclosing the user's identity.
Existing OR protocols do allow for such replies, but do not provably protect the payload (i.e., message) of replies against manipulation. Kuhn et al. (IEEE S&P 2020) show that such manipulations can in fact be leveraged to break anonymity of the whole protocol.
In this work, we close this gap and provide the first framework and protocols for OR with protected replies. We define security in the sense of an ideal functionality in the universal composability model, and provide corresponding (less complex) game-based security notions for the individual properties.
We also provide two secure instantiations of our framework: one based on updatable encryption, and one based on succinct non-interactive arguments (SNARGs) to authenticate payloads both in requests and replies. In both cases, our central technical handle is an implicit authentication of the transmitted payload data, as opposed to an explicit, but insufficient authentication (with MACs) in previous solutions. Our results exhibit a new and surprising application of updatable encryption outside of long-term data storage.

2021

TCC

On the Impossibility of Purely Algebraic Signatures
📺
Abstract

The existence of one-way functions implies secure digital sig- natures, but not public-key encryption (at least in a black-box setting). Somewhat surprisingly, though, efficient public-key encryption schemes appear to be much easier to construct from concrete algebraic assumptions (such as the factoring of Diffie-Hellman-like assumptions) than efficient digital signature schemes. In this work, we provide one reason for this apparent difficulty to construct efficient signature schemes. Specifically, we prove that a wide range of algebraic signature schemes (in which verification essentially checks a number of linear equations over a group) fall to conceptually surprisingly simple linear algebra attacks. In fact, we prove that in an algebraic signature scheme, sufficiently many signatures can be linearly combined to a signature of a fresh message. We present attacks both in known-order and hidden-order groups (although in hidden-order settings, we have to restrict our definition of algebraic signatures a little). More explicitly, we show:
– the insecurity of all algebraic signature schemes in Maurer’s generic group model, as long as the signature schemes do not rely on other cryptographic assumptions, such as hash functions.
– the insecurity of a natural class of signatures in hidden-order groups, where verification consists of linear equations over group elements.
We believe that this highlights the crucial role of public verifiability in digital signature schemes. Namely, while public-key encryption schemes do not require any publicly verifiable structure on ciphertexts, it is exactly this structure on signatures that invites attacks like ours and makes it hard to construct efficient signatures.

2021

TCC

Towards Tight Adaptive Security of Non-Interactive Key Exchange
📺
Abstract

We investigate the quality of security reductions for non-interactive key
exchange (NIKE) schemes. Unlike for many other cryptographic building blocks
(like public-key encryption, signatures, or zero-knowledge proofs), all known
NIKE security reductions to date are non-tight, i.e., lose a factor of at least
the number of users in the system. In that sense, NIKE forms a particularly
elusive target for tight security reductions.
The main technical obstacle in achieving tightly secure NIKE schemes are
adaptive corruptions. Hence, in this work, we explore security notions and
schemes that lie between selective security and fully adaptive security.
Concretely:
- We exhibit a tradeoff between key size and reduction loss.
We show that a tighter reduction can be bought by larger public and secret NIKE
keys. Concretely, we present a simple NIKE scheme with a reduction loss of
O(N^2 log(\nu)/\nu^2), and public and secret keys of O(\nu) group
elements, where N denotes the overall number of users in the system, and
\nu is a freely adjustable scheme parameter.
Our scheme achieves full adaptive security even against multiple "test
queries" (i.e., adversarial challenges), but requires keys of size O(N) to
achieve (almost) tight security under the matrix Diffie-Hellman assumption.
Still, already this simple scheme circumvents existing lower bounds.
- We show that this tradeoff is inherent.
We contrast the security of our simple scheme with a lower bound for all NIKE
schemes in which shared keys can be expressed as an ``inner product in the
exponent''. This result covers the original Diffie-Hellman NIKE scheme, as well
as a large class of its variants, and in particular our simple scheme. Our
lower bound gives a tradeoff between the ``dimension'' of any such scheme
(which directly corresponds to key sizes in existing schemes), and the
reduction quality. For \nu = O(N), this shows our simple scheme and reduction
optimal (up to a logarithmic factor).
- We exhibit a tradeoff between security and key size for tight reductions.
We show that it is possible to circumvent the inherent tradeoff above by
relaxing the desired security notion. Concretely, we consider the natural
notion of semi-adaptive security, where the adversary has to commit to a single
test query after seeing all public keys. As a feasibility result, we bring
forward the first scheme that enjoys compact public keys and tight
semi-adaptive security under the conjunction of the matrix Diffie-Hellman and
learning with errors assumptions.
We believe that our results shed a new light on the role of adaptivity in NIKE
security, and also illustrate the special role of NIKE when it comes to tight
security reductions.

2020

JOFC

Multilinear Maps from Obfuscation
Abstract

We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the $${\text {DDH}} $$ DDH assumption hold for them. Our first construction is symmetric and comes with a $$\kappa $$ κ -linear map $$\mathbf{e }: {{\mathbb {G}}}^\kappa \longrightarrow {\mathbb {G}}_T$$ e : G κ ⟶ G T for prime-order groups $${\mathbb {G}}$$ G and $${\mathbb {G}}_T$$ G T . To establish the hardness of the $$\kappa $$ κ -linear $${\text {DDH}} $$ DDH problem, we rely on the existence of a base group for which the $$\kappa $$ κ -strong $${\text {DDH}} $$ DDH assumption holds. Our second construction is for the asymmetric setting, where $$\mathbf{e }: {\mathbb {G}}_1 \times \cdots \times {\mathbb {G}}_{\kappa } \longrightarrow {\mathbb {G}}_T$$ e : G 1 × ⋯ × G κ ⟶ G T for a collection of $$\kappa +1$$ κ + 1 prime-order groups $${\mathbb {G}}_i$$ G i and $${\mathbb {G}}_T$$ G T , and relies only on the 1-strong $${\text {DDH}} $$ DDH assumption in its base group. In both constructions, the linearity $$\kappa $$ κ can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness-indistinguishability, and zero knowledge), and additively homomorphic encryption for the group $$\mathbb {Z}_N^{+}$$ Z N + . At a high level, we enable “bootstrapping” multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.

2020

EUROCRYPT

On Instantiating the Algebraic Group Model from Falsifiable Assumptions
📺
Abstract

We provide a standard-model implementation (of a relaxation) of the algebraic group model (AGM, [Fuchsbauer, Kiltz, Loss, CRYPTO 2018]). Specifically, we show that every algorithm that uses our group is algebraic, and hence "must know" a
representation of its output group elements in terms of its input group
elements. Here, "must know" means that a suitable extractor can extract such
a representation efficiently. We stress that our implementation relies only on
falsifiable assumptions in the standard model, and in particular does not use
any knowledge assumptions.
As a consequence, our group allows to transport a number of results obtained in
the AGM into the standard model, under falsifiable assumptions. For instance,
we show that in our group, several Diffie-Hellman-like assumptions (including
computational Diffie-Hellman) are equivalent to the discrete logarithm
assumption. Furthermore, we show that our group allows to prove the Schnorr
signature scheme tightly secure in the random oracle model.
Our construction relies on indistinguishability obfuscation, and hence should
not be considered as a practical group itself. However, our results show that
the AGM is a realistic computational model (since it can be instantiated in the
standard model), and that results obtained in the AGM are also possible with
standard-model groups.

2020

PKC

The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
📺
Abstract

We consider the problem of removing subexponential reductions to indistinguishability obfuscation (iO) in the context of obfuscating probabilistic programs. Specifically, we show how to apply complexity absorption (Zhandry Crypto 2016) to the recent notion of probabilistic indistinguishability obfuscation (piO, Canetti et al. TCC 2015). As a result, we obtain a variant of piO which allows to obfuscate a large class of probabilistic programs, from polynomially secure indistinguishability obfuscation and extremely lossy functions. Particularly, our piO variant is able to obfuscate circuits with specific input domains regardless of the performed computation. We then revisit several (direct or indirect) applications of piO, and obtain – a fully homomorphic encryption scheme (without circular security assumptions), – a multi-key fully homomorphic encryption scheme with threshold decryption, – an encryption scheme secure under arbitrary key-dependent messages, – a spooky encryption scheme for all circuits, – a function secret sharing scheme with additive reconstruction for all circuits, all from polynomially secure iO, extremely lossy functions, and, depending on the scheme, also other (but polynomial and comparatively mild) assumptions. All of these assumptions are implied by polynomially secure iO and the (non-polynomial, but very well-investigated) exponential DDH assumption. Previously, all the above applications required to assume the subexponential security of iO (and more standard assumptions).

2019

PKC

On Tightly Secure Primitives in the Multi-instance Setting
Abstract

We initiate the study of general tight reductions in cryptography. There already exist a variety of works that offer tight reductions for a number of cryptographic tasks, ranging from encryption and signature schemes to proof systems. However, our work is the first to provide a universal definition of a tight reduction (for arbitrary primitives), along with several observations and results concerning primitives for which tight reductions have not been known.Technically, we start from the general notion of reductions due to Reingold, Trevisan, and Vadhan (TCC 2004), and equip it with a quantification of the respective reduction loss, and a canonical multi-instance extension to primitives. We then revisit several standard reductions whose tight security has not yet been considered. For instance, we revisit a generic construction of signature schemes from one-way functions, and show how to tighten the corresponding reduction by assuming collision-resistance from the used one-way function. We also obtain tightly secure pseudorandom generators (by using suitable rerandomisable hard-core predicates), and tightly secure lossy trapdoor functions.

2019

EUROCRYPT

Designated-Verifier Pseudorandom Generators, and Their Applications
📺
Abstract

We provide a generic construction of non-interactive zero-knowledge (NIZK) schemes. Our construction is a refinement of Dwork and Naor’s (FOCS 2000) implementation of the hidden bits model using verifiable pseudorandom generators (VPRGs). Our refinement simplifies their construction and relaxes the necessary assumptions considerably.As a result of this conceptual improvement, we obtain interesting new instantiations:A designated-verifier NIZK (with unbounded soundness) based on the computational Diffie-Hellman (CDH) problem. If a pairing is available, this NIZK becomes publicly verifiable. This constitutes the first fully secure CDH-based designated-verifier NIZKs (and more generally, the first fully secure designated-verifier NIZK from a non-generic assumption which does not already imply publicly-verifiable NIZKs), and it answers an open problem recently raised by Kim and Wu (CRYPTO 2018).A NIZK based on the learning with errors (LWE) assumption, and assuming a non-interactive witness-indistinguishable (NIWI) proof system for bounded distance decoding (BDD). This simplifies and improves upon a recent NIZK from LWE that assumes a NIZK for BDD (Rothblum et al., PKC 2019).

2019

ASIACRYPT

Dual-Mode NIZKs from Obfuscation
Abstract

Two standard security properties of a non-interactive zero-knowledge (NIZK) scheme are soundness and zero-knowledge. But while standard NIZK systems can only provide one of those properties against unbounded adversaries, dual-mode NIZK systems allow to choose dynamically and adaptively which of these properties holds unconditionally. The only known dual-mode NIZK schemes are Groth-Sahai proofs (which have proved extremely useful in a variety of applications), and the FHE-based NIZK constructions of Canetti et al. and Peikert et al, which are concurrent and independent to this work. However, all these constructions rely on specific algebraic settings.Here, we provide a generic construction of dual-mode NIZK systems for all of NP. The public parameters of our scheme can be set up in one of two indistinguishable ways. One way provides unconditional soundness, while the other provides unconditional zero-knowledge. Our scheme relies on subexponentially secure indistinguishability obfuscation and subexponentially secure one-way functions, but otherwise only on comparatively mild and generic computational assumptions. These generic assumptions can be instantiated under any one of the DDH, $$k$$-LIN, DCR, or QR assumptions.As an application, we reduce the required assumptions necessary for several recent obfuscation-based constructions of multilinear maps. Combined with previous work, our scheme can be used to construct multilinear maps from obfuscation and a group in which the strong Diffie-Hellman assumption holds. We also believe that our work adds to the understanding of the construction of NIZK systems, as it provides a conceptually new way to achieve dual-mode properties.

2018

CRYPTO

On Tightly Secure Non-Interactive Key Exchange
📺
Abstract

We consider the reduction loss of security reductions for non-interactive key exchange (NIKE) schemes. Currently, no tightly secure NIKE schemes exist, and in fact Bader et al. (EUROCRYPT 2016) provide a lower bound (of $$\varOmega (n^2)$$, where $$n$$ is the number of parties an adversary interacts with) on the reduction loss for a large class of NIKE schemes.We offer two results: the first NIKE scheme with a reduction loss of $$n/2$$ that circumvents the lower bound of Bader et al., but is of course still far from tightly secure. Second, we provide a generalization of Bader et al.’s lower bound to a larger class of NIKE schemes (that also covers our NIKE scheme), with an adapted lower bound of $$n/2$$ on the reduction loss. Hence, in that sense, the reduction for our NIKE scheme is optimal.

2018

PKC

Interactively Secure Groups from Obfuscation
Abstract

We construct a mathematical group in which an interactive variant of the very general Uber assumption holds. Our construction uses probabilistic indistinguishability obfuscation, fully homomorphic encryption, and a pairing-friendly group in which a mild and standard computational assumption holds. While our construction is not practical, it constitutes a feasibility result that shows that under a strong but generic, and a mild assumption, groups exist in which very general computational assumptions hold. We believe that this grants additional credibility to the Uber assumption.

2018

ASIACRYPT

Identity-Based Encryption Tightly Secure Under Chosen-Ciphertext Attacks
Abstract

We propose the first identity-based encryption (IBE) scheme that is (almost) tightly secure against chosen-ciphertext attacks. Our scheme is efficient, in the sense that its ciphertext overhead is only seven group elements, three group elements more than that of the state-of-the-art passively (almost) tightly secure IBE scheme. Our scheme is secure in a multi-challenge setting, i.e., in face of an arbitrary number of challenge ciphertexts. The security of our scheme is based upon the standard symmetric external Diffie-Hellman assumption in pairing-friendly groups, but we also consider (less efficient) generalizations under weaker assumptions.

2018

PKC

Graded Encoding Schemes from Obfuscation
Abstract

We construct a graded encoding scheme (GES), an approximate form of graded multilinear maps. Our construction relies on indistinguishability obfuscation, and a pairing-friendly group in which (a suitable variant of) the strong Diffie–Hellman assumption holds. As a result of this abstract approach, our GES has a number of advantages over previous constructions. Most importantly:
We can prove that the multilinear decisional Diffie–Hellman (MDDH) assumption holds in our setting, assuming the used ingredients are secure (in a well-defined and standard sense). Hence, our GES does not succumb to so-called “zeroizing” attacks if the underlying ingredients are secure.Encodings in our GES do not carry any noise. Thus, unlike previous GES constructions, there is no upper bound on the number of operations one can perform with our encodings. Hence, our GES essentially realizes what Garg et al. (EUROCRYPT 2013) call the “dream version” of a GES.
Technically, our scheme extends a previous, non-graded approximate multilinear map scheme due to Albrecht et al. (TCC 2016-A). To introduce a graded structure, we develop a new view of encodings at different levels as polynomials of different degrees.

2016

TCC

2015

JOFC

2013

JOFC

Polynomial Runtime and Composability
Abstract

We devise a notion of polynomial runtime suitable for the simulation-based security analysis of multi-party cryptographic protocols. Somewhat surprisingly, straightforward notions of polynomial runtime lack expressivity for reactive tasks and/or lead to an unnatural simulation-based security notion. Indeed, the problem has been recognized in previous works, and several notions of polynomial runtime have already been proposed. However, our new notion, dubbed reactive polynomial time, is the first to combine the following properties: it is simple enough to support simple security/runtime analyses,it is intuitive in the sense that all intuitively feasible protocols and attacks (and only those) are considered polynomial-time,it supports secure composition of protocols in the sense of a universal composition theorem. We work in the Universal Composability (UC) protocol framework. We remark that while the UC framework already features a universal composition theorem, we develop new techniques to prove secure composition in the case of reactively polynomial-time protocols and attacks.

2012

JOFC

Bonsai Trees, or How to Delegate a Lattice Basis
Abstract

We introduce a new lattice-based cryptographic structure called a bonsai tree, and use it to resolve some important open problems in the area. Applications of bonsai trees include an efficient, stateless ‘hash-and-sign’ signature scheme in the standard model (i.e., no random oracles), and the first hierarchical identity-based encryption (HIBE) scheme (also in the standard model) that does not rely on bilinear pairings. Interestingly, the abstract properties of bonsai trees seem to have no known realization in conventional number-theoretic cryptography.

2012

JOFC

Programmable Hash Functions and Their Applications
Abstract

We introduce a new combinatorial primitive called programmable hash functions (PHFs). PHFs can be used to program the output of a hash function such that it contains solved or unsolved discrete logarithm instances with a certain probability. This is a technique originally used for security proofs in the random oracle model. We give a variety of standard model realizations of PHFs (with different parameters).The programmability makes PHFs a suitable tool to obtain black-box proofs of cryptographic protocols when considering adaptive attacks. We propose generic digital signature schemes from the strong RSA problem and from some hardness assumption on bilinear maps that can be instantiated with any PHF. Our schemes offer various improvements over known constructions. In particular, for a reasonable choice of parameters, we obtain short standard model digital signatures over bilinear maps.

2009

EUROCRYPT

#### Program Committees

- Crypto 2021
- TCC 2019
- TCC 2019 (Program chair)
- Eurocrypt 2018
- PKC 2017
- Crypto 2017
- Eurocrypt 2016
- TCC 2015
- TCC 2014
- Crypto 2013
- Eurocrypt 2012
- TCC 2012
- Asiacrypt 2011
- Asiacrypt 2010
- TCC 2008

#### Coauthors

- Masayuki Abe (1)
- Thomas Agrikola (3)
- Martin R. Albrecht (2)
- Christoph Bader (1)
- Boaz Barak (1)
- Mihir Bellare (2)
- Florian Böhl (4)
- Nicholas Brandt (1)
- David Cash (2)
- Geoffroy Couteau (2)
- Ronald Cramer (2)
- Gareth T. Davies (1)
- Nico Döttling (1)
- Pooya Farshim (3)
- Serge Fehr (1)
- Eduarda S.V. Freire (2)
- Romain Gay (3)
- Iftach Haitner (1)
- Shuai Han (1)
- Goichiro Hanaoka (1)
- Dominik Hartmann (1)
- Gottfried Herold (1)
- Julia Hesse (5)
- Kathrin Hövelmanns (1)
- Hideki Imai (1)
- Yuval Ishai (1)
- Tibor Jager (9)
- Dingding Jia (1)
- Julia Kastner (2)
- Dakshita Khurana (1)
- Eike Kiltz (17)
- Edward Knapp (1)
- Jessica Koch (3)
- Lisa Kohl (4)
- Daniel Kraschewski (1)
- Christiane Kuhn (1)
- Roman Langrehr (1)
- Enrique Larraia (3)
- Yong Li (1)
- John Malone-Lee (2)
- Christian Matt (1)
- Ueli Maurer (1)
- Jörn Müller-Quade (3)
- Ngoc Khanh Nguyen (1)
- Ryo Nishimaki (1)
- Miyako Ohkubo (1)
- Jiaxin Pan (3)
- Rafael Pass (1)
- Kenneth G. Paterson (4)
- Chris Peikert (2)
- Carla Ràfols (1)
- Vanishree Rao (1)
- Andy Rupp (5)
- Amit Sahai (1)
- Sven Schäge (1)
- Jae Hong Seo (1)
- Abhi Shelat (1)
- Victor Shoup (1)
- Martijn Stam (2)
- Rainer Steinwandt (1)
- Christoph Striecks (4)
- Thorsten Strufe (1)
- Akin Ünal (1)
- Dominique Unruh (4)
- Bogdan Ursu (2)
- Vinod Vaikuntanathan (1)
- Brent Waters (1)
- Hoeteck Wee (2)
- Daniel Wichs (1)
- Scott Yilek (1)
- Mark Zhandry (1)