Location: Engineering bldg. 1102 room #2 (ground floor)
The event is also carried out at: https://us02web.zoom.us/j/82587497200
Schedule:
!3:30-14:00: Welcome & Light snacks
14:00 – 14:45: Hila Dahari (Weizmann Institute of Science)
14:45 – 15:00: break
15:00 – 15:45: Yonatan Karidi (Tel Aviv University) (Video)
15:45 – 16:00: break
16:00 – 16:45: Uri Stemmer (Ben-Gurion University) (Video)
Title: Towards Accountability in CRS Generation
Speaker: Hila Dahary, Weizmann Institute of Science
It is well known that several cryptographic primitives cannot be achieved without a common reference string (CRS). Those include, for instance, non-interactive zero-knowledge for NP, or maliciously secure computation in fewer than four rounds. The security of those primitives heavily relies upon on the assumption that the trusted authority, who generates the CRS, does not misuse the randomness used in the CRS generation. However, we argue that there is no such thing as an unconditionally trusted authority and every authority must be held accountable for any trust to be well-founded. Indeed, a malicious authority can, for instance, recover private inputs of honest parties given transcripts of the protocols executed with respect to the CRS it has generated. While eliminating trust in the trusted authority may not be entirely feasible, can we at least move towards achieving some notion of accountability? We propose a new notion in which, if the CRS authority releases the private inputs of protocol executions to others, we can then provide a publicly-verifiable proof that certifies that the authority misbehaved. We study the feasibility of this notion in the context of non-interactive zero knowledge and two-round secure two-party computation.
Joint work with Prabhanjan Ananth, Gilad Asharov and Vipul Goyal.
_______________________________________________________________________
Title: A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip
Speaker: Yonatan Karidi, Tel Aviv University
In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems ’83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS ’85], the parties communicate over a broadcast channel and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n-party majority protocol is resilient to O(\sqrt{n}) corruptions (ignoring poly-logarithmic factors), and conjectured this is a tight upper bound for any n-party protocol (of any round complexity). Their conjecture was proved to be correct for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein, Linial and Saks [Combinatorica ’89], symmetric protocols Goldwasser, Tauman Kalai and Park [ICALP ’15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai, Komargodski and Raz [DISC ’18]. Yet, the question for many-turn protocols was left completely open.
In this work we close the above gap, proving that no n-party protocol (of any round complexity) is resilient to \omega(n) (adaptive) corruptions.
A joint work with Iftach Haitner.
_______________________________________________________________________
Title: Adversarial Streaming, Differential Privacy, and Adaptive Data Analysis
Speaker: Uri Stemmer, Ben-Gurion University
IStreaming algorithms are algorithms for processing large data streams, using only a limited amount of memory. Classical streaming algorithms typically work under the assumption that the input stream is chosen independently from the internal state of the algorithm. Recently, there is a growing interest in studying streaming algorithms that maintain utility also when the input stream is chosen by an adaptive adversary, possibly as a function of previous estimates given by the streaming algorithm. Such streaming algorithms are said to be adversarially-robust. In this talk I will highlight two connections with adversarial streaming: A connection with the notion of differential privacy (leading to positive results for adversarial streaming) and a connection with the recent line of work on adaptive data analysis (leading to negative results for adversarial streaming).
This talk is based on joint works with Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Kobbi Nissim.
Posted by