## CryptoDB

### Dan Boneh

#### Affiliation: Stanford University

#### Publications

**Year**

**Venue**

**Title**

2020

ASIACRYPT

Improving Speed and Security in Updatable Encryption Schemes
📺
Abstract

Periodic key rotation is a common practice designed to limit the long-term power of cryptographic keys. Key rotation refers to the process of re-encrypting encrypted content under a fresh key, and overwriting the old ciphertext with the new one. When encrypted data is stored in the cloud, key rotation can be very costly: it may require downloading the entire encrypted content from the cloud, re-encrypting it on the client's machine, and uploading the new ciphertext back to the cloud.
An updatable encryption scheme is a symmetric-key encryption scheme designed to support efficient key rotation in the cloud. The data owner sends a short update token to the cloud. This update token lets the cloud rotate the ciphertext from the old key to the new key, without learning any information about the plaintext. Recent work on updatable encryption has led to several security definitions and proposed constructions. However, existing constructions are not yet efficient enough for practical adoption, and the existing security definitions can be strengthened.
In this work we make three contributions. First, we introduce stronger security definitions for updatable encryption (in the ciphertext-dependent setting) that capture desirable security properties not covered in prior work. Second, we construct two new updatable encryption schemes. The first construction relies only on symmetric cryptographic primitives, but only supports a bounded number of key rotations. The second construction supports a (nearly) unbounded number of updates, and is built from the Ring Learning with Errors (RLWE) assumption. Due to complexities of using RLWE, this scheme achieves a slightly weaker notion of integrity compared to the first. Finally, we implement both constructions and compare their performance to prior work. Our RLWE-based construction is 200x faster than a prior proposal for an updatable encryption scheme based on the hardness of elliptic curve DDH. Our first construction, based entirely on symmetric primitives, has the highest encryption throughput, approaching the performance of AES, and the highest decryption throughput on ciphertexts that were re-encrypted fewer than fifty times. For ciphertexts re-encrypted over fifty times, the RLWE construction dominates it in decryption speed.

2020

ASIACRYPT

Oblivious Pseudorandom Functions from Isogenies
📺
Abstract

An oblivious PRF, or OPRF, is a protocol between a client and a server, where the server has a key $k$ for a secure pseudorandom function $F$, and the client has an input $x$ for the function. At the end of the protocol the client learns $F(k,x)$, and nothing else, and the server learns nothing. An OPRF is verifiable if the client is convinced that the server has evaluated the PRF correctly with respect to a prior commitment to $k$. OPRFs and verifiable OPRFs have numerous applications, such as private-set-intersection protocols, password-based key-exchange protocols, and defense against denial-of-service attacks. Existing OPRF constructions use RSA-, Diffie-Hellman-, and lattice-type assumptions. The first two are not post-quantum secure.
In this paper we construct OPRFs and verifiable OPRFs from isogenies. Our main construction uses isogenies of supersingular elliptic curves over $\Fpp$ and tries to adapt the Diffie-Hellman OPRF to that setting. However, a recent attack on supersingular-isogeny
systems due to Galbraith~et~al.~[ASIACRYPT 2016] makes this approach difficult to secure. To overcome this attack, and to validate the server's response, we develop two new zero-knowledge protocols that convince each party that its peer has sent valid messages. With these protocols in place, we obtain an OPRF in the SIDH setting and prove its security in the UC framework.
Our second construction is an adaptation of the Naor-Reingold PRF to commutative group actions. Combining it with recent constructions of oblivious transfer from isogenies, we obtain an OPRF in the CSIDH setting.

2019

TCHES

Fast and simple constant-time hashing to the BLS12-381 elliptic curve
📺
Abstract

Pairing-friendly elliptic curves in the Barreto-Lynn-Scott family are seeing a resurgence in popularity because of the recent result of Kim and Barbulescu that improves attacks against other pairing-friendly curve families. One particular Barreto-Lynn-Scott curve, called BLS12-381, is the locus of significant development and deployment effort, especially in blockchain applications. This effort has sparked interest in using the BLS12-381 curve for BLS signatures, which requires hashing to one of the groups of the bilinear pairing defined by BLS12-381.While there is a substantial body of literature on the problem of hashing to elliptic curves, much of this work does not apply to Barreto-Lynn-Scott curves. Moreover, the work that does apply has the unfortunate property that fast implementations are complex, while simple implementations are slow.In this work, we address these issues. First, we show a straightforward way of adapting the “simplified SWU” map of Brier et al. to BLS12-381. Second, we describe optimizations to this map that both simplify its implementation and improve its performance; these optimizations may be of interest in other contexts. Third, we implement and evaluate. We find that our work yields constant-time hash functions that are simple to implement, yet perform within 9% of the fastest, non–constant-time alternatives, which require much more complex implementations.

2019

CRYPTO

Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains
📺
Abstract

We present batching techniques for cryptographic accumulators and vector commitments in groups of unknown order. Our techniques are tailored for distributed settings where no trusted accumulator manager exists and updates to the accumulator are processed in batches. We develop techniques for non-interactively aggregating membership proofs that can be verified with a constant number of group operations. We also provide a constant sized batch non-membership proof for a large number of elements. These proofs can be used to build the first positional vector commitment (VC) with constant sized openings and constant sized public parameters. As a core building block for our batching techniques we develop several succinct proof systems in groups of unknown order. These extend a recent construction of a succinct proof of correct exponentiation, and include a succinct proof of knowledge of an integer discrete logarithm between two group elements. We circumvent an impossibility result for Sigma-protocols in these groups by using a short trapdoor-free CRS. We use these new accumulator and vector commitment constructions to design a stateless blockchain, where nodes only need a constant amount of storage in order to participate in consensus. Further, we show how to use these techniques to reduce the size of IOP instantiations, such as STARKs. The full version of the paper is available online [BBF18b].

2019

CRYPTO

Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs
📺
Abstract

We introduce and study the notion of fully linear probabilistically checkable proof systems. In such a proof system, the verifier can make a small number of linear queries that apply jointly to the input and a proof vector.Our new type of proof system is motivated by applications in which the input statement is not fully available to any single verifier, but can still be efficiently accessed via linear queries. This situation arises in scenarios where the input is partitioned or secret-shared between two or more parties, or alternatively is encoded using an additively homomorphic encryption or commitment scheme. This setting appears in the context of secure messaging platforms, verifiable outsourced computation, PIR writing, private computation of aggregate statistics, and secure multiparty computation (MPC). In all these applications, there is a need for fully linear proof systems with short proofs.While several efficient constructions of fully linear proof systems are implicit in the interactive proofs literature, many questions about their complexity are open. We present several new constructions of fully linear zero-knowledge proof systems with sublinear proof size for “simple” or “structured” languages. For example, in the non-interactive setting of fully linear PCPs, we show how to prove that an input vector $$x\in {\mathbb {F}}^n$$, for a finite field $${\mathbb {F}}$$, satisfies a single degree-2 equation with a proof of size $$O(\sqrt{n})$$ and $$O(\sqrt{n})$$ linear queries, which we show to be optimal. More generally, for languages that can be recognized by systems of constant-degree equations, we can reduce the proof size to $$O(\log n)$$ at the cost of $$O(\log n)$$ rounds of interaction.We use our new proof systems to construct new short zero-knowledge proofs on distributed and secret-shared data. These proofs can be used to improve the performance of the example systems mentioned above.Finally, we observe that zero-knowledge proofs on distributed data provide a general-purpose tool for protecting MPC protocols against malicious parties. Applying our short fully linear PCPs to “natural” MPC protocols in the honest-majority setting, we can achieve unconditional protection against malicious parties with sublinear additive communication cost. We use this to improve the communication complexity of recent honest-majority MPC protocols. For instance, using any pseudorandom generator, we obtain a 3-party protocol for Boolean circuits in which the amortized communication cost is only one bit per AND gate per party (compared to 10 bits in the best previous protocol), matching the best known protocols for semi-honest parties.

2018

CRYPTO

Threshold Cryptosystems from Threshold Fully Homomorphic Encryption
📺
Abstract

We develop a general approach to adding a threshold functionality to a large class of (non-threshold) cryptographic schemes. A threshold functionality enables a secret key to be split into a number of shares, so that only a threshold of parties can use the key, without reconstructing the key. We begin by constructing a threshold fully-homomorphic encryption scheme (ThFHE) from the learning with errors (LWE) problem. We next introduce a new concept, called a universal thresholdizer, from which many threshold systems are possible. We show how to construct a universal thresholdizer from our ThFHE. A universal thresholdizer can be used to add threshold functionality to many systems, such as CCA-secure public-key encryption (PKE), signature schemes, pseudorandom functions, and others primitives. In particular, by applying this paradigm to a (non-threshold) lattice signature system, we obtain the first single-round threshold signature scheme from LWE.

2018

CRYPTO

Verifiable Delay Functions
📺
Abstract

We study the problem of building a verifiable delay function (VDF). A $$\text {VDF}$$VDFrequires a specified number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified. $$\text {VDF}$$VDFs have many applications in decentralized systems, including public randomness beacons, leader election in consensus protocols, and proofs of replication. We formalize the requirements for $$\text {VDF}$$VDFs and present new candidate constructions that are the first to achieve an exponential gap between evaluation and verification time.

2018

TCC

Exploring Crypto Dark Matter:
Abstract

Pseudorandom functions (PRFs) are one of the fundamental building blocks in cryptography. Traditionally, there have been two main approaches for PRF design: the “practitioner’s approach” of building concretely-efficient constructions based on known heuristics and prior experience, and the “theoretician’s approach” of proposing constructions and reducing their security to a previously-studied hardness assumption. While both approaches have their merits, the resulting PRF candidates vary greatly in terms of concrete efficiency and design complexity.In this work, we depart from these traditional approaches by exploring a new space of plausible PRF candidates. Our guiding principle is to maximize simplicity while optimizing complexity measures that are relevant to cryptographic applications. Our primary focus is on weak PRFs computable by very simple circuits—specifically, depth-2$$\mathsf {ACC}^0$$ circuits. Concretely, our main weak PRF candidate is a “piecewise-linear” function that first applies a secret mod-2 linear mapping to the input, and then a public mod-3 linear mapping to the result. We also put forward a similar depth-3 strong PRF candidate.The advantage of our approach is twofold. On the theoretical side, the simplicity of our candidates enables us to draw many natural connections between their hardness and questions in complexity theory or learning theory (e.g., learnability of $$\mathsf {ACC}^0$$ and width-3 branching programs, interpolation and property testing for sparse polynomials, and new natural proof barriers for showing super-linear circuit lower bounds). On the applied side, the piecewise-linear structure of our candidates lends itself nicely to applications in secure multiparty computation (MPC). Using our PRF candidates, we construct protocols for distributed PRF evaluation that achieve better round complexity and/or communication complexity (often both) compared to protocols obtained by combining standard MPC protocols with PRFs like AES, LowMC, or Rasta (the latter two are specialized MPC-friendly PRFs).Finally, we introduce a new primitive we call an encoded-input PRF, which can be viewed as an interpolation between weak PRFs and standard (strong) PRFs. As we demonstrate, an encoded-input PRF can often be used as a drop-in replacement for a strong PRF, combining the efficiency benefits of weak PRFs and the security benefits of strong PRFs. We conclude by showing that our main weak PRF candidate can plausibly be boosted to an encoded-input PRF by leveraging standard error-correcting codes.

2018

ASIACRYPT

Compact Multi-signatures for Smaller Blockchains
Abstract

We construct new multi-signature schemes that provide new functionality. Our schemes are designed to reduce the size of the Bitcoin blockchain, but are useful in many other settings where multi-signatures are needed. All our constructions support both signature compression and public-key aggregation. Hence, to verify that a number of parties signed a common message m, the verifier only needs a short multi-signature, a short aggregation of their public keys, and the message m. We give new constructions that are derived from Schnorr signatures and from BLS signatures. Our constructions are in the plain public key model, meaning that users do not need to prove knowledge or possession of their secret key.In addition, we construct the first short accountable-subgroup multi-signature (ASM) scheme. An ASM scheme enables any subset $$ S $$ of a set of n parties to sign a message m so that a valid signature discloses which subset generated the signature (hence the subset $$ S $$ is accountable for signing m). We construct the first ASM scheme where signature size is only $$O(\kappa )$$ bits over the description of $$ S $$, where $$\kappa $$ is the security parameter. Similarly, the aggregate public key is only $$O(\kappa )$$ bits, independent of n. The signing process is non-interactive. Our ASM scheme is very practical and well suited for compressing the data needed to spend funds from a t-of-n Multisig Bitcoin address, for any (polynomial size) t and n.

2016

ASIACRYPT

2015

EUROCRYPT

2014

CRYPTO

2014

EUROCRYPT

2013

CRYPTO

2011

PKC

2010

EPRINT

Algebraic Pseudorandom Functions with Improved Efficiency from the Augmented Cascade
Abstract

We construct an algebraic pseudorandom function (PRF) that is more efficient than the classic Naor- Reingold algebraic PRF. Our PRF is the result of adapting the cascade construction, which is the basis of HMAC, to the algebraic settings. To do so we define an augmented cascade and prove it secure when the underlying PRF satisfies a property called parallel security. We then use the augmented cascade to build new algebraic PRFs. The algebraic structure of our PRF leads to an efficient large-domain Verifiable Random Function (VRF) and a large-domain simulatable VRF.

2010

EPRINT

Preventing Pollution Attacks in Multi-Source Network Coding
Abstract

Network coding is a method for achieving channel capacity in networks.
The key idea is to allow network routers to linearly mix packets as
they traverse the network so that recipients receive linear
combinations of packets. Network coded systems are vulnerable to
pollution attacks where a single malicious node floods the network
with bad packets and prevents the receiver from decoding correctly.
Cryptographic defenses to these problems are based on homomorphic
signatures and MACs. These proposals, however, cannot handle mixing of
packets from multiple sources, which is needed to achieve the full
benefits of network coding. In this paper we address integrity of
multi-source mixing. We propose a security model for this setting
and provide a generic construction.

2010

EPRINT

Homomorphic Signatures over Binary Fields: Secure Network Coding with Small Coefficients
Abstract

We propose a new signature scheme that can be used to authenticate data and prevent pollution attacks in networks that use network coding. At its core, our system is a homomorphic signature scheme that authenticates vector subspaces of a given ambient space. Our system has several novel properties not found in previous proposals:
- It is the first such scheme that authenticates vectors defined over *binary fields*; previous proposals could only authenticate vectors with large or growing coefficients.
- It is the first such scheme based on the problem of finding short vectors in integer lattices, and thus enjoys the worst-case security guarantees common to lattice-based
cryptosystems.
Security of our scheme (in the random oracle model) is based on a new hard problem on lattices, called k-SIS, that reduces to standard average-case and worst-case lattice problems.
Our construction gives an example of a cryptographic primitive -- homomorphic signatures over F_2 -- that can be built using lattice methods, but cannot currently be built using bilinear maps or other traditional algebraic methods based on factoring or discrete-log type problems.

2008

EPRINT

Signing a Linear Subspace: Signature Schemes for Network Coding
Abstract

Network coding offers increased throughput and improved robustness
to random faults in completely decentralized networks.
In contrast to traditional routing schemes, however, network coding
requires intermediate nodes to modify data packets en route;
for this reason, standard signature schemes are inapplicable and it
is a challenge to provide resilience to tampering by malicious
nodes.
Here, we propose two signature schemes that can be used in
conjunction with network coding to prevent malicious modification of
data. In particular, our schemes can be viewed as signing linear
subspaces in the sense that a signature on V
authenticates exactly those vectors in V.
Our first scheme is homomorphic and has better performance,
with both public key size and per-packet overhead being constant.
Our second scheme does not rely on random oracles and uses weaker assumptions.
We also prove a lower bound on the length of signatures for
linear subspaces showing that both of our schemes are essentially optimal in
this regard.

2007

EPRINT

Public Key Encryption that Allows PIR Queries
Abstract

Consider the following problem: Alice wishes to maintain her email
using a storage-provider Bob (such as a Yahoo! or hotmail e-mail
account). This storage-provider should provide for Alice the ability
to collect, retrieve, search and delete emails but, at the same
time, should learn neither the content of messages sent from the
senders to Alice (with Bob as an intermediary), nor the search
criteria used by Alice. A trivial solution is that messages will be
sent to Bob in encrypted form and Alice, whenever she wants to
search for some message, will ask Bob to send her a copy of the
entire database of encrypted emails. This however is highly
inefficient. We will be interested in solutions that are communication-efficient and, at the same time, respect the privacy of Alice. In this paper, we show how to create a public-key encryption scheme for Alice that allows PIR searching over encrypted documents. Our solution provides a theoretical solution to an open problem posed by Boneh, DiCrescenzo, Ostrovsky and Persiano on ``Public-key Encryption with Keyword Search'', providing the first scheme that does not reveal any partial information regarding user's search (including the access pattern) in the public-key setting and with non-trivially
small communication complexity.
The main technique of our solution also allows for Single-Database PIR writing with sub-linear communication complexity, which we consider of independent interest.

2007

EPRINT

Space-Efficient Identity Based Encryption Without Pairings
Abstract

Identity Based Encryption (IBE) systems are often constructed
using bilinear maps (a.k.a. pairings) on elliptic curves. One
exception is an elegant system due to Cocks which builds an IBE
based on the quadratic residuosity problem modulo an RSA composite
N. The Cocks system, however, produces long ciphertexts. Since
the introduction of the Cocks system in 2001 it has been an open
problem to construct a space efficient IBE system without
pairings. In this paper we present an IBE system in which
ciphertext size is short: an encryption of an L-bit message
consists of a single element in Z_N plus L+1 additional
bits. Security, as in the Cocks system, relies on the quadratic
residuosity problem. The system is based on the theory of ternary
quadratic forms and as a result, encryption and decryption are
slower than in the Cocks system.

2006

EPRINT

Fully Collusion Resistant Traitor Tracing
Abstract

We construct the first fully collusion resistant tracing traitors
system with sublinear size ciphertexts and constant size private keys.
More precisely, let $N$ be the total number of users. Our system
generates ciphertexts of size $O(\sqrt{N})$ and private keys of size
$O(1)$. We build our system by first building a simpler primitive
called private linear broadcast encryption (PLBE). We then show
that any PLBE gives a tracing traitors system with the same
parameters. Our system uses bilinear maps in groups of composite
order.

2006

EPRINT

Conjunctive, Subset, and Range Queries on Encrypted Data
Abstract

We construct public-key systems that support comparison queries ($x
\geq a)$ on encrypted data as well as more general queries such as
subset queries $(x \in S)$. These systems also support arbitrary
conjunctive queries ($P_1 \wedge \cdots \wedge P_\ell$) without
leaking information on individual conjuncts. We present a general
framework for constructing and analyzing public-key systems
supporting queries on encrypted data.

2006

EPRINT

A Fully Collusion Resistant Broadcast, Trace, and Revoke System
Abstract

We introduce a simple primitive called Augmented Broadcast
Encryption (ABE) that is sufficient for constructing broadcast
encryption, traitor-tracing, and trace-and-revoke systems. These
ABE-based constructions are resistant to an arbitrary number of
colluders and are secure against adaptive adversaries.
Furthermore, traitor tracing requires no secrets and can be done by anyone. These broadcast systems are designed for broadcasting to arbitrary sets of users. We then construct a secure ABE system for which the resulting concrete trace-and-revoke system has ciphertexts and private keys of size $\sqrt{N}$ where $N$ is the total number of users in the system. In particular, this is the first example of a fully collusion resistant broadcast system with sub-linear size ciphertexts and private keys that is secure against adaptive adversaries. The
system is publicly traceable.

2005

EPRINT

Hierarchical Identity Based Encryption with Constant Size Ciphertext
Abstract

We present a Hierarchical Identity Based Encryption (HIBE) system
where the ciphertext consists of just three group elements and decryption
requires only two bilinear map computations,
independent of the hierarchy depth. Encryption is as efficient
as in other HIBE systems. We prove that the scheme is selective-ID secure
in the standard model and fully secure in the random oracle
model. Our system has a number of applications: it gives very
efficient forward secure public key and identity based cryptosystems (where ciph
ertexts are
short), it converts the NNL broadcast encryption system into an
efficient public key broadcast system, and it provides an efficient
mechanism for encrypting to the future. The system also supports
limited delegation where users can be given restricted private keys
that only allow delegation to certain descendants. Sublinear size private
keys can also be achieved at the expense of some ciphertext expansion.

2005

EPRINT

Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys
Abstract

We describe two new public key broadcast encryption systems for
stateless receivers. Both systems are fully secure against any number
of colluders. In our first construction both ciphertexts and private
keys are of constant size (only two group elements), for any
subset of receivers. The public key size in this system is
linear in the total number of receivers. Our second system is a
generalization of the first that provides a tradeoff between
ciphertext size and public key size. For example, we achieve a
collusion resistant broadcast system for n users where both
ciphertexts and public keys are of size O(sqrt(n)) for any subset
of receivers. We discuss several applications of these systems.

2004

EPRINT

Short Signatures Without Random Oracles
Abstract

We describe a short signature scheme which is existentially unforgeable under a chosen message attack without using random oracles. The security of our scheme depends on a new complexity assumption we call the {\em Strong Diffie-Hellman} assumption. This assumption has similar properties to the Strong RSA assumption, hence the name. Strong RSA was previously used to construct signature schemes without random oracles. However, signatures generated by our scheme are much shorter and simpler than signatures from schemes based on Strong RSA. Furthermore, our scheme provides a limited form of message recovery.

2004

EPRINT

Secure Identity Based Encryption Without Random Oracles
Abstract

We present a fully secure identity based encryption scheme whose proof of security does not rely on the random oracle heuristic. Security is based on the decisional bilinear Diffie-Hellman assumption. Previous constructions of this type incurred a large penalty factor in the security reduction from the underlying complexity assumption. The security reduction of the present system is polynomial in all the parameters.

2004

EPRINT

Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles
Abstract

We construct two efficient Identity Based Encryption (IBE) systems that are selective identity secure {\em without the random oracle model} in groups equipped with a bilinear map. Selective identity secure IBE is a slightly weaker security model than the standard security model for IBE. In this model the adversary must commit ahead of time to the identity that it intends to attack, whereas in the standard model the adversary is allowed to choose this identity adaptively. The first system is based on the decisional bilinear Diffie-Hellman assumption, and extends to give a selective identity Hierarchical IBE secure without random oracles. The second system is based on a related assumption called the bilinear Diffie-Hellman inversion assumption. Applications of either system include an efficient CCA2 public key cryptosystem that supports non-interactive threshold decryption in the standard model, and a simple and practical IBE system that remains secure against full adaptive-ID attacks, under some security penalty, without random oracles.

2004

EPRINT

Short Group Signatures
Abstract

We construct a short group signature scheme. Signatures in our scheme are approximately the size of a standard RSA signature with the same security. Security of our group signature is based on the Strong Diffie-Hellman assumption and a new assumption in bilinear groups called the Decision Linear assumption. We prove security of our system, in the random oracle model, using a variant of the security definition for group signatures recently given by Bellare, Micciancio, and Warinschi.

2004

EPRINT

Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption
Abstract

Recently, Canetti, Halevi, and Katz showed a general method for constructing CCA-secure encryption schemes from identity-based encryption schemes in the standard model. We improve the efficiency of their construction, and show two specific instantiations of our resulting scheme which offer the most efficient encryption (and, in one case, key generation) of any CCA-secure encryption scheme to date.

2003

EPRINT

Public Key Encryption with keyword Search
Abstract

We study the problem of searching on data that is encrypted using a
public key system. Consider user Bob who sends email to user Alice
encrypted under Alice's public key. An email gateway wants to test
whether the email contains the keyword `urgent' so that it could
route the email accordingly. Alice, on the other hand does not wish
to give the gateway the ability to decrypt all her messages. We define
and construct a mechanism that enables Alice to provide a key to the
gateway that enables the gateway to test whether the word `urgent'
is a keyword in the email without learning anything else about the
email. We refer to this mechanism as <I>Public Key Encryption with
keyword Search</I>. As another example, consider a mail server that
stores various messages publicly encrypted for Alice by others. Using
our mechanism Alice can send the mail server a key that will enable
the server to identify all messages containing some specific keyword,
but learn nothing else. We define the concept of public key
encryption with keyword search and give several constructions.

2002

EPRINT

Applications of Multilinear Forms to Cryptography
Abstract

We study the problem of finding efficiently computable non-degenerate multilinear maps from (G_1)^n to G_2, where G_1 and G_2 are groups of the same prime order, and where computing discrete logarithms in G_1 is hard. We present several applications to cryptography, explore directions for building such maps, and give some reasons to believe that finding examples with n > 2 may be difficult.

2002

EPRINT

Aggregate and Verifiably Encrypted Signatures from Bilinear Maps
Abstract

An aggregate signature scheme is a digital signature that supports
aggregation: Given $n$ signatures on $n$ distinct messages from
$n$ distinct users, it is possible to aggregate all these
signatures into a single short signature. This single signature
(and the $n$ original messages) will convince the verifier that
the $n$ users did indeed sign the $n$ original messages (i.e.,
user $i$ signed message $M_i$ for $i=1,\ldots,n$). In this paper
we introduce the concept of an aggregate signature scheme, present
security models for such signatures, and give several applications
for aggregate signatures. We construct an efficient aggregate
signature from a recent short signature scheme based on bilinear
maps due to Boneh, Lynn, and Shacham. Aggregate signatures are
useful for reducing the size of certificate chains (by aggregating
all signatures in the chain) and for reducing message size in
secure routing protocols such as SBGP. We also show that
aggregate signatures give rise to verifiably encrypted signatures.
Such signatures enable the verifier to test that a given
ciphertext $C$ is the encryption of a signature on a given message
$M$. Verifiably encrypted signatures are used in contract-signing
protocols. Finally, we show that similar ideas can be used to
extend the short signature scheme to give simple ring signatures.

2001

EPRINT

Identity Based Encryption From the Weil Pairing
Abstract

We propose a fully functional identity-based encryption scheme (IBE).
The scheme has chosen ciphertext security in the random oracle model
assuming an elliptic curve variant of the computational Diffie-Hellman
problem. Our system is based on bilinear maps between groups. The
Weil pairing on elliptic curves is an example of such a map. We give
precise definitions for secure identity based encryption schemes and
give several applications for such systems.

1997

EPRINT

Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring
Abstract

The Diffie-Hellman key-exchange protocol may naturally be
extended to k>2 parties. This gives rise to the generalized
Diffie-Hellman assumption (GDH-Assumption).
Naor and Reingold have recently shown an efficient construction
of pseudo-random functions and reduced the security of their
construction to the GDH-Assumption.
In this note, we prove that breaking this assumption modulo a composite
would imply an efficient algorithm for factorization.
Therefore, the security of both the key-exchange protocol and
the pseudo-random functions can be reduced to factoring.

1996

CRYPTO

1996

CRYPTO

#### Program Committees

- Crypto 2017
- Crypto 2012
- Crypto 2011
- Eurocrypt 2010
- Crypto 2009
- Crypto 2003
- Eurocrypt 2002
- Eurocrypt 2000
- Asiacrypt 2000
- Crypto 2000
- Eurocrypt 1999
- Crypto 1998

#### Coauthors

- Martín Abadi (2)
- Shweta Agrawal (4)
- Jae Hyun Ahn (2)
- Eli Biham (1)
- Joseph Bonneau (2)
- Xavier Boyen (17)
- Elette Boyle (1)
- Benedikt Bünz (3)
- Jan Camenisch (2)
- Jeremy Clark (1)
- Henry Corrigan-Gibbs (3)
- Giovanni Di Crescenzo (2)
- Özgür Dagdelen (1)
- Gaby G. Dagher (1)
- Richard A. DeMillo (2)
- Manu Drijvers (1)
- Glenn Durfee (4)
- Saba Eskandarian (1)
- Ben Fisch (2)
- Marc Fischlin (1)
- Yair Frankel (1)
- Matthew K. Franklin (5)
- David Freeman (7)
- Rosario Gennaro (1)
- Craig Gentry (7)
- Niv Gilboa (1)
- Eu-Jin Goh (3)
- Steven Goldfeder (1)
- Philippe Golle (1)
- Sergey Gorbunov (2)
- Divya Gupta (1)
- Shai Halevi (4)
- Mike Hamburg (3)
- Susan Hohenberger (2)
- Nick Howgrave-Graham (2)
- William E. Skeith III (2)
- Yuval Ishai (4)
- Aayush Jain (1)
- Markus Jakobsson (1)
- Antoine Joux (1)
- Ari Juels (1)
- Jonathan Katz (3)
- Sam Kim (4)
- Dmitry Kogan (1)
- Eyal Kushilevitz (2)
- Anja Lehmann (1)
- Kevin Lewi (4)
- Richard J. Lipton (4)
- Ben Lynn (4)
- Ilya Mironov (3)
- Hart Montgomery (1)
- Hart William Montgomery (3)
- Moni Naor (1)
- Gregory Neven (1)
- Phong Q. Nguyen (1)
- Valeria Nikolaenko (2)
- Kobbi Nissim (1)
- Rafail Ostrovsky (5)
- Alain Passelègue (1)
- Giuseppe Persiano (2)
- Ananth Raghunathan (7)
- Peter M. R. Rasmussen (1)
- Mariana Raykova (1)
- Omer Reingold (1)
- Amit Sahai (9)
- Christian Schaffner (1)
- Stuart E. Schechter (1)
- Gil Segev (6)
- Hovav Shacham (6)
- James Shaw (1)
- Abhi Shelat (2)
- Emily Shen (1)
- Maurice Shih (1)
- Igor E. Shparlinski (1)
- Alice Silverberg (1)
- Vinod Vaikuntanathan (2)
- Ramarathnam Venkatesan (2)
- Dhinakaran Vinayagamurthy (2)
- Riad S. Wahby (1)
- Brent Waters (16)
- Katharine Woo (1)
- David J. Wu (5)
- Mark Zhandry (7)
- Sheng Zhong (1)
- Joe Zimmerman (1)