Friday October 23 at MIT
Please join us for first Charles River Crypto Day of this academic year on Friday, October 23 at MIT.
Location:
32 Vassar St (Stata Center)
G449 (Patil/Kiva)
Cambridge MA 02139.
Thanks to NSF MACS Project for their generous support.
Program:
9:30 – 10:00.  Introduction/Coffee 
10:00 – 11:00.  Eshan Chattopadhyay, University of Texas Austin NonMalleable Extractors and Codes, with their Many Tampered Extensions 
11:30 – 12:30. 
Shai Halevi, IBM Research
The State of Multilinear 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 SubLinear 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 
Abstracts:
Speaker: Eshan Chattopadhyay
Title: NonMalleable 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 nonmalleable extractors, introduced by Dodis and Wichs; seedless nonmalleable extractors, introduced by Cheraghchi and Guruswami; and nonmalleable codes, introduced by Dziembowski, Pietrzak and Wichs. Besides being interesting on their own, they also have important applications in cryptography. For example, seeded nonmalleable extractors are closely related to privacy amplification with an active adversary, nonmalleable codes are related to nonmalleable secret sharing, and seedless nonmalleable extractors provide a universal way to construct explicit nonmalleable codes.
However, explicit constructions of nonmalleable extractors appear to be hard, and the known constructions are far behind their nontampered counterparts. Indeed, the best known seeded nonmalleable extractor requires minentropy rate at least 0.49; while explicit constructions of nonmalleable twosource extractors were not known even if both sources have full minentropy, and was left as an open problem in the work of CheraghchiGuruswami. In addition, current constructions of nonmalleable 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 nonmalleable extractor for minentropy . This dramatically improves all previous results and gives a simpler 2round privacy amplification protocol with optimal entropy loss, matching the best known result by Li.
(2) We construct the first explicit nonmalleable twosource extractor for minentropy , with output size and error .
(3) We motivate and initiate the study of two natural generalizations of seedless nonmalleable extractors and nonmalleable codes, where the sources or the codeword may be tampered many times. For this, we construct the first explicit nonmalleable twosource extractor with tampering degree t up to , which works for minentropy , with output size and error .
We further show that we can efficiently sample uniformly from any preimage. By the connection in [CG14b], we also obtain the first explicit nonmalleable codes with tampering degree t up to , relative rate , and error .
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 SubLinear Time
An interactive proof of proximity (IPP) is an interactive protocol in which a prover tries to convince a sublineartime verifier that x \in L. Since the verifier runs in sublineartime, 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 subexponentially secure FHE scheme, we construct a oneround 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 etal, 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 generalpurpose VBB obfuscation by using an idealizedgraded encoding scheme that enables performing \emph{highdegree} “zerotests” on encodings.
Building on a result of Canetti, Kalai and Paneth (TCC’15), we first show the impossibility of VBB obfuscation when the idealizedgraded encoding scheme only allows evaluating constantdegree zerotests on encodings. The main technique is to show how constantdegree zerotests used in an obfuscation scheme can be “removed” by learning what the zerotests would have answered, resulting in approximatelycorrect VBB obfuscation. This main technique also rules out subexponential secure VBB for general circuits when the idealized graded encoding scheme only allows evaluating degree n^\alpha zerotests.
We then apply the technique to indistinguishability obfuscation schemes and combine with wellknown complexity results to show that constructing iO schemes from constantdegree graded encoding schemes in a blackbox way is as hard as basing publickey cryptography on oneway functions.
This is joint work with Rafael Pass, and with Mohammad Mahmoody, Ameer Mohammed, and Soheil Nematihaji.