Oct 21, 2022 (Friday) at Columbia University, the Mudd Building, Computer Science Dept, 500 West 120th Street, New York, NY. CSB 453.
Program
| 09:30 – 10:00. | Introduction/Coffee |
| 10:00 – 11:05. | Tancrède Lepoint (AWS Privacy Engineering) CRYSTALS-Kyber and CRYSTALS-Dilithium: Future PQC Standards |
| 11:15 – 12:05. | Yiping Ma (University of Pennsylvania) Single-Server Private Information Retrieval in the Shuffle Model |
| 12:05 – 02:00. | Lunch (not provided) |
| 02:00 – 02:50. | Ghada Almashaqbeh (University of Connecticut) Unclonable Polymers and Their Cryptographic Applications |
| 03:00 – 03:50. | David Heath (University of Illinois Urbana-Champaign) Stacked Garbling and MPC with Improved Conditional Branching |
Venue
Address: Columbia University, the Mudd Building, Computer Science Dept, 500 West 120th Street, New York, NY. CSB 453.
The department office is at the entrance to the Computer Science Building, itself located in the lobby of the 4th floor of the Mudd Engineering Building. There are doors to Mudd on the 1st floor at 500 West 120th Street (near Amsterdam Avenue). The Mudd doors on the campus level are on the 4th floor. Starting at the main entrance to the campus at Broadway and 116th Street, walk along College Walk and turn left up the steps. At the top of the steps is a large building with a dome: Low Library. Take the walkway to the right of Low Library, and the Mudd building is at the end of this walk. Upon entering Mudd, turn right and then right again. This is the entrance to Computer Science.
Organizers
Fabrice Benhamouda (Algorand Foundation)
Nicholas Genise (Duality Technologies)
Tal Rabin (University of Pennsylvania)
with the help and support of Tal Malkin (Columbia).
Support
NY CryptoDay is sponsored by Google.
Abstracts
- CRYSTALS-Kyber and CRYSTALS-Dilithium: Future PQC Standards / Tancrède Lepoint (AWS Privacy Engineering)
In this talk, we will present CRYSTALS-Kyber and CRYSTALS-Dilithium, respectively a public-key encryption and key-establishment algorithm and a digital signature scheme, selected for standardization and recommended for general use by NIST. Both algorithms are based on hard problems over module lattices and are designed to withstand attacks by large quantum computers. We will also briefly overview the other digital signatures selected for standardization (SPHINCS+ and Falcon) and will discuss the trade-offs they offer.
- Single-Server Private Information Retrieval in the Shuffle Model / Yiping Ma (University of Pennsylvania)
We consider the problem of private information retrieval (PIR) in the shuffle model, where queries can be made anonymously by multiple clients. We present the first single-server PIR protocol in this model that has sublinear per-client communication and information-theoretic security. Moreover, following one-time preprocessing, our protocol only requires sublinear per-client computation. Concretely, for every γ > 0, the protocol has O(n^γ) communication and computation costs per client, with 1/poly(n) statistical security, assuming that a size-n database is simultaneously accessed by poly(n) clients. This should be compared with a previous protocol of Ishai, Kushilevitz, Ostrovsky, and Sahai (FOCS 2006), which in a similar setting achieves computational security under a nonstandard cryptographic assumption.
Finally, we show a unique advantage of PIR in the shuffle model: it enables PIR on variable-length database records without the overhead of padding to the same length, while only revealing (an upper bound on) the total size of records retrieved by all clients.
- Unclonable Polymers and Their Cryptographic Applications / Ghada Almashaqbeh (University of Connecticut)
We propose a mechanism for generating and manipulating protein polymers to obtain a new type of consumable storage that exhibits intriguing cryptographic “self-destruct” properties, assuming the hardness of certain polymer-sequencing problems. To demonstrate the cryptographic potential of this technology, we first develop a formalism that captures (in a minimalistic way) the functionality and security properties provided by the technology. Next, using this technology, we construct and prove security of two cryptographic applications that are currently obtainable only via trusted hardware that implements logical circuitry (either classical or quantum). The first application is a password-controlled secure vault where the stored data is irrecoverably erased once a threshold of unsuccessful access attempts is reached. The second is (a somewhat relaxed version of) one-time programs, namely a device that allows evaluating a secret function only a limited number of times before self-destructing, where each evaluation is made on a fresh user-chosen input. Finally, while our constructions, modeling, and analysis are designed to capture the proposed polymer-based technology, they are sufficiently general to be of potential independent interest.
- Stacked Garbling and MPC with Improved Conditional Branching / David Heath (University of Illinois Urbana-Champaign)
In multiparty computation (MPC), cost traditionally scales proportionally with the size of the circuit we wish to compute. A recent line of work that began with Stacked Garbling (Heath and Kolesnikov, Crypto 2020) shows that MPC cost can be reduced when handling circuits with conditional behavior. Such behavior naturally arises from program IF and SWITCH statements. In this talk, I will present Stacked Garbling (SGC). SGC is an improvement to the classic Garbled Circuit (GC) technique that reduces communication cost for circuits with conditional behavior while still relying only on symmetric-key cryptography. SGC’s communication cost scales only with the size of the single largest conditional branch, not with the total size of the circuit. I will present the technical details of our approach with an emphasis on high-level ideas that translate to settings outside GC. I will also briefly discuss how the idea of “stacking” has found success outside of GC, and how MPC has recently become more efficient for programs with conditional branching.
nycryptoday 