Storage Efficient Substring Searchable Symmetric Encryption

ABSTRACT

We address the problem of substring searchable encryption. A single user produces a big stream of data and later on wants to learn the positions in the string that some patterns occur. Although current techniques exploit auxiliary data structures to achieve efficient substring search on the server side, the cost at the user side may be prohibitive. We revisit the work of substring searchable encryption in order to reduce the storage cost of auxiliary data structures. Our solution entails a suffix array based index design, which allows optimal storage cost $O(n)$ with small hidden factor at the size of the string n. Moreover, we implemented our scheme and the state of the art protocol \citeChase to demonstrate the performance advantage of our solution with precise benchmark results.

References

1. Mohamed Ibrahim Abouelhoda, Enno Ohlebusch, and Stefan Kurtz. 2002. Optimal Exact String Matching Based on Suffix Arrays. In In Proceedings of the Ninth International Symposium on String Processing and Information Retrieval. SpringerVerlag, Lecture Notes in Computer Science.
2. Robert S. Boyer and J. Strother Moore. 1977. A Fast String Searching Algorithm. Commun. ACM 20, 10 (Oct. 1977), 762--772.
3. M. Burrows and D. J. Wheeler. 1994. A block-sorting lossless data compression algorithm. Technical Report.
4. 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. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18--22, 2013. Proceedings, Part I. 353--373.
5. Yan-Cheng Chang and Michael Mitzenmacher. 2005. Privacy Preserving Keyword Searches on Remote Encrypted Data. In Proceedings of the Third International Conference on Applied Cryptography and Network Security (ACNS'05). SpringerVerlag, Berlin, Heidelberg, 442--455.
6. Melissa Chase and Seny Kamara. 2010. Structured Encryption and Controlled Disclosure. In 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.
7. Melissa Chase and Emily Shen. 2015. Substring-Searchable Symmetric Encryption. PoPETs 2015, 2 (2015), 263--281. http://www.degruyter.com/view/j/popets.2015. 2015.issue-2/popets-2015-0014/popets-2015-0014.xml
8. Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. 2006. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions. In Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS '06). ACM, New York, NY, USA, 79--88.
9. Sky Faber, Stanislaw Jarecki, Hugo Krawczyk, Quan Nguyen, Marcel-Catalin Rosu, and Michael Steiner. 2015. Rich Queries on Encrypted Data: Beyond Exact Matches. In Computer Security - ESORICS 2015 - 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21--25, 2015, Proceedings, Part II. 123--145.
10. Sebastian Faust, Carmit Hazay, and Daniele Venturi. 2013. Outsourced Pattern Matching. In Automata, Languages, and Programming, FedorV. Fomin, Rusins Freivalds, Marta Kwiatkowska, and David Peleg (Eds.). Lecture Notes in Computer Science, Vol. 7966. Springer Berlin Heidelberg, 545--556.
11. P. Ferragina and G. Manzini. 2000. Opportunistic Data Structures with Applications. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS '00). IEEE Computer Society, Washington, DC, USA, 390--. http://dl.acm.org/citation.cfm?id=795666.796543
12. Craig Gentry, Kenny A. Goldman, Shai Halevi, Charanjit S. Jutla, Mariana Raykova, and Daniel Wichs. 2013. Optimizing ORAM and Using It Efficiently for Secure Computation. In Privacy Enhancing Technologies - 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10--12, 2013. Proceedings. 1--18.
13. Gaston H. Gonnet, Ricardo A. Baeza-Yates, and Tim Snider. 1992. Information Retrieval. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, Chapter New Indices for Text: PAT Trees and PAT Arrays, 66--82.
14. Juha Karkkainen and Peter Sanders. 2003. Simple Linear Work Suffix Array Construction. In Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings. 943--955.
15. Richard M. Karp and Michael O. Rabin. 1987. Efficient Randomized Patternmatching Algorithms. IBM J. Res. Dev. 31, 2 (March 1987), 249--260.
16. Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. 1977. Fast Pattern Matching in Strings. SIAM J. Comput. 6, 2 (1977), 323--350.
17. Iraklis Leontiadis and Ming Li. 2018. Storage Efficient Substring Searchable Symmetric Encryption. EPFL scientific publications, Report 254805. (2018). https: //infoscience.epfl.ch/record/254805.
18. Yehuda Lindell. 2016. How To Simulate It - A Tutorial on the Simulation Proof Technique. IACR Cryptology ePrint Archive 2016 (2016), 46. http://eprint.iacr.org/ 2016/046
19. Udi Manber and Gene Myers. 1990. Suffix Arrays: A New Method for On-line String Searches. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '90). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 319--327.
20. Edward M. McCreight. 1976. A Space-Economical Suffix Tree Construction Algorithm. J. ACM 23, 2 (April 1976), 262--272.
21. Tarik Moataz and Erik-Oliver Blass. 2015. Oblivious Substring Search with Updates. Cryptology ePrint Archive, Report 2015/722. (2015). http://eprint.iacr. org/2015/722.
22. E. Ukkonen. 1958. On-line construction of suffix trees. Algorithmica 14, 3 (1958), 249--260.
23. Peter Weiner. 1973. Linear pattern matching algorithms. In Switching and Automata Theory, 1973. SWAT '08.

Index Terms

• Networks

  • Network properties

    • Network security

      • Security protocols

• Security and privacy

  • Database and storage security