Workshop Details

Many efficient cryptographic schemes, especially in symmetric cryptography, are built from simpler building blocks such as hash functions and block ciphers, which are in turn assumed to satisfy a wide range of security properties.

Applied cryptographers have spent significant thought towards the goal of finding a simpler universal building block. In particular, a recent trend has been to base efficient symmetric cryptography on (keyless) permutations, i.e., efficiently computable and invertible one-to-one functions. From a practical standpoint, this has been very successful -- permutations have been used to build hash functions (e.g, SHA-3), authenticated encryption schemes, PRNGs, MACs, garbling schemes, and much more. From a theoretical perspective, however, the state of affairs is somewhat unsatisfactory: No good standard-model assumptions are known on such permutations, and it is unclear what kind of cryptographic hardness they provide. Security proofs for permutation-based cryptography thus inevitably end up making strong ideal assumptions on them, i.e., assuming the permutation to be random.

Our work initiates the study of security assumptions on permutations. In particular, similar to the complexity-theoretic treatment of hash functions, we enhance such permutations with a public seed, and introduce a definitional framework for the security of seeded permutations. The resulting notion, called public-seed pseudorandom permutations (or psPRP, for short), is rich in applications and an interesting object of theoretical study. This talk will give an overview, and highlight a number of open questions in the area.

Joint work with Pratik Soni.

Mutlilinear maps are extremely powerful objects that imply the holy grail of general purpose indistinguishability obfuscation (IO). A fundamental goal is identifying the lowest degree of multilinearity that suffice for constructing IO, answering, in particular, whether bilinear maps are sufficient for IO, and if not what is the magic degree that makes the important difference. The state-of-the-art (Lin, EUROCRYPT'16, ePrint'16; Lin and Vaikunthanathan, FOCS'16; Ananth and Sahai, EUROCRYPT'17) is that assuming the existence of pseudo-random generators (PRG) with output locality L, L-linear maps suffice for constructing IO. However, these works do not shed light on the power of multilinear maps with degree L < 5, as no polynomial-stretch PRG with locality lower than 5 exists.

In this work, we make progress towards the fundamental goal by showing that trilinear maps are sufficient for constructing IO, assuming the existence of PRGs with block-wise locality 3 and subexponential LWE. A PRG has block-wise locality L if every output bit depends on at most L (disjoint) input blocks, each consisting of up to log λ input bits. Concretely, we give:

A construction of a general-purpose indistinguishability obfuscator from L-linear maps and a subexponentially-secure PRG with block-wise locality L and polynomial stretch.

A construction of general-purpose functional encryption from L-linear maps and any slightly super-polynomially secure PRG with block-wise locality L and polynomial stretch.

All our constructions are based on the SXDH assumption on L-linear maps and subexponential Learning With Errors (LWE) assumption.

Concurrently, we initiate the study of candidate PRGs with block-wise locality based on Goldreich's local functions, and their (in)security. In particular, we show that the security of instantiations with block-wise locality L ≥ 3 is backed by similar validation as constructions with (conventional) locality 5. We further complement this with hardness amplification techniques that weaken the pseudorandomness requirement on our candidates to qualitatively weaker requirements.

Our result implies that any advance in instantiating multilinear maps beyond the bilinear case would lead to the holy grail of IO. We leave open the question whether bilinear maps are sufficient for IO or trilinear maps are inherently needed.

Lin and Tessaro (Eprint 2017/250) recently proposed indistinguishability obfuscation and functional encryption candidates and proved their security based on a standard assumption on bilinear maps and a non-standard assumption on "Goldreich-like" pseudorandom generators (PRG). In a nutshell, they require the existence of pseudo-random generators G : Sigma^n to {0,1}^m for some poly(n)-size alphabet Sigma where each output bit depends on at most two input alphabet symbols, and which achieve sufficiently large stretch. We show a polynomial-time attack against such generators. Our attack uses tools from the literature on two-source extractors (Chor and Goldreich, SICOMP 1988) and efficient refutation of 2-CSPs over large alphabets (Allen, O'Donnell and Witmer, FOCS 2015).

Joint work with Alex Lombardi (MIT).

Knowledge assumptions have been studied for almost three decades now. They have lead to strong applications such as round-efficient protocols and succinct non-interactive proofs, which are now widely used in crypto currencies and contracts. There is no significant evidence against their correctness. Yet, we continue to dislike them.

In this talk, I will survey our current knowledge of these assumptions including: definitions and abstractions, applications, limitations, why we don't like them, and the possibility of reducing them to assumptions that we do like.

In a recent result, Dachman-Soled et al.~(TCC '15) proposed a new notion called locally decodable and updatable non-malleable codes, which informally, provides the security guarantees of a non-malleable code while also allowing for efficient random access. They also considered locally decodable and updatable non-malleable codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering. Unfortunately, the locality of their construction in the continual setting was Omega(log n), meaning that if the original message size was n, then Omega(log n) positions of the codeword had to be accessed upon each decode and update instruction.

In this work, we ask whether super-constant locality is inherent in this setting. We answer the question affirmatively by showing tight upper and lower bounds. Specifically, in any threat model which allows for a rewind attack-wherein the attacker leaks a small amount of data, waits for the data to be overwritten and then writes the original data back-we show that a locally decodable and updatable non-malleable code with block size Chi in poly(lambda) number of bits requires locality delta(n) in omega(1), where n = poly(lambda) is message length and lambda is security parameter. On the other hand, we re-visit the threat model of Dachman-Soled et al.~(TCC '15)-which indeed allows the adversary to launch a rewind attack-and present a construction of a locally decodable and updatable non-malleable code with block size Chi in Omega(lambda^{1/mu}) number of bits (for constant 0 < mu < 1) with locality delta(n), for any delta(n) in omega(1), and n = poly(lambda).

Joint work with Mukul Kulkarni and Aria Shahverdi.

In this talk, we will describe the recent progress on proving lower-bounds on assumptions behind Indistinguishability Obfuscations.
1. We start by discussing fully-black-box separations for IO from basic primitives such as collision-resistant hash functions (or "random oracle-based" primitives in general).
2. Then, in light of recent *positive* results on basing IO on functional encryption [Bitansky-Vaikuntanathan16,Ananth-Jain16] which are *not* black-box, we will see a more "extended" model of black-box constructions that covers constructions such as [BV16,AJ16]. The model is general and applies to "self eating" primitives (including IO itself) that accept generic circuits as inputs.
3. Finally, we will discuss some new lower bounds for IO in this model from primitives such as witness encryption and predicate encryption.

Based on several joint works with: Sanjam Garg, Ameer Mohammed, Soheil Nematihaji, Rafael Pass, Abhi Shelat.

This will be a tutorial on how various notions of computational entropy can be useful in understanding, simplifying, and improving constructions of cryptographic primitives. We will focus on the case of constructing pseudorandom generators from one-way functions. We will begin with revisiting the classic construction of pseudorandom generators from one-way permutations using this modern perspective, relating one-wayness to "guessing pseudoentropy", which in turn can be turned into pseudorandomness via "reconstructive extractors". Then we will turn to constructions of pseudorandom generators from general one-way functions. Here we will relate one-wayness to "sampling relative entropy," which in turn can be related to "(HILL) pseudoentropy," which can also be converted to pseudorandomness via randomness extractors. Time permitting, we will sketch how this approach yields a construction of pseudorandom generators with a seed length of O~(n^3) from a one-way function with input length n [Haitner-Reingold-Vadhan \`10, Vadhan-Zheng \`11], and discuss potential approaches for improved positive or negative results.

A homomorphic secret sharing (HSS) scheme is a secret sharing scheme that supports a compact local evaluation of functions of the shared secret. For the purpose of applications of HSS, it is useful to make the stronger requirement that the output can be reconstructed via addition. That is, if a secret s is split into shares s_1,...,s_m, then f(s) can be written as F(s_1)+...+F(s_m) for some efficiently computable F, where addition is over a finite abelian group.

The talk will survey the state of the art on HSS and its applications, focusing mainly on: (1) computationally secure 2-out-of-2 HSS schemes for simple function classes using any one-way function, and (2) similar HSS schemes for branching programs from the DDH assumption. These can provide alternatives to fully homomorphic encryption in the context of minimizing the communication complexity and round complexity of secure computation.

Based on joint works with Elette Boyle and Niv Gilbo.

We will provide historical perspective on assumptions used in bilinear maps and survey some recent attempts to extend them to the multilinear setting.