Author Archives: Vinod

UPDATE: Videos from the Crypto Day are now posted here. Enjoy!

Join us for the second Charles River Crypto Day of 2017 on Friday, May 12 at Boston University.

To help us plan for the event, please register here.

When: Friday, May 12.

Where: Hariri Seminar Room, 111 Cummington Mall Room 180, Boston MA.

Organizers: Ran Canetti, Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.


9:30 – 10:00. Introduction/Coffee/Light Breakfast
10:00 – 10:50.
Raluca Ada Popa, UC Berkeley
An Oblivious and Encrypted Distributed Analytics Platform
11:00 – 11:50.
Justin Holmgren, MIT
Delegation with Nearly Minimal Time-Space Overhead
12:00 – 1:30. Lunch (provided)
1:30 – 2:20.
Fabrice Ben Hamouda, IBM Research
On the Robustness of Non-Interactive Multi-Party Computation
2:30 – 3:20.
Abhi Shelat, Northeastern
Full Accounting for Verifiable Outsourcing
3:30 – 3:50. Coffee Break
3:50 – 4:40.
Eran Tromer, Tel Aviv University and Columbia University
PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations
4:40. Ushering of Summer Reception


TITLE: An Oblivious and Encrypted Distributed Analytics Platform

SPEAKER: Raluca Ada Popa, Berkeley


Many systems run rich data analytics on sensitive data in the cloud, but are prone to data
breaches. A recent hardware enclave architecture promises data confidentiality and isolated
execution of arbitrary computations, yet still suffers from leakage due to memory and network accesses patterns. In this talk, I will describe Opaque, a distributed data analytics platform supporting a wide range of queries while protecting the data. Even a compromised operating system sees only encrypted data. Opaque also protects against leakage from memory and network accesses outside of the enclave (a property called obliviousness). To accomplish this goal, Opaque introduces new distributed oblivious relational operators, as well as new query planning techniques to optimize these new operators. Opaque is implemented on Spark SQL with few changes to the underlying system. Opaque provides data encryption, authentication, and computation verification with a performance ranging from 52% faster to 3.3x slower than vanilla Spark SQL; obliviousness comes with a 1.6–46x overhead. At the same time, Opaque provides an improvement of three orders of magnitude over state-of- the-art oblivious protocols.

Joint work with W. Zheng, A. Dave, J. G. Beekman, J. E. Gonzalez, and I. Stoica.

TITLE: Delegation with nearly minimal time-space overhead

SPEAKER: Justin Holmgren, MIT


Consider a scenario in which a client wants to utilize a powerful, but untrusted, server to
perform computations which are beyond the client’s ability. Since the client does not trust the server, we would like the server to certify the correctness of the result. We would like the verification procedure to be extremely efficient, whereas the complexity of proving shouldn’t be much larger than that of computing.

Assuming LWE, we construct a one-round argument-system for proving the correctness of any
time T and space S computation, in which both the verifier and prover are extremely efficient. In particular, the prover runs in time T * poly(k) and space S + poly(k), where k is a security parameter.

Our result builds on a line of work initiated by Kalai et al. (STOC, 2014). The prover in all of these works runs in time T^c for a large constant c (where c is at least 3). As an additional contribution we significantly simplify a central construct that appears in all of these works.

Joint work with Ron Rothblum.

TITLE: On the Robustness of Non-Interactive Multi-Party Computation

SPEAKER: Fabrice Ben Hamouda, IBM


Non-Interactive Multiparty Computation (Beimel et al., Crypto 2014) is a very powerful notion equivalent (under some corruption model) to garbled circuits, Private Simultaneous Messages protocols, and obfuscation. We present robust solutions to the problem of Non-Interactive Multiparty Computation in the computational and information-theoretic models. Our results include the first efficient and robust protocols to compute any function in NC1 for constant-size collusions, in the information-theoretic setting and in the computational setting, to compute any function in P for constant-size collusions, assuming the existence of one-way functions. Our constructions start from a Private Simultaneous Messages construction (Feige, Killian Naor, STOC 1994 and Ishai, Kushilevitz, ISTCS 1997) and transform it into a Non-Interactive Multiparty Computation for constant-size collusions.

We also present a new Non-Interactive Multiparty Computation protocol for symmetric functions with significantly better communication complexity compared to the only known one of Beimel et al.

This is joint work with Hugo Krawczyk and Tal Rabin.

TITLE:  Full accounting for verifiable outsourcing

SPEAKER: Abhi Shelat, Northeastern


Systems for verifiable outsourcing incur costs for a prover, a verifier, and precomputation; outsourcing makes sense when these costs are cheaper than not outsourcing. Yet, prover costs are generally ignored. The only exception is Verifiable ASICs~(VA), wherein the prover is a custom chip; however, the only prior VA system ignores the cost of precomputation.

This paper describes a new VA system, called Giraffe; charges Giraffe for all three costs; and identifies regimes where outsourcing is worthwhile. Giraffe’s base is an interactive proof geared to data parallel computation. Giraffe makes this protocol asymptotically optimal for the prover, i.e., for a large enough batch size, the prover’s running time is linear in the total number of gates in the arithmetic circuit (whereas prior work incurs an extra log(width of circuit) factor).

Giraffe wins even when outsourcing several tens of sub-computations, scales to 500X larger computations than prior work, and can profitably outsource parts of programs that are not worthwhile to outsource in full.

Joint work with Riad Wahby, Ye Ji, Andrew J Blumberg, Justin Thaler, Michael Walfish and Thomas Wies.

TITLE:  PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations

SPEAKER: Eran Tromer, Tel Aviv University and Columbia University


Authenticating images that claim to depict real events is desirable in many context. Some
cameras already attach digital signatures to photographs, but plain signatures become invalid when the image undergoes legitimate processing such as cropping, rotation, brightness-adjustment or compression. Prior attempts to address this need had inadequate functionality and/or security.

We present PhotoProof, a new approach to image authentication based on cryptographic proofs. It can be configured according to application requirements, to allow any permissible set of (efficiently computable) transformations. Starting with a signed image, the scheme attaches, to each legitimately derived image, a succinct proof of computational integrity attesting that the transformation was permissible. Anyone can verify these proofs, and generate updated proofs when applying further permissible transformations. Moreover, the proofs are zero-knowledge so that, for example, an authenticated cropped image reveals nothing about the cropped-out regions.

PhotoProof is based on Proof-Carrying Data (PCD), a cryptographic primitive for verified
execution of distributed computations, built on top of zero-knowledge SNARK proofs. We will
discuss the scheme, its implementation, and possible extensions to other forms of data provenance.

Joint with with Assa Naveh.

Come to the first Charles River Crypto Day of this academic year and get your fix of coffee, blockchains, rational proofs, memory hard functions and (need we say) indistinguishability obfuscation.

When: Friday, October 14 at MIT.

Where: 32 Vassar St (Stata Center)
G-882 (Hewlett), Cambridge MA 02139.

Organizers: Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.


9:30 – 10:00. Introduction/Coffee
10:00 – 11:00.
Nir Bitansky, MIT
From Cryptomania to Obfustopia through Secret-Key Functional Encryption
11:00 – 12:00.
Rachel Lin, UC Santa Barbara
Indistinguishability Obfuscation from DDH-like Assumptions on Constant-Degree Graded Encodings
12:00 – 1:30. Lunch (provided)
1:30 – 2:30. Jing Chen, Stony Brook
Rational Proofs with Multiple Provers
2:30 – 3:30. Elaine Shi, Cornell
Blockchains and Beyond: Rethinking Distributed Consensus in New Settings
3:30 – 4:00. Coffee Break
4:00 – 5:00. Jeremiah Blocki, Purdue
Towards a Theory of Data-Independent Memory Hard Functions


Speaker: Nir Bitansky
Title: From Cryptomania to Obfustopia through Secret-Key Functional Encryption

Functional encryption lies at the frontiers of current research in cryptography; some variants have been shown sufficiently powerful to yield indistinguishability obfuscation (IO) while other variants have been constructed from standard assumptions such as LWE. Indeed, most variants have been classified as belonging to either the former or the latter category. However, one mystery that has remained is the case of \emph{secret-key functional encryption} with an unbounded number of keys and ciphertexts. On the one hand, this primitive is not known to imply anything outside of minicrypt, the land of secret-key crypto, but on the other hand, we do no know how to construct it without the heavy hammers in obfustopia.

In this work, we show that (subexponentially secure) secret-key functional encryption is powerful enough to construct indistinguishability obfuscation if we additionally assume the existence of (subexponentially secure) plain public-key encryption. In other words, secret-key functional encryption provides a bridge from cryptomania to obfustopia.

On the technical side, our result relies on two main components. As our first contribution, we show how to use secret key functional encryption to get “exponentially-efficient indistinguishability obfuscation” (XIO), a notion recently introduced by Lin et al. (PKC ’16) as a relaxation of IO. Lin et al. show how to use XIO and the LWE assumption to build IO. As our second contribution, we improve on this result by replacing its reliance on the LWE assumption with any plain public-key encryption scheme.

Lastly, we ask whether secret-key functional encryption can be used to construct public-key encryption itself and therefore take us all the way from minicrypt to obfustopia. A result of Asharov and Segev (FOCS ’15) shows that this is not the case under black-box constructions, even for exponentially secure functional encryption. We show, through a non-black box construction, that subexponentially secure-key functional encryption indeed leads to public-key encryption. The resulting public-key encryption scheme, however, is at most quasi-polynomially secure, which is insufficient to take us to obfustopia.

Joint work with Ryo Nishimaki, Alain Passelègue, and Daniel Wichs

Speaker: Rachel Lin
Title: Indistinguishability Obfuscation from DDH-like Assumptions on Constant-Degree Graded Encodings

All constructions of general purpose indistinguishability obfuscation (IO) rely on either meta-assumptions that encapsulate an exponential family of assumptions (e.g., Pass, Seth and Telang, CRYPTO 2014) or polynomial families of assumptions, on graded encoding schemes with a high polynomial degree/multilinearity (e.g., Gentry, Lewko, Sahai and Waters, FOCS 2014).

In this talk, we present two recent works on simplifying graded encodings needed for constructing IO [Lin EUROCRYPT 2016 and Lin-Vaikuntanathan FOCS 2016]. These two works show that IO can be constructed from only constant-degree graded encodings, with a security reduction to a DDH-like assumption — called the joint-SXDH assumption — on the graded encodings, and the sub-exponential security of a polynomial-stretch PRG in NC0. Our assumption on graded encodings is simple, has constant size, and does not require handling composite-order rings. This narrows the gap between the mathematical objects that exist (bilinear maps, from elliptic curve groups) and ones that suffice to construct general purpose IO.

Speaker: Jing Chen
Title: Rational Proofs with Multiple Provers

Classic interactive proofs model a world where a verifier delegates computation to an untrustworthy prover, verifying the prover’s claims before accepting them. We provide the first model that extends rational interactive proofs to allow multiple provers. A verifier pay the provers according to his own randomness and the information received from them. The provers are rational rather than untrustworthy —they may lie, but only to increase the payment. Properly designed protocols incentivize the provers to provide correct information and hence let the verifier to learn the correct answer.

We give tight upper and lower bounds on the computation power of this model. On the way, we show that multiple rational provers are strictly more powerful than one, under standard complexity-theoretic assumptions. We further show that the full power of rational proofs with multiple provers can be achieved using only two provers and five rounds of interaction. Finally, we consider more demanding models where the verifier wants the payment to decrease significantly when the provers are lying, and fully characterize the power of the model when the payment gap must be noticeable.

Speaker: Elaine Shi
Title: Blockchains and Beyond: Rethinking Distributed Consensus in New Settings

Abstract coming soon.

Speaker: Jeremiah Blocki
Title: Towards a Theory of Data-Independent Memory Hard Functions

There is a growing interest in functions which are moderately hard to compute on a normal single-processor machine, but which cannot be computed at a significantly lower cost of dedicated hardware. Such functions are necessary for password-hashing to prevent brute-force attacks implemented on application specific integrated circuits (ASICs). Towards this goal memory-hard functions (MHFs) have been proposed, motivated by the observation that memory costs on customized hardware is not much cheaper than on general architectures. A MHF should have the properties that: (1) Computing the MHF on any input, using a sequential algorithm requires a moderate amount of computational resources (memory and time), and (2) The MHF cannot be repeatedly computed in parallel with significantly less computational resources even if an adversary can amortize his costs across multiple instances (e.g., password guesses). More specifically, we want to ensure that any algorithm evaluating multiple instances of the MHF has high amortized ST-cost — Space X Time divided by #instances evaluated. The second property ensures that the amortized cost of computing an MHF cannot be significantly reduced by developing application specific integrated circuits (ASICs).

Of particular interest in the context of password hashing are data-independent MHFs (iMHFs) as they enjoy a natural resistance to certain side channel attacks which might otherwise leak information about the user’s password. An iMHF can be specified by fixing a directed acyclic graph (DAG) G_n on n nodes of constant indegree and a single sink node n. G_n represents the data-dependency graph between intermediate calls to an underlying hash function during the computation of the iMHF and node n represents final output.

This talk will overview recent results demonstrating that a combinatorial property called depth-robustness fully characterizes iMHFs with high amortized ST-cost. On the positive side we construct a family of DAGs G_n with ST-cost at least $\Omega(n^2/log(n))$. We also show that any iMHF has amortized ST-cost at most $O(n^2 log(log(n))/log(n))$ so our construction is nearly optimal in an asymptotic sense. On the negative side we show that Argon2i, the winner of the password hashing competition, is defined using a directed acyclic graph G_n that is not depth-robust and can be computed by an algorithm with low amortized ST-cost $O(n^{1.71})$. The resulting attacks are practical for realistic settings of the Argon2i parameters.

Based on joint works with Joel Alwen and Krzysztof Pietrzak.

Please join us for second Charles River Crypto Day of this academic year on Friday, February 26 at MSR New England.

Location and Arrival Instructions:
Microsoft New England Research and Development Center
Clara Barton Room (First Floor),
One Memorial Drive, Cambridge MA 02142.

Thanks to NSF MACS Project for their generous support.


9:30 – 10:00. Introduction/Coffee
10:00 – 11:00. Ron Rothblum, MIT
Constant-round Interactive-proofs for Delegating Computations
11:30 – 12:30.
Omer Paneth, Boston University
Delegating RAM Computations
12:30 – 1:30. Lunch (provided)
1:30 – 2:30. Silas Richelson, MIT
Three round Non-Malleable Commitment from Non-Malleable Codes
3:00 – 4:00. Muthu Venkitasubramaniam, University of Rochester
On the Power of Secure Two-Party Computation


Speaker: Ron Rothblum
Title: Constant-round Interactive-proofs for Delegating Computations

Interactive proofs have had a dramatic impact on Complexity Theory and Cryptography. In particular, the celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds. It is very natural and well motivated to examine the power of more efficient interactive proofs, and this is the focus of this work.

Our main result is that for every statement that can be evaluated in polynomial time and bounded-polynomial space there exists an interactive proof that satisfies the following strict efficiency requirements: (1) the honest prover runs in polynomial time, (2) the verifier is almost linear time (and under some conditions even sub linear), and (3) the interaction consists of only a constant number of communication rounds.

We introduce several new notions for interactive proofs that turn out to be very useful in our work and may be of independent interest. One of these notions is that of unambiguous interactive proofs where the prover has a unique successful strategy. Another notion is that of probabilistically checkable interactive proofs (PCIPs) where the verifier only reads a few bits of the transcript in checking the proof (this could be viewed as an interactive extension of PCPs).

Joint work with Omer Reingold and Guy Rothblum.

Speaker: Omer Paneth
Title: Delegating RAM Computations

In the setting of cloud computing a user wishes to delegate its data, as well as computations over this data, to a cloud provider. Each computation may read and modify the data, and these modifications should persist between computations. Minding the computational resources of the cloud, delegated computations are modeled as RAM programs. In particular, the delegated computations’ running time may be sub-linear, or even exponentially smaller than the memory size.

We construct a two-message protocol for delegating RAM computations to an untrusted cloud. In our protocol, the user saves a short digest of the delegated data. For every delegated computation, the cloud returns, in addition to the computation’s output, the digest of the modified data, and a proof that the output and digest were computed correctly. When delegating a T-time RAM computation M with security parameter k, the cloud runs in time T * Poly(k) and the user in time Poly(|M|, log(T), k).

Our protocol is secure assuming super-polynomial hardness of the Learning with Error (LWE) assumption. Security holds even when the delegated computations are chosen adaptively as a function of the data and output of previous computations.

We note that RAM delegation schemes are an improved variant of memory delegation schemes [Chung et al. CRYPTO 2011]. In memory delegation, computations are modeled as Turing machines, and therefore, the cloud’s work always grows with the size of the delegated data.

Joint work with Yael Tauman Kalai.

Speaker: Silas Richelson
Title: Three-Round Non-Malleable Commitments from Non-Malleable Codes

We present a new non-malleable commitment protocol. Our protocol has the following features:

1) The protocol has only three rounds of interaction. Pass (TCC 2013) showed an impossibility result for a two-round non-malleable commitment scheme w.r.t. a black-box reduction to any “standard” intractability reduction. Thus, this resolves the round complexity of non-malleable commitment at least w.r.t. black-box security reductions. Our construction is secure as per the standard notion of non-malleability w.r.t. commitment.

2) Our protocol is efficient. In our basic protocol, the entire computation of the committer is dominated by just three invocations of a non-interactive statically binding commitment scheme, while, the receiver computation (in the commitment stage) is limited to just sampling a random string. Unlike many previous works, we directly construct a protocol for large tags and hence avoid any non-malleability amplification steps.

3) Our protocol is based on a black-box use of any non-interactive statistically binding commitment scheme. Such schemes, in turn, can be based on any one-to-one one-way function (or any one-way function at the cost of an extra initialization round). Previously, the best known black-box construction of non-malleable commitments required a larger (constant) number of rounds.

4) Our construction is public-coin and makes use of only black-box simulation. Prior to our work, no public-coin constant round non-malleable commitment schemes were known based on black-box simulation.

Our techniques depart significantly from the techniques used previously to construct non-malleable commitment schemes. As a main technical tool, we rely on non-malleable codes in the split state model. Our proofs of security are purely combinatorial in nature.

In addition, we also present a simple construction of constant round non-malleable commitments from any one-way function. While this result is not new, the main feature is its simplicity compared to any previous construction of non-malleable commitments (regardless of the number of rounds). We believe the construction is simple enough to be covered in a graduate level course on cryptography. The construction uses non-malleable codes in the split state model in a black-box way.

This is joint work with Vipul Goyal and Omkant Pandey.

Speaker: Muthu Venkitasubramaniam
Title: On the Power of Secure Two-Party Computation

Ishai, Kushilevitz, Ostrovsky and Sahai (STOC`07, SIAM JoC 2009) introduced the powerful “MPC-in-the-head” technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a “black-box” way. In this work, we extend this technique and provide a generic transformation of any semi-honest secure two-party computation (2PC) protocol (with mild adaptive security guarantees) in the so called \emph{oblivious-transfer} hybrid model to an adaptive ZK proof for any NP-language, in a “black-box” way assuming only one-way functions. Our basic construction based on Goldreich-Micali-Wigderson’s 2PC protocol yields an adaptive ZK proof with communication complexity proportional to quadratic in the size of the circuit implementing the NP relation. Previously such proofs relied on an expensive Karp reduction of the NP language to Graph Hamiltonicity (Lindell and Zarosim (TCC`09, Journal of Cryptology 2011)). We also improve our basic construction to obtain the first linear-rate adaptive ZK proofs by relying on efficient maliciously secure 2PC protocols. Core to this construction is a new way of transforming 2PC protocols to efficient (adaptively secure) instance-dependent commitment schemes.

As our second contribution, we provide a general transformation to construct a randomized encoding of a function f from any 2PC protocol that securely computes a related functionality (in a black-box way). We show that if the 2PC protocol has mild adaptive security guarantees then the resulting randomized encoding (RE) can be decomposed to an offline/online encoding.

As an application of our techniques, we show how to improve the construction of Lapidot and Shamir (Crypto`90) to obtain black-box constructions of commit-and-prove protocols with the so called input-delayed property where the honest prover’s algorithm does not require the actual statement until the last round. Using this, we obtain first constructions of a 4-round concurrent non-malleable commitments scheme based on one-way permutations where the underlying one-way permutation is used in a black-box way. Previous constructions either required more number of rounds or made non-black-box usage of the underlying primitive. We also show how these proofs can improve round complexity of secure computation protocols in the tamper-proof model.

Joint work with Carmit Hazay.

Please join us for first Charles River Crypto Day of this academic year on Friday, October 23 at MIT.

32 Vassar St (Stata Center)
G-449 (Patil/Kiva)
Cambridge MA 02139.

Thanks to NSF MACS Project for their generous support.


9:30 – 10:00. Introduction/Coffee
10:00 – 11:00. Eshan Chattopadhyay, University of Texas Austin
Non-Malleable Extractors and Codes, with their Many Tampered Extensions
11:30 – 12:30.
Shai Halevi, IBM Research
The State of Multi-linear Maps
12:30 – 1:30. Lunch (provided)
1:30 – 2:00. Rump Session
2:00 – 3:00. Ron Rothblum, MIT
Proofs and Arguments of Proximity: Verifying Computations in Sub-Linear Time
3:30 – 4:30. abhi shelat, University of Virginia
Impossibility and Difficulty in Constructing Obfuscation Schemes

Rump program:

Aanchal Malhotra, BU
Adam Sealfon, MIT
Shortest Paths and Distances with Differential Privacy
Yilei Chen, BU
On the correlation intractability of obfuscated pseudorandom functions (a.k.a. the foundation of bitcoin hash functions)
Zahra Jafargholi, NEU
The New Realization of Adaptively Secure Garbled Circuits


Speaker: Eshan Chattopadhyay

Title: Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced by Dodis and Wichs; seedless non-malleable extractors, introduced by Cheraghchi and Guruswami; and non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs. Besides being interesting on their own, they also have important applications in cryptography. For example, seeded non-malleable extractors are closely related to privacy amplification with an active adversary, non-malleable codes are related to non-malleable secret sharing, and seedless non-malleable extractors provide a universal way to construct explicit non-malleable codes.

However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts. Indeed, the best known seeded non-malleable extractor requires min-entropy rate at least 0.49; while explicit constructions of non-malleable two-source extractors were not known even if both sources have full min-entropy, and was left as an open problem in the work of Cheraghchi-Guruswami. In addition, current constructions of non-malleable codes in the information theoretic setting only deal with the situation where the codeword is tampered once, and may not be enough for certain applications.

In this paper we make progress towards solving the above problems. Our contributions are as follows.

(1) We construct an explicit seeded non-malleable extractor for min-entropy k > \log^2 n . This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result by Li.

(2) We construct the first explicit non-malleable two-source extractor for min-entropy k > n-n^{\Omega(1)} , with output size n^{\Omega(1)} and error 2^{-n^{\Omega(1)}} .

(3) We motivate and initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. For this, we construct the first explicit non-malleable two-source extractor with tampering degree t up to n^{\Omega(1)} , which works for min-entropy k \geq n-n^{\Omega(1)} , with output size n^{\Omega(1)} and error 2^{-n^{\Omega(1)}} .

We further show that we can efficiently sample uniformly from any pre-image. By the connection in [CG14b], we also obtain the first explicit non-malleable codes with tampering degree t up to n^{\Omega(1)} , relative rate n^{\Omega(1)}/n , and error 2^{-n^{\Omega(1)}} .

Speaker: Shai Halevi

Title: The State of Cryptographic Multilinear Maps

This talk will give an overview of current state of the constructions of and attacks against cryptographic multilinear maps.

Speaker: Ron Rothblum

Title: Proofs and Arguments of Proximity: Verifying Computations in Sub-Linear Time

An interactive proof of proximity (IPP) is an interactive protocol in which a prover tries to convince a sublinear-time verifier that x \in L. Since the verifier runs in sublinear-time, following the property testing literature, the verifier is only required to reject inputs that are far from L. In a recent work, (Guy) Rothblum, Vadhan and Wigderson (STOC, 2013) constructed an IPP for every language computable by a low depth circuit.

In this work we consider the computational analogue, where soundness is required to hold only against a computationally bounded cheating prover. We call such protocols interactive arguments of proximity.

Assuming the existence of a sub-exponentially secure FHE scheme, we construct a one-round argument of proximity for every language computable in time t, where the running time of the verifier is o(n) + polylog(t) and the running time of the prover is poly(t).

As our second result, assuming sufficiently hard cryptographic PRGs, we give a lower bound, showing that the parameters obtained both in the IPPs of Rothblum et-al, and in our arguments of
proximity, are close to optimal.

Based on joint work with Yael Kalai.

Speaker: abhi shelat

Title: Impossibility and Difficulty in Constructing Obfuscation Schemes

The golden standard for obfuscation, Virtual blackbox obfuscation, was shown to be impossible to achieve for general circuits in the standard model by the celebrated work of Barak et al (CRYPTO 2001). Recently, Brakerski and Rothblum (TCC’15), and Barak et al (Eurocrypt’14) overcome the impossibility and show how to achieve general-purpose VBB obfuscation by using an idealized-graded encoding scheme that enables performing \emph{high-degree} “zero-tests” on encodings.

Building on a result of Canetti, Kalai and Paneth (TCC’15), we first show the impossibility of VBB obfuscation when the idealized-graded encoding scheme only allows evaluating constant-degree zero-tests on encodings. The main technique is to show how constant-degree zero-tests used in an obfuscation scheme can be “removed” by learning what the zero-tests would have answered, resulting in approximately-correct VBB obfuscation. This main technique also rules out sub-exponential secure VBB for general circuits when the idealized graded encoding scheme only allows evaluating degree n^\alpha zero-tests.

We then apply the technique to indistinguishability obfuscation schemes and combine with well-known complexity results to show that constructing iO schemes from constant-degree graded encoding schemes in a blackbox way is as hard as basing public-key cryptography on one-way functions.

This is joint work with Rafael Pass, and with Mohammad Mahmoody, Ameer Mohammed, and Soheil Nematihaji.