## CryptoDB

### Brent Waters

#### Affiliation: UT Austin

#### Publications

**Year**

**Venue**

**Title**

2019

CRYPTO

ABE for DFA from k-Lin
📺
Abstract

We present the first attribute-based encryption (ABE) scheme for deterministic finite automaton (DFA) based on static assumptions in bilinear groups; this resolves an open problem posed by Waters (CRYPTO 2012). Our main construction achieves selective security against unbounded collusions under the standard k-linear assumption in prime-order bilinear groups, whereas previous constructions all rely on q-type assumptions.

2019

PKC

Collusion Resistant Broadcast and Trace from Positional Witness Encryption
Abstract

An emerging trend is for researchers to identify cryptography primitives for which feasibility was first established under obfuscation and then move the realization to a different setting. In this work we explore a new such avenue—to move obfuscation-based cryptography to the assumption of (positional) witness encryption. Our goal is to develop techniques and tools, which we will dub “witness encryption friendly” primitives and use these to develop a methodology for building advanced cryptography from positional witness encryption.We take a bottom up approach and pursue our general agenda by attacking the specific problem of building collusion-resistant broadcast systems with tracing from positional witness encryption. We achieve a system where the size of ciphertexts, public key and private key are polynomial in the security parameter $$\lambda $$ and independent of the number of users N in the broadcast system. Currently, systems with such parameters are only known from indistinguishability obfuscation.

2019

CRYPTO

Realizing Chosen Ciphertext Security Generically in Attribute-Based Encryption and Predicate Encryption
📺
Abstract

We provide generic and black box transformations from any chosen plaintext secure Attribute-Based Encryption (ABE) or One-sided Predicate Encryption system into a chosen ciphertext secure system. Our transformation requires only the IND-CPA security of the original ABE scheme coupled with a pseudorandom generator (PRG) with a special security property.In particular, we consider a PRG with an n bit input $$s \in \{0,1\}^n$$ and $$n \cdot \ell $$ bit output $$y_1, \ldots , y_n$$ where each $$y_i$$ is an $$\ell $$ bit string. Then for a randomly chosen s the following two distributions should be computationally indistinguishable. In the first distribution $$r_{s_i, i} = y_i$$ and $$r_{\bar{s}_i, i}$$ is chosen randomly for $$i \in [n]$$. In the second distribution all $$r_{b, i}$$ are chosen randomly for $$i \in [n], b \in \{0,1\}$$.We show that such PRGs can be built from either the computational Diffie-Hellman assumption (in non-bilinear groups) or the Learning with Errors (LWE) assumption (and potentially other assumptions). Thus, one can transform any IND-CPA secure system into a chosen ciphertext secure one by adding either assumption. (Or by simply assuming an existing PRG is hinting secure.) In addition, our work provides a new approach and perspective for obtaining chosen ciphertext security in the basic case of public key encryption.

2019

CRYPTO

Watermarking Public-Key Cryptographic Primitives
📺
Abstract

A software watermarking scheme enables users to embed a message or mark within a program while preserving its functionality. Moreover, it is difficult for an adversary to remove a watermark from a marked program without corrupting its behavior. Existing constructions of software watermarking from standard assumptions have focused exclusively on watermarking pseudorandom functions (PRFs).In this work, we study watermarking public-key primitives such as the signing key of a digital signature scheme or the decryption key of a public-key (predicate) encryption scheme. While watermarking public-key primitives might intuitively seem more challenging than watermarking PRFs, our constructions only rely on simple assumptions. Our watermarkable signature scheme can be built from the minimal assumption of one-way functions while our watermarkable public-key encryption scheme can be built from most standard algebraic assumptions that imply public-key encryption (e.g., factoring, discrete log, or lattice assumptions). Our schemes also satisfy a number of appealing properties: public marking, public mark-extraction, and collusion resistance. Our schemes are the first to simultaneously achieve all of these properties.The key enabler of our new constructions is a relaxed notion of functionality-preserving. While traditionally, we require that a marked program (approximately) preserve the input/output behavior of the original program, in the public-key setting, preserving the “functionality” does not necessarily require preserving the exact input/output behavior. For instance, if we want to mark a signing algorithm, it suffices that the marked algorithm still output valid signatures (even if those signatures might be different from the ones output by the unmarked algorithm). Similarly, if we want to mark a decryption algorithm, it suffices that the marked algorithm correctly decrypt all valid ciphertexts (but may behave differently from the unmarked algorithm on invalid or malformed ciphertexts). Our relaxed notion of functionality-preserving captures the essence of watermarking and still supports the traditional applications, but provides additional flexibility to enable new and simple realizations of this powerful cryptographic notion.

2019

CRYPTO

Broadcast and Trace with
$N^{\varepsilon }$
Ciphertext Size from Standard Assumptions
📺
Abstract

We construct a broadcast and trace scheme (also known as trace and revoke or broadcast, trace and revoke) with N users, where the ciphertext size can be made as low as
$$O(N^\varepsilon )$$
, for any arbitrarily small constant
$$\varepsilon >0$$
. This improves on the prior best construction of broadcast and trace under standard assumptions by Boneh and Waters (CCS ‘06), which had ciphertext size
$$O(N^{1/2})$$
. While that construction relied on bilinear maps, ours uses a combination of the learning with errors (LWE) assumption and bilinear maps.Recall that, in both broadcast encryption and traitor-tracing schemes, there is a collection of N users, each of which gets a different secret key
$${\mathsf {sk}}_i$$
. In broadcast encryption, it is possible to create ciphertexts targeted to a subset
$$S \subseteq [N]$$
of the users such that only those users can decrypt it correctly. In a traitor tracing scheme, if a subset of users gets together and creates a decoder box D that is capable of decrypting ciphertexts, then it is possible to trace at least one of the users responsible for creating D. A broadcast and trace scheme intertwines the two properties, in a way that results in more than just their union. In particular, it ensures that if a decoder D is able to decrypt ciphertexts targeted toward a set S of users, then it should be possible to trace one of the users in the set S responsible for creating D, even if other users outside of S also participated. As of recently, we have essentially optimal broadcast encryption (Boneh, Gentry, Waters CRYPTO ’05) under bilinear maps and traitor tracing (Goyal, Koppula, Waters STOC ’18) under LWE, where the ciphertext size is at most poly-logarithmic in N. The main contribution of our paper is to carefully combine LWE and bilinear-map based components, and get them to interact with each other, to achieve broadcast and trace.

2019

TCC

New Approaches to Traitor Tracing with Embedded Identities
Abstract

In a traitor tracing (TT) system for n users, every user has his/her own secret key. Content providers can encrypt messages using a public key, and each user can decrypt the ciphertext using his/her secret key. Suppose some of the n users collude to construct a pirate decoding box. Then the tracing scheme has a special algorithm, called $$\mathsf {Trace}$$, which can identify at least one of the secret keys used to construct the pirate decoding box.Traditionally, the trace algorithm output only the ‘index’ associated with the traitors. As a result, to use such systems, either a central master authority must map the indices to actual identities, or there should be a public mapping of indices to identities. Both these options are problematic, especially if we need public tracing with anonymity of users. Nishimaki, Wichs, and Zhandry (NWZ) [Eurocrypt 2016] addressed this problem by constructing a traitor tracing scheme where the identities of users are embedded in the secret keys, and the trace algorithm, given a decoding box D, can recover the entire identities of the traitors. We call such schemes ‘Embedded Identity Traitor Tracing’ schemes. NWZ constructed such schemes based on adaptively secure functional encryption (FE). Currently, the only known constructions of FE schemes are based on nonstandard assumptions such as multilinear maps and iO.In this work, we study the problem of embedded identities TT based on standard assumptions. We provide a range of constructions based on different assumptions such as public key encryption (PKE), bilinear maps and the Learning with Errors (LWE) assumption. The different constructions have different efficiency trade offs. In our PKE based construction, the ciphertext size grows linearly with the number of users; the bilinear maps based construction has sub-linear ($$\sqrt{n}$$) sized ciphertexts. Both these schemes have public tracing. The LWE based scheme is a private tracing scheme with optimal ciphertexts (i.e., $$\log (n)$$). Finally, we also present other notions of traitor tracing, and discuss how they can be build in a generic manner from our base embedded identity TT scheme.

2019

ASIACRYPT

Output Compression, MPC, and iO for Turing Machines
Abstract

In this work, we study the fascinating notion of output-compressing randomized encodings for Turing Machines, in a shared randomness model. In this model, the encoder and decoder have access to a shared random string, and the efficiency requirement is, the size of the encoding must be independent of the running time and output length of the Turing Machine on the given input, while the length of the shared random string is allowed to grow with the length of the output. We show how to construct output-compressing randomized encodings for Turing machines in the shared randomness model, assuming iO for circuits and any assumption in the set
$$\{$$
LWE, DDH, N
$$^{th}$$
Residuosity
$$\}$$
.We then show interesting implications of the above result to basic feasibility questions in the areas of secure multiparty computation (MPC) and indistinguishability obfuscation (iO): 1.Compact MPC for Turing Machines in the Random Oracle Model. In the context of MPC, we consider the following basic feasibility question: does there exist a malicious-secure MPC protocol for Turing Machines whose communication complexity is independent of the running time and output length of the Turing Machine when executed on the combined inputs of all parties? We call such a protocol as a compact MPC protocol. Hubácek and Wichs [HW15] showed via an incompressibility argument, that, even for the restricted setting of circuits, it is impossible to construct a malicious secure two party computation protocol in the plain model where the communication complexity is independent of the output length. In this work, we show how to evade this impossibility by compiling any (non-compact) MPC protocol in the plain model to a compact MPC protocol for Turing Machines in the Random Oracle Model, assuming output-compressing randomized encodings in the shared randomness model.2.Succinct iO for Turing Machines in the Shared Randomness Model. In all existing constructions of iO for Turing Machines, the size of the obfuscated program grows with a bound on the input length. In this work, we show how to construct an iO scheme for Turing Machines in the shared randomness model where the size of the obfuscated program is independent of a bound on the input length, assuming iO for circuits and any assumption in the set
$$\{$$
LWE, DDH, N
$$^{th}$$
Residuosity
$$\}$$
.

2018

CRYPTO

Risky Traitor Tracing and New Differential Privacy Negative Results
Abstract

In this work we seek to construct collusion-resistant traitor tracing systems with small ciphertexts from standard assumptions that also move toward practical efficiency. In our approach we will hold steadfast to the principle of collusion resistance, but relax the requirement on catching a traitor from a successful decoding algorithm. We define a f-risky traitor tracing system as one where the probability of identifying a traitor is $$f(\lambda ,n)$$f(λ,n) times the probability a successful box is produced. We then go on to show how to build such systems from prime order bilinear groups with assumptions close to those used in prior works. Our core system achieves, for any $$k > 0$$k>0, $$f(\lambda ,n) \approx \frac{k}{n + k - 1}$$f(λ,n)≈kn+k-1 where ciphertexts consists of $$(k + 4)$$(k+4) group elements and decryption requires $$(k + 3)$$(k+3) pairing operations.At first glance the utility of such a system might seem questionable since the f we achieve for short ciphertexts is relatively small. Indeed an attacker in such a system can more likely than not get away with producing a decoding box. However, we believe this approach to be viable for four reasons:1.A risky traitor tracing system will provide deterrence against risk averse attackers. In some settings the consequences of being caught might bear a high cost and an attacker will have to weigh his utility of producing a decryption D box against the expected cost of being caught.2.Consider a broadcast system where we want to support low overhead broadcast encrypted communications, but will periodically allow for a more expensive key refresh operation. We refer to an adversary produced algorithm that maintains the ability to decrypt across key refreshes as a persistent decoder. We show how if we employ a risky traitor tracing systems in this setting, even for a small f, we can amplify the chances of catching such a “persistent decoder” to be negligibly close to 1.3.In certain resource constrained settings risky traitor tracing provides a best tracing effort where there are no other collusion-resistant alternatives. For instance, suppose we had to support 100 K users over a radio link that had just 10 KB of additional resources for extra ciphertext overhead. None of the existing $$\sqrt{N}$$N bilinear map systems can fit in these constraints. On the other hand a risky traitor tracing system provides a spectrum of tracing probability versus overhead tradeoffs and can be configured to at least give some deterrence in this setting.4.Finally, we can capture impossibility results for differential privacy from $$\frac{1}{n}$$1n-risky traitor tracing. Since our ciphertexts are short ($$O(\lambda )$$O(λ)), we get the negative result which matches what one would get plugging in the obfuscation based tracing system Boneh-Zhandry [9] solution into the prior impossibility result of Dwork et al. [14].

2018

TCC

Upgrading to Functional Encryption
Abstract

The notion of Functional Encryption (FE) has recently emerged as a strong primitive with several exciting applications. In this work, we initiate the study of the following question: Can existing public key encryption schemes be “upgraded” to Functional Encryption schemes without changing their public keys or the encryption algorithm? We call a public-key encryption scheme with this property to be FE-compatible. Indeed, assuming ideal obfuscation, it is easy to see that every CCA-secure public-key encryption scheme is FE-compatible. Despite the recent success in using indistinguishability obfuscation to replace ideal obfuscation for many applications, we show that this phenomenon most likely will not apply here. We show that assuming fully homomorphic encryption and the learning with errors (LWE) assumption, there exists a CCA-secure encryption scheme that is provably not FE-compatible. We also show that a large class of natural CCA-secure encryption schemes proven secure in the random oracle model are not FE-compatible in the random oracle model.Nevertheless, we identify a key structure that, if present, is sufficient to provide FE-compatibility. Specifically, we show that assuming sub-exponentially secure iO and sub-exponentially secure one way functions, there exists a class of public key encryption schemes which we call Special-CCA secure encryption schemes that are in fact, FE-compatible. In particular, each of the following popular CCA secure encryption schemes (some of which existed even before the notion of FE was introduced) fall into the class of Special-CCA secure encryption schemes and are thus FE-compatible:1.[CHK04] when instantiated with the IBE scheme of [BB04].2.[CHK04] when instantiated with any Hierarchical IBE scheme.3.[PW08] when instantiated with any Lossy Trapdoor Function.

2018

TCC

Impossibility of Simulation Secure Functional Encryption Even with Random Oracles
Abstract

In this work we study the feasibility of achieving simulation security in functional encryption (FE) in the random oracle model. Our main result is negative in that we give a functionality for which it is impossible to achieve simulation security even with the aid of random oracles.We begin by giving a formal definition of simulation security that explicitly incorporates the random oracles. Next, we show a particular functionality for which it is impossible to achieve simulation security. Here messages are interpreted as seeds to a (weak) pseudorandom function family F and private keys are ascribed to points in the domain of the function. On a message s and private key x one can learn F(s, x). We show that there exists an attacker that makes a polynomial number of private key queries followed by a single ciphertext query for which there exists no simulator.Our functionality and attacker access pattern closely matches the standard model impossibility result of Agrawal, Gorbunov, Vaikuntanathan and Wee (CRYPTO 2013). The crux of their argument is that no simulator can succinctly program in the outputs of an unbounded number of evaluations of a pseudorandom function family into a fixed size ciphertext. However, their argument does not apply in the random oracle setting since the oracle acts as an additional conduit of information which the simulator can program. We overcome this barrier by proposing an attacker who decrypts the challenge ciphertext with the secret keys issued earlier without using the random oracle, even though the decryption algorithm may require it. This involves collecting most of the useful random oracle queries in advance, without giving the simulator too many opportunities to program.On the flip side, we demonstrate the utility of the random oracle in simulation security. Given only public key encryption and low-depth PRGs we show how to build an FE system that is simulation secure for any poly-time attacker that makes an unbounded number of message queries, but an a-priori bounded number of key queries. This bests what is possible in the standard model where it is only feasible to achieve security for an attacker that is bounded both in the number of key and message queries it makes. We achieve this by creating a system that leverages the random oracle to get one-key security and then adapt previously known techniques to boost the system to resist up to q queries.Finally, we ask whether it is possible to achieve simulation security for an unbounded number of messages and keys, but where all key queries are made after the message queries. We show this too is impossible to achieve using a different twist on our first impossibility result.

2018

TCC

Traitor-Tracing from LWE Made Simple and Attribute-Based
Abstract

A traitor tracing scheme is a public key encryption scheme for which there are many secret decryption keys. Any of these keys can decrypt a ciphertext; moreover, even if a coalition of users collude, put together their decryption keys and attempt to create a new decryption key, there is an efficient algorithm to trace the new key to at least one the colluders.Recently, Goyal, Koppula and Waters (GKW, STOC 18) provided the first traitor tracing scheme from LWE with ciphertext and secret key sizes that grow polynomially in $$\log n$$, where n is the number of users. The main technical building block in their construction is a strengthening of (bounded collusion secure) secret-key functional encryption which they refer to as mixed functional encryption (FE).In this work, we improve upon and extend the GKW traitor tracing scheme:We provide simpler constructions of mixed FE schemes based on the LWE assumption. Our constructions improve upon the GKW construction in terms of expressiveness, modularity, and security.We provide a construction of attribute-based traitor tracing for all circuits based on the LWE assumption.

2017

EUROCRYPT

2015

ASIACRYPT

2013

CRYPTO

2013

CRYPTO

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.

2012

CRYPTO

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

EUROCRYPT

2010

EPRINT

Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption
Abstract

In this paper, we present two fully secure functional encryption schemes. Our first result is a fully secure attribute-based encryption (ABE) scheme. Previous constructions of ABE were only proven to be selectively secure. We achieve full security by adapting the dual system encryption methodology recently introduced by Waters and previously leveraged to obtain fully secure IBE and HIBE systems. The primary challenge in applying dual system encryption to ABE is the richer structure of keys and ciphertexts. In an IBE or HIBE system, keys and ciphertexts are both associated with the same type of simple object: identities. In an ABE system, keys and ciphertexts are associated with more complex objects: attributes and access formulas. We use a novel information-theoretic argument to adapt the dual system encryption methodology to the more complicated structure of ABE systems. We construct our system in composite order bilinear groups, where the order is a product of three primes. We prove the security of our system from three static assumptions. Our ABE scheme supports arbitrary monotone access formulas.
Our second result is a fully secure (attribute-hiding) predicate encryption (PE) scheme for inner-product predicates. As for ABE, previous constructions of such schemes were only proven to be selectively secure. Security is proven under a non-interactive assumption whose size does not depend on the number of queries. The scheme is comparably efficient to existing selectively secure schemes. We also present a fully secure hierarchical PE scheme under the same assumption. The key technique used to obtain these results is an elaborate combination of the dual system encryption methodology (adapted to the structure of inner product PE systems) and a new approach on bilinear pairings using the notion of dual pairing vector spaces (DPVS) proposed by Okamoto and Takashima.

2010

EPRINT

Identity-Based Encryption Secure under Selective Opening Attack
Abstract

We present the first Identity-Based Encryption (IBE) scheme that is proven secure against
selective opening attack (SOA). This means that if an adversary, given a vector of ciphertexts, adaptively
corrupts some fraction of the senders, exposing not only their messages but also their coins, the privacy
of the unopened messages is guaranteed. Achieving security against such attacks is well-known to be
challenging and was only recently solved in the PKE case via lossy encryption. We explain why those
methods wont work for IBE and instead rely on an approach based on encryption schemes that have a
property we call one-sided public openability. Our SOA-secure IBE scheme is quite efficient and proven
secure without random oracles based on the Decision Linear assumption.

2010

EPRINT

Decentralizing Attribute-Based Encryption
Abstract

We propose a Multi-Authority Attribute-Based Encryption (ABE) system.
In our system, any party can become an authority and there is no
requirement for any global coordination other than the creation of an
initial set of common reference parameters. A party can simply act as
an ABE authority by creating a public key and issuing private keys to
different users that reflect their attributes. A user can encrypt
data in terms of any boolean formula over attributes issued from any
chosen set of authorities. Finally, our system does not require any
central authority.
In constructing our system, our largest technical hurdle is to make it collusion resistant. Prior Attribute-Based Encryption systems achieved collusion resistance when the ABE system authority ``tied'' together different components (representing different attributes) of a user's private key by randomizing the key. However, in our system each component will come from a potentially different authority, where we assume no coordination between such authorities. We create new techniques to tie key components together and prevent collusion attacks between users with different global identifiers.
We prove our system secure using the recent dual system encryption
methodology where the security proof works by first converting the
challenge ciphertexts and private keys to a semi-functional form and
then arguing security. We follow a recent variant of the dual system
proof technique due to Lewko and Waters and build our system using
bilinear groups of composite order. We prove security under similar
static assumptions to the LW paper in the random oracle model.

2010

EPRINT

On the Insecurity of Parallel Repetition for Leakage Resilience
Abstract

A fundamental question in leakage-resilient cryptography is: can leakage resilience always be amplified by parallel repetition? It is natural to expect that if we have a leakage-resilient primitive tolerating $\ell$ bits of leakage, we can take $n$ copies of it to form a system tolerating $n\ell$ bits of leakage. In this paper, we show that this is not always true. We construct a public key encryption system which is secure when at most $\ell$ bits are leaked, but if we take $n$ copies of the system and encrypt a share of the message under each using an $n$-out-of-$n$ secret-sharing scheme, leaking $n\ell$ bits renders the system insecure.
Our results hold either in composite order bilinear groups under a variant of the subgroup decision assumption \emph{or} in prime order bilinear groups under the decisional linear assumption. We note that the $n$ copies of our public key systems share a common reference parameter.

2010

EPRINT

Achieving Leakage Resilience Through Dual System Encryption
Abstract

In this work, we show that strong leakage resilience for cryptosystems with advanced functionalities can be obtained quite naturally within the methodology of dual system encryption, recently introduced by Waters. We demonstrate this concretely by providing fully secure IBE, HIBE, and ABE systems which are resilient to bounded leakage from each of many secret keys per user, as well as many master keys. This can be realized as resilience against continual leakage if we assume keys are periodically updated and no (or logarithmic) leakage is allowed during the update process. Our systems are obtained by applying a simple modification to previous dual system encryption constructions: essentially this provides a generic tool for making dual system encryption schemes leakage-resilient.

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

EUROCRYPT

2008

EPRINT

Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization
Abstract

We present new techniques for realizing Ciphertext-Policy Attribute
Encryption (CP-ABE) under concrete and noninteractive cryptographic
assumptions. Our solutions allow any encryptor to specify access
control in terms of an LSSS matrix, $M$, over the attributes in the
system. We present three different constructions that allow different
tradeoffs between the systems efficiency and the complexity of the
assumptions used. All three constructions use a common methodology of
``directly'' solving the CP-ABE problem that enable us to get much
better efficiency than prior approaches.

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

Adaptive Security in Broadcast Encryption Systems
Abstract

We present new techniques for achieving adaptive security
in broadcast encryption systems. Previous work on fully-collusion
resistant broadcast encryption with short ciphertexts was limited
to only considering static security.
First, we present a new definition of security that we call
semi-static security and show a generic ``two-key"
transformation from semi-statically secure systems to adaptively
secure ones that have comparable-sized ciphertexts. Using bilinear
maps, we then construct broadcast encryption systems that are
semi-statically secure in the standard model and have constant
size ciphertexts. Our semi-static constructions work when the
number of indices or identifiers in the system is polynomial in
the security parameter.
For identity-based broadcast encryption, where the number of
potential indices or identifiers may be exponential, we present
the first adaptively secure system with sublinear ciphertexts. We
prove security in the standard model.

2008

EPRINT

Delegating Capabilities in Predicate Encryption Systems
Abstract

In predicate encryption systems, given a capability, one can evaluate one or more predicates on the encrypted data, while all other information about the plaintext remains hidden. We consider the first such systems to permit delegation of capabilities. In a system that supports delegation, a user Alice who has a capability can delegate to Bob a more restrictive capability, which allows him to learn less about encrypted data than she did.
We formally define delegation in predicate encryption systems, and propose a new security definition for delegation. In addition, we present an efficient construction supporting conjunctive queries. The security of our construction can be reduced to the general 3-party Bilinear Diffie-Hellman assumption, and the Bilinear Decisional Diffie-Hellman assumption in composite-order bilinear groups.

2008

EPRINT

Revocation Systems with Very Small Private Keys
Abstract

In this work, we design a new public key broadcast encryption system,
and we focus on a critical parameter of device key size: the amount of
the cryptographic key material that must be stored securely on the
receiving devices. Our new scheme has ciphertext size overhead O(r),
where $r$ is the number of revoked users, and the size of public and
private keys is only a constant number of group elements from
an elliptic-curve group of prime order. All previous work, even in the
restricted case of systems based on symmetric keys, required at least
lg(n) keys stored on each device. In addition, we show that our
techniques can be used to realize Attribute-Based Encryption (ABE)
systems with non-monotonic access formulas, where are key storage is
significantly more efficient than previous solutions. Our results are
in the standard model under a new, but non-interactive, assumption.

2008

EPRINT

Compact Signatures for Network Coding
Abstract

Network coding offers increased throughput and improved robustness to random faults in completely decentralized networks. Since it does not require centralized control, network coding has been suggested for routing packets in ad-hoc networks, for content distribution in P2P file systems, and for improving the efficiency of large-scale data dissemination over the Internet.
In contrast to traditional routing schemes, however, network coding requires intermediate nodes to process and modify data packets en route. For this reason, standard signature schemes are inapplicable and it is therefore a challenge to provide resilience to tampering by malicious nodes in the network. Here, we propose a novel homomorphic signature scheme that can be used in conjunction with network coding to prevent malicious modification of data. The overhead of our scheme is small and independent of the file or packet size: both public keys and signatures in our scheme consist of only a single group element.

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

Attribute-Based Encryption with Non-Monotonic Access Structures
Abstract

We construct an Attribute-Based Encryption (ABE) scheme
that allows a user's private key to be expressed in terms
of any access formula over attributes. Previous ABE
schemes were limited to expressing only monotonic access structures. We provide a proof of security for our scheme based on the
Decisional Bilinear Diffie-Hellman (BDH) assumption.
Furthermore, the performance of our new scheme compares
favorably with existing, less-expressive schemes.

2007

EPRINT

Lossy Trapdoor Functions and Their Applications
Abstract

We propose a new general primitive called lossy trapdoor
functions (lossy TDFs), and realize it under a variety of different
number theoretic assumptions, including hardness of the decisional
Diffie-Hellman (DDH) problem and the worst-case hardness of
standard lattice problems.
Using lossy TDFs, we develop a new approach for constructing many
important cryptographic primitives, including standard trapdoor
functions, CCA-secure cryptosystems, collision-resistant hash
functions, and more. All of our constructions are simple, efficient,
and black-box.
Taken all together, these results resolve some long-standing open
problems in cryptography. They give the first known (injective)
trapdoor functions based on problems not directly related to integer
factorization, and provide the first known CCA-secure cryptosystem
based solely on worst-case lattice assumptions.

2007

EPRINT

A Framework for Efficient and Composable Oblivious Transfer
Abstract

We propose and simple, general, and unified framework for constructing
oblivious transfer (OT) protocols that are \emph{efficient},
\emph{universally composable}, and \emph{generally realizable} from a
variety of standard number-theoretic assumptions, such as the
decisional Diffie-Hellman assumption and the Quadratic Residuosity
assumption. Most interestingly, we can also instantiate our framework
with \emph{worst-case} complexity assumptions relating to
\emph{lattices}.
Our OT protocols are round-optimal (one message each way), efficient
in the parties' communication and local computation, and use only one
reference string for an unbounded number of executions. Furthermore,
the protocols can provide \emph{unconditional} security to either the
sender or receiver, simply by changing the distribution of the
reference string. (For several versions of the protocol, even a
common \emph{random} string suffices.)
One of our key technical contributions is a simple and novel
abstraction that we call a \emph{dual-mode} cryptosystem. We
implement dual-mode cryptosystems by taking a unified view of several
cryptosystems in the literature that have what we call
``message-lossy'' public keys, whose defining property is that a
ciphertext produced under such a key carries \emph{no information}
(even statistically) about the encrypted message.
As a contribution of independent interest, we also provide a multi-bit
version of Regev's lattice-based cryptosystem (STOC 2005) whose time
and space efficiency are improved by a linear factor. In particular,
the amortized runtime per message bit is only $\tilde{O}(n)$ bit
operations, and the ciphertext expansion can be made as small as a
constant.

2007

EPRINT

Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products
Abstract

Predicate encryption is a new paradigm generalizing, among other
things, identity-based encryption. In a predicate encryption scheme,
secret keys correspond to predicates and ciphertexts are associated
with attributes; the secret key SK_f corresponding to the predicate
f can be used to decrypt a ciphertext associated with attribute I if and only if f(I)=1. Constructions of such schemes are currently known for relatively few classes of predicates.
We construct such a scheme for predicates corresponding to the evaluation of inner products over N (for some large integer N).
This, in turn, enables constructions in which predicates correspond to the evaluation of disjunctions, polynomials, CNF/DNF formulae, or threshold predicates (among others). Besides serving as what we feel is a significant step forward in the theory of predicate encryption,
our results lead to a number of applications that are interesting in their own right.

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

Anonymous Hierarchical Identity-Based Encryption (Without Random Oracles)
Abstract

We present an identity-based cryptosystem that features fully anonymous ciphertexts and hierarchical key delegation. We give a proof of security in the standard model, based on the mild Decision Linear complexity assumption in bilinear groups. The system is efficient and practical, with small ciphertexts of size linear in the depth of the hierarchy. Applications include search on encrypted data, fully private communication, etc.
Our results resolve two open problems pertaining to anonymous identity-based encryption, our scheme being the first to offer provable anonymity in the standard model, in addition to being the first to realize fully anonymous HIBE at all levels in the hierarchy.

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

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

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.

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.

2006

EPRINT

Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data
Abstract

As more sensitive data is shared and stored by third-party sites on
the Internet, there will be a need to encrypt data stored at these
sites. One drawback of encrypting data, is that it can be
selectively shared only at a coarse-grained level (i.e., giving
another party your private key). We develop a new cryptosystem for
fine-grained sharing of encrypted data that we call Key-Policy
Attribute-Based Encryption (KP-ABE). In our cryptosystem, ciphertexts
are labeled with sets of attributes and private keys are associated
with access structures that control which ciphertexts a user is able
to decrypt. We demonstrate the applicability of our construction to
sharing of audit-log information and broadcast encryption. Our
construction supports delegation of private keys which subsumes
Hierarchical Identity-Based Encryption (HIBE).

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.

2005

EPRINT

Direct Chosen Ciphertext Security from Identity-Based Techniques
Abstract

We describe a new encryption technique that is secure in the standard model against adaptive chosen ciphertext (CCA2) attacks. We base our method on two very efficient Identity-Based Encryption (IBE) schemes without random oracles due to Boneh and Boyen, and Waters.
Unlike previous CCA2-secure cryptosystems that use IBE as a black box, our approach is endogenous, very simple, and compact. It makes direct use of the underlying IBE structure, and requires no cryptographic primitive other than the IBE scheme itself. This conveys several advantages. We achieve shorter ciphertext size than the best known instantiations of the other methods, and our technique is as efficient as the Boneh and Katz method (and more so than that of Canetti, Halevi, and Katz). Further, our method operates nicely on hierarchical IBE, and since it allows the validity of ciphertexts to be checked publicly, it can be used to construct systems with non-interactive threshold decryption.
In this paper we describe two main constructions: a full encryption system based on the Waters adaptive-ID secure IBE, and a KEM based on the Boneh-Boyen selective-ID secure IBE. Both systems are shown CCA2-secure in the standard model, the latter with a tight reduction. We discuss several uses and extensions of our approach, and draw comparisons with other schemes that are provably secure in the standard model.

2005

EPRINT

Compact Group Signatures Without Random Oracles
Abstract

We present the first efficient group signature scheme that is provably
secure without random oracles. We achieve this result by combining
provably secure hierarchical signatures in bilinear groups with a
novel adaptation of the recent Non-Interactive Zero Knowledge proofs
of Groth, Ostrovsky, and Sahai. The size of signatures in our scheme is
logarithmic in the number of signers; we prove it secure under the
Computational Diffie-Hellman and the Subgroup Decision assumptions in
the model of Bellare, Micciancio, and Warinshi, as relaxed by Boneh,
Boyen, and Shacham.

2004

EPRINT

Fuzzy Identity Based Encryption
Abstract

We introduce a new type of Identity-Based Encryption
(IBE) scheme that we call Fuzzy Identity-Based Encryption.
In Fuzzy IBE we view an identity as set of descriptive attributes.
A Fuzzy IBE scheme allows for a private key for an identity, $\omega$, to decrypt a ciphertext encrypted with an identity, $\omega'$, if
and only if the identities $\omega$ and $\omega'$ are close to each
other as measured by the ``set overlap'' distance metric.
A Fuzzy IBE scheme can be applied to enable encryption
using biometric inputs as identities; the error-tolerance property
of a Fuzzy IBE scheme is precisely what allows for the use of
biometric identities, which inherently will have some noise each
time they are sampled. Additionally, we show that Fuzzy-IBE can
be used for a type of application that we term ``attribute-based encryption''.
In this paper we present two constructions of Fuzzy IBE schemes. Our
constructions can be viewed as an Identity-Based Encryption of a
message under several attributes that compose a (fuzzy) identity.
Our IBE schemes are both error-tolerant and secure against collusion
attacks. Additionally, our basic construction does not use random
oracles. We prove the security of our schemes under the Selective-ID
security model.

2004

EPRINT

Efficient Identity-Based Encryption Without Random Oracles
Abstract

We present the first efficient Identity-Based Encryption
(IBE) scheme that is fully secure without random
oracles. We first present our IBE construction and reduce the
security of our scheme to the decisional Bilinear Diffie-Hellman
(BDH) problem. Additionally, we show that our techniques can be used
to build a new signature scheme that is secure under the
computational Diffie-Hellman assumption without random oracles.

#### Program Committees

- Eurocrypt 2019
- Eurocrypt 2017
- TCC 2016
- Crypto 2014
- Crypto 2010
- PKC 2010
- TCC 2009
- Crypto 2008
- Eurocrypt 2008
- Eurocrypt 2007
- Asiacrypt 2007

#### Coauthors

- Shashank Agrawal (1)
- Jae Hyun Ahn (2)
- Benny Applebaum (1)
- Saikrishna Badrinarayanan (2)
- Mihir Bellare (5)
- Allison Bishop (18)
- Nir Bitansky (1)
- Dan Boneh (16)
- Xavier Boyen (7)
- Jan Camenisch (2)
- Yilei Chen (1)
- Apoorvaa Deshpande (1)
- Rafael Dowsley (1)
- Rex Fernando (1)
- David Freeman (2)
- Sanjam Garg (1)
- Craig Gentry (9)
- Michael Gerbush (1)
- Shafi Goldwasser (1)
- Junqing Gong (1)
- Vipul Goyal (1)
- Rishab Goyal (9)
- Shai Halevi (1)
- Dennis Hofheinz (1)
- Susan Hohenberger (20)
- Yuval Ishai (1)
- Tibor Jager (1)
- Abhishek Jain (1)
- Jonathan Katz (5)
- Dakshita Khurana (3)
- Eike Kiltz (1)
- Sam Kim (1)
- Venkata Koppula (16)
- Eyal Kushilevitz (1)
- Steve Lu (2)
- Nathan Manohar (1)
- Qixiang Mei (1)
- Adam O'Neill (2)
- Tatsuaki Okamoto (4)
- Rafail Ostrovsky (3)
- Omkant Pandey (2)
- Omer Paneth (1)
- Chris Peikert (5)
- Krzysztof Pietrzak (2)
- Andrew Poelstra (1)
- Willy Quach (1)
- Kim Ramchen (3)
- Yannis Rouselakis (3)
- Andrew Russell (1)
- Amit Sahai (24)
- Hakan Seyalioglu (1)
- Hovav Shacham (8)
- Abhi Shelat (2)
- Emily Shen (3)
- Elaine Shi (2)
- Igors Stepanovs (1)
- Katsuyuki Takashima (2)
- Vinod Vaikuntanathan (4)
- Satyanarayana Vusirikala (1)
- Hoeteck Wee (2)
- Daniel Wichs (4)
- David J. Wu (1)
- Scott Yilek (3)
- Mark Zhandry (3)