GTACS @ WIS, January 8th, 2019

Please register here.

Time: Tuesday, January 8th, 2019, 9:40 - 16:00.

Place: Weizmann Institute of Science

Ziskind Building, Room 155

Parking: At any available spot on campus (please specify to guards at the gate that you are coming to an event of the computer science department). Finding a free spot at this hour can be tough, so please allow sufficient time for searching.

Schedule:

09:40 - 10:00 Gathering and Coffee (Ziskind Lobby)

10:00 - 11:00 Alon Rosen (IDC): Finding a Nash Equilibrium is No Easier than Breaking Fiat-Shamir

11:00 - 11:20 Coffee Break (Ziskind Lobby)

11:20 - 12:20 Venkata Koppula (Weizmann): CPA to CCA Transformation via Hinting PRGs

12:20 - 13:40 Lunch Break (Ziskind Lobby)

13:40 - 14:40 Yuval Ishai (Technion): Compressing Vector OLE: Secure Computation with Silent Preprocessing

14:40 - 15:00 Coffee Break (Ziskind Lobby)

15:00 - 16:00 Omer Paneth (Northeastern University and MIT): How to Delegate Computations Publicly

Abstracts:

Finding a Nash Equilibrium is No Easier than Breaking Fiat-Shamir (Alon Rosen, IDC)

The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol's transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.

We show that solving the END-OF-METERED-LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.

Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n).

Joint work with Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, and Guy Rothblum.

CPA to CCA Transformation via Hinting PRGs (Venkata Koppula, Weizmann)

In this talk, I will present a generic and black box transformation from any encryption scheme secure against chosen plaintext attacks (CPA) to a chosen ciphertext attack (CCA) secure system. Furthermore, this transformation also works for advanced encryption schemes such as broadcast encryption, attribute based encryption, one-sided predicate encryption etc. Our transformation requires only the IND-CPA security of the original scheme coupled with a pseudorandom generator (PRG) with a special security property, which we call 'hinting property'.

Given a PRG that maps n bits to n strings, consider the following distribution: choose a random seed s, compute PRG(s) = (z1, ..., zn). Choose random strings (y1, ..., yn). For each index i, if the ith bit of s is 1, output (yi, zi), else output (zi, yi). A PRG is a 'hinting PRG' if the output of this distribution is indistinguishable from n pairs of random strings.

We show constructions for hinting PRGs based on standard assumptions such as Learning with Errors (LWE) and Computational Diffie Hellman (CDH).

Joint work with Brent Waters.

Compressing Vector OLE: Secure Computation with Silent Preprocessing (Yuval Ishai, Technion)

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn a linear combination of a pair of field elements held by a sender. Vector OLE (VOLE) extends OLE by allowing the receiver to learn a linear combination of two vectors held by the sender. OLE and VOLE serve as common building blocks in secure computation of arithmetic circuits, analogous to the roles of oblivious transfer (OT) and string OT for boolean circuits.

We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency.

Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) problem over large fields.

Finally, we present several applications of VOLE generators, including efficient secure computation with "silent" preprocessing and NIZK with a reusable correlated randomness setup.

Joint work with Elette Boyle, Geoffroy Couteau, and Niv Gilboa.

How to Delegate Computations Publicly (Omer Paneth, Northeastern University and MIT)

We construct a delegation scheme for all polynomial time computations. Our scheme is publicly verifiable and completely non-interactive in the common reference string (CRS) model.

Our scheme is based on an efficiently falsifiable decisional assumption on groups with bilinear maps. Prior to this work, publicly verifiable non-interactive delegation schemes were only known under knowledge assumptions (or in the Random Oracle model), or under non-standard assumptions related to obfuscation or multilinear maps.

We obtain our result in two steps. First, we construct a scheme with a long CRS (polynomial in the running time of the computation) by following the blueprint of Paneth and Rothblum (TCC 2017). Then we show how to bootstrap this scheme to obtain a short CRS. Our bootstrapping theorem exploits the fact that our scheme can securely delegate certain classes of non-deterministic computations.

Joint work with Yael Kalai and Lisa Yang.