Why combine ORAM and FHE?
- Oblivious RAM (ORAM) hides the access pattern of memory reads/writes, preventing leakage from which data is accessed.
- Fully Homomorphic Encryption (FHE) lets a server compute on encrypted data without ever seeing the plaintext.
When both are used, an adversary learns nothing about the data values or the sequence of operations—crucial for secure cloud computation on sensitive workloads.
Core construction
| Step | Operation (performed by the client) | Operation (performed by the server) |
|---|---|---|
| 1 | Encrypt each data block with an FHE scheme → ciphertexts c_i. | — |
| 2 | Store the ciphertexts in an ORAM tree (e.g., Path‑ORAM). | Maintain the tree structure; no decryption needed. |
| 3 | To read/write block b:• Client generates a homomorphic query token that encodes the logical path to b. | Server uses the token to homomorphically evaluate the ORAM routing logic, retrieving the encrypted block without learning which leaf was accessed. |
| 4 | Server returns the ciphertext (or updated ciphertext) to the client. | All operations are performed on ciphertexts; the server never sees plaintext or the actual address. |
| 5 | Client decrypts (if needed) and, for writes, re‑encrypts the updated block and repeats the ORAM eviction step homomorphically. | Server runs the eviction algorithm on encrypted blocks, preserving the ORAM invariant. |
Achieving constant‑time behavior
- Fixed‑size buckets – Each ORAM node stores a constant number
Zof ciphertexts (e.g.,Z = 4). - Uniform access pattern – Every logical operation triggers the same number of homomorphic evaluations (e.g., always traverse a full path of height
log₂ N). - Parallel homomorphic evaluation – Modern FHE schemes (CKKS, BFV) support SIMD packing; the server can process all buckets of a level in a single homomorphic batch, keeping latency independent of the accessed block.
Thus the total runtime per logical access is O(log N) in the number of homomorphic batches, but each batch has a constant size, yielding a practically constant‑time routine from the client’s perspective.
Example parameter set
- Data size:
N = 2¹⁶blocks. - ORAM bucket size:
Z = 4. - FHE scheme: BFV with 128‑bit security, ciphertext modulus
q ≈ 2⁶⁴. - Batch size:
Z·log₂ N = 4·16 = 64ciphertext slots per homomorphic evaluation.
With these settings, a single logical read/write requires:
- One homomorphic evaluation of the routing function per tree level (16 levels).
- One homomorphic eviction pass (also 16 levels).
Both steps are executed in parallel across the 64 slots, giving a predictable wall‑clock time (e.g., ~200 ms on a modern GPU‑accelerated FHE server).
Security notes
- Access‑pattern leakage is eliminated by ORAM’s obliviousness.
- Data‑value leakage is prevented by the semantic security of the FHE scheme.
- The combined construction remains secure under the standard IND‑CPA assumption for FHE and the ORAM security definition (indistinguishability of access sequences).
In summary, a constant‑time routine can be built by storing FHE‑encrypted blocks in a fixed‑bucket ORAM tree, using homomorphic tokens to traverse the tree uniformly, and performing parallel homomorphic evaluations for routing and eviction. This yields predictable latency while protecting both data values and access patterns.