A succinct non-interactive argument (SNARG) for NP allows a prover to convince a verifier that an NP statement x is true with a proof of size o(|x| + |w|), where w is the associated NP witness. A SNARG satisfies adaptive soundness if the malicious prover can choose the statement to prove after seeing the scheme parameters. In this work, we provide the first adaptively-sound SNARG for NP in the plain model assuming sub-exponentially-hard indistinguishability obfuscation, sub-exponentially-hard one-way functions, and either the (polynomial) hardness of the discrete log assumption or the (polynomial) hardness of factoring. This gives the first adaptively-sound SNARG for NP from falsifiable assumptions. All previous SNARGs for NP in the plain model either relied on non-falsifiable cryptographic assumptions or satisfied a weak notion of non-adaptive soundness (where the adversary has to choose the statement it proves before seeing the scheme parameters).

We put forward a new approach for achieving non-interactive zero-knowledge proofs (NIKZs) from the learning with errors (LWE) assumption (with subexponential modulus to noise ratio). We provide a LWE-based construction of a hidden bits generator that gives rise to a NIZK via the celebrated hidden bits paradigm. A notable feature of our construction is its simplicity. Our construction employs lattice trapdoors, but beyond that uses only simple operations. Unlike prior solutions, we do not rely on a correlation intractability argument nor do we utilize fully homomorphic encryption techniques. Our solution provides a new methodology that adds to the diversity of techniques for solving this fundamental problem.

Suppose a user wants to broadcast an encrypted message to K recipients. With public-key encryption, the sender would construct K different ciphertexts, one for each recipient. The size of the broadcasted message then scales linearly with K. A natural question is whether the sender can encrypt the message with a ciphertext whose size scales \em sublinearly with the number of recipients.

We introduce a new technique, that we call punctured programs, to apply indistinguishability obfuscation towards cryptographic problems. We use this technique to carry out a systematic study of the applicability of indistinguishability obfuscation to a variety of cryptographic goals. Along the way, we resolve the 16-year-old open question of deniable encryption, posed by Canetti et al. in 1997: In deniable encryption, a sender who is forced to reveal to an adversary both her message and the randomness she used for encrypting it should be able to convincingly provide “fake” randomness that can explain any alternative message that she would like to pretend that she sent. We resolve this question by giving the first construction of deniable encryption that does not require any preplanning by the party that must later issue a denial. In addition, we show the generality of our punctured programs technique by also constructing a variety of core cryptographic objects from indistinguishability obfuscation and one-way functions (or close variants). In particular we obtain public-key encryption, short “hash-and-sign” selectively secure signatures, chosen-ciphertext secure public-key encryption, noninteractive zero knowledge arguments and injective trapdoor functions. These results suggest the possibility of indistinguishability obfuscation becoming a “central hub” for cryptography.

Pairing-based cryptography is widely used for its efficiency and functionality. When designing pairing-based schemes, one common task is to devise algorithms for verifying a set of untrusted group elements with respect to a set of trusted group elements. One might be searching for a verification algorithm for a signature scheme or a method for verifying an IBE/ABE private key with respect to the IBE/ABE public parameters. In ACM CCS 2019 Hohenberger Vusirikala, the AutoPPE software tool was introduced for automatically generating a set of pairing product equations (PPEs) that can verify the correctness of a set of pairing group elements with respect to a set of trusted group elements. This task is non-trivial. Some schemes (e.g., those based on dual system encryption) provably do not support any efficient algorithm for verifying the private keys with respect to the public parameters. Other schemes (e.g., the Boyen-Waters anonymous IBE) were left in a gray area by Hohenberger-Vusirikala (CCS 19) -- no conjunction of PPEs was known for testing them, but no proof of untestability either.

In this work we provide a traitor tracing construction with ciphertexts that grow polynomially in log(n) where n is the number of users and prove it secure under the Learning with Errors (LWE) assumption. This is the first traitor tracing scheme with such parameters provably secure from a standard assumption. In addition to achieving new traitor tracing results, we believe our techniques push forward the broader area of computing on encrypted data under standard assumptions. Notably, traitor tracing is substantially different problem from other cryptography primitives that have seen recent progress in LWE solutions.

In this paper we introduce the notion of lockable obfuscation. In a lockable obfuscation scheme there exists an obfuscation algorithm Obf that takes as input a security parameter, a program P, a message msg and lock value lck and outputs an obfuscated program oP. One can evaluate the obfuscated program oP on any input x where the output of evaluation is the message msg if P(x) = lck and otherwise receives a rejecting symbol. We proceed to provide a construction of lockable obfuscation and prove it secure under the Learning with Errors (LWE) assumption. Notably, our proof only requires LWE with polynomial hardness and does not require complexity leveraging. We follow this by describing multiple applications of lockable obfuscation. First, we show how to transform any attribute-based encryption (ABE) scheme into one in which the attributes used to encrypt the message are hidden from any user that is not authorized to decrypt the message. (Such a system is also know as predicate encryption with one-sided security.) The only previous construction due to Gorbunov, Vaikuntanathan and Wee is based off of a specific ABE scheme of Boneh. By enabling the transformation of any ABE scheme we can inherent different forms and features of the underlying scheme such as: multi-authority, adaptive security from polynomial hardness, regular language policies, etc. We also show applications of lockable obfuscation to separation and uninstantiability results. We first show how to create new separation results in circular encryption that were previously based on indistinguishability obfuscation. This results in new separation results from learning with error including a public key bit encryption scheme that it IND-CPA secure and not circular secure. The tool of lockable obfuscation allows these constructions to be almost immediately realized by translation from previous indistinguishability obfuscation based constructions. In a similar vein we provide random oracle uninstantiability results of the Fujisaki-Okamoto transformation (and related transformations) from the lockable obfuscation combined with fully homomorphic encryption. Again, we take advantage that previous work used indistinguishability obfuscation that obfuscated programs in a form that could easily be translated to lockable obfuscation.

Time-lock puzzles are a mechanism for sending messages "to the future". A sender can quickly generate a puzzle with a solution s that remains hidden until a moderately large amount of time t has elapsed. The solution s should be hidden from any adversary that runs in time significantly less than t, including resourceful parallel adversaries with polynomially many processors.

In this work, we study indistinguishability obfuscation and functional encryption for general circuits: Indistinguishability obfuscation requires that given any two equivalent circuits $C_0$ and $C_1$ of similar size, the obfuscations of $C_0$ and $C_1$ should be computationally indistinguishable. In functional encryption, ciphertexts encrypt inputs $x$ and keys are issued for circuits $C$. Using the key $\mathrm{SK}_C$ to decrypt a ciphertext $\mathrm{CT}_x={\sf Enc}(x)$ yields the value $C(x)$ but does not reveal anything else about $x$. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually. We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps: (1) We describe a candidate construction for indistinguishability obfuscation for $\mathbf{NC}^1$ circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call multilinear jigsaw puzzles. (2) We show how to use indistinguishability obfuscation for $\mathbf{NC}^1$ together with fully homomorphic encryption (with decryption in $\mathbf{NC}^1$) to achieve indistinguishability obfuscation for all circuits. (3) Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and noninteractive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.

We revisit the question of constructing secure general-purpose indistinguishability obfuscation, with a security reduction based on explicit computational assumptions over multilinear maps. Previous to our work, such reductions were only known to exist based on meta-assumptions and/or ad-hoc assumptions: In the original constructive work of Garg et al. (FOCS 2013), the underlying explicit computational assumption encapsulated an exponential family of assumptions for each pair of circuits to be obfuscated. In the more recent work of Pass et al. (Crypto 2014), the underlying assumption is a meta-assumption that also encapsulates an exponential family of assumptions, and this meta-assumption is invoked in a manner that captures the specific pair of circuits to be obfuscated. The assumptions underlying both these works substantially capture (either explicitly or implicitly) the actual structure of the obfuscation mechanism itself. In our work, we provide the first construction of general-purpose indistinguishability obfuscation proven secure via a reduction to a natural computational assumption over multilinear maps, namely, the Multilinear Subgroup Elimination Assumption. This assumption does not depend on the circuits to be obfuscated (except for its size), and does not correspond to the underlying structure of our obfuscator. The technical heart of our paper is our reduction, which gives a new way to argue about the security of indistinguishability obfuscation.

We show how to build indistinguishability obfuscation (iO) for Turing Machines where the overhead is polynomial in the security parameter λ, machine description |M| and input size |x| (with only a negligible correctness error). In particular, we avoid growing polynomially with the maximum space of a computation. Our construction is based on iO for circuits, one way functions and injective pseudo random generators.

Randomized encodings of functions can be used to replace a “complex” function $f(x)$ by a “simpler” randomized mapping $\hat{f}(x;r)$ whose output distribution on an input $x$ encodes the value of $f(x)$ and hides any other information about $x$. One desirable feature of randomized encodings is low online complexity. That is, the goal is to obtain a randomized encoding $\hat{f}$ of $f$ in which most of the output can be precomputed and published before seeing the input $x$. When the input $x$ is available, it remains to publish only a short string $\hat{x}$, where the online complexity of computing $\hat{x}$ is independent of (and is typically much smaller than) the complexity of computing $f$. Yao's garbled circuit construction gives rise to such randomized encodings in which the online part $\hat{x}$ consists of $n$ encryption keys of length $\kappa$ each, where $n=|x|$ and $\kappa$ is a security parameter. Thus, the online rate $|\hat{x}|/|x|$ of this encoding is proportional to the security parameter $\kappa$. In this paper, we show that the online rate can be dramatically improved. Specifically, we show how to encode any polynomial-time computable function $f:\{0,1\}^n\to\{0,1\}^{m(n)}$ with online rate of $1+o(1)$ and with nearly linear online computation. More concretely, the online part $\hat{x}$ consists of an $n$-bit string and a single encryption key. These constructions can be based on the decisional Diffie--Hellman (DDH) assumption, the learning with errors (LWE) assumption, or the RSA assumption. We also present a variant of this result which applies to arithmetic formulas, where the encoding only makes use of arithmetic operations, as well as several negative results which complement our positive results. Our positive results can lead to efficiency improvements in most contexts where randomized encodings of functions are used. We demonstrate this by presenting several concrete applications. These include protocols for secure multiparty computation and for noninteractive verifiable computation in the preprocessing model which achieve, for the first time, an optimal online communication complexity, as well as noninteractive zero-knowledge proofs which simultaneously minimize the online communication and the prover's online computation.

In this work we explore new techniques for building short signatures from obfuscation. Our goals are twofold. First, we would like to achieve short signatures with adaptive security proofs. Second, we would like to build signatures with fast signing, ideally significantly faster than comparable signatures that are not based on obfuscation. The goal here is to create an "imbalanced'' scheme where signing is fast at the expense of slower verification.

We introduce a new technique, that we call punctured programs, to apply indistinguishability obfuscation towards cryptographic problems. We use this technique to carry out a systematic study of the applicability of indistinguishability obfuscation to a variety of cryptographic goals. Along the way, we resolve the 16-year-old open question of Deniable Encryption, posed by Canetti, Dwork, Naor, and Ostrovsky in 1997: In deniable encryption, a sender who is forced to reveal to an adversary both her message and the randomness she used for encrypting it should be able to convincingly provide "fake" randomness that can explain any alternative message that she would like to pretend that she sent. We resolve this question by giving the first construction of deniable encryption that does not require any pre-planning by the party that must later issue a denial.

We propose two large universe Attribute-Based Encryption constructions. In a large universe ABE system any string can be used as an attribute and attributes need not be enumerated at system setup. Our first construction establishes a novel large universe Ciphertext-Policy ABE scheme on prime order bilinear groups, while the second achieves a significant efficiency improvement over the large universe Key-Policy ABE system of Lewko-Waters and Lewko. Both schemes are selectively secure in the standard model under two ``q-type'' assumptions similar to ones used in prior works. Our work brings back ``program and cancel'' techniques to this problem and aims in providing practical large universe ABE implementations. To showcase the efficiency improvements over prior constructions, we provide implementations and benchmarks of our schemes in Charm; a programming environment for rapid prototyping of cryptographic primitives. We compare them to implementations of the only three published constructions that offer unbounded ABE in the standard model.

In this work, we study indistinguishability obfuscation and functional encryption for general circuits: Indistinguishability obfuscation requires that given any two equivalent circuits C0and C1of similar size, the obfuscations of C0and C1should be computationally indistinguishable. In functional encryption, cipher texts encrypt inputs x and keys are issued for circuits C. Using the key SKCto decrypt a cipher text CTx= Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually. We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps: - (1) We describe a candidate construction for indistinguishability obfuscation for NC1circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles. (2) We show how to use indistinguishability obfuscation for NC1together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits. (3) Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct cipher texts, which enables several other applications.

We present the design, security proof, and implementation of an anonymous subscription service. Users register for the service by providing some form of identity, which might or might not be linked to a real-world identity such as a credit card, a web login, or a public key. A user logs on to the system by presenting a credential derived from information received at registration. Each credential allows only a single login in any authentication window, or epoch. Logins are anonymous in the sense that the service cannot distinguish which user is logging in any better than random guessing. This implies unlinkability of a user across different logins. We find that a central tension in an anonymous subscription service is the service provider's desire for a long epoch (to reduce server-side computation) versus users' desire for a short epoch (so they can repeatedly "re-anonymize" their sessions). We balance this tension by having short epochs, but adding an efficient operation for clients who do not need unlinkability to cheaply re-authenticate themselves for the next time period. We measure performance of a research prototype of our protocol that allows an independent service to offer anonymous access to existing services. We implement a music service, an Android-based subway-pass application, and a web proxy, and show that adding anonymity adds minimal client latency and only requires 33 KB of server memory per active user.

We put forth the concept of witness encryption. A witness encryption scheme is defined for an NP language L (with corresponding witness relation R). In such a scheme, a user can encrypt a message M to a particular problem instance x to produce a ciphertext. A recipient of a ciphertext is able to decrypt the message if x is in the language and the recipient knows a witness w where R(x,w) holds. However, if x is not in the language, then no polynomial-time attacker can distinguish between encryptions of any two equal length messages. We emphasize that the encrypter himself may have no idea whether $x$ is actually in the language. Our contributions in this paper are threefold. First, we introduce and formally define witness encryption. Second, we show how to build several cryptographic primitives from witness encryption. Finally, we give a candidate construction based on the NP-complete Exact Cover problem and Garg, Gentry, and Halevi's recent construction of "approximate" multilinear maps.

Secure Computation of Face Identification (SCiFI) [20] is a recently developed secure face recognition system that ensures the list of faces it can identify (e.g., a terrorist watch list) remains private. In this work, we study the consequences of malformed input attacks on the system - from both a security and computer vision standpoint. In particular, we present 1) a cryptographic attack that allows a dishonest user to undetectably obtain a coded representation of faces on the list, and 2) a visualization approach that exploits this breach, turning the lossy recovered codes into human-identifiable face sketches. We evaluate our approach on two challenging datasets, with face identification tasks given to a computer and human subjects. Whereas prior work considered security in the setting of honest inputs and protocol execution, the success of our approach underscores the risk posed by malicious adversaries to todays automatic face recognition systems.

We put forward the notion of targeted malleability: given a homomorphic encryption scheme, in various scenarios we would like to restrict the homomorphic computations one can perform on encrypted data. We introduce a precise framework, generalizing the foundational notion of non-malleability introduced by Dolev, Dwork, and Naor (SICOMP '00), ensuring that the malleability of a scheme is targeted only at a specific set of "allowable" functions.

We consider the question of how to store a value secretly on devices that continually leak information about their internal state to an external attacker. If the secret value is stored on a single device from which it is efficiently retrievable, and the attacker can leak even a single predicate of the internal state of that device, then she may learn some information about the secret value itself. Therefore, we consider a setting where the secret value is shared between multiple devices (or multiple components of a single device), each of which continually leaks arbitrary adaptively chosen predicates its individual state. Since leakage is continual, each device must also continually update its state so that an attacker cannot just leak it entirely one bit at a time. In our model, the devices update their state individually and asynchronously, without any communication between them. The update process is necessarily randomized, and its randomness can leak as well. As our main result, we construct a sharing scheme for two devices, where a constant fraction of the internal state of each device can leak in between and during updates. Our scheme has the structure of a public-key encryption, where one share is a secret key and the other is a ciphertext. As a contribution of independent interest, we also get public-key encryption in the continual leakage model, introduced by Brakerski et al. and Dodis et al. (FOCS '10). This scheme tolerates continual leakage on the secret key and the updates, and simplifies the recent construction of Lewko, Lewko and Waters (STOC '11). For our main result, we show how to update the ciphertexts of the encryption scheme so that the message remains hidden even if an attacker interleaves leakage on secret key and ciphertext shares. The security of our scheme is based on the linear assumption in prime-order bilinear groups. We also provide an extension to general access structures realizable by linear secret sharing schemes across many devices. The main advantage of this extension is that the state of some devices can be compromised entirely, while that of the all remaining devices is susceptible to continual leakage. Lastly, we show impossibility of information theoretic sharing schemes in our model, where continually leaky devices update their state individually.

In the continual memory leakage model, security against attackers who can repeatedly obtain leakage is achieved by periodically updating the secret key. This is an appealing model which captures a wide class of side-channel attacks, but all previous constructions in this model provide only a very minimal amount of leakage tolerance during secret key updates. Since key updates may happen frequently, improving security guarantees against attackers who obtain leakage during these updates is an important problem. In this work, we present the first cryptographic primitives which are secure against a super-logarithmic amount of leakage during secret key updates. We present signature and public key encryption schemes in the standard model which can tolerate a constant fraction of the secret key to be leaked between updates as well as a constant fraction of the secret key and update randomness to be leaked during updates. Our signature scheme also allows us to leak a constant fraction of the entire secret state during signing. Before this work, it was unknown how to tolerate super-logarithmic leakage during updates even in the random oracle model. We rely on subgroup decision assumptions in composite order bilinear groups.

We propose a general cryptographic primitive called lossy trapdoor functions (lossy TDFs), and we use it to develop new approaches for constructing several important cryptographic tools, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems (in the standard model). All of these constructions are simple, efficient, and black-box. We realize lossy TDFs based on a variety of cryptographic assumptions, including the hardness of the decisional Diffie–Hellman (DDH) problem and the hardness of the “learning with errors” problem (which is implied by the worst-case hardness of various lattice problems). Taken together, our results resolve some long-standing open problems in cryptography. They give the first injective TDFs based on problems not directly related to integer factorization and provide the first chosen ciphertext-secure cryptosystem based solely on worst-case complexity assumptions.

We design the first Leakage-Resilient Identity-Based Encryption (LR-IBE) systems from static assumptions in the standard model. We derive these schemes by applying a hash proof technique from Alwen et.al. (Eurocrypt '10) to variants of the existing IBE schemes of Boneh-Boyen, Waters, and Lewko-Waters. As a result, we achieve leakage-resilience under the respective static assumptions of the original systems in the standard model, while also preserving the efficiency of the original schemes. Moreover, our results extend to the Bounded Retrieval Model (BRM), yielding the first regular and identity-based BRM encryption schemes from static assumptions in the standard model.

In [8,9] Boneh et al. presented the first fully collusion-resistant traitor tracing and trace & revoke schemes. These schemes are based on composite order bilinear groups and their security depends on the hardness of the subgroup decision assumption.

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 ℓ bits of leakage, we can take n copies of it to form a system tolerating nℓ 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 ℓ 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ℓ bits renders the system insecure. Our results hold either in composite order bilinear groups under a variant of the subgroup decision assumption 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.

In this work, we design a method for creating public key broadcast encryption systems. Our main technical innovation is based on a new "two equation" technique for revoking users. This technique results in two key contributions: First, 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. In addition, the public key allows us to encrypt to an unbounded number of users. Our system is the first to achieve such parameters. We give two versions of our scheme: a simpler version which we prove to be selectively secure in the standard model under a new, but non-interactive assumption, and another version that employs the new dual system encryption technique of Waters to obtain adaptive security under the d-BDH and decisional Linear assumptions. Second, we show that our techniques can be used to realize Attribute-Based Encryption (ABE) systems with nonmonotonic access formulas, where our key storage is significantly more efficient than previous solutions. This result is also proven selectively secure in the standard model under our new non-interactive assumption.

Attributes define, classify, or annotate the datum to which they are assigned. However, traditional attribute architectures and cryptosystems are ill-equipped to provide security in the face of diverse access requirements and environments. In this paper, we introduce a novel secure information management architecture based on emerging attribute-based encryption (ABE) primitives. A policy system that meets the needs of complex policies is defined and illustrated. Based on the needs of those policies, we propose cryptographic optimizations that vastly improve enforcement efficiency. We further explore the use of such policies in two proposed applications: a HIPAA compliant distributed file system and a social network. A performance analysis and characterization of ABE primitives demonstrates the ability to reduce cryptographic costs by as much as 98% over previously proposed constructions. Through this, we demonstrate that our attribute system is an efficient solution for securely managing information in large, loosely-coupled, distributed systems.

In this paper, we generalize Naor and Reingold's construction of pseudorandom functions under the DDH Assumption [22] to yield a construction of pseudorandom functions under the decisional k-Linear Assumption, for each k › 1. The decisional Linear Assumption was first introduced by Boneh, Boyen, and Shacham in [5] as an alternative assumption for settings where the DDH problem is easy, such as bilinear groups. Shacham [25] and Hofheinz and Kiltz [16] independently introduced the generalized decisional k-Linear Assumptions and showed that the decisional (k+1)-Linear problem is hard for generic groups even when the decisional k-Linear problem is easy. It is thus desirable to have constructions of cryptographic primitives based on the decisional k-Linear Assumption instead of DDH. Not surprisingly, one must pay a small price for added security: as k increases, our constructed functions become slightly less efficient to compute and the key size increases (quadratically in k).

A system for private stream searching, introduced by Ostrovsky and Skeith, allows a client to provide an untrusted server with an encrypted search query. The server uses the query on a stream of documents and returns the matching documents to the client while learning nothing about the nature of the query. We present a new scheme for conducting private keyword search on streaming data which requires O ( m ) server to client communication complexity to return the content of the matching documents, where m is an upper bound on the size of the documents. The required storage on the server conducting the search is also O ( m ). The previous best scheme for private stream searching was shown to have O ( m log m ) communication and storage complexity. Our solution employs a novel construction in which the user reconstructs the matching files by solving a system of linear equations. This allows the matching documents to be stored in a compact buffer rather than relying on redundancies to avoid collisions in the storage buffer as in previous work. This technique requires a small amount of metadata to be returned in addition to the documents; for this the original scheme of Ostrovsky and Skeith may be employed with O ( m log m ) communication and storage complexity. We also present an alternative method for returning the necessary metadata based on a unique encrypted Bloom filter construction. This method requires O ( m log( t / m )) communication and storage complexity, where t is the number of documents in the stream. In this article we describe our scheme, prove it secure, analyze its asymptotic performance, and describe a number of extensions. We also provide an experimental analysis of its scalability in practice. Specifically, we consider its performance in the demanding scenario of providing a privacy preserving version of the Google News Alerts service.

A well-known concern in the setting of identity based encryption is that the PKG is all powerful and has to be completely trusted. To mitigate this problem, the notion of Accountable Authority Identity-Based Encryption (A-IBE) was recently introduced by Goyal. Goyal provided constructions to realize the notion of A-IBE only in the white box and weak black box models. However, the security guarantees provided by these models fall short of those required in practice.

We ask whether an Identity Based Encryption (IBE) system can be built from simpler public-key primitives. We show that there is no black-box construction of IBE from Trapdoor Permutations (TDP) or even from Chosen Ciphertext Secure Public Key Encryption (CCA-PKE). These black-box separation results are based on an essential property of IBE, namely that an IBE system is able to compress exponentially many public-keys into a short public parameters string.

Several important security protocols require parties to perform computations based on random challenges. Traditionally, proving that the challenges were randomly chosen has required interactive communication among the parties or the existence of a trusted server. We offer an alternative solution where challenges are harvested from oblivious servers on the Internet. This paper describes a framework for deriving “harvested challenges ” by mixing data from various pre-existing online sources. While individual sources may become predictable or fall under adversarial control, we provide a policy language that allows application developers to specify combinations of sources that meet their security needs. Participants can then convince each other that their challenges were formed freshly and in accordance with the policy. We present Combine, an open source implementation of our framework, and show how it can be applied to a variety of applications, including remote storage auditing and non-interactive client puzzles.

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.

In several distributed systems a user should only be able to access data if a user posses a certain set of credentials or attributes. Currently, the only method for enforcing such policies is to employ a trusted server to store the data and mediate access control. However, if any server storing the data is compromised, then the confidentiality of the data will be compromised. In this paper we present a system for realizing complex access control on encrypted data that we call ciphertext-policy attribute-based encryption. By using our techniques encrypted data can be kept confidential even if the storage server is untrusted; moreover, our methods are secure against collusion attacks. Previous attribute-based encryption systems used attributes to describe the encrypted data and built policies into user's keys; while in our system attributes are used to describe a user's credentials, and a party encrypting data determines a policy for who can decrypt. Thus, our methods are conceptually closer to traditional access control methods such as role-based access control (RBAC). In addition, we provide an implementation of our system and give performance measurements.

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

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.

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 subsumesHierarchical Identity-Based Encryption (HIBE).

Attributes define, classify, or annotate the datum to which they are assigned. However, traditional attribute architectures and cryptosystems are ill-equipped to provide security in the face of diverse access requirements and environments. In this paper, we introduce a novel secure information management architecture based on emerging attribute-based encryption (ABE) primitives. A policy system that meets the needs of complex policies is defined and illustrated. Based on the needs of those policies, we propose cryptographic optimizations that vastly improve enforcement efficiency. We further explore the use of such policies in two example applications: a HIPAA compliant distributed file system and a social network. A performance analysis of our ABE system and example applications demonstrates the ability to reduce cryptographic costs by as much as 98% over previously proposed constructions. Through this, we demonstrate that our attribute system is an efficient solution for securely managing information in large, loosely-coupled, distributed systems.

A system for private stream searching allows a client to retrieve documents matching some search criteria from a remote server while the server evaluating the request remains provably oblivious to the search criteria. In this extended abstract, we give a high level outline of a new scheme for this problem and an experimental analysis of its scalability. The new scheme is highly efficient in practice. We demonstrate the practical applicability of the scheme by considering its performance in the demanding scenario of providing a privacy preserving version of the Google News Alerts service

We describe a new encryption technique that is secure in the standard model against chosen ciphertext 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 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.

Computer users are asked to generate, keep secret, and recall an increasing number of passwords for uses including host accounts, email servers, e-commerce sites, and online financial services. Unfortunately, the password entropy that users can comfortably memorize seems insufficient to store unique, secure passwords for all these accounts, and it is likely to remain constant as the number of passwords (and the adversary's computational power) increases into the future. In this paper, we propose a technique that uses a strengthened cryptographic hash function to compute secure passwords for arbitrarily many accounts while requiring the user to memorize only a single short password. This mechanism functions entirely on the client; no server-side changes are needed. Unlike previous approaches, our design is both highly resistant to brute force attacks and nearly stateless, allowing users to retrieve their passwords from any location so long as they can execute our program and remember a short secret. This combination of security and convenience will, we believe, entice users to adopt our scheme. We discuss the construction of our algorithm in detail, compare its strengths and weaknesses to those of related approaches, and present Password Multiplier, an implementation in the form of an extension to the Mozilla Firefox web browser.

We explore new techniques for the use of cryptographic puzzles as a countermeasure to Denial-of-Service (DoS) attacks. We propose simple new techniques that permit the out-sourcing of puzzles; their distribution via a robust external service that we call a bastion. Many servers can rely on puzzles distributed by a single bastion. We show how a bastion, somewhat surprisingly, need not know which servers rely on its services. Indeed, in one of our constructions, a bastion may consist merely of a publicly accessible random data source, rather than a special purpose server. Our out-sourcing techniques help eliminate puzzle distribution as a point of compromise.

We describe a new method for protecting the anonymity of message receivers in an untrusted network. Surprisingly, existing methods fail to provide the required level of anonymity for receivers (although those methods do protect sender anonymity). Our method relies on the use of multicast, along with a novel cryptographic primitive that we call an Incomparable Public Key cryptosystem, which allows a receiver to efficiently create many anonymous "identities" for itself without divulging that these separate "identities" actually refer to the same receiver, and without increasing the receiver's workload as the number of identities increases. We describe the details of our method, along with a prototype implementation.