Implementation and Evaluation of Improved Secure Index Scheme Using Standard and Counting Bloom Filters

Year 2017, Volume: 6 Issue: 4, 46 - 56, 01.12.2017

Leyla Tekin Serap Şahin

Abstract

This paper presents an improved Secure Index scheme as a searchable symmetric encryption technique and provides a solution that enables a secure and efficient data storage and retrieval system. Secure Index scheme, conceived by Goh, is based on standard Bloom filters SBFs . Knowledge of the limitations of SBFs, such as handling insertions but not deletions, helps in understanding the advantages of counting Bloom filters CBFs . Thus, we have extended this scheme by adding a new algorithm so that CBFs can also be applicable. Unlike the old scheme, our scheme can handle dynamic update of a document by updating the existing index without rebuilding it. Moreover, we give a complementary comparison of both filters in our scheme. Finally, a detailed performance evaluation shows that our scheme exhibits similar performance with regard to the query overhead and the false positive probability and is quite efficient than the old scheme with regard to the update overhead by allocating more space.

Keywords

Searchable symmetric encryption, keyword search, indexes, bloom filters, dynamic update

References

• B.H. Bloom, “Space/time trade-offs in hash coding with allow- able errors”, Communications of the ACM, Vol.13, No.7, pp.422- 426, 1970.
• E.-J. Goh. Secure Indexes. Cryptology ePrint Archive, Report 2003/216. http://eprint.iacr.org/2003/216, 2003.
• L. Fan, P. Cao, J.M. Almeida, and A.Z. Broder, “Summary cache: a scalable wide-area web cache sharing protocol”, IEEE/ACM Transactions on Networking (TON), Vol.8, No.3, pp.281-293, 2000.
• Q. Tang. Search in Encrypted Data: Theoretical Models and Prac- tical Applications. Cryptology ePrint Archive, Report 2012/648. http://eprint.iacr.org/2012/648, 2012.
• D.X. Song, D. Wagner, and A. Perrig, “Practical techniques for searches on encrypted data”, IEEE Symposium on Security and Privacy, pp.44-55, 2000.
• D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano. Public key encryption with keyword search. Eurocrypt, Vol.3027, pp.506-522, 2004.
• S. Tarkoma, C.E. Rothenberg, E. Lagerspetz, “Theory and prac- tice of bloom filters for distributed systems”, IEEE Communica- tions Surveys and Tutorials, Vol.14, No.1, pp.131-155, 2012.
• http://www.ietf.org/rfc.html, RFC, Request For Comments Database, Latest Access Time is 14 July 2017.
• https://lucene.apache.org, ApacheLucene, Latest Access Time is 30 June 2017.
• http://openjdk.java.net/projects/code-tools/jmh/, JMH, Java Mi- crobenchmark Harness, Latest Access Time is 27 August 2017.
• Y.-C. Chang and M. Mitzenmacher, “Privacy preserving key- word searches on remote encrypted data”, ACNS, Vol.5, pp.442- 455, 2005.
• P. van Liesdonk, S. Sedghi, J. Doumen, P. Hartel, and W. Jonker, “Computationally Efficient Searchable Symmetric Encryption”, Secure data management, Vol.6358, pp.87-100, 2010.
• S. Kamara, C. Papamanthou, and T. Roeder, “Dynamic search- able symmetric encryption”, ACM Conference on Computer and Communications Security, pp.965-976, 2012.
• R. Ramasamy, S.S. Vivek, P. George, and B.S.R. Kshatriya. Dynamic Verifiable Encrypted Keyword Search Using Bitmap Index and Homomorphic MAC. Cryptology ePrint Archive, Re- port 2017/676. http://eprint.iacr.org/2017/676, 2017.