GTACS @ BIU, Jan 8 2015

Location: Beck Auditorium, Bar Ilan University (Building 410, not far from our location in building 408. See campus map.)

Schedule:
9:00- 9:30   Coffee and welcome
9:30-11:00  Yael Tauman-Kalai: Delegating Computation: Past, Present, and Future
11:00-11:30 Coffee
11:30-11:50 Ran Cohen: Fairness Versus Guaranteed Output Delivery in Secure Multiparty Computation
11:55-12:15 Ilan Komargodski: One-Way Functions and (Im)perfect Obfuscation
12:15-13:15 Lunch
13:15-14:15 Rafael Pass: Constant-round Concurrent Zero-Knowledge, Delegation, and Indistinguishability Obfuscation
14:15-14:30 Coffee
14:30-15:15 Iddo Bentov:  Bitcoin and Secure Computation With Money
15:15-          Beer and informal discussions

Don't forget to register on our registration form

Abstracts: 

Yael Tauman-Kalai: Delegating Computation: Past, Present, and Future

Abstract: With cloud computing, computations and data are increasingly being delegated to powerful remote servers. This brings new computational challenges: How do we ensure privacy? How do we guarantee that computations are performed correctly?  In this talk we will focus on the latter question.

We will start with a brief history on the evolution of proofs in computer science.  We will then show how these beautiful ideas have been used for delegating computation.  We will end the talk by focusing on a specific method for delegating computation, which is based on a connection to "no-signaling strategies" from quantum physics.  This method is joint work with Ran Raz and Ron Rothblum.

Ran Cohen: Fairness Versus Guaranteed Output Delivery in Secure Multiparty Computation
In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties \emph{including} fairness and guaranteed output delivery), and protocols that do not assume an honest majority (and achieve all properties \emph{except for} fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same.

In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these properties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial functions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery, and shows that these properties should sometimes be considered separately. 

Based on a joint work with Yehuda Lindell

Ilan Komargodski: One-Way Functions and (Im)perfect Obfuscation
Abstract: A program obfuscator takes a program and outputs a ``scrambled'' version of it, where the goal is that the obfuscated program will not reveal much about its structure beyond what is apparent from executing it. There are several ways of formalizing this goal. Specifically, in indistinguishability obfuscation, first defined by Barak et al. (CRYPTO 2001), the requirement is that the results of obfuscating any two functionally equivalent programs (circuits) will be computationally indistinguishable. Recently, a fascinating candidate construction for indistinguishability obfuscation was proposed by Garg et al. (FOCS 2013).  This has led to a flurry of discovery of intriguing constructions of primitives and protocols whose existence was not previously known (for instance, fully deniable encryption by Sahai and Waters, STOC 2014). Most of them explicitly rely on additional hardness assumptions, such as one-way functions.

 Our goal is to get rid of this extra assumption. We cannot argue that indistinguishability obfuscation of all polynomial-time circuits implies the existence of one-way functions, since if P = NP, then program obfuscation (under the indistinguishability notion) is possible. Instead, the ultimate goal is to argue that if P != NP and program obfuscation is possible, then one-way functions exist.

 Our main result is that if NP \not\subseteq ioBPP and there is an efficient (even imperfect) indistinguishability obfuscator, then there are one-way functions. In addition, we show that the existence of an indistinguishability obfuscator implies (unconditionally) the existence of SZK-arguments for NP. This, in turn, provides an alternative version of our main result, based on the assumption of hard-on-the average NP problems. To get some of our results we need obfuscators for simple programs such as CNF formulas.

The talk is based on joint work with Tal Moran, Moni Naor, Rafael Pass, Alon Rosen and Eylon Yogev.

Rafael Pass: Constant-round Concurrent Zero-Knowledge, Delegation, and Indistinguishability Obfuscation
Abstract: Since their introduction by Dwork, Naor and Sahai, concurrent zero-knowledge protocols have been extensively studied. The central open question in the area is whether *constant-round* concurrent zero-knowledge protocols exist for non-trivial languages.

We demonstrate the existence of constant-round concurrent zero-knowledge protocols for NP based on the existence of collision-resistant hash
functions and certain types of "unique" two-round delegation schemes for polynomial-time computations. We additionally show that such delegation schemes can be constructed based on the existence of indistinguishability obfuscators for P/poly and one-way permutations (with slightly super-polynomial security).

Joint work with Kai-min Chung and Huijia Lin.

Iddo Benotv: Bitcoin and Secure Computation With Money
Abstract: We study a model of secure computation in which deviating parties are forced to pay monetary penalties, without relying on a trusted party to provide an ideal bank functionality. In this model we obtain the following results.

1. We show how to transform any secure multiparty computation protocol into a protocol that enforces fairness with penalties, meaning that all corrupt parties who abort on receiving output are forced to pay a mutually predefined monetary penalty.

2. We introduce protocols for {\em secure cash distribution with penalties}, a variant of secure computation in which the inputs and outputs of the parties are also comprised of money. In particular, our protocols allow dropout-tolerant realizations of digital games in which money changes hands, in the sense that any party who drops out in the middle of the game is forced to pay a penalty to all other parties. This implies that it is feasibile to play real poker rather than just mental poker, in the absence of a trusted referee.

The secure cash distribution with penalties primitive simultaneously generalizes secure computation with penalties of Bentov and Kumaresan (Crypto 2014), and secure lottery with penalties of Andrychowicz et al. (Security and Privacy 2014).

Our protocols work in a hybrid model where parties have access to claim-or-refund or multilock ideal functionalities, which can be efficiently realized in (a variant of) Bitcoin.

Joint work with Ranjit Kumaresan and Tal Moran.