Available Projects
The following projects are ready to be taken by students. Yet, we would be happy to offer projects to students based on their other ideas related to distributed systems, CRDTs, blockchain, cryptography, obfuscation, and compilation techniques.
Index:
- Compiler Front End for Aporia [Compilation]
- Run-Time Interleaving for Aporia [Compilation]
- Trusted-Execution Environment Support for Aporia [Interpretation][Security]
- Software Engineering of Commitment Scheme [Crypto]
- Software Engineering of Fully Homomorphic Encryption Scheme [Crypto]
- SSH-based Access Control of Server-Hosted Replicas for Git-based Applications [Distributed Systems][Git]
- Adding Pull-based Replication Hooks to Git Core [Git][C Programming][Open Source Contribution]
- Optimize the Processing Time and Memory Size of Delta-GOC-Ledger [Lower-level Programming][Optimization][Git]
- Decentralized Application Design with CRDTs [Distributed Systems][DWeb][Startup]
Compiler Front End for Aporia
Bachelor or Master Thesis (Scope adjusted according to level)
Supervisor: Ali Ajorian (main), Erick Lavoie (support)
Aporia is a language-based security framework, that enables a set of programs written in high-level languages to become indistinguishable from one another when executed on commodity hardware. This framework currently comprises a new execution model, a runtime environment, and an interpreter that reads programs in a low-level syntax that makes instruction independence easier to achieve. We are looking for a motivated Bachelor or Master student to take on the challenge of designing and implementing a translator/compiler from a widely-used language, such as Python, to our custom low-level syntax.
Pre-requisites:
- (Mandatory) Good familiarity with the source language (ex: Python)
- (Desirable) Experience with text transformation or writing compilers (successful completion of Seminar on Interpretation and Compilation of Programming Languages definitely a plus!)
References:
- Current draft of "Instruction-Independent Obfuscation" paper available on demand
Run-Time Interleaving for Aporia
Master Thesis
Supervisor: Ali Ajorian (main), Erick Lavoie (support)
Aporia is a language-based security framework, that enables a set of programs written in high-level languages to become indistinguishable from one another when executed on commodity hardware. This framework currently comprises a new execution model, a runtime environment, and an interpreter that reads programs in a low-level syntax that makes instruction independance easier to achieve. The goal is to modify the interpreter to support adding a new program that was not known at compile-time. This may require modification of the compiler, run-time environment, and interpreter.
Pre-requisites:
- (Desirable) Familiarity C/C++ Linking Process
- (Desirable) Experience with text transformation or writing compilers (successful completion of Seminar on Interpretation and Compilation of Programming Languages definitely a plus!)
References:
- Current draft of "Instruction-Independent Obfuscation" paper available on demand
Trusted-Execution Environment Support for Aporia
Bachelor Thesis, Master Project (12 Credits) or Master Thesis (Scope adjusted according to level)
Supervisor: Ali Ajorian (main), Erick Lavoie (support)
Aporia is a language-based security framework, that enables a set of programs written in high-level languages to become indistinguishable from one another when executed on commodity hardware. This framework currently comprises a new execution model, a runtime environment, and an interpreter that reads programs in a low-level syntax that makes instruction independance easier to achieve. The goal of this project is to modify the current interpreter to use a Trusted Execution Environment for implementing security-critical operations such as randomization of memory layout and address translation.
Pre-requisites:
- (Desirable) Familiarity with C/C++
- (Desirable) Experience with writing compilers and interpreters (successful completion of Seminar on Interpretation and Compilation of Programming Languages definitely a plus!)
References:
- Current draft of "Instruction-Independent Obfuscation" paper available on demand
Software Engineering of Commitment Scheme
Bachelor or Master Thesis (Scope adjusted according to level)
Supervisor: Osman Biçer
Commitment schemes are cryptographic primitives highly useful for blockchain applications, banking systems, and online gambling. They are network system analogs of envelopes used in non-computer real-life settings. The goal of the project will be gaining hands-on experience with cryptographic software engineering by implementing a commitment scheme that can be chosen together with the supervisor. The student will be able to gain experience on cryptographic algorithms and protocols as well as their applications. The programming language can be chosen based on student's skills and desires.
Pre-requisites:
- (Mandatory all levels) Proven background of a low-level programming language such as C, C++, Go, Rust.
References:
Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: CRYPTO ’91 (1992). [ePrint]
Di Crescenzo, G., Ishai, Y., Ostrovsky, R.: Non-interactive and non-malleable commitment. In: ACM STOC ’98 (1998). [ACM]
Jain, A., Krenn, S., Pietrzak, K., Tentes, A.: Commitments and efficient zero-knowledge proofs from learning parity with noise. In: ASIACRYPT ’12 (2012). [ePrint]
Our work "Oblivious Homomorphic Encryption".
Software Engineering of Fully Homomorphic Encryption Scheme
Bachelor or Master Thesis (Scope adjusted according to level)
Supervisor: Osman Biçer
Fully Homomorphic Encryption enables outsourcing arbitrary computations on private data. The party that executes the computations obtains the results in encrypted form and returns the owner who can see the result in open form. They are quite promising primitives for cloud applications, particularly useful for medical applications on private patient data, outsourced authentication, etc. The goal of the project will be to gain hands-on experience with cryptographic software engineering by implementing a fully homomorphic encryption scheme that can be chosen together with the supervisor. The student will be able to gain experience on cryptographic algorithms and protocols as well as their applications. The programming language can be chosen based on student's skills and desires.
Pre-requisites:
- (Mandatory all levels) Proven background of a low-level programming language such as C, C++, Go, Rust
References:
Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) lwe. In: IEEE FOCS ’11 (2011). [ePrint]
Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. In: ITCS ’12 (2012). [ePrint]
Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In: ASIACRYPT ’16 (2016). [ePrint]
Our work "Oblivious Homomorphic Encryption".
SSH-based Access Control of Server-Hosted Replicas for Git-based Applications
Bachelor Thesis or Master Project (6 credits)
Supervisor: Erick Lavoie
Peer-to-peer replication protocols for eventually-consistent decentralized applications, such as Secure-Scuttlebutt (SSB), Dat/Hypercore, Nostr, etc. use (optional) highly-available server-hosted replicas to speed up propagation of new updates to other participants. These replicas often rely on custom server logic for replication and access control (ex: Pubs and Rooms in SSB). The goal of this project is to replicate the replication and access-control functionalities of Pubs using well-established technologies such as Git and SSH instead, for Git-based applications. Configuration of the replica will be performed through authenticated Git commits, structured as append-only logs, with a format that will be defined during the project.
Pre-requisites:
- (Mandatory Bachelor-level) Successful completion of Distributed Programming and the Internet Architecture
- (Mandatory Master-level) Successful completion of Foundations of Distributed Systems
- (Desirable) Familiarity with Append-Only Logs
References:
- Tarr, Dominic et al. "Secure scuttlebutt: An identity-centric protocol for subjective and decentralized applications" ICN 2019 [DOI]
- Kermarrec et al. "Gossiping with Append-Only Logs in Secure Scuttlebutt", DICG 2020, [DOI]
- Lavoie, Erick. "2P-BFT-Log: 2-Phases Single-Author Append-Only Log for Adversarial Environments." arXiv preprint arXiv:2307.08381 (2023). [url] [pdf]
- P2P Basel Workshop
Adding Pull-based Replication Hooks to Git Core
Bachelor Thesis or Master Project (12 credits)
Supervisor: Erick Lavoie
Git supports hooks, which are scripts invoked during the replication process, to customize the replication behaviour by enforcing that, for example, commits are signed, new commits are descendants of the current HEAD, a committer has the right capabilities to update the references, etc. Unfortunately, certain hooks (ex: pre-receive) are supported on the receiving side of a push but not on the receiving side of a pull. This is because a replica hosted on a trusted platform such as GitHub or GitLab, is usually trusted while the pushers to that replica are not. However, when using Git in a peer-to-peer setting or when the server cannot be trusted, it would be useful to also validate the updates just pulled with hooks before updating the state of a local repository. The goal of this project is to modify the core library of Git to have the same hooks available when receving a pulled update, as for a pushed update. If the resulting solution is of a high-enough quality, it will be submitted to the Git maintainers for hopefully merging into the official repository.
Pre-requisites:
- (Mandatory Bachelor-level) Completed the equivalent of 2 years
- (Mandatory Master-level) None
- (Mandatory) Familiarity with writing C code or in similar low(er)-level languages
References:
Optimize the Processing Time and Memory Size of Delta-GOC-Ledger
Bachelor Thesis, Master Project (12 credits), or Master Thesis
Supervisor: Erick Lavoie
Eventually-consistent ledgers relax the usual blockchain requirement that double-spending should be prevented with consensus mechanisms, such as proof-of-work, proof-of-stake, etc., and instead detect the double-spending after it has occurred and later punish the offenders. [1] This relaxation allows crypto-tokens to be implemented with eventually-consistent databases such as Git, Secure-Scuttlebutt [4,5], or others.
The Delta-GOC-Ledger [2] is a novel implementation of an eventually-consistent ledger based on delta-state Conflict-Free Replicated Data Types (CRDTs), with lower communication requirements than the state-based GOC-Ledger [3] it is based on. While robust, the current implementation still has two significant limitations:
- It relies heavily on Git trees to encode updates, which in turn dominate the storage and communication requirements;
- It is implemented in Bash, which performs loops very slowly and creates a sub-process for every command executed.
The goal of the project is to further lower storage and communication requirements by finding an alternative for encoding delta-state updates, possibly using commit messages [2], and lower processing time by re-implementing the key bottleneck operations in a faster language, C or other, up to the preference of the student.
Pre-requisites:
- (Mandatory Bachelor-level) Successful completion of Distributed Programming and the Internet Architecture
- (Mandatory Master-level) Successful completion of Foundations of Distributed Systems
References:
- [1] Lavoie, Erick, and Christian Tschudin. "Local crypto-tokens for local economics." Proceedings of the 3rd International Workshop on Distributed Infrastructure for the Common Good. 2022. [doi][pdf]
[2] Heisch, Jannick "Delta-GOC-Ledger: Incremental Checkpointing and Lower Message Sizes for Grow-Only Counters Ledgers with Delta-CRDTs", Master Thesis, University of Basel, Apr 2024 [pdf]
[3] Lavoie, Erick. "GOC-Ledger: State-based Conflict-Free Replicated Ledger from Grow-Only Counters." arXiv preprint arXiv:2305.16976 (2023). [url] [pdf]
[4] Tarr, Dominic et al. "Secure scuttlebutt: An identity-centric protocol for subjective and decentralized applications" ICN 2019 [DOI]
[5] Kermarrec et al. "Gossiping with Append-Only Logs in Secure Scuttlebutt", DICG 2020, [DOI]
- P2P Basel Workshop
Decentralized Application Design with Conflict-Free Replicated Data Types
Bachelor Thesis, Master Project (12 credits), or Master Thesis
Supervisor: Erick Lavoie
Centralized applications, such as Twitter/X, Facebook, Dropbox, Messenger, Google Docs, Maps, etc. have become essential services with limited mature alternatives because of network effects, economies of scale, and more than a decade of continuous and well-funded developments. However they are prone to privacy-violation, abuse of market position, and catastrophic failures. Fortunately, the decrease in the cost of storage and the tremendous amount of performance of modern hardware makes it now possible to build alternatives based on decentralized principles with the ability to work offline [5] and without most of the infrastructure costs that are otherwise required for centralized hosting [4].
Conflict-Free Replicated Data Types (CRDTs) [1] are a mathematical framework that simplifies the design and implementation of eventually-consistent applications that must tolerate both concurrent updates and intermittent failures. The goal of this project is to better understand how to design alternatives to centralized applications by using CRDTs to implement the core functionalities of one application among the followings:
- Any of the previous mentioned (Twitter/X, Facebook, etc.)
- Archive.org for Backups of the Internet
- Arxiv.org for Storing and Distributing Pre-prints of Academic Papers
- BoardGameArena for Remote Multiplayer Boardgames
- Substack for Optionally-Paid Blogging/Newsletters
- Podcasting
Any other suggestion, up to the interest of students is welcome!
A high-quality implementation may be promising to later use as a basis for new startups after graduation, using economic models compatible with decentralized designs. [4]
Pre-requisites:
- (Mandatory Bachelor-level) Successful completion of Distributed Programming and the Internet Architecture
- (Mandatory Master-level) Successful completion of Foundations of Distributed Systems
- (Mandatory) Working Knowledge of Discrete Mathematics
References:
- [1] Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. "Conflict-free Replicated Data Types." SSS 2011 - 13th International Symposium Stabilization, Safety, and Security of Distributed Systems, Oct 2011, Grenoble, France. pp.386-400, ⟨10.1007/978-3-642-24550-3_29⟩. ⟨hal-00932836⟩
[2] Heisch, Jannick "Delta-GOC-Ledger: Incremental Checkpointing and Lower Message Sizes for Grow-Only Counters Ledgers with Delta-CRDTs", Master Thesis, University of Basel, Apr 2024 [pdf]
[3] Lavoie, Erick. "GOC-Ledger: State-based Conflict-Free Replicated Ledger from Grow-Only Counters." arXiv preprint arXiv:2305.16976 (2023). [url] [pdf]
[4] Lavoie, Erick. "Designing Peer-to-Peer Systems as Closed Knowledge Commons." Proceedings of the 4th International Workshop on Distributed Infrastructure for the Common Good. 2023. [doi][pdf]
[5] Kleppmann, Martin, et al. "Local-first software: you own your data, in spite of the cloud." Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software. 2019. [doi][pdf]
- P2P Basel Workshop
Completed Master Projects
Jannick Heisch: Delta-GOC-Ledger: Incremental Checkpointing and Lower Message Sizes for Grow-Only Counters Ledgers with Delta-CRDTs, Apr 2024 [pdf]
Sebastian Lukas Philipp: Memory-Bounded Replication of Mutable Data Structures over Immutable Append-Only Logs, Jan 2023
Nikolai Rutz: Implementation and Evaluation of Function Placement Strategies for Networking the IoT, Sep 2022
Manual Rosenthaler: Secure Scuttlebutt-Like Network based on QUIC, Jun 2022
Timo Castelberg: Virtual Bulletin Boards as local-first Software based on CRDTs in decentralized networks, Jan 2022
Fabrizio Parillo: A Decentralized Wiki based on the Solid Ecosystem, Jul 2020
Completed Bachelor Projects
Marc Schäfer: Security Bubble-Informed Replication for tinySSB, Jul 2024
Adam Gohar: A Decentralized App-Store prototype for (tiny) Secure Scuttlebutt, Jun 2024
Severin Memmishofer: Porting the Tremola Backend (Kotlin) to the "Socket Runtime" (JavaScript) , Jun 2024
Lars Waldvogel: Implementing the Double Ratchet algorithm in Tremola, a Scuttlebutt based messaging app for Android , Oct 2022
Silas Bötschi: Ed25519 for Micropython on the ESP32, Aug 2022
Jannick Heisch: Decentralized Kanban board using Secure Scuttlebutt and Conflict-Free Replicated Data Types, Jul 2022
Maximilian Barth: Managing and Distributing Software Updates Using Append-Only Logs, Jun 2022
Simon Laube: Managing Resources of Network Nodes Using Append-Only-Logs, Jun 2022
Carlos Andr:s Tejera: NetShell Network: An identity-centric store-and-forward network, Jan 2022
Etienne Mettaz: A Discovery Protocol for Secure Scuttlebutt based on chat app Tremola, Jan 2022
Oliver Weinmeier: ObfuscatedRetrieval - Encrypted Private Information Retrieval for Remote Procedure Calls in BACnet, Oct 2021
Marco Banholzer: Simulation of the BlueConnect Stack on Windows OS, Aug 2021
David Seger: Secure, Infrastructure-Less and History-Aware Append-Only Log Synchronization on Android, Mar 2021
Luca Frey: PSync Synchronization for a Chattool in PiCN, Mar 2021
Martin Zumsteg: Optimizing Network Performance using Explicit Planning in Software-Defined Networks, Jan 2021
Tim Babies: Feasibility of Private Subchannels in Immutable Append-Only-Log-based Peer-to-Peer Communication Protocols, Jan 2021
Raphael Schellander: Computing Trust of Certificates in Named Data Networking, Jan 2021
Luc Kury: Long-term Sessions and Mobility in Information-Centric Networking, Oct 2022
Jannik Jaberg: A Feed Bundle Protocol for Scuttlebutt, Jul 2020
Eric da Costa: Pipelining for Named Function Networking, Jun 2020