Monthly Archives: May 2014

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


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 ]


Tal Rabin (IBM) and Sanjam Garg (IBM)
with the help and support of Yevgeniy Dodis (NYU).


  • 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.
%d bloggers like this: