[Busec] Tomorrow, Friday, Feb 20: Charles River Crypto Day @ MSR

Sharon Goldberg goldbe at cs.bu.edu
Thu Feb 19 10:23:01 EST 2015

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

Daniel, Vinod, Yael, Nir

> *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,
> Stanford
> *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
> Obfuscation*
> 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
> assumption
> 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.

Sharon Goldberg
Computer Science, Boston University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20150219/c1bc0bb3/attachment.html>

More information about the Busec mailing list