## CryptoDB

### Matthew Green

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

Abuse Resistant Law Enforcement Access Systems
Abstract

The increased deployment of end-to-end encryption has ignited a debate between technology firms and law enforcement agencies over the need for lawful access to encrypted communications. Unfortunately, existing solutions to this problem suffer from serious technical risks, such as the possibility of operator abuse and theft of escrow key material. In this work we investigate the problem of constructing law enforcement access systems that mitigate the possibility of unauthorized surveillance. We first define a set of desirable properties for an abuse-resistant law enforcement access system (ARLEAS), and motivate each of these properties. We then formalize these definitions in the Universal Composability framework, and present two main constructions that realize this definition. The first construction enables {\em prospective} access, allowing surveillance only if encryption occurs after a warrant has been issued and activated. The second, more powerful construction, allows {\em retrospective} access to communications that occurred prior to a warrant's issuance. To illustrate the technical challenge of constructing the latter type of protocol, we conclude by investigating the minimal assumptions required to realize these systems.

2021

CRYPTO

Fluid MPC: Secure Multiparty Computation with Dynamic Participants
📺
Abstract

Existing approaches to secure multiparty computation (MPC) require all participants to commit to the entire duration of the protocol. As interest in MPC continues to grow, it is inevitable that there will be a desire to use it to evaluate increasingly complex functionalities, resulting in computations spanning several hours or days.
Such scenarios call for a *dynamic* participation model for MPC where participants have the flexibility to go offline as needed and (re)join when they have available computational resources. Such a model would also democratize access to privacy-preserving computation by facilitating an ``MPC-as-a-service'' paradigm --- the deployment of MPC in volunteer-operated networks (such as blockchains, where dynamism is inherent) that perform computation on behalf of clients.
In this work, we initiate the study of *fluid MPC*, where parties can dynamically join and leave the computation. The minimum commitment required from each participant is referred to as *fluidity*, measured in the number of rounds of communication that it must stay online. Our contributions are threefold:
- We provide a formal treatment of fluid MPC, exploring various possible modeling choices.
- We construct information-theoretic fluid MPC protocols in the honest-majority setting. Our protocols achieve *maximal fluidity*, meaning that a party can exit the computation after receiving and sending messages in one round.
- We implement our protocol and test it in multiple network settings.

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.

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.

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).

2006

EPRINT

Identity-Based Proxy Re-encryption
Abstract

In a proxy re-encryption scheme a semi-trusted proxy converts a ciphertext for Alice into a ciphertext for Bob {\em without} seeing the underlying plaintext. A number of solutions have
been proposed in the public-key setting. In this paper, we address the problem of Identity-Based proxy re-encryption, where ciphertexts are transformed from one {\it identity} to another. Our schemes are compatible with current IBE deployments and do not require any extra work from the IBE trusted-party key generator. In addition, they are non-interactive and one of them permits multiple re-encryptions. Their security is based on a standard assumption (DBDH) in the random oracle model.

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

Correlation-Resistant Storage via Keyword-Searchable Encryption
Abstract

We consider the problem of using untrusted components to build correlation-resistant survivable storage systems that protect file replica locations, while allowing nodes to continuously re-distribute files throughout the network. The principal contribution is a chosen-ciphertext secure, searchable public key encryption scheme which allows for dynamic re-encryption of ciphertexts, and provides for node-targeted searches based on keywords or other identifiers. The scheme is provably secure under the SXDH assumption which holds in certain subgroups of elliptic curves, and a closely related assumption that we introduce.

#### Program Committees

- Crypto 2017
- PKC 2015
- PKC 2012

#### Coauthors

- Jae Hyun Ahn (1)
- Giuseppe Ateniese (2)
- Lucas Ballard (1)
- Eli Ben-Sasson (1)
- David Cash (1)
- Alessandro Chiesa (2)
- Arka Rai Choudhuri (1)
- Scott E. Coull (1)
- Anna Lisa Ferrara (1)
- Kevin Fu (1)
- Christina Garman (1)
- Aarushi Goel (1)
- Susan Hohenberger (12)
- Abhishek Jain (1)
- Gabriel Kaptchuk (2)
- Jingcheng Liu (1)
- Breno de Medeiros (1)
- Peihan Miao (1)
- Ian Miers (2)
- Pratyush Mishra (1)
- Fabian Monrose (1)
- Michael Østergaard Pedersen (1)
- Eran Tromer (1)
- Gijs Van Laer (1)
- Madars Virza (1)