skip to main content
10.1145/3029806.3029839acmconferencesArticle/Chapter ViewAbstractPublication PagescodaspyConference Proceedingsconference-collections
poster

A New Bloom Filter Structure for Searchable Encryption Schemes

Published: 22 March 2017 Publication History

Abstract

We propose a new Bloom filter structure for searchable encryption schemes in which a large Bloom filter is treated as (replaced with) two smaller ones for the search index. False positive is one inherent drawback of Bloom filter. We formulate the false positive rates for one regular large Bloom filter, and then derive the false positive rate for the two smaller ones. With examples, we show how the new scheme cuts down the false positive rate and the size of Bloom filter to a balanced point that fulfills the user requirements and increases the efficiency of the structure.

References

[1]
S. Bellovin and W. Cheswick. Privacy-enhanced searches using encrypted bloom filters. Technical Report CUCS-034-07, Dept. of Computer Science, Columbia Univ., Sept. 2007, 1--16.
[2]
B. Bloom. Space/time trade-offs in hash coding with allowable errors. Comm. of the ACM, 13(7):422--426, 1970.
[3]
C. Bosch, P. Hartel, W. Jonker, and A. Peter. A survey of provably secure searchable encryption. ACM Comput. Surv., 47(2), 2014. Article 18.
[4]
P. Bose, H. Guo, E. Kranakis, A. Maheshwari, and P. Morin. On the false-positive rate of bloom filters. Technical Report TR-07-07, School of Computer Science, Carleton University.
[5]
E.-J. Goh. Secure indexes. Technical Report 2003/216, IACR ePrint Cryptography Archive, 2003.
[6]
S. Pal, P. Sardana, and A. Sardana. Efficient search on encrypted data using bloom filter. In Proc. of 2014 Int. Conf. on Computing for Sustainable Global Development (INDIACom), pages 412--416, 2014.
[7]
V. Pappas, F. Krell, B. Vo, V. Kolesnikov, T. Malkin, S. Choi, W. George, A. Keromytis, and S. Bellovin. Blind seer: A scalable private dbms. In Proc. of 2014 IEEE Symposium on Security and Privacy, pages 359--374, 2014.
[8]
M. Raykova, B. Vo, S. Bellovin, and T. Malkin. Secure anonymous database search. In Proc. of 2009 CCSW, ACM, pages 115--126, 2009.
[9]
Q. Tang. Search in encrypted data: theoretical models and practical applications. Technical Report 2012/648, IACR ePrint Cryptography Archive, 2012.

Cited By

View all
  • (2022)A Keyword-Grouping Inverted Index Based Multi-Keyword Ranked Search Scheme Over Encrypted Cloud DataIEEE Transactions on Sustainable Computing10.1109/TSUSC.2021.31255207:3(561-578)Online publication date: 1-Jul-2022
  • (2021)Enhancement of Precision on Cloud Data using Multi-Layered Bloom Filter2021 IEEE 18th India Council International Conference (INDICON)10.1109/INDICON52576.2021.9691668(1-7)Online publication date: 19-Dec-2021
  • (2021)Partitioned Searchable EncryptionProvable and Practical Security10.1007/978-3-030-90402-9_4(63-79)Online publication date: 2-Nov-2021
  • Show More Cited By

Index Terms

  1. A New Bloom Filter Structure for Searchable Encryption Schemes

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    CODASPY '17: Proceedings of the Seventh ACM on Conference on Data and Application Security and Privacy
    March 2017
    382 pages
    ISBN:9781450345231
    DOI:10.1145/3029806
    Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 22 March 2017

    Check for updates

    Author Tags

    1. bloom filter
    2. cryptographic hash function
    3. false positive rate
    4. searchable encryption

    Qualifiers

    • Poster

    Conference

    CODASPY '17
    Sponsor:

    Acceptance Rates

    CODASPY '17 Paper Acceptance Rate 21 of 134 submissions, 16%;
    Overall Acceptance Rate 149 of 789 submissions, 19%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)4
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2022)A Keyword-Grouping Inverted Index Based Multi-Keyword Ranked Search Scheme Over Encrypted Cloud DataIEEE Transactions on Sustainable Computing10.1109/TSUSC.2021.31255207:3(561-578)Online publication date: 1-Jul-2022
    • (2021)Enhancement of Precision on Cloud Data using Multi-Layered Bloom Filter2021 IEEE 18th India Council International Conference (INDICON)10.1109/INDICON52576.2021.9691668(1-7)Online publication date: 19-Dec-2021
    • (2021)Partitioned Searchable EncryptionProvable and Practical Security10.1007/978-3-030-90402-9_4(63-79)Online publication date: 2-Nov-2021
    • (2019)Hunting the Pertinency of Bloom Filter in Computer Networking and BeyondJournal of Computer Networks and Communications10.1155/2019/27124172019Online publication date: 5-Feb-2019
    • (2019)A Split Bloom Filter for Better PerformanceJournal of Applied Security Research10.1080/19361610.2019.1613090(1-14)Online publication date: 3-Oct-2019
    • (2019)rDBFJournal of Network and Computer Applications10.1016/j.jnca.2019.03.004136:C(100-113)Online publication date: 15-Jun-2019
    • (2018)Parallel hash collision search by Rho method with distinguished points2018 IEEE Long Island Systems, Applications and Technology Conference (LISAT)10.1109/LISAT.2018.8378028(1-7)Online publication date: May-2018

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media