The Oblivious Random Access Memory (ORAM)

Oblivious RAM (ORAM), first investigated by Goldreich and Ostrovsky, is a primitive intended for hiding storage access patterns. The problem was initially studied in the context of software protection, i.e., hiding a program's memory access patterns to prevent reverse engineering. However, hiding access pattern is caused of process overhead which cannot make it work effectively in practical. The general characteristic of ORAM consists of

  • Client has small storage when compare with the Server side.
  • Server cannot distinguish any access pattern (Read, Write, etc.) that client has requested.
  • Client must not read at same address twice from Server's storage to protect its information of side channel investigation.
  • Server cannot distinguish between real information and dummy information which are contained in server's storage.
  • Server cannot modify information that keeps in its storage. If any information has been altered, those altered information can be recognized by client.

To hiding the access pattern, when client asks to write or read access request to server, client must sending along with read or write access respectively to server to make its request indistinguishable from the server point of view. In additional, accessing to the same address more than one time is also leaking some critical information to server. Thus after read/write access, the address of information in server's storage must be shuffled. From those all conditions, ORAM working procedure consumes a lot of communication overhead (Read/Write hiding pattern) and calculation overhead (Sorting and Shuffling process) which is impractical in real environment. Nowadays, many researchers try to achieve to make practical ORAM by reducing the overhead however, there is not existing scheme that introduce about multiple clients using ORAM on same server. Even though we can design individual ORAM for each single client, it can leak client information to server because of client information "must" be stored within the specific ORAM which count as information leakage to server. To solve this problem, the share space ORAM for multiple clients is considering. By sharing same space, server cannot distinguish the owner of information and it still keeps the original concept of ORAM. However, there are some problem statement that have to be consideration which are

  • Queue management for storing information from clients to server
  • Shared shuffling and sorting pattern between group of clients
  • Achieve the low communication and process overhead.
Top