Comparison of access pattern protection schemes and proposals for efficient implementation

Yuto Nakano, Shinsaku Kiyomoto, Yutaka Miyake, Kouichi Sakurai

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)2576-2585
Number of pages10
JournalIEICE Transactions on Information and Systems
Issue number10
Publication statusPublished - Oct 1 2014

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'Comparison of access pattern protection schemes and proposals for efficient implementation'. Together they form a unique fingerprint.

Cite this