Archive

Monthly Archives: January 2017

Join us for the first Charles River Crypto Day of 2017 on Friday, February 17 at Microsoft Research New England. In addition to celebrating great research, we are also celebrating Yevgeniy Dodis’s upcoming wedding!

When: Friday, February 17.

Where:  Microsoft New England Research and Development Center
Clara Barton Room (First Floor),
One Memorial Drive, Cambridge MA 02142.

Organizers: Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.

Program:

9:30 – 10:00. Introduction/Coffee
10:00 – 11:00.
Tal Rabin, IBM Research
Privacy-Preserving Search of Similar Patients in Genomic Data
11:00 – 12:00.
Yevgeniy Dodis, NYU (Congratulations on upcoming wedding!!!)
Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited
12:00 – 1:30. Lunch (provided)
1:30 – 2:30. Mark Zhandry, Princeton
The Magic of ELFs
2:30 – 3:30. Chris Peikert, Michigan
Pseudo-randomness of Ring-LWE for any Ring and Modulus
3:30 – 4:00. Coffee Break
4:00 – 5:00. Hoeteck Wee, CNRS and ENS
“Real Cryptographers don’t use Obfuscation”

Abstracts:

TITLE: Privacy-Preserving Search of Similar Patients in Genomic Data

SPEAKER: Tal Rabin, IBM Research

ABSTRACT:
The growing availability of genomic data holds great promise for advancing medicine and research, but unlocking its full potential requires adequate methods for protecting the privacy of individuals whose genome data we use. One example of this tension is running Similar Patient Query on remote genomic data: In this setting a doctor that holds the genome of his/her patient may try to find other individuals with “close” genomic data (in edit distance), and use the data of these individuals to help diagnose and find effective treatment for that patient’s conditions. This is clearly a desirable mode of operation, however, the privacy exposure implications are considerable, so we would like to carry out the above “closeness” computation in a privacy preserving manner.

In this work we put forward a new approach for highly efficient edit-distance approximation that works well even in settings with much higher divergence. We present contributions both in the design of the approximation method itself and in the protocol for computing it privately.

We also implemented our system. There is a preprocessing step which takes 11-15 seconds and then each query can be answered in 1-2 second depending on the database size.

Joint work with Gilad Asharov, Shai Halevi, and Yehuda Lindell.

TITLE: Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited

SPEAKER: Yevgeniy Dodis, New York University

ABSTRACT:

We revisit security proofs for various cryptographic primitives in the random oracle model with auxiliary input (ROM-AI): a (computationally unbounded) attacker A can compute arbitrary S bits of leakage z=z(O) 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 in 2007 (CRYPTO 2007), but dates back to the seminal paper of Hellman in 1980 about time-space tradeoffs for inverting random functions, and has natural applications in settings where traditional random oracle proofs are not useful: (a) security against non-uniform attackers; (b) space-time tradeoffs; (c) security against preprocessing; (d) resilience to backdoors in hash functions.

We obtain a number of new results about ROM-AI, but our main message is that ROM-AI is the “new cool kid in town”: it nicely connects theory and practice, has a lot of exciting open questions, leads to beautiful math, short definitions, elegant proofs, surprising algorithms, and is still in its infancy. In short, you should work on it!

Joint Work with Siyao Guo and Jonathan Katz.

TITLE: The Magic of ELFs

SPEAKER: Mark Zhandry, Princeton

ABSTRACT:

We introduce the notion of an Extremely Lossy Function (ELF). An ELF is a family of functions with an image size that is tunable anywhere from injective to having a polynomial-sized image. Moreover, for any efficient adversary, for a sufficiently large polynomial r (necessarily chosen to be larger than the running time of the adversary), the adversary cannot distinguish the injective case from the case of image size r.

We develop a handful of techniques for using ELFs, and show that such extreme lossiness is useful for instantiating random oracles in several settings. In particular, we show how to use ELFs to build secure point function obfuscation with auxiliary input, as well as polynomially-many hardcore bits for any one-way function. Such applications were previously known from strong knowledge assumptions — for example polynomially-many hardcore bits were only know from differing inputs obfuscation, a notion whose plausibility has been seriously challenged. We also use ELFs to build a simple hash function with output intractability, a new notion we define that may be useful for generating common reference strings.

Next, we give a construction of ELFs relying on the exponential hardness of the decisional Diffie-Hellman problem, which is plausible in elliptic curve groups. Combining with the applications above, our work gives several practical constructions relying on qualitatively different — and arguably better — assumptions than prior works.

TITLE: Pseudorandomness of Ring-LWE for Any Ring and Modulus

SPEAKER: Chris Peikert, University of Michigan

ABSTRACT:

Our main result is a quantum polynomial-time reduction from worst-case problems on ideal lattices to the decision version of Learning With Errors over Rings (Ring-LWE), for any number ring and any modulus that is not too small (relative to the error rate). Such a reduction was previously known for the search version of Ring-LWE, but hardness of the decision version—which is typically needed for cryptographic applications—was only known to hold for the special case of Galois number rings, such as cyclotomics. The new reduction at least matches, and in some cases improves upon, the parameters obtained in prior work for both the search and decision problems.

Our approach also applies to the original Learning With Errors (LWE) problem, yielding a quantum reduction from worst-case problems on general lattices to decision LWE, again matching or improving upon the parameters obtained by all prior reductions.

Joint work with Oded Regev and Noah Stephens-Davidowitz.

TITLE: “Real cryptographers don’t use obfuscation”

SPEAKER: Hoeteck Wee, CNRS and ENS Paris

ABSTRACT:

In this talk, I will provide a survey of several recent works showing how to use pairing groups to “compile” private-key primitives to public-key ones.