[Busec] [charles-river-crypto-day] Charles River Crypto Day on Friday, Feb 17 @ MSR

Vinod Vaikuntanathan vinod.nathan at gmail.com
Sun Feb 12 12:25:05 EST 2017

Dear Friends,

Join us for the first Charles River Crypto Day of this year!

*When:* *Friday Feb 17*

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

*Why: Experience CRYPTOMANIA*™ *with five great speakers!*

See https://bostoncryptoday.wordpress.com/ or below for details.

See you all there!




10-11 Tal Rabin, IBM Research
Privacy-Preserving Search of Similar Patients in Genomic Data

11-12 Yevgeniy Dodis, NYU
Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input,

12-1:30 lunch

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 Coffee Break

4-5 Hoeteck Wee, CNRS and ENS
"Real Cryptographers don't use Obfuscation"

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

SPEAKER: Tal Rabin, IBM Research


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,

SPEAKER: Yevgeniy Dodis, New York University


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


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


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


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

You received this message because you are subscribed to the Google Groups "Charles River Crypto Day" group.
To unsubscribe from this group and stop receiving emails from it, send an email to charles-river-crypto-day+unsubscribe at googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/charles-river-crypto-day/CALd0SCUGrV7AJ2ThkKKwxubyzUBcKvZAMU%2B8AEYmne%2BCj7p69Q%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20170212/85d9ee82/attachment-0001.html>

More information about the Busec mailing list