🔬 What's Novel
- Database-specific oblivious access patterns exploiting LSM and content-addressing structure
- Formal analysis of information leakage in multi-tenant database deployments
- Tiered obliviousness framework balancing security guarantees and performance overhead
- Practical implementation targeting real-world shared hosting scenarios
🔧 Technical Approach
Phase 1 — Threat Model
Formalize the multi-tenant adversary model: an attacker can observe I/O patterns, timing, and memory access patterns (side channels) to infer sensitive information about co-tenant queries.
Phase 2 — Pattern Analysis
Characterize SkeinDB's access patterns per query type. Identify which patterns leak information and which are inherently obfuscated by content-addressing.
Phase 3 — Oblivious Primitives
Build oblivious ValueStore lookup (padding + dummy accesses), oblivious index traversal (oblivious sorting), and oblivious scan operations (deterministic padding).
Phase 4 — Tiered System
Policy-based obliviousness levels per table/column. The system auto-applies the appropriate protection level, from full ORAM for highly sensitive data to minimal padding for public tables.
🧪 Hypotheses
Database-specific access patterns can be protected more efficiently than generic ORAM because they exhibit structural regularity.
ValueStore content-addressing provides inherent obfuscation; targeted padding can achieve formal obliviousness guarantees.
Tiered obliviousness (stronger for sensitive data, weaker for public) provides practical security-performance tradeoffs.
🔗 SkeinDB Integration
📚 Key References
- Stefanov et al. — "Path ORAM: An Extremely Simple Oblivious RAM Protocol" (2013)
- Crooks et al. — "Obladi: Oblivious Serializable Transactions in the Cloud" (2018)
- Eskandarian & Zaharia — "ObliDB: Oblivious Query Processing for Secure Databases" (2019)