[Busec] DC Area Crypto Day

Adam O'Neill adam at cs.georgetown.edu
Tue Sep 9 21:48:57 EDT 2014

As promised, here's a detailed schedule for the day.

9AM-10AM: Breakfast (in 2460 A.V. Williams Bldg)
10AM-11AM: David Cash, Rutgers University (in 2460 A.V. Williams Bldg)
11AM-11:30AM: Break
11:30AM-12:30PM: Mark Zhandry, Stanford University (in 2460 A.V. Williams
12:30PM-2PM: Lunch (on your own; a number of convenient options are nearby)
2PM-3PM: John Kelsey, NIST (in 2460 A.V. Williams Bldg)
3PM-3:30PM: Break
3:30PM-5PM: Elaine Shi, University of Maryland (in CSIC 3117)

Please find the titles and abstracts for the talks below.  We look forward
to seeing you!

Speaker: David Cash, Rutgers University
Title:  The Locality of Searchable Encryption

Abstract: Searchable encryption allows a data owner to encrypt an index in
a way that allows for searching on her behalf by an untrusted server that
cannot decrypt the data. The author’s recent work (joint with a team at IBM
Research) on constructing searchable encryption revealed that, in contrast
to most cryptographic computation, the primary performance bottleneck of
encrypted search came from poor external memory (disk) utilization and not
in, say, number-theoretic processing. This was due to a lack of “spatial
locality” in all known constructions. While performing an encrypted search,
the server must read a random-looking sequence of positions on the disk.
This non-locality dramatically reduced throughput compared to a plaintext
search, which can arrange to read only a few blocks from the disk.

Motivated by our difficulties, this work initiates the study of the
relationship between external memory utilization and security. While the
area of external memory algorithms is well-developed and widely used for
deployed systems, we are unaware of any prior connection between the area
and security.  Our results are primarily negative: We will show that, in an
asymptotic sense, the poor external memory utilization of our system is an
unavoidable property of any searchable encryption construction. In more
detail, we show that any secure searchable encryption must read memory in a
non-local way or suffer some other impractical drawback such as hugely
enlarging the index during encryption. On the positive side we give a
theoretical construction that provides a trade-off between locality and
index size not previously achieved.


Speaker: Mark Zhandry, Stanford University
Title: Fully Secure Functional Encryption Without Obfuscation

Abstract: Previously known functional encryption (FE) schemes for general
circuits relied on indistinguishability obfuscation, which in turn either
relies on an exponential number of assumptions (basically, one per
circuit), or a polynomial set of assumptions, but with an exponential loss
in the security reduction. Additionally these schemes are proved in an
unrealistic selective security model, where the adversary is forced to
specify its target before seeing the public parameters. For these
constructions, full security can be obtained but at the cost of an
exponential loss in the security reduction.

In this work, we overcome the above limitations and realize a fully
secure functional encryption scheme without using indistinguishability
obfuscation. Specifically the security of our scheme relies only on the
polynomial hardness of simple assumptions on multilinear maps.


Speaker: John Kelsey, NIST
Title: Making a New Hash Standard

Abstract: Between 2007 and 2012, NIST ran a competition to find a new
hashing standard.  In this talk, I will discuss what led us to run the
competition, how the competition went, and the process of going from a
competition winner to a set of standards.  I'll also talk about some of the
lessons we learned in running this competition, and our current plans for
writing standards related to the SHA3 hashing standard.


Speaker: Elaine Shi, University of Maryland
Title: A Survey of Tree-Based ORAM Schemes and their Applications

Abstract: Oblivious RAM (ORAM), originally proposed by Goldreich and
Ostrovsky, is a cryptographic construction for provably obfuscating access
patterns to sensitive data during computation. Since the initial proposal
of Oblivious RAM, the two biggest open questions in this area are 1)
whether ORAM can be made practical; and 2) whether Goldreich and
Ostrovsky's ORAM lower bound is tight.

In this talk, I will describe a new tree-based paradigm for constructing
Oblivious RAMs. This new paradigm has not only yielded extremely simple
constructions, but also given encouraging answers to the above questions.
Notably, in this the tree-based framework, we construct Path ORAM and
Circuit ORAM. The former has enabled, for the first time, ORAM-capable
secure processors to be prototyped; while the latter is, to date, the ORAM
scheme of choice in cryptographic secure computation. Moreover, Circuit
ORAM also shows that certain stronger interpretations of Goldreich and
Ostrovksy's ORAM lower bound are tight.

Finally, I will describe programming language techniques for memory-trace
oblivious program execution. We not only provide formal security guarantees
through new type systems, but also enable compile-time optimizations that
lead to order-of-magnitude speedup in practice.

On Wed, Aug 27, 2014 at 5:41 PM, Adam O'Neill <adam at cs.georgetown.edu>

> Dear Colleagues,
> Please save the date and join us for our first DC Area Crypto Day, on *Monday,
> September 15 *at the University of Maryland (College Park).  We hope to
> help solidify the growing community of cryptographers in the DC area, and
> to foster interactions amongst our community and those nearby.
> We are pleased to announce the following speakers:
> David Cash, Rutgers University
> John Kelsey, NIST
> Elaine Shi, University of Maryland
> Mark Zhandry, Stanford University
> DC is easy to get to by flight, train, or bus, and the University of
> Maryland is connected to the DC metro.  For location and lodging info
> please see:
> http://cs.umd.edu/location
> http://cvs.umd.edu/visitors/offcampus.html
> We anticipate the day to go from about 10am to 5pm, to allow ample time
> for free discussion.  A detailed program will follow shortly.
> Please forward this announcement to anyone (especially students and
> post-docs) who may be interested.
> Cheers,
> Adam
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20140909/f439e0b7/attachment-0001.html>

More information about the Busec mailing list