Practical Private DB Querying
summary
Practical system for private queries on ~100M records uses an encrypted bloom-filter tree and deterministic tokens to get sublinear search with ~log-depth boolean circuits, trading leakage of access patterns and circuit size for speed. Policy checks run inside a universal garbled circuit so authorized queries are enforced with almost zero overhead versus semi-honest execution. Measured footprint: leaves ~25 GB, root ~0.5 GB, fits in 96 GB RAM; leaf false positives around 0.01%, and leakage quantifies query-complexity and visited node paths.
AI-written summary · about
chapters (16)
- 0:00Intro
- 2:21Mediumsized database
- 3:05Architecture
- 4:07Requirements
- 4:55Access Patterns
- 5:53Bloom Filter
- 6:41How we do it
- 9:57What can you learn
- 11:05The Bloom Filter
- 13:07Security Requirements
- 19:19Universal Gate
- 19:59Free XOR Gate
- 20:24Practical Applications
- 24:54Concurrent Security
- 27:24Bloom Filters
- 29:22False Positive
related talks
44mBreaking Encrypted Databases: Generic Attacks on Range Queries
44mBreaking Encrypted Databases: Generic Attacks on Range Queries
28mSharing Information and Intelligence without Disclosing It - Private Search Set (PSS)
19mPrefix Siphoning: Exploiting LSM-Tree Range Filters For Information Disclosure
31mFast, highly effective database security using searchable encryption (without the yak shave)
12mLessons from years of building privacy-preserving technologies
37mFrontiers in Cryptography
41mNon-traditional Encryption Problems And Solutions