Cover
Vol. 17 No. 2 (2021)

Published: December 31, 2021

Pages: 17-26

Original Article

Backward Private Searchable Symmetric Encryption with Improved Locality

Salim S. Bilbul 1 Ayad I. Abdulsada
1Department of Computer science, Education College for Pure Sciences, University of Basrah, Basrah, 61004, Iraq
History
  • Received: June 9, 2021
  • Revised: July 12, 2021
  • Accepted: July 13, 2021
  • Available Online: July 17, 2021
DOI

https://doi.org/10.37917/ijeee.17.2.3

Abstract

Searchable symmetric encryption (SSE) enables clients to outsource their encrypted documents into a remote server and allows them to search the outsourced data efficiently without violating the privacy of the documents and search queries. Dynamic SSE schemes (DSSE) include performing update queries, where documents can be added or removed at the expense of leaking more information to the server. Two important privacy notions are addressed in DSSE schemes: forward and backward privacy. The first one prevents associating the newly added documents with previously issued search queries. While the second one ensures that the deleted documents cannot be linked with subsequent search queries. Backward has three formal types of leakage ordered from strong to weak security: Type-I, Type-II, and Type-III. In this paper, we propose a new DSSE scheme that achieves Type-II backward and forward privacy by generating fresh keys for each search query and preventing the server from learning the underlying operation (del or add) included in update query. Our scheme improves I/O performance and search cost. We implement our scheme and compare its efficiency against the most efficient backward privacy DSSE schemes in the literature of the same leakage: MITRA and MITRA*. Results show that our scheme outperforms the previous schemes in terms of efficiency in dynamic environments. In our experiments, the server takes 699ms to search and return (100,000) results.

Keywords

References

  1. Emil Stefanov, Charalampos Papamanthou, and Elaine Shi. Practical dynamic searchable encryption with small leakage. In NDSS, volume 71, pages 72–75, 2014.
  2. Raphël Bost, Brice Minaud, and Olga Ohrimenko. Forward and backward private searchable encryption from constrained cryptographic primitives. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1465–1482, 2017.
  3. Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. 2006. Searchable symmetric encryption: improved definitions and efficient constructions. In ACM CCS 2016. 79–88.
  4. C. Liu, L. Zhu, M. Wang, and Y.-a. Tan, “Search pattern leakage in searchable encryption: Attacks and new construction,” Information Sciences, vol. 265, 2014.
  5. Raphael Bost. Forward secure searchable encryption. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 1143–1154, 2016.
  6. David Cash, Joseph Jaeger, Stanislaw Jarecki, Charanjit S Jutla, Hugo Krawczyk, Marcel Catalin Rosu, and Michael Steiner. Dynamic searchable encryption in very-large databases: data structures and implementation. In NDSS, volume 14, pages 23–26. Citeseer, 2014.
  7. David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. Leakage-abuse attacks against searchable encryption. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 668–679, 2015.
  8. M. Islam, M. Kuzu, and M. Kantarcioglu, “Access pattern disclosure on searchable encryption: Ramification, attack and mitigation,” in Network and Distributed System Security (NDSS), 2012.
  9. Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. All your queries are belong to us: The power of file-injection attacks on searchable encryption. In 25th {USENIX} Security Symposium ({USENIX} Security 16), pages 707–720, 2016.
  10. Y.-C. Chang and M. Mitzenmacher, “Privacy preserving keyword searches on remote encrypted data,” in International conference on applied cryptography and network security. Springer, 2005, pp. 442–455.
  11. S. Kamara and C. Papamanthou, “Parallel and dynamic searchable symmetric encryption,” in International Conference on Financial Cryptography and Data Security. Springer, 2013, pp. 258–274.
  12. S. Kamara and T. Moataz, “Boolean searchable symmetric encryption with worst-case sub-linear complexity,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2017, pp. 94–124.
  13. S. Garg, P. Mohassel, and C. Papamanthou, “Tworam: efficient oblivious ram in two rounds with applications to searchable encryption,” in Annual International Cryptology Conference. Springer, 2016, pp. 563–592.
  14. X. Song, C. Dong, D. Yuan, Q. Xu, and M. Zhao, “Forward private searchable symmetric encryption with optimized i/o efficiency,” IEEE Transactions on Dependable and Secure Computing, 2018.
  15. K. S. Kim, M. Kim, D. Lee, J. H. Park, and W.-H. Kim, “Forward secure dynamic searchable symmetric encryption with efficient updates,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1449–1463.
  16. O. Goldreich and R. Ostrovsky, “Software protection and simulation on oblivious rams,” Journal of the ACM (JACM), vol. 43, no. 3, pp. 431–473, 1996.
  17. M. Naveed, S. Kamara, and C. V. Wright, “Inference attacks on property-preserving encrypted databases,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015, pp. 644– 655.
  18. D. X. Song, D. Wagner, and A. Perrig, “Practical techniques for searches on encrypted data,” in Proceeding2000 IEEE Symposium on Security and Privacy. S&P 2000. IEEE, 2000, pp. 44–55.
  19. D. Cash, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Ros¸u, and M. Steiner, “Highly-scalable searchable symmetric encryption with support for boolean queries,” in Annual cryptology conference. Springer, 2013, pp. 353– 373.
  20. S. Kamara, C. Papamanthou, and T. Roeder, “Dynamic searchable symmetric encryption,” in Proceedings of the 2012 ACM conference on Computer and communications security, 2012, pp. 965–976.
  21. D. Boneh and B. Waters, “Constrained pseudorandom functions and their applications,” in International conference on the theory and application of cryptology and information security. Springer, 2013, pp. 280–300.
  22. M. Etemad, A. K¨upc¸ ¨u, C. Papamanthou, and D. Evans, “Efficient dynamic searchable encryption with forward privacy,” Proceedings on Privacy Enhancing Technologies, vol. 2018, no. 1, pp. 5–20, 2018.
  23. O. Goldreich, S. Goldwasser, and S. Micali, “How to construct randolli functions,” in 25th Annual Symposium On Foundations of Computer Science, 1984. IEEE, 1984, pp. 464–479.
  24. M. D. Green and I. Miers, “Forward secure asynchronous messaging from puncturable encryption,” in 2015 IEEE Symposium on Security and Privacy. IEEE, 2015, pp. 305 320.
  25. J. Ghareh Chamani, D. Papadopoulos, C. Papamanthou, and R. Jalili, “New constructions for forward and backward private symmetric searchable encryption,” in Bilbul & Abdulsada Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018, pp. 1038– 1055.
  26. M. Bellare and P. Rogaway, “Introduction to modern cryptography,” Ucsd Cse, vol. 207, p. 207, 2005.
  27. E. Stefanov, M. Van Dijk, E. Shi, C. Fletcher, L. Ren, X. Yu, and S. Devadas, “Path oram: an extremely simple oblivious ram protocol,” in Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, 2013, pp. 299–310.
  28. D. Cash and S. Tessaro, “The locality of searchable symmetric encryption,” in Annual international conference on the theory and applications of cryptographic techniques. Springer, 2014, pp. 351–368.
  29. G. Asharov, M. Naor, G. Segev, and I. Shahaf, “Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations,” in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 1101–1114.
  30. I. Demertzis and C. Papamanthou, “Fast searchable encryption with tunable locality,” in Proceedings of the 2017 ACM International Conference on Management of Data, 2017, pp. 1053–1067.
  31. F. Saad Muhi, "A Pseudorandom Binary Generator Based on Chaotic Linear Feedback Shift Register," Iraqi Journal for Electrical and Electronic Engineering vol. 12, pp. 155-160, 2016.