GTACS@BIU 28/4/2021

Location: Engineering bldg. 1102 room #2 (ground floor)

The event is also carried out at:


!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