## CryptoDB

### Hovav Shacham

#### Affiliation: UC San Diego

#### Publications

**Year**

**Venue**

**Title**

2013

JOFC

Compact Proofs of Retrievability
Abstract

In a proof-of-retrievability system, a data storage center must prove to a verifier that he is actually storing all of a client’s data. The central challenge is to build systems that are both efficient and provably secure—that is, it should be possible to extract the client’s data from any prover that passes a verification check. In this paper, we give the first proof-of-retrievability schemes with full proofs of security against arbitrary adversaries in the strongest model, that of Juels and Kaliski.Our first scheme, built from BLS signatures and secure in the random oracle model, features a proof-of-retrievability protocol in which the client’s query and server’s response are both extremely short. This scheme allows public verifiability: anyone can act as a verifier, not just the file owner. Our second scheme, which builds on pseudorandom functions (PRFs) and is secure in the standard model, allows only private verification. It features a proof-of-retrievability protocol with an even shorter server’s response than our first scheme, but the client’s query is long. Both schemes rely on homomorphic properties to aggregate a proof into one small authenticator value.

2010

ASIACRYPT

2008

EPRINT

Compact Proofs of Retrievability
Abstract

In a proof-of-retrievability system, a data storage center must
prove to a verifier that he is actually storing all of a client's
data. The central challenge is to build systems that are both
efficient and provably secure -- that is, it should be possible
to extract the client's data from any prover that passes a
verification check. All previous provably secure solutions
require that a prover send O(l) authenticator values (i.e., MACs
or signatures) to verify a file, for a total of O(l^2) bits of
communication, where l is the security parameter. The extra cost
over the ideal O(l) communication can be prohibitive in systems
where a verifier needs to check many files.
We create the first compact and provably secure proof of
retrievability systems. Our solutions allow for compact proofs
with just one authenticator value -- in practice this can lead to
proofs with as little as 40 bytes of communication. We present
two solutions with similar structure. The first one is privately
verifiable and builds elegantly on pseudorandom functions (PRFs);
the second allows for publicly verifiable proofs and is built
from the signature scheme of Boneh, Lynn, and Shacham in bilinear
groups. Both solutions rely on homomorphic properties to
aggregate a proof into one small authenticator value.

2008

EPRINT

Delegatable Anonymous Credentials
Abstract

We construct an efficient delegatable anonymous credential system. Users can anonymously and unlinkably obtain credentials from any authority, delegate their credentials to other users, and prove possession of a credential $L$ levels away from the given authority. The size of the proof (and time to compute it) is $O(Lk)$, where $k$ is the security parameter. The only other construction of delegatable anonymous credentials (Chase and Lysyanskaya, Crypto 2006) relies on general non-interactive proofs for NP-complete languages of size $k \Omega(2^{L})$.
We revise the entire approach to constructing anonymous credentials
and identify \emph{randomizable} zero-knowledge proof of knowledge
systems as the key building block. We formally define the notion of
randomizable non-interactive zero-knowledge proofs, and give the first construction by showing how to appropriately rerandomize Groth and Sahai (Eurocrypt 2008) proofs. We show that such proof systems, in combination with an appropriate authentication scheme and a few other protocols, allow us to construct delegatable anonymous credentials. Finally, we instantiate these building blocks under appropriate assumptions about groups with bilinear maps.

2007

EPRINT

A Cramer-Shoup Encryption Scheme from the Linear Assumption and from Progressively Weaker Linear Variants
Abstract

We describe a CCA-secure public-key encryption scheme, in the
Cramer-Shoup paradigm, based on the Linear assumption of Boneh,
Boyen, and Shacham. Through a comparison to the Kiltz
tag-encryption scheme from TCC 2006, our scheme gives evidence
that the Cramer-Shoup paradigm yields CCA encryption with shorter
ciphertexts than the Canetti-Halevi-Katz paradigm.
We present a generalization of the Linear assumption into a
family of progressively weaker assumptions and show how to
instantiate our Linear Cramer-Shoup encryption using the
progressively weaker members of this family.

2007

EPRINT

The BBG HIBE Has Limited Delegation
Abstract

At Eurocrypt 2005, Boneh, Boyen, and Goh presented a hierarchical IBE
for which they claimed a novel property, called limited delegation: it
is possible to give an entity a private key that restricts it from
generating descendant private keys beyond some depth d; in particular,
with d equal to the entity's depth, such a key allows decryption only.
In this paper, we argue that this claim is nonobvious and requires
proof, provide a precise model for arguing about limited delegation,
and prove that the Boneh-Boyen-Goh system does, in fact, have limited
delegation. Whereas Boneh, Boyen, and Goh prove their system
semantically secure under the BDHI assumption, our proof of limited
delegation requires the stronger BDHE assumption.

2006

EPRINT

Sequential Aggregate Signatures and Multisignatures without Random Oracles
Abstract

We present the first aggregate signature, the first multisignature,
and the first verifiably encrypted signature provably secure without
random oracles. Our constructions derive from a novel application
of a recent signature scheme due to Waters. Signatures in our
aggregate signature scheme are sequentially constructed, but
knowledge of the order in which messages were signed is not necessary
for verification. The aggregate signatures obtained are shorter than
Lysyanskaya et~al. sequential aggregates and can be verified more
efficiently than Boneh et~al. aggregates. We also consider
applications to secure routing and proxy signatures.

2006

EPRINT

Efficient Ring Signatures without Random Oracles
Abstract

We describe the first efficient ring signature scheme secure,
without random oracles, based on standard assumptions. Our ring
signatures are based in bilinear groups. For $l$ members of a
ring our signatures consist of $2l+2$ group elements and require
$2l+3$ pairings to verify. We prove our scheme secure in the
strongest security model proposed by Bender, Katz, and Morselli:
namely, we show our scheme to be anonymous against full key
exposure and unforgeable with respect to insider corruption. A
shortcoming of our approach is that all the users' keys must be
defined in the same group.

2006

EPRINT

Forward-Secure Signatures with Untrusted Update
Abstract

In most forward-secure signature constructions, a program that updates
a user's private signing key must have full access to the private key.
Unfortunately, these schemes are incompatible with several security
architectures including Gnu Privacy Guard (GPG) and S/MIME, where the
private key is encrypted under a user password as a ``second factor''
of security, in case the private key storage is corrupted, but the
password is not.
We introduce the concept of forward-secure signatures with untrusted
update, where the key update can be performed on an encrypted version
of the key. Forward secure signatures with untrusted update allow us
to add forward security to signatures, while still keeping passwords
as a second factor of security. We provide a construction that has
performance characteristics comparable with the best existing
forward-secure signatures. In addition, we describe how to modify the
Bellare-Miner forward secure signature scheme to achieve untrusted
update.

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.

2003

EPRINT

Sequential Aggregate Signatures from Trapdoor Permutations
Abstract

An aggregate signature scheme (recently proposed by Boneh, Gentry,
Lynn and Shacham) is a method for combining $n$ signatures from $n$
different signers on $n$ different messages into one signature of unit
length. We propose \emph{sequential aggregate signatures}, in which
the set of signers is ordered. The aggregate signature is computed by
having each signer, in turn, add his signature to it. We show how to
realize this in such a way that the size of the aggregate signature is
independent of $n$. This makes sequential aggregate signatures a
natural primitive for certificate chains, whose length can be reduced
by aggregating all signatures in a chain. We give a construction
based on families of certified trapdoor permutations, and show how to
instantiate our scheme based on RSA.

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.

#### Program Committees

- Crypto 2018
- Crypto 2017
- Eurocrypt 2014
- Crypto 2013
- Eurocrypt 2011
- PKC 2010
- PKC 2009
- Crypto 2008
- Eurocrypt 2008
- PKC 2007
- Crypto 2006
- Asiacrypt 2006
- Asiacrypt 2005

#### Coauthors

- Mira Belenkiy (2)
- Mihir Bellare (1)
- Dan Boneh (6)
- Xavier Boyen (3)
- Zvika Brakerski (1)
- Jan Camenisch (2)
- Melissa Chase (2)
- David Freeman (1)
- Craig Gentry (2)
- Nadia Heninger (1)
- Markulf Kohlweiss (2)
- Steve Lu (2)
- Ben Lynn (4)
- Anna Lysyanskaya (4)
- Sarah Meiklejohn (1)
- Silvio Micali (2)
- Moni Naor (1)
- Rafail Ostrovsky (2)
- Leonid Reyzin (2)
- Thomas Ristenpart (2)
- Amit Sahai (2)
- Gil Segev (1)
- Emily Shen (1)
- Thomas Shrimpton (1)
- Brent Waters (8)
- Scott Yilek (1)