Abstract
Preface
Acknowledgments
Contents
1 Introduction
1.1 The Necessity for Always-Encrypted Data
1.2 Searching Always-Encrypted Databases
1.3 Architecture and Operation Framework
1.3.1 The Abstracted Scenario
1.3.2 Threat Assumptions
Semi-Honest vs. Malicious Model
Snapshot vs. Persistent Adversary
1.4 Balancing Among Security, Performance, and Functionality
1.4.1 Encrypted Search with Controlled Leakage
1.4.2 Common Choices of Allowed Information Leakages
1.5 Early Results, Progress Today, and Challenges Ahead
1.6 Summary and Further Readings
2 Fundamental Cryptographic Algorithms and Technologies
2.1 Property-Preserving Encryption
2.1.1 Deterministic Encryption
2.1.2 Order-Preserving/Order-Revealing Encryption
2.2 Homomorphic Encryption
2.3 Oblivious RAM
2.4 Trusted Execution Environment
2.5 Summary and Further Reading
3 Searchable Encryption Semantics
3.1 Definitions for Searchable Symmetric Encryption
3.1.1 Security Definitions
3.1.2 Non-adaptive and Adaptive Semantic Security for SSE
3.2 Efficient and Secure Searchable Symmetric Encryption
3.2.1 The Evolutionary Process of SSE Schemes
3.2.2 A Milestone Design
3.2.3 Encrypted Multi-Map and Searchable Structured Encryption
3.3 Public-Key Encryption with Keyword Search
3.4 Summary and Further Reading
4 Recent Advancements on Functionality and Performance
4.1 Toward Dynamic Data Support with Scalability
4.1.1 An Intuitive SSE Extension Supporting Data Dynamics
An Illustrative Example
Performance and Leakage
4.1.2 A More Scalable Construction Considering Add-Only Updates
Extension for Updates
Performance and Leakage
4.1.3 A Conceptually Forward Private Construction
Necessity of Forward Privacy
Performance and Leakage
4.1.4 An Efficient Dynamic SSE Achieving Forward Privacy
General Ideas to Achieve Forward Privacy
Performance and Leakage
Limitations Induced by Forward Privacy
4.1.5 Handling Backward Privacy with Data Deletions
4.2 Multiple-User Support
4.2.1 An Intuitive SSE Extension Supporting Multiple Users
Performance and Security
4.2.2 Multi-User Support with Search Token Distribution
4.2.3 Multi-Writer Searchable Encryption Schemes
4.3 Boolean Query Support
4.3.1 Extension Basis
4.3.2 Oblivious Cross-Tags (OXT) Protocol
4.3.3 Processing Boolean Queries
4.4 Performance Optimizations
4.4.1 Constructions Supporting Data Locality
4.4.2 Some Impossibility Results Regarding Data Locality
4.4.3 Taking into Account Page Efficiency
4.4.4 Constructions Supporting Parallel Search Execution
4.5 Summary and Further Reading
5 Security Impact of Leakage Profiles: Threats andCountermeasures
5.1 Understanding Leakage Profiles
5.1.1 A Leakage Hierarchy for SE
In-Place SE Schemes
Inverted-Index SE
5.2 Exploit Leakage Profiles Against SE Schemes
5.2.1 Leveraging Co-Occurrence Pattern to Recover User Queries
5.2.2 The Count Attack
Attack Description
5.2.3 The Subgraph Attack
5.3 File-Injection Attacks
5.3.1 Binary-Search Attack
Threshold Countermeasure
5.3.2 Hierarchical-Search Attack
5.4 More Threats from Leakage Profiles
5.4.1 Attacks Against Encrypted Range Queries
Theoretical Bounds
5.4.2 Approximate Reconstruction Attacks
Generalized Range-Query Attack
5.4.3 Other Attacks Against ESAs
5.5 Countermeasures and Future Directions
5.5.1 An Almost Zero-Leakage Searchable Encryption Scheme
The Cache-Based Compiler
5.5.2 Volume-Hiding Encryption Schemes
5.5.3 More Practical Volume-Hiding Multi-Maps
5.5.4 Differentially Private Volume-Hiding Scheme
5.5.5 Frequency Smoothing
5.6 Further Reading
6 Toward Fully Functional Encrypted Databases
6.1 Overview of Database Systems
6.2 Using Cryptographic Primitives
6.2.1 A Confidential Database System Over Efficient SQL-Aware Encryption Schemes
SQL-Aware Encryption
Improving Security and Performance
6.2.2 A More Secure Encrypted Database Using Semantically Secure Encryption
Architecture Overview
Functionalities Supported by Arx
Building Blocks
ArxEq and Equality Queries
ArxRange and Order-Based Queries
Performance of Arx
6.2.3 Interoperable Encrypted Database
6.3 Using Hardware-Assisted Secure Enclave
6.3.1 A Scalable Encrypted Database Supporting Full SQL Query Types with Intel SGX
Database Creation
DBMS Initialization
Client Authentication
Query Execution
Security Analysis
Performance Evaluation
6.3.2 Oblivious Query Processing for Secure Databases
Security Guarantees
Architecture and Data Structures
Oblivious Query Processing
Oblivious Aggregate and Group-By Queries
Oblivious Join Queries
Query Planner
Performance and Security
6.4 Design Choices in Building Encrypted Databases
6.4.1 Exploration to a Broader Design Space
6.4.2 An Enclave-Native Storage Design for Practical Encrypted Databases
Enclage Index
Parameter Selection
Enclage Store
Scalability and Integrity Protection
6.5 Further Reading and Future Suggestions
7 Conclusion
References