The first GTACS of the year will be at IDC Herzliya, Wed Oct 28
at the Efi Arazi School of Computer Science
PROGRAM
09:00-09:30 Coffee & Registration
09:30-10:30 Eran Omri, Parallel Hashing via List Recoverability
10:30-11:00 Coffee break
11:00-12:00 Gilad Asharov, On Constructing One-Way Permutations from Indistinguishability Obfuscation
12:00-13:30 Lunch
13:30-14:30 Pavel Hubáček, When Can Limited Randomness Be Used in Repeated Games?
14:30-15:00 Coffee break
15:00-16:00 Noah Stephens-Davidowitz, Cryptographic Reverse Firewalls
ABSTRACTS
Eran Omri, Ariel
Parallel Hashing via List Recoverability
Abstract:
Motivated by the goal of constructing efficient hash functions, we investigate the possibility of hashing a long message by only making parallel, non-adaptive calls to a hash function on short messages.
Our main result is a simple construction of a collision-resistant hash function $h: \{0,1\}^n \mapsto \{0,1\}^k$ that makes a polynomial number of parallel calls to a random function $f: \{0,1\}^k \mapsto \{0,1\}^k$, for any polynomial $n=n(k)$. This should be compared with the traditional use of a Merkle hash tree, that requires at least $\log(n/k)$ rounds of calls to $f$, and with a more complex construction of Maurer and Tessaro (Crypto 2007) that requires two rounds of calls to $f$. We also show that our hash function $h$ satisfies a relaxed form of the notion of indifferentiability of Maurer et al (TCC 2004) that suffices for implementing the Fiat-Shamir paradigm. As a corollary, we get sublinear-communication non-interactive arguments for NP that only make two rounds of calls to a small random oracle.
An attractive feature of our construction is that h can be implemented by Boolean circuits that only contain parity gates in addition to the parallel calls to $f$. Thus, we get the first domain-extension scheme which is degree-preserving in the sense that the algebraic degree of $h$ over the binary field is equal to that of $f$.
Our construction makes use of list-recoverable codes, a generalization of list-decodable codes that is closely related to the notion of randomness condensers. We show that list-recoverable codes are necessary for any construction of this type.
Joint work with Iftach Haitner, Yuval Ishai, and Ronen Shaltiel
Gilad Asharov, Hebrew University
On Constructing One-Way Permutations from Indistinguishability Obfuscation
Abstract:
We prove that there is no black-box construction of a one-way permutation family from a one-way function and an indistinguishability obfuscator for the class of all oracle-aided circuits, where the construction is "domain invariant" (i.e., where each permutation may have its own domain, but these domains are independent of the underlying building blocks).
Following the framework of Asharov and Segev (FOCS '15), by considering indistinguishability obfuscation for oracle-aided circuits we capture the common techniques that have been used so far in constructions based on indistinguishability obfuscation. These include, in particular, non-black-box techniques such as the punctured programming approach of Sahai and Waters (STOC '14) and its variants, as well as sub-exponential security assumptions. For example, we fully capture the construction of a trapdoor permutation family from a one-way function and an indistinguishability obfuscator due to Bitansky, Paneth and Wichs (TCC '16). Their construction is not domain invariant and our result shows that this, somewhat undesirable property, is unavoidable using the common techniques.
In fact, we observe that constructions which are not domain invariant circumvent all known negative results for constructing one-way permutations based on one-way functions, starting with Rudich's seminal work (PhD thesis '88). We revisit this classic and fundamental problem, and resolve this somewhat surprising gap by ruling out all such black-box constructions -- even those that are not domain invariant.
Joint work with Gil Segev.
Pavel Hubáček, Weizmann
When Can Limited Randomness Be Used in Repeated Games?
Abstract:
A Nash equilibrium is a collection of players' strategies such that no player can improve her utility by a unilateral deviation. The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game, their randomness might be insufficient if the game is played many times sequentially.
In this talk we explore how much randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games, containing arbitrary two-player zero-sum games, approximate Nash equilibria of the $n$-stage repeated version of the game exist if and only if both players have $\Omega(n)$ random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the $n$-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits.
When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators exist (or, equivalently, one-way functions), then the players can base their strategies on “random-like” sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then $\Omega(n)$ random bits remain necessary for equilibria to exist.
No knowledge of Game Theory will be assumed. Joint work with Moni Naor and Jonathan Ullman.
Noah Stephens-Davidowitz, NYU
Cryptographic Reverse Firewalls
Abstract:
Recent history has shown us that a user's own hardware and software often cannot be trusted. Apparently inadvertent bugs are regularly found in widespread cryptographic implementations, and Snowden's revelations proved that powerful actors are willing to go to extraordinary lengths to compromise hardware and software. This motivates us to consider the following (seemingly absurd and rather scary) question: How can we guarantee a user's security when she may be using a buggy, malfunctioning, or even arbitrarily compromised machine?
To that end, we introduce the notion of a cryptographic reverse firewall (RF). Such a machine sits between the user's computer and the outside world, potentially modifying the messages that she sends and receives as she engages in a cryptographic protocol. A good firewall guarantees a user's security even when her own computer is arbitrarily corrupted. (Importantly, it does this without sharing any secrets with the user.) This model generalizes much prior work and provides a general framework for building cryptographic schemes that remain secure when run on a compromised machine. Perhaps surprisingly, we show that we are able to instantiate very strong primitives with secure reverse firewalls (such as private function evaluation), and we show that efficient and practical implementations exist for important primitives such as CCA-secure message transmission.
Joint work with Yevgeniy Dodis and Ilya Mironov