More Like this

1. Bounded Collusion ABE for TMs from IBE

   Goyal, Rishab ; Syed, Ridwan ; Waters, Brent ( December 2021 , Asiacrypt 2021)

   We give an attribute-based encryption system for Turing Machines that is provably secure assuming only the existence of identity-based 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 Diffie-Hellman 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 »however, to prove security we need to introduce a new notion of security called iterated simulation security. We then show how to transform our core construction into one that is secure for an a-priori bounded number of key queries that can occur either before or after the challenge ciphertext. We do this by first showing how one can use a special type of non-committing encryption to transform a system that is secure only if a single key is chosen before the challenge ciphertext is declared into one where the single key can be requested either before or after the challenge ciphertext. We give a simple construction of this non-committing encryption from public key encryption in the Random Oracle Model. Next, one can apply standard combinatorial techniques to lift from single-key adaptive security to -key adaptive security.« less
2. Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and Simplification.

   https://doi.org/10.1007/978-3-030-77883-5_4  

   Gay, Romain ; Jain, Aayush ; Lin, Huijia ; Sahai, Amit ( January 2021 , EUROCRYPT)

   In this work, we study the question of what set of simple-to-state assumptions suffice for constructing functional encryption and indistinguishability obfuscation (IO), supporting all functions describable by polynomial-size circuits. Our work improves over the state-of-the-art 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 constant-degree polynomials over the integers, evaluated on the error of the LWE samples. In contrast, Boolean pseudorandom generators (PRGs) computable by constant-degree polynomials have been extensively studied since the work of Goldreichmore »(2000). (Goldreich and follow-up works study Boolean pseudorandom generators with constant-locality, which can be computed by constant-degree polynomials.) We show how to replace the novel pseudorandom objects over the integers used in previous works, with appropriate Boolean pseudorandom generators with sufficient stretch, when combined with LWE with binary error over suitable parameters. Both binary error LWE and constant degree Goldreich PRGs have been a subject of extensive cryptanalysis since much before our work and thus we back the plausibility of our assumption with security against algorithms studied in context of cryptanalysis of these objects. New Techniques: we introduce a number of new techniques: – We show how to build partially-hiding public-key functional encryption, supporting degree-2 functions in the secret part of the message, and arithmetic NC1 functions over the public part of the message, assuming only standard assumptions over asymmetric pairing groups. – We construct single-ciphertext secret-key functional encryption for all circuits with linear key generation, assuming only the LWE assumption. Simplification: Unlike prior works, our new techniques furthermore let us construct public-key functional encryption for polynomial-sized circuits directly (without invoking any bootstrapping theorem, nor transformation from secret-key to public key FE), and based only on the polynomial hardness of underlying assumptions. The functional encryption scheme satisfies a strong notion of efficiency where the size of the ciphertext grows only sublinearly in the output size of the circuit and not its size. Finally, assuming that the underlying assumptions are subexponentially hard, we can bootstrap this construction to achieve iO.« less
3. Indistinguishability obfuscation from well-founded assumptions.

   Jain, Aayush ; Lin, Huijia ; Sahai, Amit ( January 2021 , STOC)

   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 well-founded assumptions. We prove: Informal Theorem: Let 𝜏∈ (0,∞), 𝛿∈ (0,1), 𝜖∈ (0,1) be arbitrary constants. Assume sub-exponential security of the following assumptions: - the Learningmore »With Errors (LWE) assumption with subexponential modulus-to-noise ratio 2^{𝑘^𝜖} and noises of magnitude polynomial in 𝑘,where 𝑘 is the dimension of the LWE secret, - the Learning Parity with Noise (LPN) assumption over general prime fields Z𝑝 with polynomially many LPN samples and error rate 1/ℓ^𝛿 ,where ℓ is the dimension of the LPN secret, - the existence of a Boolean Pseudo-Random Generator (PRG) in NC0 with stretch 𝑛^{1+𝜏}, where 𝑛 is the length of the PRG seed, - the Decision Linear (DLIN) assumption on symmetric bilinear groups of prime order. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.« less
4. On the Communication Complexity of Key-Agreement Protocols

   Haitner, Iftach ; Mazor, Noam ; Oshman, Rotem ; Reingold, Omer ; Yehudayoff, Amir ( January 2019 , Innovations in Theoretical Computer Science Conference)

   In a key-agreement 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 key-agreement protocols whose security is based on “public-key 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 key-agreement protocols can only guarantee limited secrecy: the key of any `l-query protocol can be revealed by an O(l^2 )-query adversary, a bound that matches the gapmore »obtained by the Merkle’s Puzzles two-message protocol of Merkle [CACM ’78]. While this quadratic gap might not seem like much, if the honest parties are willing to work “hard enough” and given continuousness improvement in common hash functions evaluation time, this gap yields a good enough advantage (assuming the security of the protocol holds when initiating the random function with a fixed hash function). In this work we consider the communication complexity of ROM key-agreement protocols. In Merkle’s Puzzles, the honest parties need to exchange Ω(l) bits (ignoring logarithmic factors) to obtain secrecy against an eavesdropper that makes roughly l^2 queries, which makes the protocol unrealizable in many settings. We show that for protocols with certain natural properties, such high communication is unavoidable. Specifically, this is the case if the honest parties’ queries are independent and uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Since two-round key-agreement protocol are equivalent to public-key encryption scheme (seeing the first message as the public-key), the latter result bounds the public-key and encryption size of public-key encryption scheme whose security is proven in the ROM.« less
5. Resource-Efficient Common Randomness and Secret-Key Schemes

   Ghazi, Badih ; Jayram, T.S. ( January 2018 , Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   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 resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicitmore »schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space. Read More: https://epubs.siam.org/doi/10.1137/1.9781611975031.120« less