Séminaire LJK-Modèles et Algorithmes Déterministes: CASYS

 

Le Jeudi 21 Septembre 2017 à 14h00 en Salle 104 - Batiment IMAG

 

Séminaire de Mr Daniel S ROCHE (United States Naval Academy Annapolis, Maryland, U.S.A.)

 

A better write-only oblivious RAM

 

Résumé:

 

Oblivious RAM (ORAM) protocols allow for the storage of private information over untrusted networks. They hide not only the contents of data (as is possible with plain encryption), but also the access patterns (which items are accessed, when, and by whom). In this talk, we will first give an overview of how ORAMs work and where they are used. We start by looking at the original "square root" construction of Goldreich & Ostrovsky (JACM '96), and then the more recent Path ORAM of Stefanov, Shi, and others (CCS '13). There has been considerable recent work in improving these schemes both in theoretical complexity as well as practical performance. We next turn to write-only ORAM schemes, which can achieve even better performance by assuming read operations are not revealed to an adversary, a setting which is applicable in multiple scenarios such as cloud backup and encrypted hidden volumes. The original write-only ORAM by Blass, Mayberry, and others (CCS '14) was a revolutionary concept, but still contained some problematic aspects of earlier constructions. Our recent construction (CCS '17, to appear) improves the write-only ORAM. It achieves absolutely optimal communication complexity for write operations, and an asymptotic O(log N) factor improvement for reads. Furthermore, the protocol is deterministic with a sequential access pattern to the underlying physical medium. This not only simplifies the security proof, but also greatly improves practical performance.