Charles River Crypto Day on Friday, April 17 @ Northeastern
Daniel Wichs
Location:
103 Churchill Hall
Northeastern University Boston, MA 02115
Program:
| 9:30 – 10:00. | Introduction/Coffee |
| 10:00 – 11:00. | Leo Reyzin, BU Wyner’s Wire-Tap Channel, Forty Years Later |
| 11:30 – 12:30. | Christopher Fletcher, MIT Onion ORAM: A Constant Bandwidth ORAM using Additively Homomorphic Encryption |
| 12:30 – 2:00. | Lunch (provided) |
| 2:00 – 3:00. | Daniele Micciancio, UCSD FHEW: Bootstrapping Homomorphic Encryption in less than a second |
| 3:30 – 4:30. | Kobbi Nissim, Ben-Gurion University and CRCS@Harvard Learning under Differential Privacy |
Abstracts:
Speaker: Leo Reyzin
Wyner’s Wire-Tap Channel, Forty Years Later
Wyner’s information theory paper “The Wire-Tap Channel” turns forty this year. Its importance is underappreciated in cryptography, where its intellectual progeny includes pseudorandom generators, privacy amplification, information reconciliation, and many flavors of randomness extractors (including plain, strong, fuzzy, robust, nonmalleable, source-private, local, and reusable). Focusing mostly on privacy amplification and fuzzy extractors, I will demonstrate the connection from Wyner’s paper to today’s research, including work on program obfuscation. I will conclude with some recent results on the feasibility of fuzzy extractors, based on joint work with Benjamin Fuller and Adam Smith.
Speaker: Christopher Fletcher
Title: Onion ORAM: A Constant Bandwidth ORAM using Additively Homomorphic Encryption
Oblivious RAM (ORAM) is a cryptographic primitive that obfuscates a client’s access pattern (address, data, read/write) to an untrusted memory source. In addition to its traditional application to outsourced storage, ORAM has proven to be an important component in the Cryptographic “swiss army knife” — finding uses in Garbled RAM, Secure Computation, Proofs of Retrievability, and more.
In this talk I will discuss Onion ORAM, a constant bandwidth ORAM that uses poly-logarithmic server computation to circumvent the well-known logarithmic lower bound in ORAM bandwidth. In addition to being constant bandwidth, Onion ORAM achieves constant client and server storage blowups — asymptotically optimal for each category — and does so without relying on Fully Homomorphic Encryption. In particular, we only require an Additively Homomorphic Encryption scheme with constant ciphertext blowup such as the Damgard-Jurik cryptosystem. We will extend the scheme to be secure against a malicious server using standard assumptions. To the best of our knowledge, Onion ORAM is the first concrete instantiation of a constant-bandwidth ORAM with poly-logarithmic computation (even for the semi-honest setting).
Joint work with Ling Ren, Srini Devadas, Marten van Dijk, Elaine Shi and Daniel Wichs
Speaker: Daniele Micciancio
Title: FHEW: Bootstrapping Homomorphic Encryption in less than a second
The main bottleneck affecting the efficiency of all known fully homomorphic encryption (FHE) schemes is Gentry’s bootstrapping procedure, which is required to refresh noisy ciphertexts and keep computing on encrypted data. We present a new method to homomorphically compute simple bit operations, and refresh (bootstrap) the resulting output, which runs on a personal computer in just about half a second.
Join work with Leo Ducas, to appear in Eurocrypt 2015
Speaker: Kobbi Nissim
Title: Learning under Differential Privacy
Learning is a task that abstracts many of the computations performed over large collections of sensitive individual information, hence natural to examine in conjunction with differential privacy. Predating differential privacy, in 2005 Blum, Dwork, McSherry and Nissim showed that any concept class that is learnable in Kearns’ model of statistical queries is also learnable with privacy. The concept of Private Learning formalized by Kasiviswanathan et al. in 2008 as the conjunction of PAC learning and differential privacy. They showed that any concept class |C| can be learned privately with O(log|C|) samples, via a construction that is somewhat analogous to the Occam Razor (non-private) learner.
Investigating the gap between the sample complexity and computational complexity of private and non-private learners resulted in a rich picture that we will highlight in the talk. In particular, we will examine some of the lower bound and upper bound techniques used in this context, and explore some of the ways to mitigate the costs of private learners. Time permitting, we will see relationships between private learning and other tasks, such as median computation and data sanitization.
Based on joint works with: Amos Beimel, Avrim Blum, Hai Brenner, Mark Bun, Cynthia Dwork, Shiva Kasiviswanathan, Homin Lee, Frank McSherry, Sofya Raskhodnikova, Adam Smith, Uri Stemmer, and Salil Vadhan.
