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:

• Git Hooks
• libgit2 [github]
• SSB over Git Tutorial [repo][video]
• P2P Basel Workshop

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:

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:

• (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:

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
7. Bulletin-Board System (BBS)

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