Secure Oblivious Storage and Anonymous Communication Through Random Mixing

When: Friday, December 14, 2018
Where: PGH 232
Time: 11:00 AM

Speaker: Prof. Eli Upfal, Brown University

Host: Prof. Gopal Pandurangan

We present two applications of random mixing in constructing secure communication protocols. In the first work (joint with O. Ohrimenko, M. T. Goodrich, and R. Tamassia) we construct a simple, efficient, and secure data-oblivious randomized shuffle algorithm. Our method improves previous oblivious storage solutions for network-based outsourcing of data, such as cloud storage.

The second work (with M. Ando, Megumi and A. Lysyanskaya) presents practical and provably secure onion routing protocols. Akin to Tor, for anonymous routing. In an onion routing protocol, messages travel through several intermediaries before arriving at their destinations; they are wrapped in layers of encryption (hence they are called "onions"). The goal is to make it hard to establish who sent the message. It is a practical and widespread tool for creating anonymous channels. Our work is the first to present provable secure protocol in that setting.

Bio:

Eli Upfal is the Rush C Hawkins professor of computer science at Brown University, where he was also the department chair from 2002 to 2007. Prior to joining Brown in 1998, he was a researcher and project manager at the IBM Almaden Research Center in California, and a professor of Applied Mathematics and Computer Science at the Weizmann Institute of Science in Israel. Upfal's research focuses on the design and analysis of algorithms. In particular he is interested in randomized algorithms, probabilistic analysis of algorithms, and computational statistics, with applications ranging from combinatorial and stochastic optimization to routing and communication networks, computational biology, and computational finance. He has published over 200 research papers in scientific journals and conferences. He is co-author of a popular textbook, Probability and Computing: Randomized Algorithms and Probabilistic Analysis (with M. Mitzenmacher, Cambridge University Press 2005, 2017), and holds 13 US patents. Professor Upfal is a Fellow of the ACM and the IEEE.