Monthly Archives: March 2014

April 4, 2014 (Friday) at Columbia CS Conference Room


10:00 – 10:30. Introduction/Coffee
10:30 – 11:20. Daniel Wichs (Northeastern University)
Outsourcing Private RAM Computation
11:30 – 12:20. Charanjit Jutla (IBM)
Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces
12:30 – 2:30. Lunch (not provided)
2:30 – 3:20. Foteini Baldimtsi (Brown)
Anonymous Credentials Light
3:30 – 4:20. Karn Seth (Cornell)
Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings

Getting Here

Address: 500 W 120th St (at Amsterdam)
google maps | official directions ]


Tal Rabin (IBM) and Sanjam Garg (IBM)
with the help and support of Allison Lewko (Columbia).


  • Outsourcing Private RAM Computation
    Daniel Wichs (Northeastern University)
    We construct the first schemes that allow a client to privately outsource arbitrary program executions to a remote server while ensuring that: (I) the client’s work is small and essentially independent of the complexity of the computation being outsourced, and (II) the server’s work is only proportional to the run-time of the computation on a random access machine (RAM), rather than its potentially much larger circuit size. Furthermore, our solutions are non-interactive and have the structure of “reusable garbled RAM programs”, where the client creates a garbled program which it gives to the server and later can outsource arbitrary executions of this program by providing fresh garbled inputs.  We also construct schemes for an augmented variant of the above scenario, where the client can initially outsource a large private and persistent database to the server, and later outsource arbitrary program executions with read/write access to this database.Our solutions are built from non-reusable garbled RAM in conjunction with new types of reusable garbled circuits that are more efficient than prior solutions but only satisfy weaker security. For the basic setting without a persistent database, we can instantiate the required reusable garbled circuits using indistinguishability obfuscation. For the more complex setting with a persistent database we need stronger notions of obfuscation. Our basic solution also requires the client to perform a one-time preprocessing step to garble a program at the cost of its RAM run-time, and we can avoid this cost using stronger notions of obfuscation. It remains an open problem to instantiate these new types of reusable garbled circuits under weaker assumptions, possibly avoiding obfuscation altogether.

    joint work with Craig Gentry, Shai Halevi and Mariana Raykova
  • Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces 
    Charanjit Jutla (IBM)
    A novel notion of quasi-adaptive NIZK proofs for probability distributions on parametrized languages is introduced. It is quasi-adaptive in the sense that the common reference string (CRS) generator can generate the CRS depending on the language parameters. However, the simulation is required to be uniform, i.e., a single efficient simulator should work for the whole class of parametrized languages. For distributions on languages that are linear subspaces of vector spaces over bilinear groups, we give quasi-adaptive computationally sound NIZKs that are shorter and more efficient than Groth-Sahai NIZKs. For many cryptographic applications quasi-adaptive NIZKs suffice, and our constructions can lead to significant improvements in the standard model. Our construction can be based on any k-linear assumption, and in particular under the eXternal Diffie Hellman (XDH) assumption our proofs are even competitive with Random-Oracle based Sigma-protocol NIZK proofs.We also show that our system can be extended to include integer tags in the defining equations, where the tags are provided adaptively by the adversary. This leads to applicability of our system to many applications that use tags, e.g. applications using Cramer-Shoup projective hash proofs. Our techniques also lead to the shortest known (ciphertext) fully secure identity based encryption (IBE) scheme under standard static assumptions (SXDH). Further, we also get a short publicly-verifiable CCA2-secure IBE scheme.
  • Anonymous Credentials Light
    Foteini Baldimtsi (Brown)
    In this talk we propose an efficient and provably secure (in the RO model) anonymous credential scheme called “Anonymous Credentials Light”. Our scheme is unlinkable under the decisional Diffie-Hellman assumption, and unforgeable under the Discrete-Logarithm assumption for sequential composition. In contrast to prior provably secure anonymous credential schemes that were based on the RSA group or on groups with pairings our construction only requires a few exponentiations in a prime-order group in which the decisional Diffie-Hellman problem is hard and thus, is very efficient even for lightweight devices. The only prior construction with similar efficiency is the one due to Stefan Brands, however, as I will briefly mention, we have shown that Brands scheme cannot be proven unforgeable in the RO model under any intractability assumption. For our scheme, we define a new cryptographic building block, called “blind signatures with attributes”, and discuss how it can be used in combination with a commitment scheme to directly get an anonymous credential system. Finally, I will briefly explain how one can construct electronic cash with attributes from our new building block and how it can be used for efficient payments in public transportation.
  •  Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings
    Karn Seth (Cornell)
    We define a notion of semantic security of multilinear (a.k.a. graded) encoding schemes, which generalizes a multilinear DDH assumption: roughly speaking, we require that if two constant-length sequences m0, m1 are pointwise statistically indistinguishable by algebraic attackers C (obeying the multilinear restrictions) in the presence of some other elements z, then encodings of these sequences should be computationally indistinguishable. Assuming the existence of semantically secure multilinear encodings and the LWE assumption, we demonstrate the existence of indistinguishability obfuscators for all polynomial-size circuits.
    We rely on the beautiful candidate obfuscation constructions of Garg et al (FOCS’13), Brakerski and Rothblum (TCC’14) and Barak et al (EuroCrypt’14) that were proven secure only in idealized generic multilinear encoding models, and develop new techniques for demonstrating security in the standard model, based only on semantic security of multilinear encodings (which trivially holds in the generic multilinear encoding model).
    Joint work with Rafael Pass and Sidharth Telang.
%d bloggers like this: