Monthly Archives: January 2014

Feb 14, 2014 (Friday) at 111 8th Avenue #302 (Room “Touchdown”)


Registration for attending this event is free but mandatory. You can register by going to the registration formPlease register by February 12, 2014 11:59 PM. Only registered participants will be allowed on Cornell NYC Tech premises.


10:00 – 10:30. Introduction/Coffee
10:30 – 11:20. Shai Halevi (IBM)
Two-round secure MPC from Indistinguishability Obfuscation
11:30 – 12:20. Thomas Ristenpart (University of Wisconsin – Madison)
New Encryption Primitives for Uncertain Times
12:30 – 2:30. Lunch (not provided)
2:30 – 3:20. Hemanta Maji (UCLA)
A Full Characterization of Completeness for Two-party Randomized Function Evaluation
3:30 – 4:20. Omer Paneth (BU)
On the Existence of Extractable One-Way Functions


Cornell Tech
111 8th Avenue #302
New York, NY 10011 

Room “Touchdown”.

Please check-in at the lobby first where you will get a sticker. Then go to the third floor and follow the corridor for Cornell Tech, and then someone will greet you in the lobby and tell you how to get to “Touchdown.”


Tal Rabin (IBM) and Sanjam Garg (IBM)
with the help and support of Rafael Pass (Cornell NYC Tech).


  • Two-round secure MPC from Indistinguishability Obfuscation
    Shai Halevi (IBM)
    One fundamental complexity measure of an MPC protocol is its *round
    complexity*. Asharov et al. recently constructed the first three-round
    protocol for general MPC in the CRS model. Here, we show how to achieve
    this result with only two rounds. We obtain UC security with abort
    against static malicious adversaries, and fairness if there is an honest
    majority. Additionally the communication in our protocol is only
    proportional to the input and output size of the function being
    evaluated and independent of its circuit size. Our main tool is
    indistinguishability obfuscation, for which a candidate construction was
    recently proposed by Garg et al.

    Joint work with Sanjam Garg, Craig Gentry, and Mariana Raykova

  • New Encryption Primitives for Uncertain Times
    Thomas Ristenpart (University of Wisconsin – Madison)
    I’ll talk about our recent work on a variety of new encryption mechanisms that deal with various functionality and security deficiencies in conventional schemes. We’ll start with format-transforming encryption, a tool we recently introduced that enables fine-grained, programmatic control over the “look” of encrypted content sent over the network. The motivating application is avoidance of deep-packet inspection used to identify censorship circumvention tools such as Tor. We’ll then look at message-locked encryption and the DupLESS system, which together enable client-side encryption of data in a way that an outsourced storage provider such as Dropbox can perform deduplication over ciphertexts. Finally, I’ll give a brief overview of very recent work on honey encryption, a new primitive for ensuring that encrypting data under passwords can retain security even when passwords are weak.This talk will cover joint work with Mihir Bellare, Scott Coull, Kevin Dyer, Ari Juels, Sriram Keelveedhi, Phil Rogaway, Thomas Shrimpton, Till Stegers, and Scott Yilek
  • A Full Characterization of Completeness for Two-party Randomized Function Evaluation
    Hemanta Maji (UCLA)
    We settle a long standing open problem which has pursued a full characterization of completeness of (potentially randomized) finite functions for 2-party computation that is secure against active adversaries. Since the first such complete function was discovered [Kilian, FOCS 1988], the question of which finite 2-party functions are complete has been studied extensively, leading to characterization in many special cases. In this work, we completely settle this problem.We provide a polynomial time algorithm to test whether a 2-party finite secure function evaluation (SFE) functionality (possibly randomized) is complete or not. The main tools in our solution include:
    1) A formal linear algebraic notion of “redundancy’’ in a general 2-party randomized function,
    2) A notion of “statistical testable games.’’ A kind of interactive proof in the information-theoretic setting where both parties are computationally unbounded but differ in their knowledge of a secret.
    3) An extension of the (weak) converse of Shannon’s channel coding theorem, where an adversary can adaptively choose the channel based on its view.

    We show that any function F, if complete, can implement any (randomized) circuit C using only O(|C| + k) calls to F, where k is the statistical security parameter. In particular, for any two-party functionality G, this establishes a universal notion of its quantitative “cryptographic complexity’’ independent of the setup and has close connections to circuit complexity. (This is a joint work with Daniel Kraschewski, Manoj Prabhakaran and Amit Sahai)

  • On the Existence of Extractable One-Way Functions
    Omer Paneth (BU)
    A function f is extractable if it is possible to algorithmically “extract,” from any adversarial program that outputs a value y in the image of f, a preimage of y. When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions.
    We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length.
    On the positive side, for programs with bounded auxiliary-input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zero-knowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions.Based on joint works with Nir Bitansky, Ran Canetti and Alon Rosen.
%d bloggers like this: