Charles River Crypto Day at BU - Speakers: Yevgeniy Dodis, Guy Bresler, David Heath, and Gabe Kaptchuk

Speaker: Yevgeniy Dodis, Guy Bresler, David Heath, and Gabe Kaptchuk

Date: Friday, March 11, 2022

Time: 9:00 AM to 4:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: BU’s Barrister Hall (located at the ground floor of the law school tower)

Event Type:

Room Description:

Host: Ran Canetti, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs

Contact: Deborah Goodwin,

Relevant URL:

Speaker URL:

Speaker Photo:

Reminders to:,,

Reminder Subject: TALK: Charles River Crypto Day at BU - Speakers: Yevgeniy Dodis, Guy Bresler, David Heath, and Gabe Kaptchuk

Logistics: All attendants are required to be fully vaccinated, and wear masks when indoors at all times.

9:00 – 9:30 Welcome and Coffee
9:30 – 10:30 Yevgeniy Dodis, NYU Small-Box Cryptography
11:00 – 12:00 Guy Bresler, MIT Average-case Reductions amongst Statistical Problems
12 – 1:30 Lunch (provided)
1:30 – 2:30 David Heath, Georgia Tech EpiGRAM: Practical Garbled RAM
2:30 – 3:00 Coffee
3:00 – 4:00 Gabe Kaptchuk, Boston University Weaving Social Accountability into Cryptographic Protocols

Speaker: Yevgeniy Dodis - Title: Small-Box Cryptography

Abstract: One of the ultimate goals of symmetric-key cryptography is to find a rigorous theoretical framework for building complex cryptographic primitives from small components, such as cryptographic S-boxes. Unfortunately, a fundamental obstacle towards reaching this goal comes from the fact that traditional security proofs cannot get security beyond 1/2^n, where n is the size of the corresponding small component. As a result, prior provably secure approaches — which we call “big-box cryptography” — always made n larger than the security parameter, which led to several problems. Most notably, the design was too coarse to really explain practical constructions, as (arguably) the most interesting design choices happening when instantiating such “big-boxes” were completely abstracted out.

In this work, we introduce a novel paradigm (or heuristic?) for building big objects from small objects, which we call small-box cryptography.

As an illustration, we apply our framework to the analysis of SPN ciphers (e.g, generalizations of AES), getting quite reasonable concrete hardness estimates for the resulting ciphers. We also apply our framework to the design of stream ciphers. Here, however, we focus on the simplicity of the resulting construction, for which we also managed to find a direct “big-box”-style security justification, under a well-studied and widely believed eXact Linear Parity with Noise (XLPN) assumption.

Overall, we hope that our work might initiate new follow-up results in the area of small-box cryptography.

Joint work with Harish Karthikeyan and Daniel Wichs.

Speaker: Guy Bresler - Title: Average-Case Reductions Amongst Statistical Problems

Abstract: In this talk I will describe a few simple average-case reduction techniques and use these techniques to show how the computational phase transitions in a variety of statistical problems with widely varying structures all follow from a slight generalization of the planted clique conjecture. Some of these problems are robust sparse linear regression, tensor PCA, and certain dense stochastic block models. The talk is based on joint work with Matthew Brennan (

Speaker: David Heath - Title: EpiGRAM: Practical Garbled RAM

Yao’s Garbled Circuit (GC) is a foundational technique for achieving secure multiparty computation (MPC). GC allows two parties to securely compute any Boolean circuit. However, many computations are naturally expressed as RAM programs, not as Boolean circuits. While any RAM program can be polynomially reduced to a circuit, in practice the reduction is often prohibitively expensive.

Garbled RAM (GRAM) is a GC improvement that directly supports random access arrays without adding extra rounds to the GC protocol. Hence, GRAM allows us to securely and directly compute RAM programs. The first non-trivial GRAM (Lu and Ostrovsky, Eurocrypt 2013) required repeated evaluation of a PRF inside GC. Unfortunately, this non-black-box use of a cryptographic primitive is staggeringly expensive. While several subsequent works improved various important aspects of GRAM, no works addressed the central issue: GRAM remained expensive.

In this talk, I will present EpiGRAM, a new construction that dramatically improves GRAM’s efficiency. EpiGRAM improves over prior work by three to four orders of magnitude and opens the door to using GRAM in implementations. Our key insight is a new garbled data structure that we call a lazy permutation network. This data structure allows the garbled circuit to efficiently (and without extra rounds) outsource RAM accesses to the GC evaluator. In this talk, I will present the technical issues inherent to GRAM, and I will show how the lazy permutation network efficiently solves these problems.

EpiGRAM is joint work with Vladimir Kolesnikov (Georgia Tech) and Rafail Ostrovsky (UCLA) and will appear at Eurocrypt 2022.

Speaker: Gabe Kaptchuk - Title: Weaving Social Accountability into Cryptographic Protocols

When deployed, cryptographic systems transform from purely technical system into sociotechnical constructs. As a result, cryptographers must take special care that it is possible to keep those who use these cryptographic systems maliciously can be help accountable, by making misuse difficult and detectable. I investigate this problem in the setting of end-to-end encrypted systems. First, I will discuss Abuse Resistant Law Enforcement Access Systems [Eurocrypt21], which studies the problem of constructing law enforcement access systems (ie. government backdoors) that ensure accountability mechanisms in the case of unauthorized surveillance. Second, I will discuss Apple’s recent CSAM scanning proposal, analyzing the system through the lens of accountability.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Deborah Goodwin Email at Friday, February 25, 2022 at 12:09 PM.