Conjunctive Searchable Symmetric Encryption From Hard Lattices

Discusses outsourcing storage and computing, encrypted data computing, and searchable symmetric encryption for data security in cloud environments. It touches on topics like data confidentiality, user revocation, and performance-oriented implementations.

• Cloud Computing
• Data Security
• Encrypted Data
• Searchable Encryption
• Outsourced Storage

moises Follow

Uploaded on Mar 06, 2024 | 2 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Conjunctive Searchable Symmetric Encryption From Hard Lattices Sikhar Patranabis, IBM Research, India Debadrita Talapatra, IIT Kharagpur, India Debdeep Mukhopadhyay, IIT Kharagpur, India https://eprint.iacr.org/2023/872

2. Outsourced Storage and Computing Unstructured data (text documents) Big-data era, resource constrained nature of Client infrastructures, IoT devices : outsourced storage and computation. Outsourcing data storage to third-party cloud server: storage,access. Relational/XML databases Specific formats (e.g., emails) Security Implications Cloud Computing Services Cloud Storage Services Amazon Web Services (AWS) Microsoft Azure Google Cloud Platform IBM Cloud Google Drive Dropbox Microsoft Server Client (honest-but-curious) Data Confidentiality Collusion between entities User Revocation

3. Computing On Encrypted Data Protects data in transit and at rest Encrypt (AES) Search Query ? Server (honest-but-curious) Client

4. Computing On Encrypted Data Fully Homomorphic Encryption1 Functional Encryption2 Order-preserving Encryption3 Deterministic Encryption4 Searchable Symmetric Encryption5,6 Security Efficiency Trade off b/w security and efficiency: Leak some but not all information to the untrusted server Performance-oriented implementations 1. 2. C. Gentry, Fully homomorphic encryption using ideal lattices, in Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 169 178. D. Boneh, A. Sahai, and B. Waters, Functional encryption: Definitions and challenges, in Theory of Cryptography: 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings 8. Springer, 2011, pp. 253 273. Rakesh Agrawal and Jerry Kiernan and Ramakrishnan Srikant and Yirong Xu, {Order-Preserving Encryption for Numeric Data, Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data, Paris, France, June 13-18, 2004. Mihir Bellare and Alexandra Boldyreva and Adam O'Neill, {Deterministic and Efficiently Searchable Encryption, Advances in Cryptology - {CRYPTO} 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007. Reza Curtmola, Juan A. Garay, Seny Kamara, and Rafail Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. In ACM CCS 2006, pages 79 88, 2006. David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. Highly-scalable searchable symmetric encryption with support for Boolean queries. In CRYPTO 2013, pages 353 373, 2013. 3. 4. 5. 6.

5. Outline . Introduction Searchable Symmetric Encryption (SSE) Motivation Oblivious Cross-Tag Protocol (OXT) Our Contribution (OQXT) Discussion

6. Searchable Symmetric Encryption (SSE) Sub-class of a broader class of encryption schemes - Structured Encryption1 Documents Collection of documents where each document is tagged with keywords Representation of a database: Each database is a collection of documents Each document is associated with an id Each document is tagged with a set of keywords Relational Databases Tables with records where each record is associated with attribute-value pairs. Boolean queries over keywords or attribute-value pairs Find all documents tagged with Crypto Find all documents tagged with Alice and Bob and Crypto Find all documents tagged with either Alice or Bob but not Crypto Plain Database (Forward Index) Inverted Index (Search Index) 1. Melissa Chase, Seny Kamara, Structured Encryption and Controlled Disclosure, ASIACRYPT2010: 577-594

7. Conjunctive SSE Server Client ? = ??? ?????? Encrypted Database (EDB) Quantum-safe -- resistant against quantum attacks. Efficient Search Complexity -- sub-linear search time for conjunctive queries. Scalable -- large real-world databases. Single communication round between client and server.

8. Outline . Introduction Searchable Symmetric Encryption (SSE) Motivation Oblivious Cross-Tag Protocol (OXT) Our Contribution (OQXT) Discussion

9. Efficient SSE Schemes rely inherently on public-key cryptographic primitives quantum broken Plausibly quantum-safe SSE schemes that exist in literature are based on purely symmetric-key primitives, and are impractical for real-world databases - Severely limited in terms of the expressiveness of queries they support1,2,3. OXT 6 Relies on discrete-log hard groups ConjFilter4, IEX-2LEV 5 Compact storage of encrypted database SSE schemes that support highly expressive Boolean queries are practically incur a storage complexity that grows quadratically with the size of the plaintext database in the worst case inefficient since they Supports general Boolean queries conjunctive queries and Fast conjunctive query processing time Highly inefficient 1. 2. Raphael Bost. o o : Forward secure searchable encryption. In ACM CCS 2016, pages 1143 1154, 2016. Rapha el Bost, Brice Minaud, and Olga Ohrimenko. Forward and backward private searchable encryption from constrained cryptographic primitives. In ACM CCS 2017, pages 1465 1482, 2017. Reza Curtmola, Juan A. Garay, Seny Kamara, and Rafail Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. In ACM CCS 2006, pages 79 88, 2006. Sarvar Patel, Giuseppe Persiano, Joon Young Seo, and Kevin Yeo. Efficient boolean search over encrypted data with reduced leakage. In ASIACRYPT 2021, volume 13092, pages 577 607, 2021. Seny Kamara and Tarik Moataz. Boolean searchable symmetric encryption with worst-case sub-linear complexity. In EUROCRYPT 2017, pages 94 124, 2017. 6. David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. Highly-scalable searchable symmetric encryption with support for Boolean queries. In CRYPTO 2013, pages 353 373, 2013. 3. 4. 5.

10. Our Contirbution: Quantum-safe SSE The first lattice-based SSE scheme that efficiently supports conjunctive queries over large encrypted databases Oblivious Post-quantum Secure Cross-tags Protocol (OQXT) builds upon a very basic prototype of OXT-like SSE (which is also widely adopted in a vast majority of the SSE literature preceding our work). We introduce several novel techniques to achieve OQXT from quantum-safe lattice-assumptions while retaining all the efficiency guarantees of OXT. Construction of elements from hard lattice assumptions like the Learning With Rounding assumption. Use of lattice-trapdoors such that the computationally intensive operations are performed at setup, thus allowing for fast online search performance Storage overhead for the encrypted database that grows linearly with the size of the plaintext database (unlike IEX-2LEV and ConjFilter), Sublinear search complexity - conjunctive query complexity that grows with the frequency of the least frequent keyword

11. Outline . Introduction Searchable Symmetric Encryption (SSE) Motivation Oblivious Cross-Tag Protocol (OXT) Our Contribution (OQXT) Discussion

12. (OXT1) Server Client Offloaded to the Server ??????????3 ???? ?? ?1,4 ? ?? ?3,??????||2 ? ?? ?3,??????||3 ???? ?? ?1,3 ? ?? ?3,??????||1 ? ???? ? ? ???? ? ? ???? ? ???? ?? ?1,5 (? ,? ) 1 1 1 ? ??? ????,3 ? ??? ????,4 ? ??? ????,5 ??????????1= ???(?1,??????) ???? ??????????2= ???(?1,??????) ???? ??????????3= ???(?1,??????) ???? EDB 1. David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. Highly-scalable searchable symmetric encryption with support for Boolean queries. In CRYPTO 2013, pages 353 373, 2013.

13. (OXT) ? = ??? ?????? Server Client s-term (least frequent ) ???? ???? ??????????? ?????? 1 , ??????[2] EDB ???? ?(??,???) ?1,?1 ?2,?2 ?????? 1,1 = ???(?3,???||1) ??(?1,??????) ?????? 2,1 = ???(?3,???||2) ??(?1,??????) ?????? 1,1?1= [???(?3,???||1) ??(?1,??????)]?1 = [???(?3,???||1) ??(?1,??????)]????.? 1 = [???(?3,???||1) ??(?1,??????)]???2,4 . ??(?3,???||1) 1 = ???(?1,??????) ???2,4 = ???????????

14. (OXT) ? = ??? ?????? Server Client s-term ???? ???? ???????????? ?????? 1 , ??????[2] EDB ?1 ???? ?(??,???) ?1,?1 ?2,?2 ?????? 1,1 = ???(?3,???||1) ??(?1,??????) ?????? 2,1 = ???(?3,???||2) ??(?1,??????) ?????? 2,1?1= [???(?3,???||2) ??(?1,??????)]?1 = [???(?3,???||2) ??(?1,??????)]????.? 1 = [???(?3,???||2) ??(?1??????)]???2,4 . ??(?3,???||2) 1 = ???(?1,??????) ???2,6 = ????????????

15. Compute corresponding to each ???? the discrete-logs Reconstruct the frequency distribution of the keywords across all documents in the database. A quantum adversary (running Shor s algorithm) can solve the discrete logarithm Elements in discrete-log hard group where DDH assumption holds. problem in polynomial time, hence break the DDH assumption. Launch leakage abuse attacks and recover the queried keywords with high accuracy thereby violating query privacy guarantees of OXT OXT is not quantum-safe

16. Outline . Introduction Searchable Symmetric Encryption (SSE) Motivation Oblivious Cross-Tag Protocol (OXT) Our Contribution (OQXT) Discussion

17. OQXT: Quantum-Safe SSE for Conjunctive Queries

18. OQXT Learning With Errors (LWE)1based oblivious cross-tags -- maps each entry in the look-up table X-Set to an LWE sample. ????,?? ??: 0,1??? ???? ? ????????????? ??????? ????? ?????? X-Set ???? = ???? ?? + ? 1. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, pages 34:1 34:40, 2009.

19. OQXT Learning With Errors (LWE) based search tokens -- ? ???? ?? ???? ????,?? ??: 0,1??? ???? ? ,? ????????????? ??????? ????? ?????? ? = ???? ?? ? ?????? = ?? ?? + ? ?? ?????? = ?? ?? ?? + ?? ? = ???? ?? + ? = ???? + ? EDB

20. OQXT Issue with LWE based search tokens ? = ??? ?? ? ? ???? ?????? = ?? ?? + ? ?? ?????? = ?? ?? ?? + ?? ? ?? ???? ????,?? ??: 0,1??? ???? = ???? ?? + ? ? ,? ????????????? ??????? ????? ?????? = ???? + ? ??is not a square matirx ? = ??? ?? 1is not guaranteed to have short entries EDB approximate ???? look-up in X-Set ???? + ? Multiple LWE samples server uses noise-averaging techniques to gain noise-free samples (????). ???? + ?

21. OQXT Lattice Trapdoor Function1,2 Computing ?????? using trapdoors for hard lattices, to ensure the oblivious computation of ???? at the server during search. Generate ? using well-known techniques2to generate a short basis a trapdoor for the lattice generated by the matrix ?? Use this short basis to solve a Short integers solution (SIS)3instance with respect to ??and the target vector ???? to generate the corresponding SIS solution vector ? 1. 2. 3. C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197 206, 2008.. Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller, EUROCRYPT 2012. Mikl os Ajtai. Generating hard instances of lattice problems. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 99 108, 1996

22. OQXT Learning With Rounding Samples1 While computing ???? we switch from discrete-log hard groups to hard lattices where the Learning With Rounding1(LWR) assumption holds. X-Set supports exact look-ups using a Bloom filter. Avoiding the security vulnerabilities associated with approximate ???? reconstruction. ??? doc-id ? keyword ?? ?? ??,? ???? ???? ?? ?I,??? ???? LWR Samples ???? = ???? ?? ? 1. Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions and lattices. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 719 737. Springer, 2012.

23. (OQXT) Server Offloaded to the Server Client ??????????3 (? ,? ) ? ??? ????,4 ? ??? ????,5 ? ??? ????,3 ? ? ? ??,??????||1 ? ? ? ??,??????||2 ? ? ? ??,??????||3 ??( ????),? ??????????? ? ,?,? ??( ????),? ??????????? ? ,?,? ??( ????),? ??????????? ? ,?,? ???? ?? ?I,3 ???? ???? ?? ?I,4 ???? ???? ?? ?I,5 ???? EDB ? ??????? ?,???,????? ? ??????? ?,???,????? ? ??????? ?,???,????? ?? ?? ??,?????? ???? ?? ?? ??,?????? ???? ?? ?? ??,?????? ???? LWR Samples ???? = ???? ???? = ???? ???? = ???? ?? ?? ?? ? ? ?

24. (OXT) ? = ??? ?????? Server Client s-term (least frequent) ???? ???? ?????? 1 , ??????[2] ??????????? EDB ???? ?(??,???) ?1,?1 ?2,?2 ? ?? ??,???||1 ?????( ????),?? ??????????? ? ,?,? ?1? ??????[1,1] ??1 ????,?????? ???? ??????[1,1] = ?????? ? ??? ? = ???????????

25. (OXT) ? = ??? ?????? Server Client s-term ???? ???? ???????????? ?????? 1 , ??????[2] ?1 EDB ???? ?(??,???) ?1,?1 ?2,?2 ? ?? ??,???||2 ?????( ????),?? ??????????? ? ,?,? ?2? ??????[2,1] ? ??1 ????,?????? ???? = ???????????? ??????[2,1] = ?????? ??? ?

26. OQXT- Complexity Analysis 1 2 3 OQXT significantly reduces the quadratic storage overhead incurred by IEX-2LEV and CONJFILTER. OQXT scales linearly with the sub-linear search complexity of OXT. Scales performance of OXT and CONJFILTER asymptotically with the search IEX-2LEV and CONJFILTER have a quadratic storage overhead. Search performance is 10? faster than IEX-2LEV 1. David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. Highly-scalable searchable symmetric encryption with support for Boolean queries. In CRYPTO 2013, pages 353 373, 2013. Sarvar Patel, Giuseppe Persiano, Joon Young Seo, and Kevin Yeo. Efficient boolean search over encrypted data with reduced leakage. In ASIACRYPT 2021, volume 13092, pages 577 607, 2021 Seny Kamara and Tarik Moataz. Boolean searchable symmetric encryption with worst-case sub-linear complexity. In EUROCRYPT 2017, pages 94 124, 2017. 2. 3.

27. OQXT- Search Overhead Lattice Parameters OQXT-I OQXT-II ? 71 512 ? 16 256 ? 256 1048576 Constant time overhead when the least frequent keyword is kept constant. Search complexity of OQXT scales with the frequency of the least frequent keyword. Identical with OXT and CONJFILTER Scales asymptotically with the search performance of OXT and CONJFILTER Considerably faster than IEX- 2LEV Search time is 10? faster than IEX-2LEV

28. OQXT- Storage Overhead Storage overhead increases linearly with the increase in the number of keywords in the database (as depicted by OQXT-I) IEX-2LEV and CONJFILTER have a quadratic storage overhead. IEX-2LEV requires around 2? OQXT-I more storage than CONJFILTER requires around 4? more storage than OQXT-I

29. Discussion FHE vs OQXT Complexity Analysis High storage requirements incurred by encrypting the entire document collection using FHE Storage Complexity Search Complexity Storage overhead of OQXT scales linearly with the size of the database (demonstrated by the storage overheads incurred by OQXT-I). OQXT-I competitive with OXT and CONJFILTER in terms of conjunctive query performance. and OQXT-II are OQXT, search index is encrypted using lattice techniques. Actual documents are simply encrypted using AES-256. Storage CONJFILTER are quadratic in the number of keywords. overheads for IEX-2Lev and Significantly outperforming IEX-2Lev. Computational costs of FHE- bootstrapping, major bottleneck when scaling FHE to extremely large databases. OQXT efficient conjunctive search overheads while ensuring a strong quantum security guarantee. achieves fast and practically OQXT-II would prove to be more scalable in terms of storage costs as compared to IEX- 2Lev and CONJFILTER extremely large databases with millions of keywords). lattice-based post- (especially for OQXT -- significantly faster searches and higher scalability in

30. Thank You! https://eprint.iacr.org/2023/872 Code to be available soon!