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, MIT Functional Encryption: Multi-Input and Randomized Functions. |
| 12:30 – 2:30. | Lunch (not provided) |
| 2:30 – 3:20. | Alexandra Berkoff, Brown Leakage Resilient Fully Homomorphic Encryption. |
| 3:30 – 4:20. | Divesh Aggarwal, NYU Non-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.
nycryptoday 