Searchable Symmetric Encryption (SSE) & Oblivious RAM (ORAM) Studio
Defend cloud databases against access pattern reconstruction attacks. Compare deterministic SSE trapdoors against Path ORAM tree traversals, evaluate bandwidth scaling vs leak resistance, and model oblivious eviction reshuffling.
1. Encrypted Database Architecture & Query Target
2. Cryptographic Execution & Access Pattern Trace
3. Encrypted Search Paradigms Comparison Matrix
| PARADIGM | BANDWIDTH OVERHEAD | SEARCH PATTERN LEAK | ACCESS PATTERN LEAK | SECURITY BOUND |
|---|---|---|---|---|
| Path ORAM (Stefanov 2013) | O(log N) (~256 KB) | ZERO | ZERO (Oblivious) | Full Information-Theoretic Obliviousness |
| SSE Inverted Index (Curtmola) | O(1) (~4 KB) | Leaks Query Repetition | Leaks Matching Document IDs | Vulnerable to Co-occurrence attacks |
| Deterministic / ECB | O(1) (Exact size) | 100% Leaked | 100% Leaked | Trivial Frequency Reconstruction |
⚠️ 5 Fatal Traps in Encrypted Database Deployments
1. Underestimating Access Pattern Reconstruction Attacks
Many engineers assume AES encryption in an SQL database (e.g. MariaDB data-at-rest encryption or encrypted indexes) secures user privacy. However, a malicious DBA who monitors disk access logs can observe which encrypted rows are queried together. With auxiliary public knowledge (e.g. zip code distributions), they can decrypt over 80% of queries.
2. Path ORAM Stash Buffer Catastrophic Overflow
In Path ORAM, blocks that cannot be written back to their assigned tree path remain in the client's stash buffer. If the bucket capacity Z is set too small (e.g. Z < 4), the stash probability distribution has a fat tail. Under high eviction load, the stash overflows, forcing un-oblivious flushes or client crash.
3. Search Token Determinism in Searchable Symmetric Encryption
In standard SSE, Trapdoor(w) = HMAC(K_s, w) produces the exact same cryptographic token every time the user searches for "w". An untrusted server can count how many times "w" is issued per day and match the query rate against public trends (e.g. Google Trends spikes during flu season), unmasking the query.
4. File Size Volume Leakage in Encrypted Object Storage
Encrypting PDF medical reports or video files without fixed-size padding leaks the exact byte size of the file. Because medical diagnostic scans have distinct characteristic file size footprints, an adversary can classify patient illnesses with 90%+ confidence simply by reading the Content-Length header.
5. Position Map Storage Scaling on Resource-Constrained Clients
Path ORAM requires a "Position Map" storing which leaf in the tree each logical block currently resides in. For a 1-billion-block cloud database, the position map requires ~4 GB of local client RAM. Mobile or embedded clients must use Recursive ORAM, which adds additional tree lookups to store the position map obliviously on the server.