Comparison of Access Pattern Protection Schemes and Proposals for Efficient Implementation

Yuto NAKANO  Shinsaku KIYOMOTO  Yutaka MIYAKE  Kouichi SAKURAI  

IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.10   pp.2576-2585
Publication Date: 2014/10/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2013THP0007
Type of Manuscript: INVITED PAPER (Special Section on Frontiers of Internet of Things)
access pattern protection,  oblivious RAM,  private information retrieval,  

Full Text: FreePDF

Oblivious RAM (ORAM) schemes, the concept introduced by Goldreich and Ostrovsky, are very useful technique for protecting users' privacy when storing data in remote untrusted servers and running software on untrusted systems. However they are usually considered impractical due to their huge overhead. In order to reduce overhead, many improvements have been presented. Thanks to these improvements, ORAM schemes can be considered practical on cloud environment where users can expect huge storage and high computational power. Especially for private information retrieval (PIR), some literatures demonstrated they are usable. Also dedicated PIRs have been proposed and shown that they are usable in practice. Yet, they are still impractical for protecting software running on untrusted systems. We first survey recent researches on ORAM and PIR. Then, we present a practical software-based memory protection scheme applicable to several environments. The main feature of our scheme is that it records the history of accesses and uses the history to hide the access pattern. We also address implementing issues of ORAM and propose practical solutions for these issues.