# Friday, December 9 at Northeastern

Join us for Charles River Crypto Day on Friday, December 9 at Northeastern University.

**When:** Friday, December 9.

**Where: 90 Snell Library, Northreastern University Campus, Boston MA **

**Directions:** This link takes you 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 Wichs.

**Thanks:** NSF MACS Project for their generous support.

### Program:

9:30 – 10:00. | Introduction/Coffee |

10:00 – 11:00. |
Dana Dachman-Soled, UMD
Towards Non-Black-Box Separations of Public Key Encryption and One Way Function |

11:15 – 12:15. |
Leo Reyzin, BU
Scrypt is Maximally Memory-Hard |

12:15– 1:30 | Lunch (provided) |

1:30 – 2:30. | Gillat Kol, PrincetonInteractive Compression for Product Distributions |

3 – 4 | Mike Rosulek, Oregon StateLinicrypt: A Model for Practical Cryptography |

### Abstracts:

**Speaker: Dana Dachman-Soled**

**Title:**

**Towards Non-Black-Box Separations of Public Key Encryption and One Way Function**Abstract: Separating public key encryption from one way functions is one of the

fundamental goals of complexity-based cryptography. Beginning with the seminal

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 way

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 BBNp

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`

no instances,” y ~ f(U_n), and Arthur may receive

probability over

polynomial-sized, non-uniform advice. This assumption is related to the

average-case analogue of the widely believed assumption coNP \not\subseteq

NP/poly.

**Speaker: Leo Reyzin**

**Title: Scrypt is Maximally Memory-Hard**

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