Paper 2023/872
Conjunctive Searchable Symmetric Encryption from Hard Lattices
Abstract
Searchable Symmetric Encryption (SSE) supports efficient keyword searches over encrypted outsourced document collections while minimizing information leakage. All practically efficient SSE schemes supporting conjunctive queries rely crucially on quantum-broken cryptographic assumptions (such as discrete-log hard groups) to achieve compact storage and fast query processing. On the other hand, quantum-safe SSE schemes based on purely symmetric-key crypto-primitives either do not support conjunctive searches, or are practically inefficient. In particular, there exists no quantum-safe yet practically efficient conjunctive SSE scheme from lattice-based hardness assumptions. We solve this open question by proposing Oblivious Post-Quantum Secure Cross Tags (OQXT) – the first lattice-based practically efficient and highly scalable conjunctive SSE scheme. The technical centerpiece of OQXT is a novel oblivious cross-tag generation protocol with provable security guarantees derived from lattice-based hardness assumptions. We prove the post-quantum simulation security of OQXT with respect to a rigorously defined and thoroughly analyzed leakage profile. We then present a prototype implementation of OQXT and experimentally validate its practical efficiency and scalability over extremely large real-world databases. Our experiments show that OQXT has competitive end-to-end search latency when compared with the best (quantum-broken) conjunctive SSE schemes.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. IEEE European Symposium on Security and Privacy
- Keywords
- Lattice-based cryptographySearchable Symmetric EncryptionPost-quantum cryptography
- Contact author(s)
-
debadritat fg2219 @ gmail com
sikharpatranabis @ gmail com
debdeep mukhopadhyay @ gmail com - History
- 2024-06-18: revised
- 2023-06-08: received
- See all versions
- Short URL
- https://ia.cr/2023/872
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2023/872, author = {Debadrita Talapatra and Sikhar Patranabis and Debdeep Mukhopadhyay}, title = {Conjunctive Searchable Symmetric Encryption from Hard Lattices}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/872}, year = {2023}, url = {https://eprint.iacr.org/2023/872} }