For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2014/10/01
Online ISSN: 1745-1361
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.