Vinod Vaikuntanathan

Title: Extracting Randomness from Extractor-Dependent Sources

Abstract: The vast literature on seeded extractors have given us ways to extract randomness from any source with min-entropy, assuming the availability of a short, truly random seed which is "unknown" to the source. Crucially, the fact that the source does not "know" the seed has allowed us to dig our way out of simple impossibility results for deterministic extraction. In this talk, we will (a) argue that this assumption does not hold in nature; and (b) show several ways to extract randomness from "extractor-dependent" sources together with matching impossibility results.

Joint work with Yevgeniy Dodis and Daniel Wichs.

Shai Halevi

Title: Instances of Practical (F)HE: NFA Encryption, Compressible HE, and PIR

Abstract: In this talk I will describe a set of related techniques, making it possible to devise practically efficient (F)HE-based solutions to some interesting problems. These techniques include manipulating encrypted matrices, compressing HE ciphertexts, and simple instances of switching between different HE cryptosystems. I will show how they can be used to get practical encrypted nondeterministic finite automata (as needed in some malware scanning applications), and for private information retrieval (PIR).

Based on join works with Nicholas Genise, Craig Gentry, Baiyu Li, and Daniele Micciancio

Jens Groth

Title: Why should I believe that?

Abstract: “On the Internet nobody knows you’re a dog”, the saying goes. The expression epitomizes the realization that very little can be trusted in the digital world and new technology such as deepfakes may worsen the situation. Attack-resilient technologies in the blockchain space and cryptography may counter this threat. Zero-knowledge proofs for instance enable the creation of convincing evidence attesting to the truth of a digital claim, and they do so without compromising privacy. Cryptographic solutions, however, also rely on assumptions and trust. We will in this talk discuss the foundation of trust in the context of non-interactive zero-knowledge proofs.

Yael Kalai

Title: No-Signaling Proofs, Their Applications, and Their Power

Abstract: No-signaling is an intriguing notion motivated by quantum mechanics. In this talk I will explain the related notion of no-signaling multi-prover interactive proofs (MIPs), and will show interesting applications to cryptography and hardness of approximation. Specifically, first we will see how such proofs can be used to obtain succinct and efficiently verifiable (single prover) proofs for the correctness of any (deterministic) computation [K-Raz-Rothblum 2014]. Then we will see how it can be used to prove that the value of a linear program cannot be approximated by a small space algorithm [K-Raz-Regev 2017]. Finally, we will discuss the power of such proof systems.

It is known that no-signaling MIPs with poly(n) provers are characterized by EXP [K-Raz-Rothblum 2014], and no-signaling MIPs with 2 provers are characterized by PSPACE. Until recently, the power of k-prover no-signaling proofs, for 2<k<poly(n) remained an open problem. In this talk, we will see that k-prover no-signaling proofs (with negligible soundness) for k=O(\sqrt{log n}) are contained in PSPACE [Holden-K 2019].

Tal Malkin

Title: Limits to Non-Malleability

Abstract: There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. Here we ask the following question: "When can we rule out the existence of a non-malleable code for a tampering class F?"

First, we start with some classes where positive results are well-known, and show that when these classes are extended in a natural way, non-malleable codes are no longer possible. Specifically, we show that no non-malleable codes exist for any of the following tampering classes: (1) Functions that change d/2 symbols, where d is the distance of the code; (2) Functions where each input symbol affects only a single output symbol; (3) Functions where each of the n output bits is a function of n−logn input bits.

Furthermore, we rule out constructions of non-malleable codes for certain classes F via reductions to the assumption that a distributional problem is hard for F, that make black-box use of the tampering functions in the proof. In particular, this yields concrete obstacles for the construction of efficient codes for NC, even assuming average-case variants of P⊈NC.

Based on joint work with Marshall Ball, Dana Dachman-Soled, and Mukul Kulkarni.

Moni Naor

Title: Distributed Verifiers: Interactive Proofs and Zero-knowledge

Abstract: We explore the power of interactive proofs with a distributed verifier. Unlike the standard centralized setting, with one prover and one verifier who has access to all the data, here the data are distributed among n verifiers sitting in the nodes of a graph G that defines their communication pattern. The prover is a single entity that communicates with all nodes by exchanging (short) messages. The goal is to verify that the data plus the graph G belong to some language in a small number of rounds and with short messages.

We suggest a new general framework for distributed interactive proofs that allows one to translate standard interactive protocols to ones where the verifier is distributed with a proof size that depends on the computational complexity of the verification algorithm run by the centralized verifier.

One of the main tools we construct is a compiler that takes any (centralized) computation performed in time O(n) on a RAM and translates it into a three-round distributed interactive protocol with O(log n) proof size. The transformation is based on memory checking. We extend this compiler to languages that can be computed in small space or by a small depth circuit as well.

We demonstrate the power of our compiler for specific problems such as Graph Non-Isomorphism, Clique and Leader Election.

We explore obtaining zero-knowledge protocols in this setting as well as using cryptographic techniques for removing interaction.

Joint work with Hila Dahari, Merav Parter and Eylon Yogev

Yuval Ishai

Title: Homomorphic Secret Sharing

Abstract: A homomorphic secret sharing (HSS) scheme is a secret sharing scheme that allows locally mapping shares of a secret x to compact shares of a function of x. The talk will survey the current state of the art on HSS, covering efficient constructions, applications in cryptography and complexity theory, and open questions.