Practical Backward-Secure Searchable Encryption from Symmetric Puncturable Encryption

ABSTRACT

Symmetric Searchable Encryption (SSE) has received wide attention due to its practical application in searching on encrypted data. Beyond search, data addition and deletion are also supported in dynamic SSE schemes. Unfortunately, these update operations leak some information of updated data. To address this issue, forward-secure SSE is actively explored to protect the relations of newly updated data and previously searched keywords. On the contrary, little work has been done in backward security, which enforces that search should not reveal information of deleted data. In this paper, we propose the first practical and non-interactive backward-secure SSE scheme. In particular, we introduce a new form of symmetric encryption, named symmetric puncturable encryption (SPE), and construct a generic primitive from simple cryptographic tools. Based on this primitive, we then present a backward-secure SSE scheme that can revoke a server's searching ability on deleted data. We instantiate our scheme with a practical puncturable pseudorandom function and implement it on a large dataset. The experimental results demonstrate its efficiency and scalability. Compared to the state-of-the-art, our scheme achieves a speedup of almost 50x in search latency, and a saving of 62% in server storage consumption.

References

1. Michel Abdalla, Dario Fiore, and Vadim Lyubashevsky. 2012. From Selective to Full Security: Semi-generic Transformations in the Standard Model Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21--23, 2012. Proceedings. 316--333.
2. Prabhanjan Ananth, Zvika Brakerski, Gil Segev, and Vinod Vaikuntanathan. 2015. From Selective to Adaptive Security in Functional Encryption Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16--20, 2015, Proceedings, Part II. 657--677.
3. Raphael Bost. 2016. (sum)o(varphi)o(varsigma): Forward Secure Searchable Encryption Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24--28, 2016. 1143--1154.
4. Raphael Bost and Pierre-Alain Fouque. 2017. Thwarting Leakage Abuse Attacks against Searchable Encryption - A Formal Approach and Applications to Database Padding. IACR Cryptology ePrint Archive bibinfovolume2017 (2017), 1060. http://eprint.iacr.org/2017/1060
5. Raphaël Bost, Brice Minaud, and Olga Ohrimenko. 2017. Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017. 1465--1482.
6. Ran Canetti, Srinivasan Raghuraman, Silas Richelson, and Vinod Vaikuntanathan. 2017. Chosen-Ciphertext Secure Fully Homomorphic Encryption Public-Key Cryptography - PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, March 28--31, 2017, Proceedings, Part II. 213--240.
7. David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. 2015. Leakage-Abuse Attacks Against Searchable Encryption Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12--16, 2015. 668--679.
8. David Cash, Joseph Jaeger, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. 2014. Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation 21st Annual Network and Distributed System Security Symposium, NDSS 2014, San Diego, California, USA, February 23--26, 2014.
9. David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. 2013. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18--22, 2013. Proceedings, Part I. 353--373.
10. David Cash and Stefano Tessaro. 2014. The Locality of Searchable Symmetric Encryption. Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11--15, 2014. Proceedings. 351--368.
11. Melissa Chase and Seny Kamara. 2010. Structured Encryption and Controlled Disclosure. Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5--9, 2010. Proceedings. 577--594.
12. Reza Curtmola, Juan A. Garay, Seny Kamara, and Rafail Ostrovsky. 2006. Searchable symmetric encryption: improved definitions and efficient constructions Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, Ioctober 30 - November 3, 2006. 79--88.
13. David Derler, Tibor Jager, Daniel Slamanig, and Christoph Striecks. 2018. Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part III. 425--455.
14. Nico Döttling and Sanjam Garg. 2017. From Selective IBE to Full IBE and Selective HIBE Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12--15, 2017, Proceedings, Part I. 372--408.
15. Mohammad Etemad, Alptekin Küpccü, Charalampos Papamanthou, and David Evans. 2018. Efficient Dynamic Searchable Encryption with Forward Privacy. PoPETs, Vol. xxx2018, 1 (2018), 5--20.
16. Sky Faber, Stanislaw Jarecki, Hugo Krawczyk, Quan Nguyen, Marcel-Catalin Rosu, and Michael Steiner. 2015. Rich Queries on Encrypted Data: Beyond Exact Matches Computer Security - ESORICS 2015 - 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21--25, 2015, Proceedings, Part II. 123--145.
17. Ben A. Fisch, Binh Vo, Fernando Krell, Abishek Kumarasubramanian, Vladimir Kolesnikov, Tal Malkin, and Steven M. Bellovin. 2015. Malicious-Client Security in Blind Seer: A Scalable Private DBMS 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17--21, 2015. 395--410.
18. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. 1984. How to Construct Random Functions (Extended Abstract) 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24--26 October 1984. 464--479.
19. Matthew D. Green and Ian Miers. 2015. Forward Secure Asynchronous Messaging from Puncturable Encryption 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17--21, 2015. 305--320.
20. Felix Günther, Britta Hale, Tibor Jager, and Sebastian Lauer. 2017. 0-RTT Key Exchange with Full Forward Secrecy. In Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part III. 519--548.
21. Florian Hahn and Florian Kerschbaum. 2014. Searchable Encryption with Secure and Efficient Updates Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3--7, 2014. 310--320.
22. Susan Hohenberger, Venkata Koppula, and Brent Waters. 2015. Adaptively Secure Puncturable Pseudorandom Functions in the Standard Model Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part I. 79--102.
23. Yuval Ishai, Eyal Kushilevitz, Steve Lu, and Rafail Ostrovsky. 2015. Private Large-Scale Databases with Distributed Searchable Symmetric Encryption. IACR Cryptology ePrint Archive bibinfovolume2015 (2015), 1190. http://eprint.iacr.org/2015/1190
24. Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. 2013. Outsourced symmetric private information retrieval 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS'13, Berlin, Germany, November 4--8, 2013. 875--888.
25. Seny Kamara and Tarik Moataz. 2017. Boolean Searchable Symmetric Encryption with Worst-Case Sub-linear Complexity Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part III. 94--124.
26. Seny Kamara and Charalampos Papamanthou. 2013. Parallel and Dynamic Searchable Symmetric Encryption Financial Cryptography and Data Security - 17th International Conference, FC 2013, Okinawa, Japan, April 1--5, 2013, Revised Selected Papers. 258--274.
27. Seny Kamara, Charalampos Papamanthou, and Tom Roeder. 2012. Dynamic searchable symmetric encryption. In the ACM Conference on Computer and Communications Security, CCS'12, Raleigh, NC, USA, October 16--18, 2012. 965--976.
28. Kee Sung Kim, Minkyu Kim, Dongsoo Lee, Je Hong Park, and Woo-Hwan Kim. 2017. Forward Secure Dynamic Searchable Symmetric Encryption with Efficient Updates Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017. 1449--1463.
29. Xianrui Meng, Seny Kamara, Kobbi Nissim, and George Kollios. 2015. GRECS: Graph Encryption for Approximate Shortest Distance Queries Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12--16, 2015. 504--517.
30. Ian Miers and Payman Mohassel. 2017. IO-DSSE: Scaling Dynamic Searchable Encryption to Millions of Indexes By Improving Locality 24th Annual Network and Distributed System Security Symposium, NDSS 2017, San Diego, California, USA, February 26 - March 1, 2017.
31. Dawn Xiaodong Song, David A. Wagner, and Adrian Perrig. 2000. Practical Techniques for Searches on Encrypted Data 2000 IEEE Symposium on Security and Privacy, Berkeley, California, USA, May 14--17, 2000. 44--55.
32. X. Song, C. Dong, D. Yuan, Q. Xu, and M. Zhao. 2018. Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency. IEEE Transactions on Dependable and Secure Computing (2018), 1--1.
33. Emil Stefanov, Charalampos Papamanthou, and Elaine Shi. 2014. Practical Dynamic Searchable Encryption with Small Leakage 21st Annual Network and Distributed System Security Symposium, NDSS 2014, San Diego, California, USA, February 23--26, 2014.
34. Shifeng Sun, Joseph K. Liu, Amin Sakzad, Ron Steinfeld, and Tsz Hon Yuen. 2016. An Efficient Non-interactive Multi-client Searchable Encryption with Support for Boolean Queries. In Computer Security - ESORICS 2016 - 21st European Symposium on Research in Computer Security, Heraklion, Greece, September 26--30, 2016, Proceedings, Part I. 154--172.
35. Peter van Liesdonk, Saeed Sedghi, Jeroen Doumen, Pieter H. Hartel, and Willem Jonker. 2010. Computationally Efficient Searchable Symmetric Encryption Secure Data Management, 7th VLDB Workshop, SDM 2010, Singapore, September 17, 2010. Proceedings. 87--100.
36. Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. 2016. All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10--12, 2016. 707--720.
37. Cong Zuo, Shifeng Sun, Joseph K. Liu, Jun Shao, and Josef Pieprzyk. 2018. Dynamic Searchable Symmetric Encryption Schemes Supporting Range Queries with Forward (and Backward) Security. In Computer Security - 23rd European Symposium on Research in Computer Security, ESORICS 2018, Barcelona, Spain, September 3--7, 2018, Proceedings, Part II. 228--246.

Index Terms

• Security and privacy

  • Database and storage security

    • Management and querying of encrypted data

  • Security services

    • Privacy-preserving protocols