Oblivious RAM (ORAM)

Encryption Alone is Not Sufficient

Encryption preserves the contents of the data, but it may still leak access patterns.
For example, if location x is accessed frequently, an observer can infer its importance—even if the data itself is encrypted.


Student and Locker Room Analogy — An Example

  1. Imagine:

    • A student (client) has secret notes stored in lockers (server).

    • Each locker has a number (like a memory address).

    • Every time the student wants to read or update a note, he walks to the corresponding locker.

  2. If someone is watching:

    • They can see which lockers the student accesses.

    • Even if they cannot read the notes, they can infer which notes are accessed frequently or repeatedly.

  3. To hide this:

    • The student always visits multiple lockers, including some randomly chosen fake ones.

    • He periodically shuffles and reorders the notes.

    • As a result, the observer cannot tell which locker contains the real note or which accesses are genuine.

This is exactly what Oblivious RAM (ORAM) does—it hides access patterns to memory so that no meaningful information is leaked from memory access behavior.

Formal Definition
An ORAM protocol is a system like

  • A client (who wants to read/write memory)

  • A server (who stores data, but is untrusted)

We require: The sequence of memory accesses (read/write, address) should reveal nothing about the actual sequence of operations, except for their total number. 

This is ensured by: 

  • Randomizing access pattern.

  • Hiding read vs dummy operations.

  • Periodically reshuffling the data.


Path ORAM — Basic Idea

i) Assumptions:

  1. Data is organized in a binary tree structure.

  2. Each block (data item) is assigned a random leaf.

  3. The server stores the full tree, while the client stores a small position map and a stash.

ii) Components:

A. Position Map (Client):
Stores, for each data block, the leaf to which it is currently assigned.

B. Stash (Client):
Temporarily holds blocks during access or reorganization.

C. Binary Tree (Server):
Each node contains a small bucket of blocks. A block is guaranteed to exist somewhere along the path from the root to its assigned leaf.

iii) Accessing a Block

Suppose the client wants to read or write block x.

Steps:

  1. Lookup Position Map:
    Find the leaf to which block x is currently assigned.

  2. Read Path:
    Read the entire path from the root to that leaf.

  3. Move Blocks to Stash:
    Temporarily store all blocks from the path into the stash.

  4. Access Block x:
    Locate block x in the stash and return or update it.

  5. Remap Block x:
    Assign block x a new random leaf.

  6. Write Back:
    Refill the buckets along the path from stash, as much as possible (based on bucket size constraints).

Important:
Every access operation reads and writes the full path from the root to a leaf, making the access pattern always look the same—regardless of which block is actually being accessed.

What the Observer Sees

From the server’s perspective:

  1. A path from the root to some leaf is accessed.

  2. However, the server cannot tell which block was accessed or whether it was a real or dummy block.


Thus, the memory access pattern is oblivious, and no meaningful information about data usage is leaked.


We thanks to..

1. https://www.youtube.com/watch?v=iGfgngtVLr4&t=1479s

Comments

Post a Comment

Popular posts from this blog

Homomorphic Encryption: A Basic Idea

Image
Homomorphic encryption has the same aim as other encryption-decryption mechanisms: maintaining confidentiality, security, privacy, etc.  In this blog, we will see homomorphic encryption and its type.  Homomorphic Encryption (HE):  It is an encryption that computes operations over encrypted data without decrypting it (or without the need for a secret key).  Mathematically speaking in a client-server architecture: client has message 'm' and function f. The task of client is to compute f(m). Due to computational expensiveness (maybe one of the reason) client sends encryption of message (say Enc(m)) and 'f' to the server. Server will compute function over encrypted message, that is, f(Enc(m)), and return the result to the client, that is, Enc(f(m)). Client will decrypt it Dec(Enc(f(m)), that is, f(m). Hence, client achieves f(m).  Let's understand HE with our daily life (Tea making process): Figure 1. Here m is message, Enc is encryption, f is function, and Eval in...
Read more

Elliptic Curve Cryptography (ECC) and ECDSA

Image
Elliptic Curve Cryptography (ECC) Elliptic curve (EC) was first introduced by Neal Kobiltz and Victor Miller in 1985. Elliptic curve is a non-singular curve that is operated on a finite field Zq (where q is the order of elliptic curve). EC consists of set of points that satisfies the following equation as follows.                                                                   Y 2 = X 3 + aX + b Where {X,Y,a,b} ∈ Zq, and 4a 3 + 27b 2 ≠ 0. Next, we discuss the encryption and decryption mechanism between two parties (Say α and γ ). Remark 1: Elements selected from party α is represented by capital letters whereas elements selected from party γ is represented by small letters. i) Key Generation: 1. Secret key: Each party α and γ selects secret keys S ∈ Zq and s ∈ Zq. 2. Public key: P ...
Read more

Fast Base Conversion and Its Application

Image
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d     77 14 \mod 77  and want to convert it to x m o d     390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x  in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q  is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ​ ), and x x  is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q  and t t  are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d     t x \mod t , it will provide x ′ m o d     t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t )  =  x  +  A q  mod  t , where A ∈ [ 0 , k − 1 ] A \in [0,...
Read more