## CryptoDB

### Susan Hohenberger

#### Publications

**Year**

**Venue**

**Title**

2020

CRYPTO

Chosen Ciphertext Security from Injective Trapdoor Functions
★
Abstract

We provide a construction of chosen ciphertext secure public-key encryption from (injective) trapdoor functions. Our construction is black box and assumes no special properties (e.g. ``lossy'', ``correlated product secure'') of the trapdoor function.

2013

CRYPTO

2012

JOFC

Batch Verification of Short Signatures
Abstract

With computer networks spreading into a variety of new environments, the need to authenticate and secure communication grows. Many of these new environments have particular requirements on the applicable cryptographic primitives. For instance, a frequent requirement is that the communication overhead inflicted be small and that many messages be processable at the same time. In this paper, we consider the suitability of public key signatures in the latter scenario. That is, we consider (1) signatures that are short and (2) cases where many signatures from (possibly) different signers on (possibly) different messages can be verified quickly. Prior work focused almost exclusively on batching signatures from the same signer.We propose the first batch verifier for messages from many (certified) signers without random oracles and with a verification time where the dominant operation is independent of the number of signatures to verify. We further propose a new signature scheme with very short signatures, for which batch verification for many signers is also highly efficient. Combining our new signatures with the best known techniques for batching certificates from the same authority, we get a fast batch verifier for certificates and messages combined. Although our new signature scheme has some restrictions, it is very efficient and still practical for some communication applications.

2010

EPRINT

Constructing Veriﬁable Random Functions with Large Input Spaces
Abstract

We present a family of verifiable random functions which are provably secure for exponentially-large input spaces under a non-interactive complexity assumption. Prior constructions required either an interactive complexity assumption or one that could tolerate a factor 2^n security loss for n-bit inputs. Our construction is practical and inspired by the pseudorandom functions of Naor and Reingold and the verifiable random functions of Lysyanskaya. Set in a bilinear group, where the Decisional Diffie-Hellman problem is easy to solve, we require the Decisional Diffie-Hellman Exponent assumption in the standard model, without a common reference string. Our core idea is to apply a simulation technique where the large space of VRF inputs is collapsed into a small (polynomial-size) input in the view of the reduction algorithm. This view, however, is information-theoretically hidden from the attacker. Since the input space is exponentially large, we can first apply a collision-resistant hash function to handle arbitrarily-large inputs.

2010

EPRINT

Practical Adaptive Oblivious Transfer from a Simple Assumption
Abstract

We present the first efficient, adaptive oblivious transfer protocol which is fully-simulatable under a simple assumption in the standard model. The sole complexity assumption required is that given (g, g^a, g^b, g^c, Q), where g generates a bilinear group of prime order p and a, b, c are selected randomly from Zp, it is hard to decide if Q = g^{abc}.
In an adaptive oblivious transfer protocol, a sender with a database of messages and a receiver repeatedly interact in such a way that the receiver obtains one message per interaction of his choice (and nothing more) while the sender learns nothing about any of the choices. All prior protocols in the standard model require dynamic "q-based" assumptions, where the number of group elements in the assumption input grows with the size of the sender's database.
Our construction makes an important change to the established "assisted decryption" technique for designing adaptive OT. As in prior works, the sender commits to a database of n messages by publishing an encryption of each message and a signature on each encryption. Then, each transfer phase can be executed in time /independent/ of n as the receiver blinds one of the encryptions and proves knowledge of the blinding factors and a signature on this encryption, after which the sender helps the receiver decrypt the chosen ciphertext. One of the main obstacles to designing an adaptive OT scheme from a simple assumption is realizing a suitable signature for this purpose (i.e., enabling signatures on group elements in a manner that later allows for efficient proofs.) We make the observation that a secure signature scheme is not necessary for this paradigm, provided that signatures can only be forged in certain ways. We then show how to efficiently integrate an insecure signature into a secure adaptive OT construction.
We believe this construction and its underlying techniques may be of interest in designing other privacy-preserving protocols from simple complexity assumptions.

2010

EPRINT

CPA and CCA-Secure Encryption Systems that are not 2-Circular Secure
Abstract

Traditional definitions of encryption guarantee security for plaintexts which can be derived by the adversary. In some settings, such as anonymous credential or disk encryption systems, one may need to reason about the security of messages potentially unknown to the adversary, such as secret keys encrypted in a self-loop or a cycle. A public-key cryptosystem is n-circular secure if it remains secure when the ciphertexts E(pk_1, sk_2), E(pk_2, sk_3), ... , E(pk_{n-1}, sk_n), E(pk_n, sk_1) are revealed, for independent key pairs.
A natural question to ask is what does it take to realize circular security in the standard model? Are all CPA-secure (or CCA-secure) cryptosystems also n-circular secure for n >1? One way to resolve this question is to produce a CPA-secure (or CCA-secure) cryptosystem which is demonstrably insecure for key cycles larger than self-loops.
Recently and independently, Acar, Belenkiy, Bellare and Cash provided a CPA-secure cryptosystem, under the SXDH assumption, that is not 2-circular secure.
In this paper, we present a different CPA-secure counterexample (under SXDH) as well as the first CCA-secure counterexample (under SXDH and the existence of certain NIZK proof systems) for n >1. Moreover, our 2-circular attacks recover the secret keys of both parties and thus exhibit a catastrophic failure of the system whereas the attack in Acar et al. provides a test whereby the adversary can distinguish whether it is given a 2-cycle or two random ciphertexts. These negative results are an important step in answering deep questions about which attacks are prevented by commonly-used definitions and systems of encryption.

2010

EPRINT

Synchronized Aggregate Signatures: New Definitions, Constructions and Applications
Abstract

An aggregate signature scheme is a digital signature scheme where anyone given n signatures on n messages from n users can aggregate all these signatures into a single short signature. Unfortunately, no ``fully non-interactive'' aggregate signature schemes are known outside of the random oracle heuristic; that is, signers must pass messages between themselves, sequentially or otherwise, to generate the signature. Interaction is too costly for some interesting applications.
In this work, we consider the task of realizing aggregate signatures in the model of Gentry and Ramzan (PKC 2006) when all signers share a synchronized clock, but do not need to be aware of or interactive with one another. Each signer may issue at most one signature per time period and signatures aggregate only if they were created during the same time period. We call this synchronized aggregation.
We present a practical synchronized aggregate signature scheme secure under the Computational Diffie-Hellman assumption in the standard model.
Our construction is based on the stateful signatures of Hohenberger and Waters (Eurocrypt 2009). Those signatures do not aggregate since each signature includes unique randomness for a chameleon hash and those random values do not compress. To overcome this challenge, we remove the chameleon hash from their scheme and find an alternative method for moving from weak to full security that enables aggregation. We conclude by discussing applications of this construction to sensor networks and software authentication.

2009

EPRINT

Realizing Hash-and-Sign Signatures under Standard Assumptions
Abstract

Currently, there are relatively few instances of ``hash-and-sign''
signatures in the standard model. Moreover, most current instances
rely on strong and less studied assumptions such as the Strong RSA
and q-Strong Diffie-Hellman assumptions.
In this paper, we present a new approach for realizing hash-and-sign
signatures in the standard model. In our approach, a signer associates
each signature with an index i that represents how many signatures
that signer has issued up to that point. Then, to make use of this
association, we create simple and efficient techniques that restrict an
adversary which makes q signature requests to forge on an index no
greater than 2q. Finally, we develop methods
for dealing with this restricted adversary.
Our approach requires that a signer maintains a small amount of state ---
a counter of the number of signatures issued. We achieve two new realizations
for hash-and-sign signatures respectively based on the RSA assumption
and the Computational Diffie-Hellman assumption in bilinear groups.

2008

EPRINT

On the Practicality of Short Signature Batch Verification
Abstract

As pervasive communication becomes a reality, where everything from vehicles to heart monitors constantly communicate with their environments, system designers are facing a cryptographic puzzle on how to authenticate messages. These scenarios require that : (1) cryptographic overhead remain short, and yet (2) many messages from many different signers be verified very quickly. Pairing-based signatures have property (1) but not (2), whereas schemes like RSA have property (2) but not (1). As a solution to this dilemma, Camenisch, Hohenberger and Pedersen showed how to batch verify two pairing-based signatures so that the total number of pairing operations was independent of the number of signatures to verify. CHP left open the task of batching privacy-friendly authentication, which is desirable in many pervasive communication scenarios.
In this work, we revisit this issue from a more practical standpoint and present the following results:
1. We describe a framework, consisting of general techniques, to help scheme and system designers understand how to {\em securely} and {\em efficiently} batch the verification of pairing equations.
2. We present a detailed study of when and how our framework can be applied to existing regular, identity-based, group, ring, and aggregate signature schemes. To our knowledge, these batch verifiers for group and ring signatures are the first proposals for batching privacy-friendly authentication, answering an open problem of Camenisch et al.
3. While prior work gave mostly asymptotic efficiency comparisons, we show that our framework is practical by implementing our techniques and giving detailed performance measurements. Additionally, we discuss how to deal with invalid signatures in a batch and our empirical results show that when roughly less than 10% of signatures are invalid, batching remains more efficient that individual verification.
Indeed, our results show that batch verification for short signatures is an effective, efficient approach.

2008

EPRINT

Universally Composable Adaptive Oblivious Transfer
Abstract

In an oblivious transfer (OT) protocol, a Sender with messages M_1,...,M_N and a Receiver with indices s_1,...,s_k interact in such a way that at the end the Receiver obtains M_{s_1},...,M_{s_k} without learning anything about the other messages, and the Sender does not learn anything about s_1,...,s_k. In an adaptive protocol, the Receiver may obtain M_{s_{i-1}} before deciding on $s_i$. Efficient adaptive OT protocols are interesting both as a building block for secure multiparty computation and for enabling oblivious searches on medical and patent databases.
Historically, adaptive OT protocols were analyzed with respect to a ``half-simulation'' definition which Naor and Pinkas showed to be flawed. In 2007, Camenisch, Neven, and shelat, and subsequent other works, demonstrated efficient adaptive protocols in the full-simulation model. These protocols, however, all use standard rewinding techniques in their proofs of security and thus are not universally composable. Recently, Peikert, Vaikuntanathan and Waters presented universally composable (UC) non-adaptive OT protocols (for the 1-out-of-2 variant). However, it is not clear how to preserve UC security while extending these protocols to the adaptive k-out-of-N setting. Further, any such attempt would seem to require O(N) computation per transfer for a database of size N. In this work, we present an efficient and UC-secure adaptive k-out-of-N OT protocol, where after an initial commitment to the database, the cost of each transfer is constant. Our construction is secure under bilinear assumptions in the standard model.

2008

EPRINT

Key-Private Proxy Re-Encryption
Abstract

Proxy re-encryption (PRE) allows a proxy to convert a ciphertext encrypted under one key into an encryption of the same message under another key. The main idea is to place as little trust and reveal as little information to the proxy as necessary to allow it to perform its translations. At the very least, the proxy should not be able to learn the keys of the participants or the content of the messages it re-encrypts. However, in all prior PRE schemes, it is easy for the proxy to determine between which participants a re-encryption key can transform ciphertexts. This can be a problem in practice. For example, in a secure distributed file system, content owners may want to use the proxy to help re-encrypt sensitive information *without* revealing to the proxy the *identity* of the recipients.
In this work, we propose key-private (or anonymous) re-encryption keys as an additional useful property of PRE schemes. We formulate a definition of what it means for a PRE scheme to be secure and key-private. Surprisingly, we show that this property is not captured by prior definitions or achieved by prior schemes, including even the secure *obfuscation* of PRE by Hohenberger, Rothblum, shelat and Vaikuntanathan (TCC 2007). Finally, we propose the first key-private PRE construction and prove its security under a simple extension of the Decisional Bilinear Diffie Hellman assumption and its key-privacy under the Decision Linear assumption in the standard model.

2007

EPRINT

Chosen-Ciphertext Secure Proxy Re-Encryption
Abstract

In a proxy re-encryption (PRE) scheme, a proxy is given special information that
allows it to translate a ciphertext under one key into a ciphertext of the
same message under a different key. The proxy cannot, however, learn
anything about the messages encrypted under either key. PRE
schemes have many practical applications, including distributed storage, email, and DRM. Previously proposed re-encryption schemes achieved
only semantic security;
in contrast, applications often require security
against chosen ciphertext attacks. We propose a definition of security
against chosen ciphertext attacks for PRE schemes, and present a
scheme that satisfies the definition. Our construction is efficient and based
only on the Decisional Bilinear Diffie-Hellman assumption
in the standard model. We also formally capture CCA security for PRE schemes
via both a game-based definition and simulation-based definitions that
guarantee universally composable security.
We note that, simultaneously with our work, Green and Ateniese proposed
a CCA-secure PRE, discussed herein.

2007

EPRINT

Batch Verification of Short Signatures
Abstract

With computer networks spreading into a variety of new environments, the need to authenticate and secure communication grows. Many of these new environments have particular requirements on the applicable cryptographic primitives. For instance, several applications require that communication overhead be small and that many messages be processed at the same time. In this paper we consider the suitability of public key signatures in the latter scenario. That is, we consider signatures that are 1) short and 2) where many signatures from (possibly) different signers on (possibly) different messages can be verified quickly. Prior work focused almost exclusively on batching signatures from the same signer.
We propose the first batch verifier for messages from many (certified) signers without random oracles and with a verification time where the dominant operation is independent of the number of signatures to verify. We further propose a new signature scheme with very short signatures, for which batch verification for many signers is also highly efficient. Combining our new signatures with the best known techniques for batching certificates from the same authority, we get a fast batch verifier for certificates and messages combined. Although our new signature scheme has some restrictions, it is very efficient and still practical for some communication applications.

2007

EPRINT

Blind Identity-Based Encryption and Simulatable Oblivious Transfer
Abstract

In an identity-based encryption (IBE) scheme, there is a {\em key extraction} protocol where a user submits an identity string to a master authority who then returns the corresponding secret key for that identity. In this work, we describe how this protocol can be performed efficiently and in a {\em blind} fashion for several known IBE schemes; that is, a user can obtain a secret key for an identity without the master authority learning anything about this identity.
We formalize this notion as {\em blind IBE} and discuss the many practical applications of such a scheme. In particular, we build upon the recent work of Camenisch, Neven, and shelat in Eurocrypt 2007 to construct oblivious transfer (OT) schemes which achieve full simulatability for both sender and receiver. OT constructions with comparable efficiency prior to Camenisch et al.\ were proven secure in the weaker half-simulation model. Our OT schemes can be constructed generically from any blind IBE, and thus require only static complexity assumptions (e.g., DBDH) whereas prior comparable schemes require dynamic complexity assumptions (e.g., $q$-PDDH).

2007

EPRINT

On Tweaking Luby-Rackoff Blockciphers
Abstract

Tweakable blockciphers, first formalized by Liskov, Rivest, and Wagner, are blockciphers with an additional input, the tweak, which allows for variability. An open problem proposed by Liskov et al. is how to construct tweakable blockciphers without using a pre-existing blockcipher. This problem has yet to receive any significant study. There are many natural questions in this area: is it significantly more effcient to incorporate a tweak directly? How do direct constructions compare to existing techniques? Are these direct constructions optimal and for what levels of security? How large of a tweak can be securely added? In this work, we address these questions for Luby-Rackoff blockciphers. We show that tweakable blockciphers can be created directly from Feistel ciphers, and in some cases show that direct constructions of tweakable blockciphers are more e±cient than previously known constructions.

2006

EPRINT

How to Win the Clone Wars: \\ Efficient Periodic n-Times Anonymous Authentication
Abstract

We create a credential
system that lets a user anonymously authenticate at most $n$ times in
a single time period. A user withdraws a dispenser of $n$ e-tokens.
She shows an e-token to a verifier to authenticate herself; each
e-token can be used only once, however, the dispenser automatically
refreshes every time period.
The only prior solution to this problem,
due to Damg{\aa}rd et al.~[DDP05], uses protocols that are a factor of $k$ slower for the user and verifier, where $k$ is the security parameter.
Damg{\aa}rd et al. also only support one authentication per time
period, while we support $n$. Because our construction is based on
e-cash, we can use existing techniques to identify a cheating user,
trace all of her e-tokens, and revoke her dispensers. We also offer a
new anonymity service: glitch protection for basically honest users
who (occasionally) reuse e-tokens. The verifier can always recognize
a reused e-token; however, we preserve the anonymity of users who do
not reuse e-tokens too often.

2005

EPRINT

Improved Proxy Re-Encryption Schemes with Applications to Secure Distributed Storage
Abstract

In 1998, Blaze, Bleumer, and Strauss (BBS) proposed an application called
atomic proxy re-encryption, in which a semi-trusted proxy
converts a ciphertext for Alice into a ciphertext for Bob without
seeing the underlying plaintext. We predict that fast and
secure re-encryption will become increasingly popular as a method for
managing encrypted file systems. Although efficiently computable, the
wide-spread adoption of BBS re-encryption has been hindered by
considerable security risks. Following recent work of Ivan and Dodis,
we present new re-encryption schemes that realize a stronger notion of
security and we demonstrate the usefulness of proxy re-encryption as a
method of adding access control to the SFS read-only file system.
Performance measurements of our experimental file system demonstrate
that proxy re-encryption can work effectively in practice.

2005

EPRINT

Compact E-Cash
Abstract

This paper presents efficient off-line anonymous e-cash schemes
where a user can withdraw a wallet containing 2^l coins each of which she can spend unlinkably. Our first result is a scheme, secure under the strong RSA and the y-DDHI assumptions, where the complexity of the withdrawal and spend operations is O(l+k)
and the user's wallet can be stored using O(l+k) bits, where k is a security parameter.
The best previously known schemes require at least one of these complexities to
be O(2^l k).
In fact, compared to previous e-cash schemes, our whole wallet of 2^l coins
has about the same size as one coin in these schemes.
Our scheme also offers exculpability
of users, that is, the bank can prove to third parties that a user has
double-spent.
We then extend our scheme to our second result, the first e-cash scheme that provides traceable coins without a trusted third party.
That is, once a user has double spent one of the 2^l coins in her wallet, all her spendings of these coins can be traced.
We present two alternate constructions. One construction shares the same complexities with our first result but requires a strong bilinear map assumption that is only conjectured to hold on MNT curves. The second construction works on more general types of elliptic curves, but the price for this is that the complexity of the spending and of the withdrawal protocols becomes O(lk) and O(lk + k^2) bits, respectively, and wallets take O(lk) bits of storage.
All our schemes are secure in the random oracle model.

2005

EPRINT

Practical Group Signatures without Random Oracles
Abstract

We provide a construction for a
group signature scheme that is provably secure in a universally composable framework,
within the standard model with trusted parameters.
Our proposed scheme is fairly simple and its efficiency falls
within small factors of the most efficient group signature schemes
with provable security in any model (including random oracles).
Security of our constructions require new
cryptographic assumptions, namely the Strong LRSW, EDH, and Strong SXDH assumptions. Evidence for any assumption we introduce is provided by proving hardness in the generic group model.
Our second contribution is the first definition of security for group signatures based on the simulatability
of real protocol executions in an ideal setting that captures
the basic properties of unforgeability, anonymity, unlinkability, and exculpability for
group signature schemes.

2005

EPRINT

Proxy Re-Signatures: New Definitions, Algorithms, and Applications
Abstract

In 1998, Blaze, Bleumer, and Strauss (BBS) proposed proxy re-signatures, in which a semi-trusted proxy acts as a translator between Alice and Bob. To translate, the proxy converts a signature from Alice into a signature from Bob on the same message. The proxy, however, does not learn any signing key and cannot sign arbitrary messages on behalf of either Alice or Bob. Since the BBS proposal, the proxy re-signature primitive has been largely ignored, but we show that it is a very useful tool for sharing web certificates, forming weak group signatures, and authenticating a network path.
We begin our results by formalizing the definition of security for a proxy re-signature. We next substantiate the need for improved schemes by pointing out certain weaknesses of the original BBS proxy re-signature scheme which make it unfit for most practical applications. We then present two secure proxy re-signature schemes based on bilinear maps.
Our first scheme relies on the Computational Diffie-Hellman (CDH) assumption; here the proxy can translate from Alice to Bob and vice-versa. Our second scheme relies on the CDH and 2-Discrete Logarithm (2-DL) assumptions and achieves a stronger security guarantee -- the proxy is only able to translate in one direction. Constructing such a scheme has been an open problem since proposed by BBS in 1998. Furthermore in this second scheme, even if the delegator and the proxy collude, they cannot sign on behalf of the delegatee. Both schemes are efficient and secure in the random oracle model.

#### Program Committees

- Eurocrypt 2020
- Crypto 2019
- PKC 2014
- TCC 2014
- Crypto 2012
- Crypto 2010
- TCC 2010
- Crypto 2008
- TCC 2008

#### Coauthors

- Jae Hyun Ahn (3)
- Joseph A. Akinyele (1)
- Giuseppe Ateniese (4)
- Karyn Benson (1)
- Allison Bishop (3)
- Dan Boneh (2)
- Jan Camenisch (9)
- Ran Canetti (1)
- David Cash (1)
- Scott E. Coull (1)
- Anna Lisa Ferrara (1)
- Kevin Fu (1)
- Christina Garman (1)
- David Goldenberg (2)
- Rishab Goyal (1)
- Matthew Green (12)
- Markulf Kohlweiss (1)
- Venkata Koppula (5)
- Moses Liskov (2)
- Anna Lysyanskaya (4)
- Breno de Medeiros (1)
- Mira Meyerovich (1)
- Steven Myers (1)
- Rafael Pass (1)
- Michael Østergaard Pedersen (4)
- Guy N. Rothblum (2)
- Amit Sahai (2)
- Elizabeth Crump Schwartz (2)
- Hakan Seyalioglu (2)
- Abhi Shelat (5)
- Vinod Vaikuntanathan (2)
- Brent Waters (21)