# [Busec] [charles-river-crypto-day] Charles River Crypto Day, This Friday, October 23 @ MIT

Nir Bitansky nbitansky at gmail.com
Sat Oct 17 05:28:11 EDT 2015

Please join us for the next installment of the Charles River Crypto Day
<https://bostoncryptoday.wordpress.com/2015/04/09/friday-april-17-at-northeastern/>
this
Friday, October 23 at MIT.
See below for location info, updated schedule, and abstracts.

This time we also plan to have a mini rump session after lunch of 1-3
talks, of 5-8 mins each. If you'd like to give a talk at the rump session
let us know. Preference will be given to students.

Looking forward to seeing you there,
Yael, Vinod, Daniel, and Nir

*Location: **MIT, Patil/Kiva Seminar Room, 32-G449 (directions
<http://www.na-mic.org/Wiki/index.php/Meeting_Locations:MIT_CSAIL_Star>)*

*Program:*
9:30 – 10:00.Introduction/Coffee10:00 – 11:00.
Shai Halevi, IBM Research
*The State of Multi-linear Maps*
11:30 – 12:30.Eshan Chattopadhyay, University of Texas Austin
*Non-Malleable Extractors and Codes, with their Many Tampered Extensions*12:30
– 1:30.Lunch (provided)1:30 – 2:00.Rump Session2: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*Abstracts:

*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.

*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 [image:
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 [image: k > n-n^{\Omega(1)}], with output size [image:
n^{\Omega(1)}] and error [image: 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 [image: n^{\Omega(1)}], which works for min-entropy [image: k \geq
n-n^{\Omega(1)}], with output size [image: n^{\Omega(1)}] and error [image:
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 [image: n^{\Omega(1)}],
relative rate [image: n^{\Omega(1)}/n], and error [image:
2^{-n^{\Omega(1)}}].

*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.

--
You received this message because you are subscribed to the Google Groups "Charles River Crypto Day" group.
To unsubscribe from this group and stop receiving emails from it, send an email to charles-river-crypto-day+unsubscribe at googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/charles-river-crypto-day/CACJEprPBm36fYjaG45QXA0qfqz3HfwRtwTUuQt37zc1%2BLUHW-Q%40mail.gmail.com.