Searchable Encryption: From Concepts to Systems

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