Friday April 17 at Northeastern

Please join us for the next installment of Crypto Day on Friday, April 17 at Northeastern University.

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.