[Busec] Fwd: [charles-river-crypto-day] This Friday, Feb 20: Charles River Crypto Day @ MSR

Sharon Goldberg goldbe at cs.bu.edu
Sun Feb 15 11:15:17 EST 2015


---------- Forwarded message ----------
From: Daniel Wichs <wichs at ccs.neu.edu>

Please join us for the next installment of Crypto Day
<https://bostoncryptoday.wordpress.com/> on Friday, February 20 at
Microsoft Research, New England. The schedule and directions are below.
Hope to see you there!

- Daniel, Nir, Vinod, Yael

*Location and Arrival Instructions:*
Microsoft New England Research and Development Center
One Memorial Drive, Cambridge MA 02142

Upon arrival, be prepared to show a picture ID and sign the Building
Visitor Log when approaching the Lobby Floor Security Desk. Alert them to
the name of the event, and ask them to direct you to the appropriate floor.
The talks will be held the First Floor Conference Center, in the Horace
Mann Conference Room. Detailed guidance on directions, via car or public
transportation, is available here
<http://research.microsoft.com/en-us/labs/newengland/visit.aspx>. Parking
will be available for the on-site parking garage for $27/day.

Program:9:30 – 10:00.Introduction/Coffee10:00 – 11:00.
Tal Malkin, Columbia
*The Power of Negations in Cryptography*
11:30 – 12:30.Rachel Lin, USCB
*Constant-Round Concurrent Zero-knowledge from Indistinguishability
Obfuscation*12:30 – 2:00.Lunch (provided)2:00 – 3:00.Alessandra Scaffuro,
BU and Northeastern
*Garbled RAM From One-Way Functions*3:30 – 4:30.Henry Corrigan-Gibbs,
*Building Anonymous Messaging Systems that ‘Hide the Metadata’*Abstracts:

*Speaker: Tal Malkin *
*Title: The Power of Negations in Cryptography*

The study of monotonicity and negation complexity for Boolean functions has
been prevalent in complexity theory as well as in computational learning
theory, but little attention has been given to it in the cryptographic
context. Recently, Goldreich and Izsak (2012) have initiated a study of
whether cryptographic primitives can be monotone, and showed that one-way
functions can be monotone (assuming they exist), but a pseudorandom
generator cannot.

In this work, we start by filling in the picture and proving that many
other basic cryptographic primitives cannot be monotone. We then initiate a
quantitative study of the power of negations, asking how many negations are
required. We provide several lower bounds, some of them tight, for various
cryptographic primitives and building blocks including one-way
permutations, pseudorandom functions, small-bias generators, hard-core
predicates, error-correcting codes, and randomness extractors. Among our
results, we highlight the following.

i) Unlike one-way functions, one-way permutations cannot be monotone.

ii) We prove that pseudorandom functions require log n−O(1) negations
(which is optimal up to the additive term).

iii) Error-correcting codes with optimal distance parameters require log
n−O(1) negations (again, optimal up to the additive term).

iv) We prove a general result for monotone functions, showing a lower bound
on the depth of any circuit with t negations on the bottom that computes a
monotone function f in terms of the monotone circuit depth of f. This
result addresses a question posed by Koroth and Sarma (2014) in the context
of the circuit complexity of the Clique problem.

Joint work with Siyao Guo, Igor Carboni Oliveira, and Alon Rosen.

*Speaker: Rachel Lin *
*Title: Constant-Round Concurrent Zero-knowledge from Indistinguishability

We present a constant-round concurrent zero-knowledge protocol for NP. Our
protocol relies on the existence of families of collision-resistant hash
functions, one-way permutations, and indistinguishability obfuscators for
P/poly (with slightly super-polynomial security).

*Speaker: Alessandra Scafuro*
*Title: Garbled RAM From One-Way Functions*

Yao’s garbled circuit construction is a fundamental construction in
cryptography and recent efficiency optimizations have brought it much
closer to practice. However these constructions work only for circuits and
garbling a RAM program involves the inefficient process of first converting
it into a circuit. Towards avoiding this inefficiency, Lu and Ostrovsky
[Eurocrypt 2013] introduced the notion of “garbled RAM” as a method to
garble RAM programs directly. It can be seen as a RAM analogue of Yao’s
garbled circuits such that, the size of the garbled program and the time it
takes to create and evaluate it, is proportional only to the running time
on the RAM program rather than its circuit size.
Known realizations of this primitive, either rely on stronger computational
assumptions such as the existence of
Identity-Based Encryption, or rely on one-way functions only but do not
achieve the aforementioned efficiency [Gentry, Halevi, Lu, Ostrovsky,
Raykova and Wichs, EUROCRYPT 2014].

In this work we provide the first construction with strictly
poly-logarithmic overhead in both space and time based only on the minimal
that one-way functions exist.

Join work with Sanjam Garg, Steve Lu and Rafail Ostrovsky.

*Speaker: Henry Corrigan-Gibbs *
*Title: Building Anonymous Messaging Systems that ‘Hide the Metadata’*

Encryption can protect the contents of a message being sent over an open
network. In many situations, though, hiding the contents of a communication
is not enough: parties to a conversation want to conceal the fact that they
ever communicated. In this talk, I will explain how anonymity-preserving
messaging systems can help ‘hide the metadata’ pertaining to a conversation
and I will survey the state of the art in anonymous messaging protocols.

A limitation of existing protocols is that they exhibit computation and
communication costs that scale linearly with the number of users (i.e., the
anonymity set size) or they require expensive zero-knowledge proofs. In
recent work, we have designed Riposte, a new system for anonymous messaging
that applies private-information-retrieval and secure multi-party
computation techniques to circumvent these limitations.

An implementation and experimental evaluation of Riposte demonstrates that,
for latency-tolerant applications, the system can provide near-ideal
anonymity for groups of millions of users—two orders of magnitude more than
current systems support. I will conclude the talk with a discussion of open
problems and directions for future work.

Joint work with: Dan Boneh and David Mazières

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
For more options, visit https://groups.google.com/d/optout.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20150215/435447e2/attachment.html>

More information about the Busec mailing list