The first GTACS of the year will be at IDC Herzliya, Wed, Nov 21st, 2018 at the Efi Arazi School of Computer Science.
The seminars will be held in the M.Sc. lab of the Computer Science/Communications building (there will be signs once you reach the building).
PROGRAM
09:30-10:00 Coffee & Registration
10:00-11:00 Ron Rothblum, Fiat Shamir, from Practice to Theory
11:00-11:15 Coffee break
11:15-12:15 Mor Weiss Private Anonymous Data Access
12:15-13:30 Lunch
13:30-14:30 Gil Kalai Analysis of Boolean Functions, Influence, and Noise
14:30-14:45 Coffee break
14:45-15:45 Noam Mazor On the Communication Complexity of Key-Agreement Protocols
ABSTRACTS
Fiat Shamir, From Practice to Theory
Ron Rothblum, Technion
Abstract:
I will describe a sequence of recent works showing how to build explicit hash functions that are "Fiat-Shamir compatible", meaning that applying the Fiat-Shamir transform to any interactive proof using these hash functions yields a sound non-interactive argument.
Our hash functions are constructed under strong lattice related assumptions but have strong implications as well: publicly verifiable non-interactive arguments for NC, and non-interactive zero-knowledge arguments for NP.
Based on joint works with: Ran Canetti, Yilei Chen, Justin Holmgren, Yael Kalai, Alex Lombardi, Leo Reyzin and Guy Rothbum.
Mor Weiss, IDC Herzliya
Abstract:
We consider a scenario where a server holds a huge database that it wants to make accessible to a large group of clients. After an initial setup phase, clients should be able to read arbitrary locations in the database while maintaining privacy (the server does not learn which locations are being read) and anonymity (the server does not learn which client is performing each read). This should hold even if the server colludes with a subset of the clients. Moreover, the run-time of both the server and the client during each read operation should be low, ideally only poly-logarithmic in the size of the database and the number of clients. We call this notion Private Anonymous Data Access (PANDA).
PANDA simultaneously combines aspects of Private Information Retrieval (PIR) and Oblivious RAM (ORAM). PIR has no initial setup, and allows anybody to privately and anonymously access a public database, but the server's run-time is linear in the data size. On the other hand, ORAM achieves poly-logarithmic server run-time, but requires an initial setup after which only a single client with a secret key can access the database. The goal of PANDA is to get the best of both worlds: allow many clients to privately and anonymously access the database as in PIR, while having an efficient server as in ORAM.
In this work, we construct bounded-collusion PANDA schemes, where the efficiency scales linearly with a bound on the number of corrupted clients that can collude with the server, but is otherwise poly-logarithmic in the data size and the total number of clients. Our solution relies on standard assumptions, namely the existence of fully homomorphic encryption, and combines techniques from both PIR and ORAM. We also extend PANDA to settings where clients can write to the database.
Joint work with Ariel Hamlin, Rafail Ostrovsky, and Daniel Wichs.
Analysis of Boolean Functions, Influence, and Noise
Gil Kalai, IDC Herzliya & HUJI
Abstract:
We will consider some early papers by Ben-Or and Linial (1985) and Kahn, Kalai, and Linial (1988) on collective coin flipping and influence, go on to describe Fourier analysis of Boolean functions, mention some old and new results, and present some open problems.
On the Communication Complexity of Key-Agreement Protocols
Noam Mazor, Tel-Aviv University
Abstract:
Key-agreement protocols whose security is proven in the random oracle model are an important alternative to protocols based on public-key cryptography. In this model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but the parties are limited in the number of queries they can make to the oracle. The random oracle serves as an abstraction for black-box access to a symmetric cryptographic primitive, such as a collision resistant hash. Unfortunately, as shown by Impagliazzo and Rudich [STOC '89] and Barak and Mahmoody [Crypto '09], such protocols can only guarantee limited secrecy: the key of any $\ell$-query protocol can be revealed by an $O(\ell^2)$-query adversary. This quadratic gap between the query complexity of the honest parties and the eavesdropper matches the gap obtained by the Merkle's Puzzles protocol of Merkle [CACM '78].
In this work we tackle a new aspect of key-agreement protocols in the random oracle model: their communication complexity. In Merkle's Puzzles, to obtain secrecy against an eavesdropper that makes roughly $\ell^2$ queries, the honest parties need to exchange $\Omega(\ell)$ bits. We show that for protocols with certain natural properties, ones that Merkle's Puzzle has, such high communication is unavoidable. Specifically, this is the case if the honest parties' queries are uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Our proof for the first setting uses a novel reduction from the set-disjointness problem in two-party communication complexity. For the second setting we prove the lower bound directly, using information-theoretic arguments.
Understanding the communication complexity of protocols whose security is proven in the random-oracle model is an important question in the study of practical protocols. Our results and proof techniques are a first step in this direction.
Joint work with Iftach Haitner, Rotem Oshman, Omer Reingold and Amir Yehudayoff