what: make r/w ops on a remote untrusted server indist to an observer. Note that a private enclave regards the rest of the machine a remote untrusted server.
why: spose client (a TEE) operates on sensitive data on an untrusted remote server. The server can observe where the user reads from and writes to, and whether the operation is read/write (the access patterns).
More what: ORAM is a compiler to transform
Example: operations on a database. Naive:
- Client C makes a request R from the server S to download the entire encrypted database D
- C decrypts D, performs some operation, re-encrypts, and uploads D'
Big issue: all operations are extremely costly, but we achieve private operations; and the database operations are indistinguishable to the server. ORAM should obtain the same security identically, without the costs.
Operation of ORAM:
- given element e, operation o, decide a subset S of remote storage that contains the element
- download S, decrypt it
- find e, perform o(e)
- reshuffle the elements of S, keeping track of order, then re-encrypt and re-upload
Costs:
- still have to download some subset
More advanced techniques exist to obtain perfect secrecy, and to use bucketing and recursion to reduce the storage on the client to logarithmic in the number of values stored on the client.
- topic:: [[topic-implementing secure storage]]
- topic:: [[topic-RAM]]
An Introduction to Oblivious RAM (ORAM) – Kudelski Security Research