Abstract
Open addressing hash tables, possibly under double hashing policy, are regarded more memory efficient than linked list hashing; as the memory used for pointers can be used for a longer table, and allow better-expected performance as the load factor is smaller and there are fewer expected collisions. We suggest further eliminating the single pointer to the memory location used in each entry of the open addressing, and using a single bit per entry, namely use a Bloom Filter to encode the memory address. Thus, obtain even a better load factor, with the same memory, and less number of wrongly mapped addresses when the load is low.
Moreover, we can prove that the content in the lookup table that is based on the bloom filter is pseudo-random (in the level of randomization implied by the hash function), thus, keeping the items and the addresses that the LookUp Table (LUT) encodes private.
This research was (partially) funded by a grant from the Ministry of Science and Technology, Israel & the Japan Science and Technology Agency (JST), the German Research Funding (DFG, Grant #8767581199), Genesis Consortium, the Rita Altura trust chair in computer science, and by the Lynne and William Frankel Center for Computer Science.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Can be found in https://github.com/segevere/BFLUT.
References
Avni, H., Dolev, S., Gilboa, N., Li, X.: SSSDB: database with private information search. In: Karydis, I., Sioutas, S., Triantafillou, P., Tsoumakos, D. (eds.) ALGOCLOUD 2015. LNCS, vol. 9511, pp. 49–61. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29919-8_4
Bellovin, S.M., Cheswick, W.R.: Privacy-enhanced searches using encrypted bloom filters. IACR Cryptol. ePrint Arch., p. 22 (2004)
Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A.: The Bloomier filter: an efficient data structure for static support lookup tables. In: Ian Munro, J. (ed.) Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, 11–14 January 2004, pp. 30–39. SIAM (2004)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2022)
Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. J. Comput. Secur. 19(5), 895–934 (2011)
Dharmapurikar, S., Song, H., Turner, J.S., Lockwood, J.W.: Fast packet classification using bloom filters. In: Bhuyan, L.N., Dubois, M., Eatherton, W. (eds.) Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems, ANCS 2006, San Jose, California, USA, 3–5 December 2006, pp. 61–70. ACM (2006)
Fisch, B.A., et al.: Malicious-client security in blind seer: a scalable private DBMS. In: 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, 17–21 May 2015, pp. 395–410. IEEE Computer Society (2015)
Benjamin Fuller, et al.: SoK: cryptographically protected database search. In: 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, 22–26 May 2017, pp. 172–191. IEEE Computer Society (2017)
Goh, E.: Secure indexes. IACR Cryptol. ePrint Arch., p. 216 (2003)
Goodrich, M.T., Mitzenmacher, M.: Invertible bloom lookup tables. In: 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011, Allerton Park & Retreat Center, Monticello, IL, USA, 28–30 September 2011, pp. 792–799. IEEE (2011)
Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)
Pontarelli, S., Reviriego, P., Mitzenmacher, M.: Improving the performance of invertible bloom lookup tables. Inf. Process. Lett. 114(4), 185–191 (2014)
Weintraub, G., Gudes, E., Dolev, S.: Needle in a haystack queries in cloud data lakes. In: Costa, C., Pitoura, E. (eds.) Proceedings of the Workshops of the EDBT/ICDT 2021 Joint Conference, Nicosia, Cyprus, Volume 2841 of CEUR Workshop Proceedings, 23 March 2021. CEUR-WS.org (2021)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Dolev, S., Gudes, E., Segev, E., Ullman, J., Weintraub, G. (2022). BFLUT Bloom Filter for Private Look Up Tables. In: Dolev, S., Katz, J., Meisels, A. (eds) Cyber Security, Cryptology, and Machine Learning. CSCML 2022. Lecture Notes in Computer Science, vol 13301. Springer, Cham. https://doi.org/10.1007/978-3-031-07689-3_35
Download citation
DOI: https://doi.org/10.1007/978-3-031-07689-3_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-07688-6
Online ISBN: 978-3-031-07689-3
eBook Packages: Computer ScienceComputer Science (R0)