Bachelor's Theses

Probabilistic data structures are data structures that employ randomness to more compactly represent data whilst also enable approximate answers to queries about the data. In particular, many of these data structures trade-off accuracy for query time and space efficiency. Probabilistic data structures are widely deployed, and have found applications in database management systems [Nor], estimating the number of Facebook Users [MH], as well as web caches and network measurement [BM03, TRL12]. These probabilistic data structures are also used in cryptographic protocols for privacy-preserving computations, e.g. private set intersection [KRS+19, HSW23], to reduce runtime and communication costs.

One such probabilistic data structure is a cuckoo filter [FAKM14, Epp16]. Cuckoo filters support membership queries, i.e., given a set S of data items, a cuckoo filter enables one to test whether some element x is contained in S with some probability of false positives. In other words, if the cuckoo filter returns “yes” for the query “is x ∈ S?” then with high probability x is in the set; if it returns “no” then with probability 1 we know that x ∉ S. Cuckoo filters are an attractive choice for many applications because of their high performance and support for updates, such as adding and deleting data items from the set.

In this project, we introduce a variation of the Cuckoo filter designed to answer proximity membership queries of the form, “Is x close to an element in S?”, where the distance between elements is measured using an appropriate metric (e.g. Hamming distance or Euclidean distance). This property is achieved through the careful use of locality-sensitive hash (LSH) functions; an LSH is a type of fuzzy hash function that hashes close items into the same buckets with high probability. Since LSH functions hash similar items into the same buckets, they are especially useful for data clustering and nearest neighbor search. This project will experimentally investigate the performance of the distance-sensitive cuckoo filter when instantiated using different LSH implementations and varying the parameter values. In particular, the goal will be to experimentally determine the optimal parameters for various use-cases of the distance-sensitive cuckoo filter.

References

[BM03] Andrei Z. Broder and Michael Mitzenmacher. Survey: Network applications of bloom filters: A survey. Internet Math., 1(4):485–509, 2003.
[Epp16] David Eppstein. Cuckoo filter: Simplification and analysis. In SWAT, 2016.
[FAKM14] Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. Cuckoo filter: Practically better than bloom. In CoNEXT, 2014.
[HSW23] Laura Hetz, Thomas Schneider, and Christian Weinert. Scaling mobile private contact discovery to billions of users. In ESORICS, 2023.
[KRS+19] Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert. Mobile private contact discovery at scale. In USENIX Security, 2019.
[MH] Arya Talebzadeh Mehrdad Honarkhah. Hyperloglog in presto: A significantly faster way to handle cardinality estimation. https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/. Accessed: 2023-11-14.
[Nor] Savannah Norem. Probabilistic data structures in redis. https://redis.com/blog/streaming-analytics-with-probabilistic-data-structures/. Accessed: 2023-11-14.
[TRL12] Sasu Tarkoma, Christian Esteve Rothenberg, and Eemil Lagerspetz. Theory and practice of bloom filters for distributed systems. IEEE Communications Surveys & Tutorials, 14(1):131–155, 2012.

(Supervisor: Prof. Kenny Paterson, Co-supervisor: Dr. Francesca Falzon)

The rise in big data has resulted in an increase in the outsourcing of data to third-party cloud servers. However, if this data is stored in plaintext form, any adversary that compromises the server or the communication channels, can not only learn the contents of this data, but also which plaintext records are accessed with each query. Structured encryption (STE) provides a practical method for mitigating such server-side or communication-channel attacks (e.g. [CGKO06, PPYY19, CK10]). In particular, it allows one to execute queries over encrypted data on the server-side. STE schemes are typically built using light-weight cryptographic primitives and offer sub-linear search in the size of the data. As such, they are efficient in practice making them attractive candidates for near-term deployment [BB22].

Unfortunately, security and efficiency are often at odds: in exchange for their efficiency, STE schemes reveal some well-defined information, i.e. leakage, about the queries and underlying data. The extent to which this leakage is harmful to security of these schemes is not fully understood and there has been a long line of work on leakage-abuse attacks that helps to further our understanding of the topic. These attacks leverage the seemingly benign leakage to either reconstruct information about the database (database reconstruction) or to infer the plaintext value of the queries that have been issued (query recovery). In 2016, Kelaris et al. [KKNO16] presented the first database reconstruction attack against an STE that supports range queries and this work consequently prompted a long line of follow-up work on attacks against range schemes.

Range queries are fundamental query type that allows one to request all records that lie in a closed interval (e.g. return all records of students between the ages of 23 and 25). This project is concerned with the study of STE schemes that support range queries. To date, no systematic review of mitigation techniques for attacks against range schemes has been carried out. Many works have proposed mitigation techniques without implementation and evaluation on real world data sets [MT19, MFET23], whilst other works have proposed solutions using oblivious data structure techniques without bench marking against standard mitigation techniques [DPPS20]. This project seeks to fill this gap by systematizing all proposed mitigation techniques; the goal is to compile them into one document, formalize these techniques as needed, and then analyze their asymptotic performance. Time allowing, these mitigation techniques can be implemented (using the language of choice) and bench-marked.

References:

[BB22] Cynthia Braund and Pramod Borkar. MongoDB Releases Queryable Encryption Preview, June 2022. external pagehttps://www.mongodb.com/blog/post/mongodb-releases-queryable-encryption-previewcall_made.

[CGKO06] R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky. Searchable symmetric encryption: Improved definitions and efficient constructions. In Proc. ACM Conf. on Computer and Communications Security, 2006.

[CK10] Melissa Chase and Seny Kamara. Structured encryption and controlled disclosure. In Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, volume 6477 of Lecture Notes in Computer Science, 2010.

[DPPS20] Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, and Saurabh Shintre. SEAL: Attack mitigation for encrypted databases via adjustable leakage. In USENIX Security Symposium, pages 2433–2450, 2020.

[KKNO16] G. Kellaris, G. Kollios, K. Nissim, and A. O’Neill. Generic attacks on secure outsourced databases. In Proc. ACM Conf. on Computer and Communications Security, 2016.

[MFET23] Evangelia Anna Markatou, Francesca Falzon, Zachary Espiritu, and Roberto Tamassia. Attacks on encrypted response-hiding range search schemes in multiple dimensions. Proceedings on Privacy Enhancing Technologies, 4:204–223, 2023.

[MT19] Evangelia Anna Markatou and Roberto Tamassia. Mitigation techniques for attacks on 1-dimensional databases that support range queries. In Proc. Int. Conf. on Information Security (ISC), volume 11723 of Lecture Notes in Computer Science. Springer, 2019.

[PPYY19] S. Patel, G. Persiano, K. Yeo, and M. Yung. Mitigating leakage in secure cloud-hosted data structures: Volume-hiding for multi-maps via hashing. In Proc. ACM Conf. on Computer and Communications Security, 2019.