Semester Projects

(Semester project in collaboration with Privacy Preserving Systems Lab)

The development of novel privacy enhancing technologies (PETs) equates enhancing "privacy" with achieving application-specific technical properties. Real-world privacy violations, on the other hand, frequently unfold in ways that are orthogonal to the properties achieved by PETs. While emerging PETs strive to tackle the privacy challenges created by the exponential increase in the amount of user data collected by organisations, PETs often fall short in effectively capturing users' needs and concerns. This shortcoming stems from disparities between the assumptions posited by a large range of PETs and real-world attack vectors. The work in this project will focus on addressing this gap by developing a holistic and systematic understanding of privacy-based attacks, considering both data flows and potential harms. We plan to survey existing PETs' threat models to understand whether their assumptions hold in practice and whether their guarantees are sufficient to avert potential harm to users. Here, we note that many existing PETs appear to focus on protecting data, whereas the harms arising from privacy incidents are inherently user-specific.

The primary goals of this project are to develop an exhaustive taxonomy of real-world privacy attacks, and to provide a critical analysis of the assumptions and guarantees of privacy-enhancing technologies. Specifically, we aim to study and systemise real-world privacy incidents by utilising reports in mainstream media across various global regions. This analysis serves as the foundation for identifying recurring attack patterns, establishing a taxonomy of attacker profiles, and delineating the harms inflicted upon users. We then analyse existing threat models in PETs and their intended data flows, focusing on the discrepancies between the modus operandi of real-life attacks and the threat modelling choices in PETs.

After devising a framework for systematising real-life privacy attacks, we study the realm of PETs as a viable countermeasure against such attacks. This work involves:
• Formally systemising the assumptions and guarantees provided by PETs (threat models) in the context of real-world attacks.
• Applying our model of privacy-based attacks to evaluate how current PETs capture and impact data flows.
• Investigate mismatches between PETs guarantees and real-world privacy needs to conclude about why these technologies are not currently preventing observed harms.

Preferable skills include having context of existing privacy-enhancing technologies literature and willingness toward qualitative coding.

(Supervisor: Prof. Kenny Paterson, Joint Supervisors: Dr. Tianxin Tang, Laura Hetz)

Private Information Retrieval (PIR) is a cryptographic primitive that allows a client to fetch entries from a server's database without letting the server know which entries it has retrieved. There exist different protocols implementing this primitive that try to improve over the trivial solution of the client just downloading the entire database in terms of computation, communication and storage complexity.

PIR has many applications due to its capability to improve the privacy for users of certain centralized services, one of them being anonymous messaging, for which PIR allows to construct systems whose users are not required to trust anyone apart from their communication partners. However, today's proposals for such systems [1-3] do not yet scale to more than a few million users.

This semester project's goal is to reinvestigate the concrete requirements of this application to the underlying PIR protocol, in order to look for optimization potential beyond general PIR assumptions. We will then study if existing protocols for this application and PIR in general can be tweaked to leverage these hopefully weaker requirements in some way, to increase the number of users feasible.

One starting point would be to examine whether a batch of requests from multiple users can be processed more efficiently than treating each request separately, similarly to what was proposed in [4] for information-theoretic PIR. In this context, the privacy demands for a user's retrieval with respect to other users of that batch receiving related responses may need to be reassessed.

More generally, the notion of privacy could potentially be defined in a weaker way than commonly done for standard PIR protocols, as, for example, in this setting it might be fine in some cases if the PIR server can observe when two different queries ask for the same index. To that end, it may also be interesting to see if the idea to relax the perfect completeness requirement in [1] can be similarly applied to the privacy property.

References:

[1] S. Angel, S. Setty: Unobservable communication over fully untrusted infrastructure

[2] S. J. Menon, D. J. Wu: Spiral: Fast, high-rate single-server PIR via FHE composition

[3] A. Henzinger, M. M. Hong, H. Corrigan-Gibbs, S. Meiklejohn, V. Vaikuntanathan: One server for the price of two: Simple and fast single-server private information retrieval

[4] W. Lueks, I. Goldberg: Sublinear scaling for multi-client private information retrieval

(Supervisor: Prof. Kenny Paterson, Joint Supervisor: Dr. Francesca Falzon)

An authenticated dictionary (AD) is a scheme that outsources the storage of a dictionary to an untrusted prover in such a way that the client can later query the database and verify that results have not been tampered with [GSTW03, PT07]. ADs are a versatile tool that can be used in a number of different settings, a couple of which we discuss below.

One application in which ADs play an important role is Certificate Transparency. Certificate Authorities enable accountable public key infrastructure by issuing and storing digital signatures of certificates, thereby binding a website to its public key. A transparency log is a tool that allows for the decentralized verification of Certificate Authorities [CW09, LLK13]. More specifically, a transparency log is an AD that should guarantee the following properties: (1) that all readers of the log have the same view, (2) that no one has modified the existing entries in the log, and (3) that new entries in the log have been appended. In particular, users should be able to efficiently look up entries in the log by label (we use the term "label" instead of "key" to avoid confusion with cryptographic keys) and efficiently verify that the log is append-only. Recent works that propose authenticated dictionaries in the context of transparency logs include [TBP+19, HHK+21].

Another important application of ADs is account-based cryptocurrencies such as Ethereum and Algorand. In this use-case, the dictionary maintains a mapping from account identifiers (i.e. public keys) to account data (i.e., the balance associated with the given account). The dictionary is hosted by untrusted servers and so to prevent tampering of the data, the servers must ensure the correctness of accesses and updates. One example of such a scheme is Aardvark [LGG+22], a concurrent AD that uses vector commitments [CF13] to commit to the label-value pairs and generate small proofs.

Despite the extensive work on ADs, no comprehensive systematization of the schemes exists. The most recent and related SoK works are those by Meiklejohn et al. [MDO+22] and Hicks [Hic23]. Both works cite ADs as a tool through which transparency can be achieved, however, the scopes of these works are quite different: the former focuses on privacy-preserving auditing of certificate inclusion and the latter on transparency more broadly.

In contrast, this project endeavors to systematize existing AD schemes. AD schemes and their variations go by many names ranging from authenticated dictionaries, to verifiable databases [BGV11], to transparency logs – to name a few – and as a result, the literature is often dispersed and fragmented. We will categorize these works based on their use-cases, functionality, asymptotic costs (i.e. bandwidth, storage, look-up time, and proof-sizes), and which cryptographic primitives they are built from. The ultimate goal is to unify the solutions within a common framework, gain a better understanding of the state-of-the-art, and uncover the challenges of real-world deployment.

References:

[BGV11] Siavosh Benabbas, Rosario Gennaro, and Yevgeniy Vahlis. Verifiable delegation of computation over large datasets. In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, pages 111–131. Springer, 2011.

[CF13] Dario Catalano and Dario Fiore. Vector commitments and their applications. In Kaoru Kurosawa and Goichiro Hanaoka, editors, Public-Key Cryptography - PKC 2013 - 16th International Conference on Practice and Theory in Public-Key Cryptography, Nara, Japan,
February 26 - March 1, 2013. Proceedings, volume 7778 of Lecture Notes in Computer Science, pages 55–72. Springer, 2013.

[CW09] Scott A. Crosby and Dan S. Wallach. Efficient data structures for tamper-evident logging. In Proceedings of the 18th Conference on USENIX Security Symposium, SSYM’09, page 317–334, USA, 2009. USENIX Association.

[GSTW03] Michael T. Goodrich, Michael Shin, Roberto Tamassia, and William H. Winsborough. Authenticated dictionaries for fresh attribute credentials. In Paddy Nixon and Sotirios Terzis, editors, Trust Management, First International Conference, iTrust 2003, Heraklion, Crete, Greece, May 28-30, 2002, Proceedings, volume 2692 of Lecture Notes in Computer Science, pages 332–347. Springer, 2003.

[HHK+21] Yuncong Hu, Kian Hooshmand, Harika Kalidhindi, Seung Jin Yang, and Raluca Ada Popa. Merkle2: A low-latency transparency log system. In 2021 IEEE Symposium on Security and Privacy (SP), pages 285–303, 2021.

[Hic23] Alexander Hicks. SoK: Log based transparency enhancing technologies. CoRR, abs/2305.01378, 2023.

[LGG+22] Derek Leung, Yossi Gilad, Sergey Gorbunov, Leonid Reyzin, and Nickolai Zeldovich. Aardvark: An asynchronous authenticated dictionary with applications to account-based cryptocurrencies. In Kevin R. B. Butler and Kurt Thomas, editors, 31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022, pages 4237–4254. USENIX Association, 2022.

[LLK13] Ben Laurie, Adam Langley, and Emilia Kasper. Certificate transparency. external pagehttps://datatracker.ietf.org/doc/html/rfc6962call_made, 2013. Online; accessed 7 August 2023.

[MDO+22] Sarah Meiklejohn, Joe DeBlasio, Devon O’Brien, Chris Thompson, Kevin Yeo, and Emily Stark. SoK: SCT auditing in certificate transparency. Proc. Priv. Enhancing Technol., 2022(3):336–353, 2022.

[PT07] Charalampos Papamanthou and Roberto Tamassia. Time and space efficient algorithms for two-party authenticated data structures. In Sihan Qing, Hideki Imai, and Guilin Wang, editors, Information and Communications Security, 9th International Conference, ICICS 2007, Zhengzhou, China, December 12-15, 2007, Proceedings, volume 4861 of Lecture Notes in Computer Science, pages 1–15. Springer, 2007.

[TBP+19] Alin Tomescu, Vivek Bhupatiraju, Dimitrios Papadopoulos, Charalampos Papamanthou, Nikos Triandopoulos, and Srinivas Devadas. Transparency logs via append-only authenticated dictionaries. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS ’19, page 1299–1316, New York, NY, USA, 2019. Association for Computing Machinery.

(Supervisor: Prof. Kenny Paterson, Joint Supervisor: Dr. Zichen Gui)

Online collaborative editing tools are tools which enable users from different parts of the world to edit the same file in real time. This technology has gained much popularity over the years due to the convenience it offers. Notable products in this area include Google Docs [5], Dropbox Paper [4], Notion [6] and many more.

However, none of these products provide privacy for the users as the service providers can see the files in clear. This is not an coincidence as encrypted online collaborative editing has not gained any attention in the cryptography community and no provably secure scheme has been proposed.

On the other hand, CryptPad [1], a product launched by a XWiki in 2015, claims that it is capable of end-to end encrypted collaborative editing. In this project, we will investigate if CryptPad is as secure as it claims. In particular, we will look at the CryptPad’s white paper [3] and inspect its source code [2] to identify vulnerabilities in its design and implementation. We will also study how encrypted online collaborative editing tools should be designed in general, paving the way for more cryptographically secure constructions in the future.

References:

[1] Cryptpad. external pagehttps://cryptpad.org/about/call_made.
[2] Cryptpad Github. external pagehttps://github.com/cryptpad/cryptpadcall_made.
[3] Cryptpad white paper. external pagehttps://blog.cryptpad.org/2023/02/02/Whitepaper/call_made.
[4] Dropbox paper. external pagehttps://www.dropbox.com/paper/startcall_made.
[5] Google docs. external pagehttps://www.google.com/docs/about/call_made.
[6] Notion. external pagehttps://www.notion.socall_made.