Title: A Survey of Computational Assumptions on Bilinear and Multilinear Maps

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

Title: Our Current Knowledge of Knowledge Assumptions

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.

Title: Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-Malleable Codes

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.

Title: Homomorphic Secret Sharing

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 Gilboa

Title: Indistinguishability Obfuscation from Trilinear Maps and Block-Wise Local PRGs

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.

Title: Black-box and Non-black-box Lower Bounds on Assumptions behind IO

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.

Title: Attacks on Blockwise Local PRGs and Indistinguishability Obfuscation

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