We give an attributebased encryption system for Turing Machines that is provably secure assuming only the existence of identitybased encryption (IBE) for large identity spaces. Currently, IBE is known to be realizable from most mainstream number theoretic assumptions that imply public key cryptography including factoring, the search DiffieHellman assumption, and the Learning with Errors assumption. Our core construction provides security against an attacker that makes a single key query for a machine before declaring a challenge string that is associated with the challenge ciphertext. We build our construction by leveraging a Garbled RAM construction of Gentry, Halevi, Raykova, and Wichs;more »
Output Compression, MPC, and iO for Turing Machines
In this work, we study the fascinating notion of outputcompressing 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 outputcompressing randomized encodings for Turing machines in the shared randomness model, assuming iO for circuits and any assumption in the set {LWE, DDH, N𝑡ℎ 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 malicioussecure 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 more »
 Publication Date:
 NSFPAR ID:
 10168542
 Journal Name:
 Advances in Cryptology ASIACRYPT 2019  25th International Conference on the Theory and Application of Cryptology and Information Securit
 Volume:
 11921
 Page Range or eLocationID:
 342370
 Sponsoring Org:
 National Science Foundation
More Like this


In this work, we study the question of what set of simpletostate assumptions suffice for constructing functional encryption and indistinguishability obfuscation (IO), supporting all functions describable by polynomialsize circuits. Our work improves over the stateoftheart work of Jain, Lin, Matt, and Sahai (Eurocrypt 2019) in multiple dimensions. New Assumption: Previous to our work, all constructions of IO from simple assumptions required novel pseudorandomness generators involving LWE samples and constantdegree polynomials over the integers, evaluated on the error of the LWE samples. In contrast, Boolean pseudorandom generators (PRGs) computable by constantdegree polynomials have been extensively studied since the work of Goldreichmore »

Indistinguishability obfuscation, introduced by [Barak et. al. Crypto2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four wellfounded assumptions. We prove: Informal Theorem: Let 𝜏∈ (0,∞), 𝛿∈ (0,1), 𝜖∈ (0,1) be arbitrary constants. Assume subexponential security of the following assumptions:  the Learningmore »

In a keyagreement protocol whose security is proven in the random oracle model (ROM), the parties and the eavesdropper can make bounded number of queries to a shared random function (an “oracle”). Such protocol are the alternative to keyagreement protocols whose security is based on “publickey assumptions”, assumptions that being more structured are presumingly more vulnerable to attacks. Barak and Mahmoody [Crypto ’09] (following Impagliazzo and Rudich [STOC ’89]) have shown the ROM keyagreement protocols can only guarantee limited secrecy: the key of any `lquery protocol can be revealed by an O(l^2 )query adversary, a bound that matches the gapmore »

We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resourceefficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicitmore »