Computer Laboratory

Student projects (Part II and ACS)

Previously completed student projects

Academic year 2010/2011

Osiris: Secure Social Backup

by James Bown, St John's College

This project received a score of 82/100 (ranked fourth in the year)

Many people would like to have secure off-site backups of their personal data. Recently, so-called "cloud storage" services (such as e.g. Amazon S3) have started providing infrastructure for this. However, there is are many inherent issues to do with trust and control: users may not trust a cloud provider with their personal data, or they might feel uncomfortable about it being stored in a country with a jurisdiction that might not protect their privacy. Furthermore, cloud storage is still prohibitively expensive.
A better concept might be for a group of friends to arrange a mututally beneficial backup system whereby everyone offers some storage space to the others (this could be on servers, desktop machines, laptops or mobile devices). The challenge is to do this in a secure way that maintains privacy and offers compelling performance.
Different pairings of people might have different degrees of trust and this could be reflected in the strenght of pairwise encryption (though one would have to consider the case of a friend accidentally giving parties with weaker trust getting accessing the data!). Alternatively, data could be distributed across multiple different friends' devices, and only the combination would be sufficient to reconstruct the old data.
This project has lots of scope for the design and implementation of clever synchronization algorithms and cryptographical constructs.
Difficulty: ★★ to ★★★

Cirrus: Distributing Application Threads on the Cloud

by Sebastian Hollington, St John's College

This project received a score of 84/100 (ranked third in the year)

This project made use of the SRG's Ciel distributed execution engine to provide a pthread-like API for writing distributed programs that can run on an elastic compute cluster or "the cloud". It allows programs to be written accordding to the familiar threading paradigm, using fork() and join() primitives. They can then run on top of a Ciel cluster, taking advantage of elastic cluster membership, transparent fault tolerance and result memoization. The thread migration was implemented using the BLCR checkpoint-restart framework; furthermore, support basic emulated shared memory functionality exists. The goal of this project was to explore intuitive programming models for parallel computation. In particular, it investigated whether a threading-like approach can compete with the traditional, special-purpose cloud programming paradigms like MapReduce.
Difficulty: ★★★

Implementing Homomorphic Encryption

by Valentin Dalibard, St John's College

This project received a score of 85/100 (ranked second in the year)

Homomorphic encryption is the idea of performing arbitrary computations on an encrypted piece of data ("ciphertext") without decrypting it first. In other words, the operations manipulate the ciphertext to generate another, different, ciphertext, which when decrypted produces a plaintext that is equivalent to the original plaintext with the operations applied. For example, operation "add 37" on plaintext "5" gives "42". Under homomorphic encryption, we apply "add 37" to E(5) (where E is an encryption function) and get back E(42), which when decrypted gives us "42" (the correct answer). The utility of this is that using homomorphic encryption, secure computation could be performed in a potentially hostile environment (e.g. untrusted servers on the "cloud").
An important observation is that a fully homomorphic scheme only needs to support two operations: addition and multiplication. These are sufficient to bootstrap any computation that we can imagine (even though it would be very, very, very slow!).
Homomorphic encryption has long (since the 1980s) been considered to be an unsolved "holy grail" of cryptography. However, recently, several working schemes have been published (the last is easiest to understand and implement as it does not require understanding of lattices). Most of the work in this space has been in theory though, and there is implementation of any of these systems available.
Your task in this project would be to implement one of the published schemes and show that it works with small examples (due to the exponential increase in computing power required, you are likely to only be able to try it with small inputs and keys, but that is enough for a proof-of-concept).
As a possible extension, the project investigated how much of the process can be parallelised (a question that has received very little attention so far) to speed it up, and found various opportunities.
Difficulty: ★★★★