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:

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:

References:

  • Current draft of "Instruction-Independent Obfuscation" paper available on demand

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:

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:

References:

  • Current draft of "Instruction-Independent Obfuscation" paper available on demand

 

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".

Bachelor Thesis or Master Project (6 credits)

SupervisorErick 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:

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

Bachelor Thesis or Master Project (12 credits)

SupervisorErick 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:

 

Bachelor Thesis, Master Project (12 credits), or Master Thesis

SupervisorErick 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:

  1. It relies heavily on Git trees to encode updates, which in turn dominate the storage and communication requirements;
  2. 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:

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

Bachelor Thesis, Master Project (12 credits), or Master Thesis

SupervisorErick 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:

  1. Any of the previous mentioned (Twitter/X, Facebook, etc.)
  2. Archive.org for Backups of the Internet
  3. Arxiv.org for Storing and Distributing Pre-prints of Academic Papers
  4. BoardGameArena for Remote Multiplayer Boardgames
  5. Substack for Optionally-Paid Blogging/Newsletters
  6. 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:

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