The first ever GTACS @ RUNI will be held at Reichman University, Wed, Oct 19th, 2022 at the Efi Arazi School of Computer Science.
Talks will be held in lecture room C.109, in the Arazi-Ofer CS building (#10 on the campus map)
Refreshments & lunch will be in the CS Research lab down the hall
PROGRAM
09:30-10:00 Coffee
10:00-11:00 Ilan Komargodski, Efficient and Secure Generation of Shared Randomness
11:00-11:30 Coffee break (Tea will be permitted)
11:30-12:30 Ron Rothblum, Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead
12:30-14:00 Lunch
14:00-15:00 Rotem Oshman, Zero-Knowledge Distributed Proofs Over Networks
15:00-15:30 Coffee break
15:30-16:30 Omer Paneth, Incrementally Verifiable Computation via Rate-1 Batch Arguments
ABSTRACTS
Efficient and Secure Generation of Shared Randomness
Ilan Komargodski, Hebrew University of Jerusalem
Abstract:
Secure generation of shared randomness lies in almost any distributed protocol. A famous lower bound of Cleve from 1986 says that in the dishonest majority setting there is an inherent tradeoff between efficiency and security of any such protocol. This tradeoff leaves significant gaps in various settings that come up in modern applications where an honest majority cannot be assumed.
In this talk, I will present two ways to circumvent Cleve's lower bound. In the first instance, we suggest using timing assumptions and in the second instance, we meaningfully weaken the security notion. In both cases, we obtain secure protocols for the dishonest majority setting.
Based on joint work with Cody Freitag, Rafael Pass, Naomi Sirkin and with Shin’ichiro Matsuo, Elaine Shi, and Ke Wu.
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead
Ron Rothblum, Technion
Abstract:
Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input x belongs to a language $L \in NP$, with communication that is much shorter than the NP witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of proving correctness.
In this work we address this problem by constructing succinct arguments for general computations, expressed as Boolean circuits (of bounded fan-in), with a strictly linear size prover. The soundness error of the protocol is an arbitrarily small constant. Prior to this work, succinct arguments were known with a quasi-linear size prover for general Boolean circuits or with linear-size only for arithmetic circuits, defined over large finite fields.
Joint work Noga Ron-Zewi.
Zero-Knowledge Distributed Proofs Over Networks
Rotem Oshman, Tel-Aviv University
Abstract:
distributed proof is a mechanism for certifying that a network is in a valid state, for example, that the network is connected and the nodes have a valid spanning tree of the network. To do this, each node is given a short certificate, and the nodes then interact with their neighbors in the network to verify the proof. Our goal is to minimize the length of the certificates, as well as the time and communication required for the verification protocol. Typically, no computational restrictions are assumed.
In this work we initiate the study of zero knowledge in distributed proofs. We suggest two definitions for zero-knowledge proofs, reconciling the traditional computational notion of zero-knowledge with the communication-based paradigm of distributed proofs; due to the dual role of the underlying graph in distributed proofs, serving as both the communication topology and the input to the problem, zero-knowledge distributed proofs must protect the graph itself. We show that efficient zero-knowledge distributed proofs can be constructed for fundamental problems such as 3-colorability and spanning tree verification. We also give a generic compiler that takes any non-ZK distributed proof and constructs from it a ZK distributed proof with related parameters.
This is joint work with Aviv Bick and Gillat Kol.
Incrementally Verifiable Computation via Rate-1 Batch Arguments>
Omer Paneth, Tel-Aviv University
Abstract:
Non-interactive delegation schemes enable producing succinct proofs (that can be efficiently verified) that a machine $M$ transitions from $c_1$ to $c_2$ in a certain number of deterministic steps. We here consider the problem of efficiently merging such proofs: given a proof $P_1$ that $M$ transitions from $c_1$ to $c_2$, and a proof $P_2$ that $M$ transitions from $c_2$ to $c_3$, can these proofs be efficiently merged into a single short proof (of roughly the same size as the original proofs) that $M$ transitions from $c_1$ to $c_3$? To date, the only known constructions of such a mergeable delegation scheme rely on strong non-falsifiable ``knowledge extraction" assumptions. In this work, we present a provably secure construction based on the standard LWE assumption.
As an application of mergeable delegation, we obtain a construction of incrementally verifiable computation (IVC) (with polylogarithmic length proofs) for any (unbounded) polynomial number of steps based on LWE; as far as we know, this is the first such construction based on any falsifiable (as opposed to knowledge-extraction) assumption.
The central building block that we rely on, and construct based on LWE, is a rate-1 batch argument (BARG): this is a non-interactive argument for NP that enables proving $k$ NP statements $x_1,..., x_k$ with communication/verifier complexity $m+o(m)$, where m is the length of one witness. Rate-1 BARGs are particularly useful as they can be recursively composed a super-constant number of times.
This is a joint work with Rafael Pass.