CryptoDay @ NYU, Friday June 1, 2018

June 1, 2018 (Friday) at NYU, WWH 1302, Warren Weaver Hall, 251 Mercer Street, New York, NY 10012.

Program

9:30 – 10:00.	Introduction/Coffee
10:00 – 10:50.	Oded Regev (NYU) The Development of LWE and the Security of Lattice-Based Cryptography
11:00 – 11:50.	Siyao Guo (Northeastern University) Random Oracles and Non-Uniformity
12:00 – 2:00.	Lunch (not provided)
2:00 – 2:50.	Tancrède Lepoint (SRI) Cryptographic Suite for Algebraic Lattices
3:00 – 3:50.	Chiraag Juvekar (MIT) Gazelle: A Low Latency Framework for Secure Neural Network Inference

Venue

Address: NYU, WWH 1302, Warren Weaver Hall, 251 Mercer Street, New York, NY 10012.
[Directions] [Google Maps]

Organizers

Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)
with the help and support of Yevgeniy Dodis (NYU).

Support

Some travel support for NY CryptoDay is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.

Abstracts

• The Development of LWE and the Security of Lattice-Based Cryptography / Oded Regev (NYU)

  My plan is to give an informal discussion of some of the attempts over the last 15 years to find quantum algorithms for lattice problems.
  I will explain how this led to the development of LWE, and mention the few cases where quantum algorithm are known to outperform classical ones.

• Random Oracles and Non-Uniformity / Siyao Guo (Northeastern University)
  We revisit security proofs for various cryptographic primitives in the auxiliary-input random oracle model (AI-ROM), in which an attacker can compute arbitrary $S$ bits of leakage about the random oracle $O$ before attacking the system and then use additional $T$ oracle queries to $O$ during the attack. This model was explicitly studied by Unruh (CRYPTO 2007) but dates back to the seminal paper of Hellman in 1980 about time-space tradeoffs for inverting random functions, and as natural applications in settings where traditional random oracle proofs are not useful: (a) security against non-uniform attackers; (b) security against preprocessing.We obtain a number of new results about the AI-ROM:(1) Unruh introduced the {\em pre-sampling technique}, which generically reduces security proofs in the AI-ROM to those in a much simpler {\em $P$-bit-fixing random oracle model} (BF-ROM), where the attacker can arbitrarily fix the values of $O$ on some $P$ coordinates, but then the remaining coordinates are chosen at random. Unruh’s security loss for this transformation is $\sqrt{ST/P}$. We improve this loss to the {\em optimal} value $O(ST/P)$, which implies nearly tight security bounds for a variety of indistinguishability applications in the AI-ROM.(2) While the basic pre-sampling technique cannot give tight bounds for unpredictability applications, we introduce a novel “multiplicative version” of pre-sampling, which allows to dramatically reduce the size of $P$ of the pre-sampled set (namely, $P=O(ST)$), and yields nearly tight security bounds for a variety of unpredictability applications in the AI-ROM. Qualitatively, it validates Unruh’s “polynomial pre-sampling conjecture” — disproved in general by Dodis et al. (Eurocrypt 2017) — for the special case of unpredictability applications.

  (3) Finally, we build two general compilers showing how to generically extend the security of applications proven in the traditional ROM to the AI-ROM. One compiler simply prepends a public salt to the random oracle and shows that salting generically provably defeats preprocessing.

  Overall, our results makes it much easier to get concrete security bounds in the AI-ROM. These bounds in turn give concrete conjectures about the security of these applications (in the standard model) against non-uniform attackers.

  Joint work with Sandro Coretti, Yevgeniy Dodis and John Steinberger.

• Cryptographic Suite for Algebraic Lattices / Tancrède Lepoint (SRI)
  In this talk, I’ll introduce CRYSTALS — Cryptographic Suite for Algebraic Lattices —, a cryptographic suite composed of a CCA-secure KEM (CRYSTALS-Kyber) and a digital signature (CRYSTALS-Dilithium) submitted to NIST post-quantum cryptography standardization effort. The CRYSTALS primitives are designed with simplicity and modularity in mind: they are based on hardness assumptions over module lattices and are designed to be simple to protect against side-channel attacks. Module lattices not only enable simple implementations (the core operation, a polynomial multiplication, has only to be implemented in dimension 256), but enable extremely simple scaling up and down of the security without the need to reimplement anything. I’ll then compare the CRYSTALS primitives to other submissions to NIST standardization effort.Joint works with Joppe Bos, Léo Ducas, Eike Kiltz, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé.

 

• Gazelle: A Low Latency Framework for Secure Neural Network Inference / Chiraag Juvekar (MIT)
  The growing popularity of cloud-based machine learning raises a natural question about the privacy guarantees that can be provided in such a setting. Our work tackles this problem in the context where a client wishes to classify private images using a convolutional neural network (CNN) trained by a server. Our goal is to build efficient protocols whereby the client can acquire the classification result without revealing their input to the server, while guaranteeing the privacy of the server’s neural network.To this end, we design Gazelle, a scalable and low-latency system for secure neural network inference, using an intricate combination of homomorphic encryption and traditional two-party computation techniques (such as garbled circuits). We evaluate our protocols on benchmark neural networks trained on the MNIST and CIFAR-10 datasets and show that Gazelle outperforms the best existing systems such as MiniONN (ACM CCS 2017) by 20x and Chameleon (Crypto Eprint 2017/1164) by 30x in online runtime. Similarly when compared with fully homomorphic approaches like CryptoNets (ICML 2016) we demonstrate three orders of magnitude faster online run-time.
  Joint work with Vinod Vaikuntanathan and Anantha Chandrakasan.