DC-Area Crypto Day

September 15, 2014

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

Please find the titles and abstracts 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.

Top of page

Clark School        UMIACS   CMNS