[Busec] [charles-river-crypto-day] Charles River Crypto Day, Friday Dec 9 @ Northeastern
wichs at ccs.neu.edu
Tue Nov 29 15:31:46 EST 2016
Join us for the next Charles River Crypto Day on Friday Dec 9 at
See https://bostoncryptoday.wordpress.com/ or below for details.
Important: you must register to attend this event by filling out: this
See you all there!
*When:* Friday, December 9.
*Where: 90 Snell Library
Northreastern University Campus, Boston MA *
*Directions:* This link
to the correct building on google maps. Also, see directions for public
transportation and driving/parking
Once you enter the library go downstairs to get to room 90.
Please register (free) to attend this event by filling out this form
We need all attendees to register to get access to Snell library.
*Organizers:* Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel
*Thanks:* NSF MACS Project <http://www.bu.edu/macs/> for their generous
9:30 – 10:00. Introduction/Coffee
10:00 – 11:00.
Dana Dachma-Soled, UMD
*Towards Non-Black-Box Separations of Public Key Encryption and One Way
11:15 – 12:15.
Leo Reyzin, BU
*Scrypt is Maximally Memory-Hard*
12:15– 1:30 Lunch (provided)
1:30 – 2:30. Gillat Kol, Princeton
*Interactive Compression for Product Distributions*
3 – 4 Mike Rosulek, Oregon State
*Linicrypt: A Model for Practical Cryptography*
*Speaker: Dana Dachman-Soled*
*Title: Towards Non-Black-Box Separations of Public Key Encryption and One
Abstract: Separating public key encryption from one way functions is one of
fundamental goals of complexity-based cryptography. Beginning with the
work of Impagliazzo and Rudich (STOC, 1989), a sequence of works have ruled
out certain classes of reductions from public key encryption (PKE)—or even
key agreement—to one way function. Unfortunately, known results—so called
black-box separations—do not apply to settings where the construction and/or
reduction are allowed to directly access the code, or circuit, of the one
function. In this work, we present a meaningful, non-black-box separation
between public key encryption (PKE) and one way function.
Specifically, we introduce the notion of BBN- reductions (similar to the
reductions of Baecher et al. (ASIACRYPT, 2013)), in which the construction E
accesses the underlying primitive in a black-box way, but wherein the
universal reduction R receives the efficient code/circuit of the underlying
primitive as input and is allowed oracle access to the adversary Adv. We
additionally require that the number of oracle queries made to Adv, and the
success probability of R are independent of the run-time/circuit size of the
underlying primitive. We prove that there is no non-adaptive, BBN- reduction
from PKE to one way function, under the assumption that certain types of
strong one way functions exist. Specifically, we assume that there exists a
regular one way function f such that there is no Arthur-Merlin protocol
proving that z not in Range(f)'', where soundness holds with high
probability overno instances,” y ~ f(U_n), and Arthur may receive
polynomial-sized, non-uniform advice. This assumption is related to the
average-case analogue of the widely believed assumption coNP \not\subseteq
*Speaker: Leo Reyzin*
*Title: Scrypt is Maximally Memory-Hard*
Abstract: The function scrypt (Percival, 2009) is defined as the result of
n steps, where each step consists of selecting one or two previously
computed w-bit values (the selection depends on the values themselves) and
hashing them to get a new w-bit value. Because it is conjectured that this
function is memory-hard, it has been used for key derivation and proofs of
work in cryptocurrencies, and has inspired subsequent designs.
We show that indeed scrypt is maximally memory-hard in the parallel random
oracle model. Specifically, we show that the product of memory and time
used during the computation of scrypt must be Theta(n^2 w), even if the
adversary is allowed to make an unlimited number of parallel random oracle
queries at each step. Moreover, even if the amount of memory used
fluctuates during the computation, we show that the sum of memory usage
over time (a.k.a. “cumulative memory complexity” introduced by Alwen and
Serbinenko at STOC 2015) is Theta(n^2 w), which implies high memory cost
even for adversaries who can amortise the cost over many evaluations.
Our result improves both quantitatively and qualitatively upon the recent
work by Alwen et al. (Eurocrypt ’16) who proved a weaker lower bound of
Omega(n^2 w / log^2 n) for a restricted class of adversaries. Our proof is
the first showing optimal memory hardness in the random oracle model for
Joint work with Joel Alwen, Binyi Chen, Krzysztof Pietrzak, and Stefano
*Speaker: Gillat Kol*
*Title: Interactive Compression for Product Distributions*
Abstract: In a profoundly influential 1948 paper, Claude Shannon introduced
information theory and used it to study one-way data transmission problems
over different channels, both noisy and noiseless. That paper initiated the
study of error correcting codes and data compression, two concepts that are
especially relevant today with the rise of the internet and data-intensive
applications. In the last decades, interactive communication protocols are
used and studied extensively, raising the fundamental question: To what
extent can Shannon’s results be generalized to the interactive setting,
where parties engage in an interactive communication protocol?
In this talk we will focus on the interactive analog of data compression in
an attempt to answer the above question. Specifically, we will consider the
case where the parties have inputs that are independent of each other, and
give a simulation protocol that communicates poly(I) bits, where I is the
information cost of the original protocol. Our protocol is the first
simulation protocol whose communication complexity is bounded by a
polynomial in the information cost of the original protocol.
*Speaker: Mike Rosulek*
*Title: Linicrypt: A Model for Practical Cryptography*
Abstract: A wide variety of objectively practical cryptographic schemes can
be constructed using only symmetric-key operations and linear operations.
To formally study this restricted class of cryptographic algorithms, we
present a new model called Linicrypt. A Linicrypt program has access to a
random oracle whose inputs and outputs are field elements, and otherwise
manipulates data only via fixed linear combinations.
Our main technical result is that it is possible to decide in polynomial
time whether two given Linicrypt programs induce computationally
indistinguishable distributions (against arbitrary PPT adversaries, in the
random oracle model).
We show also that indistinguishability of Linicrypt programs can be
expressed as an existential formula, making the model amenable to automated
program synthesis. In other words, it is possible to use a SAT/SMT solver
to automatically generate Linicrypt programs that satisfy a given security
constraint. Interestingly, the properties of Linicrypt imply that this
synthesis approach is both sound and complete. We demonstrate this approach
by synthesizing Linicrypt constructions of garbled circuits.
This talk is joint work with Brent Carmer.
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/CAHpnE7ZE%3DzLBUqy6uBoEh6JYra_EYu8b9XvLXMUKUVoRYjZfWA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Busec