CryptoDay at Columbia

Jan 23, 2015 (Friday) at Columbia Costas Engineering Commons, in the CEPSR Building Room 750 located at 530 West 120th Street, New York, NY

Program

9:30 – 10:00.	Introduction/Coffee
10:00 – 10:50.	Shai Halevi, IBM Research Cryptographic Graded-Encoding Schemes: Recent Developments
11:00 – 11:50.	Mike Walfish, NYU Verifying the Correctness of Remote Executions: from Theoretical Possibility to Near Practicality
12:00 – 2:00.	Lunch (not provided)
2:00 – 2:50.	Venkata Koppula , University of Texas, Austin Adaptively Secure Puncturable PRFs and Constrained PRFs
3:00 – 3:50.	Guy Rothblum, Stanford Publicly-Verifiable Non-Interactive Arguments for Delegating Computation

Venue

Columbia University, CEPSR building Room 750

Directions to CEPSR (Shapiro) building are available here:

http://www.cs.columbia.edu/resources/directions

(on the bottom).

Here are two options to enter the building:

You enter from campus (that’s 4th floor) and go up to 7th floor and then look for the appropriate room.

There is also an entrance to the building from 120th street between Broadway and Amsterdam but it’s more complicated (e.g., it may require an ID to get in; there you go first in one elevator to 4th floor and then switch to the other elevator to 7th).

Organizers
Tal Rabin (IBM)
with the help and support of Tal Malkin.

Abstracts

• Cryptographic Graded-Encoding Schemes: Recent Developments / Shai Halevi (IBM Research) Graded-encoding schemes are an extremely powerful tool in our crypto toolbox. Introduced two years ago by Garg, Gentry, and Halevi (as an approximation of multilinear maps), they were used to realize such “impossible goals” as general-purpose obfuscation, functional encryption, witness encryption, and more. However so far we have very few candidate constructions of graded encoding schemes, all based on similar principles, and the security of these candidates is poorly understood.Recently, Cheon, Han, Lee, Ryu, and Stehle developed a powerful line of attacks on the existing candidate constructions (extending early attacks of Garg, Gentry, and Halevi), and showed how to break many of the hardness assumptions that were made about these schemes. These attacks were further developed by Gentry et al. and Coron et al., extending them to even wider settings and adapting them to defeat some attempted counter-measures.In this talk I will survey the existing constructions and attacks, and try to describe our current view of the security landscape for these constructions.

• Verifying the Correctness of Remote Executions: from Theoretical Possibility to Near Practicality / Mike Walfish (NYU) How can a machine specify a computation to another one and then, without executing the computation, check that the remote machine carried it out correctly? And how can this be done without assumptions about the performer (replication, etc.) or restrictions on the computation? This is a classic problem in systems security, and is relevant in multiple contexts: cloud computing, an untrusted hardware supply chain, etc. For decades, it has been known that this problem can be solved in theory, using probabilistically checkable proofs (PCPs) coupled with cryptographic tools. The rub was practicality: if implemented naively, the theory would be astronomically more expensive than simply executing the computation locally.Over the last several years, a number of projects have brought this theory to near practicality. In this emerging area of proof-based verifiable computation, the pace of progress has been rapid, and there have been many encouraging developments: factors-of-a-trillion speedups, compilers that transform from high-level programs to executables that implement the protocol entities, and sophisticated implementations.I will discuss the general area and my group’s efforts in refining theory and building systems. A notable recent result is our Buffet system. Buffet has very good expressivity (it handles almost the entire C programming language as well as setups such as remote MapReduce jobs, database queries, etc.) and achieves the best performance in the area by multiple orders of magnitude. I will also cover the remaining obstacles to practicality in this research area; my hope is to communicate cautious optimism, with the emphasis on cautious.

• Adaptively Secure Puncturable PRFs and Constrained PRFs/Venkata Koppula (UT Austin) A constrained pseudo random function (PRF) behaves like a standard PRF, but with the added feature that the (master) secret key holder, having secret key K, can produce a constrained key, K_f, that allows for the evaluation of the PRF on a subset of the domain as determined by a predicate function f within some family F. While previous constructions gave constrained PRFs for poly-sized circuits, all reductions for such functionality were based in the selective model of security where an attacker declares which point he is attacking before seeing any constrained keys. Adaptive security was not known for even the most basic family of constrained PRFs – puncturable PRFs, where the constrained key is associated with an element x’ in the input domain and it allows evaluation at all points x \neq x’. In this talk, we will first discuss how to build puncturable PRFs with adaptive security proofs in the standard model that involve only polynomial loss to the underlying assumptions. This construction uses indistinguishability obfuscation and DDH-hard algebraic groups of composite order.

  Next, we will discuss a new constrained PRF construction for circuits that can be proven adaptively secure in the random oracle model. This solution is constructed from two recently emerged primitives: adaptively secure Attribute-Based Encryption (ABE) for circuits and a Universal Parameters scheme as introduced by Hofheinz et al. Both primitives are constructible from indistinguishability obfuscation (and injective pseudorandom generators) with only polynomial loss.

• Publicly-Verifiable Non-Interactive Arguments for Delegating Computation / Guy Rothblum (Stanford)We construct publicly verifiable non-interactive arguments that can be used to delegate polynomial time computations. These computationally sound proof systems are completely non-interactive in the common reference string model. The verifier’s running time is nearly-linear in the input length, and poly-logarithmic in the complexity of the delegated computation. Our protocol is based on graded encoding schemes, introduced by Garg, Gentry and Halevi (Eurocrypt 2012). Security is proved under a falsifiable and arguably simple cryptographic assumption about graded encodings. All prior publicly verifiable non-interactive argument systems were based on non-falsifiable knowledge assumptions. Our new result builds on the beautiful recent work of Kalai, Raz and Rothblum (STOC 2014), who constructed privately verifiable 2-message arguments. While building on their techniques, our protocols avoid no-signaling PCPs, and we obtain a simplified and modular analysis.

  As a second contribution, we also construct a publicly verifiable non-interactive argument for (logspace-uniform) computations of bounded depth. The verifier’s complexity grows with the depth of the circuit. This second protocol is adaptively sound, and its security is based on a falsifiable assumption about the hardness of a search problem on graded encodings (a milder cryptographic assumption). This result builds on the interactive proof of Goldwasser, Kalai and Rothblum (STOC 2008), using graded encodings to construct a non-interactive version of their protocol.

  Joint work with Omer Paneth