Zoom link
https://us02web.zoom.us/j/82587497200
Campus map:
https://www2.biu.ac.il/Tour/campus-map.pdf
Schedule:
14:00-14:45 Hila Dahari
14:45-15:00 Break
15:00-15:45 Yonatan Karidi
15:45-16:00 Break
16:00-16:45 Uri Stemmer
Talks Details
Hila Dahari
Towards Accountabilityin CRS Generation
Abstract:
It is well known thatseveral cryptographic primitives cannot be achieved without a common referencestring (CRS). Those include, for instance, non-interactive zero-knowledge forNP, 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 CRSgeneration. However, we argue that there is no such thing as an unconditionallytrusted authority and every authority must be held accountable for any trust tobe well-founded. Indeed, a malicious authority can, for instance, recoverprivate inputs of honest parties given transcripts of the protocols executedwith respect to the CRS it has generated. While eliminating trust in thetrusted authority may not be entirely feasible, can we at least move towards achieving some notion of accountability? We propose a new notion in which, ifthe CRS authority releases the private inputs of protocol executions to others,we can then provide a publicly-verifiable proof that certifies that theauthority misbehaved. We study the feasibility of this notion in thecontext of non-interactive zero knowledge and two-round secure two-party computation.
Joint workwith Prabhanjan Ananth, Gilad Asharov and Vipul Goyal.
Yonatan Karidi
A Tight Lower Bound onAdaptively Secure Full-Information Coin Flip
Abstract:
In a distributedcoin-flipping protocol, Blum [ACM Transactions on Computer Systems '83], theparties try to output a common (close to) uniform bit, even when someadversarially chosen parties try to bias the common output. In an adaptivelysecure full-information coin flip, Ben-Or and Linial [FOCS '85], the partiescommunicate over a broadcast channel and a computationally unbounded adversarycan choose which parties to corrupt along the protocol execution. Ben-Or andLinial proved that the n-party majority protocol is resilient to O(\sqrt{n})corruptions (ignoring poly-logarithmic factors), and conjectured this is atight upper bound for any n-party protocol (of any round complexity). Theirconjecture was proved to be correct for single-turn (each party sends a singlemessage) single-bit (a message is one bit) protocols Lichtenstein, Linial andSaks [Combinatorica '89], symmetric protocols Goldwasser, Tauman Kalai and Park[ICALP '15], and recently for (arbitrary message length) single-turn protocolsTauman Kalai, Komargodski and Raz [DISC '18]. Yet, the question for many-turnprotocols was left completely open.
In this work weclose 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.
Uri Stemmer
Adversarial Streaming,Differential Privacy, and Adaptive Data Analysis
Abstract:
Streaming algorithms arealgorithms for processing large data streams, using only a limited amount ofmemory. Classical streaming algorithms typically work under the assumption thatthe input stream is chosen independently from the internal state of thealgorithm. Recently, there is a growing interest in studying streamingalgorithms that maintain utility also when the input stream is chosen by anadaptive adversary, possibly as a function of previous estimates given by thestreaming algorithm. Such streaming algorithms are said to beadversarially-robust. In this talk I will highlight two connections withadversarial streaming: A connection with the notion of differential privacy(leading to positive results for adversarial streaming) and a connection withthe recent line of work on adaptive data analysis (leading to negative resultsfor adversarial streaming).
This talk is based onjoint works with Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias,and Kobbi Nissim.