This book comprehensively reviews searchable encryption, which represents a series of research developments that directly enable search functionality over encrypted data. The book majorly covers: 1) the design and implementation of encrypted search algorithms, data structures, and systems that facilitate various forms of search over always-encrypted databases; 2) different threat models, assumptions, and the related security guarantees, when using searchable encryption in the real-world settings; and 3) latest efforts in building full-fledged encrypted database systems that draw insights from searchable encryption constructions.
The book fits in the timely context, where the necessity of safeguarding important and sensitive data has been globally recognized. Traditional security measures, such as storing data behind network firewalls and layers of access control mechanisms to keep attackers out, are no longer sufficient to cope with the expanding landscape of surging cyber threats. There is an urgent call to keep sensitive data always encrypted to protect the data at rest, in transit, and in use. Doing so guarantees data confidentiality for owners, even if the data is out of their hands, e.g., hosted at in-the-cloud databases. The daunting challenge is how to perform computation over encrypted data. As we unfold in this book, searchable encryption, as a specific line of research in this broadly defined area, has received tremendous advancements over the past decades.
This book is majorly oriented toward senior undergraduates, graduate students, and researchers, who want to work in the field and need extensive coverage of encrypted database research. It also targets security practitioners who want to make well-informed deployment choices of the latest advancements in searchable encryption for their targeted applications. Hopefully, this book will be beneficial in both regards.
Author(s): Kui Ren, Cong Wang
Series: Wireless Networks
Publisher: Springer
Year: 2023
Language: English
Pages: 177
City: Cham
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
