In the framework of the Theory Fest event (December 29th 2019 - January 3rd 2020 link to the event) at Tel-Aviv University, a cryptography workshop supported by the PROMETHEUS project is organized on December 31th 2019.

**Workshop Program****08:30** Registration & Coffee

**09:15** **Vinod Vaikuntanathan, MIT****Title: ** A New Connection between Data Structure Lower Bounds and Cryptography**Abstract:** We show a new connection between (static) data structure lower bounds and the problem of constructing cryptographic objects secure in the presence of (lots of) preprocessing. Focusing then on specific problems, e.g., the problem of 3SUM with preprocessing, we show new algorithms, lower-bounds and cryptographic applications.

Work with Sasha Golovnev, Thibaut Horel, Siyao Guo and Sunoo Park.

**10:00 Shai Halevi, Algorand Foundation****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.

**coffee break - 25min**

**11:05 Jens Groth, Dfinity****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.

**11:50 Yael Kalai, MSR New England****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].

*lunch - 1.5hrs*

**14:00 Hugo Krawczyk, Algorand Foundation****Title: ** Passwords are Cool**Abstract:** Password authentication is the shallowest, most boring and inherently insecure cryptographic primitive. Or, is it?

In this talk we will review recent results on password authentication and password management that may challenge the above conventional wisdom.

**14:45 Tal Malkin, Columbia University****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.

*coffee break - 25min*

**15:50 Moni Naor, Weizmann Inst****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.

**16:35 Yuval Ishai, Technion****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.

See the bio of each speaker in the complete program in the website of the workshop.