**May 23, 2014 (Friday) at NYU (WWH 1302)**

Program

10:00 – 10:30. | Introduction/Coffee |

10:30 – 11:20. |
Aris Tentes, NYU
Coin Flipping of Any Constant Bias Implies One-Way Functions. |

11:30 – 12:20. | Abhishek Jain, MITFunctional Encryption: Multi-Input and Randomized Functions. |

12:30 – 2:30. | Lunch (not provided) |

2:30 – 3:20. | Alexandra Berkoff, BrownLeakage Resilient Fully Homomorphic Encryption. |

3:30 – 4:20. | Divesh Aggarwal, NYUNon-malleable Codes in the Split-State Model. |

Getting Here

Address: 251 Mercer St

[ google maps | official directions | restaurants on yelp | coffee ]

Organizers

Tal Rabin (IBM) and Sanjam Garg (IBM)

with the help and support of Yevgeniy Dodis (NYU).

Abstracts

**Coin Flipping of Any Constant Bias Implies One-Way Functions**

Aris Tentes (NYU)We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (\eg $.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS ’11], who proved this implication for protocols with bias $\frac{\sqrt2 -1}2 – o(1) \approx .207$. Unlike the result of Hainter and Omri, our result also holds for weak coin-flipping protocols.

**Functional Encryption: Multi-Input and Randomized Functions**

Abhishek Jain (MIT)In this talk, I will discuss some recent advances in Functional Encryption. I’ll first introduce the problem of Multi-Input Functional Encryption (MiFE), where a secret key SK_f may correspond to an n-ary function that takes multiple ciphertexts as input. MiFE is a general tool for computing on encrypted data that allows for mining aggregate information from several different data sources (as opposed to a single source as in “single-input” functional encryption). I will discuss various security notions for MiFE and present constructions based on program obfuscation.Time permitting, I will also discuss how to extend the definitions of FE to incorporate randomized functions, and present constructions for the same.Based on joint works with Vipul Goyal, Shafi Goldwasser, Venkata Koppula and Amit Sahai.

**Leakage Resilient Fully Homomorphic Encryption**

Alexandra Berkoff (Brown)We construct the first leakage resilient variants of fully homomorphic encryption (FHE) schemes. Our leakage model is bounded adaptive leakage resilience. We first construct a leakage-resilient leveled FHE scheme, meaning the scheme is both leakage resilient and homomorphic for all circuits of depth less than some pre-established maximum set at the time of key generation. We then go beyond simply leveled FHE, removing the need for an a priori maximum circuit depth, by presenting a novel way to combine leakage resilient leveled FHE with multi-key FHE. Our new scheme can homomorphically evaluate circuits of arbitrary depth, with a bounded number of distinct input ciphertexts.

**Non-malleable Codes in the Split-State Model**

Divesh Aggarwal (NYU)Non-malleable codes provide a useful and meaningful security guarantee

in situations where traditional error-correction (and even

error-detection) is impossible; for example, when the attacker can

completely overwrite the encoded message. Informally, a code is

non-malleable if the message contained in a modified codeword is

either the original message, or a completely unrelated value. Although

such codes do not exist if the family of “tampering functions” F is

completely unrestricted, they are known to exist for many broad

tampering families F. One such natural family is the family of

tampering functions in the so called split-state model. Here the

message m is encoded into a constant number of shares, and the

attacker is allowed to arbitrarily tamper with each share

individually. The split-state tampering arises in many realistic

applications, such as the design of non-malleable secret sharing

schemes, motivating the question of designing efficient non-malleable

codes in this model. Prior to this work, non-malleable codes in the

split-state model received considerable attention in the literature,

but were either (1) constructed in the random oracle model [DPW10], or

(2) relied on advanced cryptographic assumptions (such as

non-interactive zero-knowledge proofs and leakage-resilient

encryption) [LL12], or (3) could only encode 1-bit messages [DKO13].

As our main result, we give two constructions of efficient, multi-bit,

information-theoretically-secure non-malleable code in the split-state

model. Our first construction [ADL14] has two shares of length O(n^7)

each (where n is the length of the message), and its analysis uses

some a surprising connection with some results from additive

combinatorics and linearity testing. In contrast, our second

construction [ADK14] uses 5 shares of length O(n^2) each, and only

relies of variour properties of randomness extractors, such as the

alternating extraction theorem of [DP07]

Joint works with Yevgeniy Dodis, Tomasz Kazana and Shachar Lovett.