Export to
Thursday, April 17, 2014 at 4:14pm.
Galois tech talk: A Gentle Introduction to Hiding Usage Patterns
Website
Description
abstract: What if you want to store encrypted files on an untrusted Cloud Server in such a way that Server does not even know if you are editing the same file today as you were yesterday, or anything else about your usage patterns other than total amount of traffic to the Server? Clearly, no matter how strong of an encryption you use, access pattern is revealed: Cloud Server can simply track where on the hard drive you read/write from – clearly encryption does not hide that information. One naive solution to prevent revealing access pattern to the Server is to simply read all your data back from the Server and re-write your entire data back to Server in its entirety for each read/write. This works, but it is clearly impractical. Oblivious Random Access Memory (ORAM) is an algorithm that allows you to completely hide arbitrary access pattern in an efficient manner. In this talk, I will describe Oblivious RAM from the ground up, starting from my own Ph.D. thesis work on this topic (STOC 1990, MIT Ph.D. 1992) which showed the first efficient ORAM. The Journal Version of this work gained over 450 references according to Google Scholar [Ostrovsky-Goldreich JACM 1996] and ORAM became an important area of research in Cryptography in the last 5 years. I will describe surprising connections of ORAM to (1) tamper-proof embedded systems, (2) Software Protection (3) Secure Multi-Party and Secure Two Party Computation as well as (4) ways to securely compile programs with loops, “goto” statements, recursion, etc. into Garbled programs without “unrolling” the execution path, yet not revealing anything about the execution path. I will also compare and contrast ORAM to Single-Server Private Information Retrieval (Single-server PIR), which I co-invented with Kushilevitz in 1997, and explain important differences of these two models. The talk will be self-contained and accessible to the general audience.
Speaker bio: Rafail Ostrovsky is a Professor of Computer Science and Professor of Mathematics at UCLA and co-founder of Stealth Software Technologies, Inc. He has over 200 papers published in refereed journals and conferences and has 11 U.S. Patents issued. In 2013, Dr. Ostrovsky was inducted as an IACR (International Association of Cryptologic Research) Fellow. He currently serves as Vice-Chair of the IEEE Technical Committee on Mathematical Foundations of Computing and has served on 38 international conference Program Committees including serving as a PC chair of FOCS 2011. He is a member of the Editorial Board of JACM, the Editorial Board of Algorithmica; and the Editorial Board of Journal of Cryptology; he serves on the Editorial and Advisory Board of the International Journal of Information and Computer Security and is a member of the steering committee of the international symposium of Security in Communication Networks (SCN). He is a recipient of multiple academic awards and honors and has google h-index factor of 55. At UCLA, Prof. Ostrovsky heads security and cryptography multi-disciplinary Research Center (http://www.cs.ucla.edu/security/) at Henry Samueli School of Engineering and Applied Science.