GTACS @ WIS, February 5th, 2015

Please register here.

Time:  Thursday, February 5th, 2015, 9:30 - 17:00

Place: Weizmann Institute of Science

Ziskind Building, Room 1


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).


09:30 - 09:45  Coffee and Registration

09:45 - 10:15  Shafi Goldwasser (MIT and Weizmann Institute of Science)

Cryptography and Beyond: Taking Advantage of Correlations


10:15 - 11:15  Siyao GUO (The Chinese University of Hong Kong)

The Power of Negations in Cryptography

11:15 - 11:40    Coffee Break

11:40 - 12:40  Orr Dunkelman (Haifa University)

How to Privately Find Double Acquisitions in Biometric Databases

12:40 - 13:40  Lunch Break

13:40 - 14:40  Aloni Cohen (MIT)

Aggregate Pseudorandom Functions and Connections to Learning


14:40 - 15:00    Coffee Break

15:00 - 16:00  Tal Moran (IDC)

Topology-Hiding Computation

16:00 - 17:00  Rump Session: Beer and Problems


Cryptography and Beyond: Taking Advantage of Correlations (Shafi Goldwasser)

The integer factorization problem has fascinated mathematicians for centuries and computer scientists for decades. It has helped us distill  some of the key concepts at the heart of the theory of computation, providing arguably the most elegant example of an NP problem which is hard to solve but easy to verify by grade school mathematics, and the impetus for much of modern day research into the power of quantum over classical computation. Recently, Henninger et al  pointed out a simple but pervasive problem with current  factorization based usage of public-key cryptography. Many composite and hard to factor numbers used in practice, are obtained by first generating their prime divisors using the outputs of weak pseudo random number generators with correlated seeds. As a result, one can obtain multiple instances of composite numbers with correlated prime divisors, which render the composite number instances trivial to factor.

This example of problem instances which are hard when they stand alone, but are easy when given correlated instances, may seem anecdotal. Our thesis is that the situation may be quite to the contrary. Instances of computational problems with correlated solutions seem to arise naturally in many scenarios. The challenge is not to find settings which present correlated instances, but how to take advantage of correlations when they exist, in cryptography and beyond.

In this work,  we focus on the complexity of constraint satisfaction problems (CSPs) with access to multiple instances with correlated solutions. We consider a variety of naturally occurring worst case and average case CSPs (such as Goldreich’s one way function proposal) , and show how availability of a small number of auxiliary instances generated through a natural generating process radically changes the complexity of solving the primary instance from intractable to expected polynomial time.

We view this work as a first step in a wider study of how to exploit correlations in available inputs.

Joint work with Irit Dinur and Rachel Lin.

The Power of Negations in Cryptography (Siyao GUO)

The study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be monotone, and showed that one-way functions can be monotone (assuming they exist), but a pseudorandom generator cannot.

In this paper, we start by filling in the picture and proving that many other basic cryptographic primitives cannot be monotone. We then initiate a quantitative study of the power of negations, asking how many negations are required. We provide several lower bounds, some of them tight, for various cryptographic primitives and building blocks including one-way permutations, pseudorandom functions, small-bias generators, hard-core predicates, error-correcting codes, and randomness extractors. Among our results, we highlight the following.

i) Unlike one-way functions, one-way permutations cannot be monotone.

ii) We prove that pseudorandom functions require logn−O(1) negations (which is optimal up to the additive term).

iii) Error-correcting codes with optimal distance parameters require logn−O(1) negations (again, optimal up to the additive term).

iv) We prove a general result for monotone functions, showing a lower bound on the depth of any circuit with t negations on the bottom that computes a monotone function f in terms of the monotone circuit depth of f. This result addresses a question posed by Koroth and Sarma

(2014) in the context of the circuit complexity of the Clique problem.

This a joint work with Tal Malkin, Igor Carboni Oliveira and Alon Rosen.

How to Privately Find Double Acquisitions in Biometric Databases (Orr Dunkelman)

As part of a fight against ID misuse, the state of Israel has decided to establish a biometric database storing biometric information (fingerprints and high definition photographs) of all citizens. Obviously, such a database is a privacy and security concern unless properly deployed and handled.

As the prominent publicly acknowledged target of this database is to detect fraudulent individuals who are in the possession of more than one ID, we propose two schemes which allows identifying this behavior while offering maximal privacy, even in the case of a complete database leakage.

Our proposed solutions are based on the notion that generating entries in the database should be controlled, whereas the generated entries should be as pseudo-random as possible. This way, the generation of the entires can be done by a practical secure multiparty computation.

This is a joint work with Melissa Chase and with Rita Osadchy.

Aggregate Pseudorandom Functions and Connections to Learning (Aloni Cohen)

In the first part of this work, we introduce a new type of pseudo-random function for which ``aggregate queries'' over exponential-sized sets can be efficiently answered. We show how to use algebraic properties of underlying classical pseudo random functions, to construct such ``aggregate pseudo-random functions'' for a number of classes of aggregation queries under cryptographic hardness assumptions. For example, one aggregate query we achieve is the product of all function values accepted by a polynomial-sized read-once boolean formula. On the flip side, we show that certain aggregate queries are impossible to support. Aggregate pseudo-random functions fall within the framework of the work of Goldreich, Goldwasser, and Nussboim \cite{GGN10} on  the ``Implementation of Huge Random Objects,'' providing truthful implementations of pseudo-random functions for which aggregate queries can be answered.

In the second part of this work, we show how various extensions of  pseudo-random functions considered recently in the cryptographic literature, yield impossibility results for various extensions of machine learning models, continuing a line of investigation originated by Valiant and Kearns in the 1980s. The extended pseudo-random functions we address include constrained pseudo random functions, aggregatable pseudo random functions, and pseudo random functions secure under related-key attacks.

Topology-Hiding Computation (Tal Moran)

Secure Multi-party Computation (MPC) is one of the foundational achievements of modern cryptography, allowing multiple, distrusting, parties to jointly compute a function of their inputs, while revealing nothing but the output of the function. Following the seminal works of Yao and Goldreich, Micali and Wigderson and Ben-Or, Goldwasser and Wigderson, the study of MPC has expanded to consider a wide variety of questions, including variants in the attack model, underlying assumptions, complexity and composability of the resulting protocols.

One question that appears to have received very little attention, however, is that of MPC over an underlying communication network whose structure is, in itself, sensitive information. This question, in addition to being of pure theoretical interest, arises naturally in many contexts: designing privacy-preserving social-networks, private peer-to-peer computations, vehicle-to-vehicle networks and the ``internet of things'' are some of the examples.

The talk will introduce the notion of  ``topology-hiding computation'', a definitional model meant to capture these concerns. We will give formal definitions in both simulation-based and indistinguishability-based flavors. We show that, even for fail-stop adversaries, there are some strong impossibility results. Despite this, we show that protocols for topology-hiding computation can be constructed in the semi-honest and fail-stop models, if we somewhat restrict the set of nodes the adversary may corrupt.

Based on joint work with Ilan Orlov and Silas RIchelson.