Jan 22, 2016 (Friday) at NYU
Warren Weaver Hall 1302 (Courant)
Located at 251 Mercer St, New York, NY
|9:30 – 10:00.||Introduction/Coffee|
|10:00 – 10:50.||
Gilad Asharov, IBM Research
Limits on the Power of Indistinguishability Obfuscation
|11:00 – 11:50.||
Elaine Shi, Cornell
Hawk: Privacy-Preserving Smart Contracts
|12:00 – 2:00.||Lunch (not provided)|
|2:00 – 2:50.||
Aloni Cohen, MIT
GGM is a Weakly One-Way Family of Functions
|3:00 – 3:50.||
Abhishek Jain, Johns Hopkins
NYU, Warren Weaver Hall 1302 (Courant), 251 Mercer St, New York, NY
Tal Rabin (IBM)
with the help and support of Victor Shoup and Yevgeniy Dodis.
Some travel support for NYC Crypto Day is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.
- Limits on the Power of Indistinguishability Obfuscation / Gilad Asharov(IBM Research) Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a “central hub” for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. However, constructions based on indistinguishability obfuscation almost always rely on non-black-box techniques, and thus the extent to which it can be used as a building block has been completely unexplored so far.
We present a framework for proving meaningful negative results on the power of indistinguishability obfuscation. 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.
Within our framework we prove the first negative results on the power of indistinguishability obfuscation. Our framework captures constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., obfuscating a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme themselves are used in a black-box manner.Based on joint works with: Gil Segev.
- Hawk: Privacy-preserving Smart Contracts/ Elaine Shi (Cornell) Existing blockchain-based cryptocurrencies such as Bitcoin and Ethereum store all financial transactions in the clear on the blockchain. This compromises the privacy of financial transactions which is essential in numerous applications. Hawk (www.oblivm.com/hawk/) is a blockchain-based smart contract system that stores encrypted transactions on the blockchain, and relies on cryptography to retain the security of the cryptocurrency. I will talk about the design of Hawk. Moreover, I will describe how to formally model and reason about protocols in the blockchain model.
- GGM is a Weakly One-Way Family of Functions/ Aloni Cohen (MIT) We prove that the GGM pseudo-random function family is a weakly one-way family of functions. Namely, any efficient algorithm fails to invert GGM on a significant fraction of the domain — even when given the secret key.A pseudo-random function ensemble is a collection of (efficient) functions indexed by a secret key with the dual properties that (1) given the key $s$, the function $f_s$ is efficiently computable and (2) without knowledge of the secret key, no probabilistic polynomial-time algorithm can distinguish between oracle access to a random function from the ensemble and access to a random oracle. The security property of pseudo-random functions depends on the absolute secrecy of the key, and no security is guaranteed when the secret key is revealed. The first construction of pseudo-random function families starting from any one-way functions came in 1986 by Goldreich, Goldwasser, and Micali.In this work, we demonstrate that the GGM family enjoys some measure of security even when the secret key is revealed to an attacker. Any efficient algorithm that — when given the secret key s — purports to invert GGM on random inputs must fail with a fixed polynomial probability.
Joint work with Saleet Klein.
Patchable Obfuscation / Abhishek Jain (Johns Hopkins) We introduce patchable obfuscation: our notion adapts the notion of indistinguishability obfuscation (iO) to a very general setting where obfuscated software evolves over time. We model this broadly by considering software patches P as arbitrary Turing Machines that take as input the description of a Turing Machine M, and output a new Turing Machine description M’ = P(M). Thus, a short patch P can cause changes everywhere in the description of M and can even cause the description length of the machine to increase by an arbitrary polynomial amount. We further consider multi-program patchable obfuscation where a patch is applied not just to a single machine, but to an unbounded set of machines.
We consider both patchable obfuscation and multi-program patchable obfuscation in a setting where there are an unbounded number of patches that can be adaptively chosen by an adversary. We show that sub-exponentially secure iO for circuits and sub-exponentially secure one-way functions imply patchable obfuscation; and we show that sub-exponentially secure iO for circuits, sub-exponentially secure one-way functions, and sub-exponentially secure DDH imply multi-program patchable obfuscation.
Finally, we exhibit some simple applications of multi-program patchable obfuscation, to demonstrate how these concepts can be applied.
Joint work with Prabhanjan Ananth and Amit Sahai.