Semester Projects

Probabilistic data structures (PDS) 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. PDS 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 PDS are also used in cryptographic protocols for privacy-preserving computations, e.g. private set intersection [KRS+19, HSW23], to reduce runtime and communication costs.

In real-world applications where the data is noisy, complex or only partially available, e.g., biometric authentication, machine learning, and proximity testing, exact matches for queries are not always possible. Hence, fuzzy matching is desired and has been a focus of research in various research fields, and more recently also cryptography [UCKBL21,vBP25]. In this project, we investigate fuzzy matching in the context of privacy-preserving protocols.

More specifically, we focus on the extension of PDS to support fuzzy matches, i.e., a match occurs if the queried element is close, given a distance metric (e.g. Hamming distance or Euclidean distance), to an element in the datastructure. This project will empirically investigate the performance of distance-sensitive probabilisitc data structures with different metrics. In particular, the goal will be to implement different fuzzy PDS and optimize their performance in the context of cryptography, as well as compare the results to related work.

[BM03] Andrei Z. Broder and Michael Mitzenmacher. Survey: Network applications of bloom filters: A survey. Internet Math., 1(4):485–509, 2003.
[GL22] Thomas Mueller Graf and Daniel Lemire. 2022. Binary Fuse Filters: Fast and Smaller Than Xor Filters. ACM J. Exp. Algorithmics 27, Article 1.5 (December 2022), 15 pages. https://doi.org/10.1145/3510449
[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. external page https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/. Accessed: 2023-11-14.
[Nor] Savannah Norem. Probabilistic data structures in redis. external page 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.
[UCKBL21] Uzun, E., Chung, S. P., Kolesnikov, V., Boldyreva, A., & Lee, W.. Fuzzy labeled private set intersection with applications to private Real-Time biometric search. In USENIX Security, 2021.
[vBP25] van Baarsen, Aron, and Sihang Pu. Fuzzy private set intersection from VOLE. In ASIACRYPT, 2025.

Approximate Nearest Neighbor (ANN) search is the problem of finding, for a given query vector, the points in a database that are closest to it under some distance metric, while allowing a small amount of error in exchange for dramatically faster query times. ANN search is a widely used tool in modern data systems for web search, recommendation systems (like Netflix), and biometric matching. As these systems often operate as cloud services over sensitive data, query privacy is critical. Private Approximate Nearest Neighbor Search (PANNS) enables a client to retrieve the nearest neighbors of a query from a server's database without revealing the query (and in some settings, without revealing the database to the client beyond what is implied by the answer).

Adding privacy to ANN search is technically challenging due to the mismatch between ANN methods and available cryptographic tools. In standard plaintext ANN search (without privacy), graph-based approaches outperform tree-based, hash-based, and quantization-based alternatives. However, graph traversal is data-dependent, which conflicts with the data-independent access patterns of cryptographic tools like Private Information Retrieval (PIR). As a result, existing PANNS schemes make trade-offs between threat model, accuracy, communication, computation, and leakage. The existing literature lacks a unified analysis that thoroughly compares PANNS schemes against one another.

Existing Work:

PANNS research takes many approaches to combine ANN methods with cryptographic privacy. On the cryptographic side, schemes differ by trust model: two-server, non-colluding constructions such as Preco [4] provide fast query performance but require stronger trust assumptions, while single-server constructions such as Panther [2] and Pacmann [3] avoid that assumption at the cost of heavy cryptographic tools (single-server PIR, garbled circuits, or homomorphic encryption). By indexing strategy, schemes have used clustering (Tiptoe [11], SANNS [5]), locality-sensitive hashing (Preco [4]), and graph traversal (Compass [1], Pacmann [3]). Applications also vary: some schemes address public databases with private queries (as in web search), while others address both private databases and private queries (as for recommendation systems).

Recent plaintext ANN research (without query privacy) provides new indexing systems with improved query performance. Recent work combines graph and hash indexes [8], uses hierarchical graph structures [9], and/or introduce new optimizations to accelerate indexing [7, 10]. These techniques might not easily be made private, but their algorithmic ideas might be adapted to private systems. So far, no published work thoroughly studies the plaintext techniques and their potential for use towards building faster PANNS.

Project Description:

The thesis is an analytical work where the student will study ANNs/PANNs deeply and consider where modern ANN techniques could be adapted to build faster PANNs. The student will work closely with a doctoral student to explore and discuss the literature together.

The student will produce a structured survey of PANNS, organized around the following deliverables:

1. Classification. A classification or "taxonomy" of existing PANNS schemes organized by threat model (single- vs multi-server, semi-honest servers vs malicious servers), application setting (public vs private database, database known by server vs. client), indexing strategy (clustering, LSH, graph-based, hybrid), and cryptographic primitives used (PIR, DPF, secret sharing, homomorphic encryption, garbled circuits).
2. Comparison. An analysis of accuracy, communication cost, computation cost, and leakage across the surveyed schemes, based on reported benchmarks. If interested, the student could reproduce the existing work's benchmarks to validate results.
3. Analysis of recent plaintext ANN techniques. A review of modern plaintext ANN techniques and an analysis of which ideas could be used in a private setting. For promising plaintext techniques, the student will analyze the cryptographic obstacles to adding privacy.

Experience Required:

• Solid foundation in algorithms and data structures. Ideally some familiarity with classical nearest-neighbor algorithms.
• An undergraduate course in cryptography. Ideally some conceptual familiarity with at least one of PIR, homomorphic encryption, garbled circuits, or secret sharing. 
• Linear algebra and basic probability, sufficient to follow locality sensitive hashing analyses.
• Programming experience, in case the optional benchmarking component is pursued.

References:

1. Zhu, J., Patel, L., Zaharia, M., Popa, R. A. Compass: Encrypted Semantic Search with High Accuracy. Cryptology ePrint Archive, Paper 2024/1255. external page https://eprint.iacr.org/2024/1255.pdf  
2. Panther: Private Approximate Nearest Neighbor Search in the Single Server Setting. Cryptology ePrint Archive, Paper 2024/1774. external page https://eprint.iacr.org/2024/1774.pdf  
3. Zhou, M., Shi, E., Fanti, G. Pacmann: Efficient Private Approximate Nearest Neighbor Search. Cryptology ePrint Archive, Paper 2024/1600. external page https://eprint.iacr.org/2024/1600.pdf  
4. Servan-Schreiber, S., Langowski, S., Devadas, S. Private Approximate Nearest Neighbor Search with Sublinear Communication. IEEE Symposium on Security and Privacy (S&P), 2022. external page https://eprint.iacr.org/2021/1157.pdf  
5. Chen, H., et al. SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search. USENIX Security Symposium, 2020. external page https://www.usenix.org/system/files/sec20-chen-hao.pdf  
6. Privacy-Preserving Approximate Nearest Neighbor Search on High-Dimensional Data. arXiv preprint, 2025. external page https://arxiv.org/pdf/2508.10373  
7. Gong, Z., Zeng, Y., Chen, L. Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts. PVLDB, Vol. 18, 2025. external page https://www.vldb.org/pvldb/vol18/p3518-chen.pdf  
8. Zhao, et al. Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces. PVLDB, Vol. 16, 2023. external page https://www.vldb.org/pvldb/vol16/p1979-zhao.pdf  
9. Lu, et al. HVS: A Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search. PVLDB, Vol. 15, 2022. external page https://www.vldb.org/pvldb/vol15/p246-lu.pdf  
10. Wei, J., Peng, B., Lee, X., Palpanas, T. DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search. arXiv preprint 2406.10938. external page https://arxiv.org/pdf/2406.10938  
11. Henzinger, A., Dauterman, E., Corrigan-Gibbs, H., Zeldovich, N. Private Web Search with Tiptoe. SOSP 2023. external page https://eprint.iacr.org/2023/1438

Usually, the communication complexity of a protocol is expressed with two parameters: The round complexity denotes the number of communication rounds needed, and the bit complexity denotes the number of bits communicated through a protocol execution.

Whereas the round complexity seems to have a direct impact on the execution time of a protocol, this is not generally true for the bit complexity. As an example, consider two protocols A and B, both among n parties, both consisting of n rounds. In protocol A, in the very first round, every party needs to send some big message, and in every subsequent round, every party needs to send just one single bit. Incontrast, in protocol B, in the i-th round, party P_i has to send some big message, and every other party needs to send just one bit. Arguably, in many realistic network settings, protocol A will perform better, because the big messages can be communicated in parallel, whereas in protocol B, the big messages need to be sent sequentially. 

In a previous Master's project, we have put forward a new dimension to express the communication complexity, namely the length of a protocol (https://ia.cr/2025/931). In a nutshell, the length of a protocol denotes the number of bits that needs to be sent in a non-parallelizable way. However, this notion is only suited for synchronous protocols. 

In this project, we aim at generalizing the length-notion to the asynchronous setting, and improve some existing asynchronous protocols with respect to the new notion. As prerequisite, students must have  attended the course Cryptographic Protocols (or an equivalent course).

(Supervisor: Prof. Kenny Paterson, Joint Supervisor: Shannon Veitch)

This project aims to provide new definitions and proofs of anonymity of  authenticated key encapsulation mechanisms (AKEMs). AKEMs are similar to key encapsulation mechanisms, with the additional feature that the sender is authenticated through incorporation of their private key in the encapsulation algorithm. Sender authentication is then implicitly verified through the inclusion of their public key in decapsulation.
AKEMs have been the focus of recent analyses of the hybrid public key encryption (HPKE) standard. Prior work on AKEMs have considered additional properties, such as deniability, but have yet to cover anonymity in detail. In this project, we will develop formal game-based definitions of anonymity for AKEMs and then prove the (in)security of existing schemes. Time permitting, we will consider constructions of AKEMs with hybrid (relying on traditional/post-quantum assumptions) anonymity guarantees.