Vitaly Skachek
General survey on post-quantum cryptography
Many commonly used cryptosystems will be completely broken once large quantum computers exist. Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems aim to remain secure even in this scenario. The paper [1] surveys various challenges and approaches in post-quantum cyrptosystem design.
In this project, a student will read [1], and possibly additional relevant papers, and will present a survey on the state-of-the-art in post-quantum crypto.
[1] Daniel J. Bernstein and Tanja Lange, "Post-quantum cryptography", Nature 549, 188–194 (2017). https://doi.org/10.1038/nature23461
BSc or MSc level
Detection of Bots in the Social Media
Bot is a software that automatically imitates legitimate users in social networks and other online platforms. In the recent years bots were massively used by private entities, political groups and governments in order to influence public opinion in the desired direction. Bots possess certain properties that often allow to distinguish them from the human users.
In this project, the student will study the distinguishing properties of the automatic bots, and develop a software that will identify possible bots in social networks.
[1] Digital Forensic Research Lab, "#BotSpot: Twelve Ways to Spot a Bot", https://medium.com/dfrlab/botspot-twelve-ways-to-spot-a-bot-aedc7d9c110c
[2] Arzum Karataş, Serap Şahin, "A Review on Social Bot Detection Techniques and Research Directions"
BSc, MSc or PhD level
A Secure Fountain Architecture for Slashing Storage Costs in Blockchains
Full nodes, which synchronize the full blockchain history and independently validate all the blocks, form the backbone of any blockchain network by playing a vital role in ensuring security properties. On the other hand, a user running a full node needs to pay a heavy price in terms of storage costs.
An architecture for blockchain is proposed in the referred paper, which is based on fountain codes, a class of erasure codes, that enables any full node to encode validated blocks into a small number of coded blocks, thereby reducing its storage costs by orders of magnitude. In particular, the proposed Secure Fountain (SeF) architecture can achieve a near optimal trade-off between the storage savings per node and the bootstrap cost in terms of the number of (honest) storage-constrained nodes a new node needs to contact to recover the entire blockchain. A key technical innovation in SeF codes is to make fountain codes secure against adversarial nodes that can provide maliciously formed coded blocks. The main idea is to use the header-chain as a side-information to check whether a coded block is maliciously formed while it is getting decoded. Further, the rateless property of fountain codes helps in achieving high decentralization and scalability.
https://arxiv.org/pdf/1906.12140.pdf
MSc or PhD level
Hendrik Dirk Lodewijk Hollmann
Private Information Retrieval and PIR codes
In the classical model for Private Information Retrieval (PIR), a user wishes to extract one bit of information from a database stored on a set of servers in such a way that no individual server gains any information on which bit the user was interested in. The efficiency of a scheme that enables PIR is measured in terms of the total communication between the user and the server. It can be shown that without data replication, the only solution is that the user asks for the entire database! If the PIR scheme replicates the database accross t>=2 servers, we say that the storage overhead of the PIR scheme is t: every bit is stored t times. A t-server PIR code is a binary k x n matrix with the property that for each of the k unit vectors, there are t disjoint set of columns that sum up (modulo 2) to that vector. PIR-codes can be used as a trick to implement a given (linear) PIR scheme with less storage overhead than the original scheme, by using the PIR code to emulate the t servers. How this magic is worked is explained in a youtube clip at The task is to understand PIR schemes and the use of PIR codes to reduce the storage overhead in the implementation of a PIR scheme as explained in the youtube clip mentioned above, to investigate how the efficiency of the PIR scheme is affected by the use of a PIR code, to collect a few examples of good PIR codes, write a short report on the topic, and present the results. Required background: Essentially none, but a coding or crypto course would be helpful. Level: Bsc.
Karan Khathuria
Fully homomorphic encryption schemes and private information retrieval
Fully homomorphic encryption (FHE) schemes are designed to allow users to perform operations on encrypted data without being able to decrypt them. On the other hand, private information retrieval (PIR) schemes are used for retrieving a file from an untrusted server without revealing any information about which file was retrieved.
In this project, the student will mainly focus on basic theory of single-server PIR schemes and FHE schemes. The task would be to study a generic way of constructing a single-server PIR scheme from an FHE scheme (see for example https://ieeexplore.ieee.org/document/618934), and present an example of a PIR scheme that is developed based on this technique.
Required background: Crypto I or comparable
Level: Master/PhD
Toomas Krips
Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation
(assigned to Hannes Veskus)
Secure computation is a method for evaluating functions on secret inputs. One such method is two-phase secret-sharing based secure computation where the secret data is split into parts among multiple parties, where each party can learn nothing about the secret from his own view and then various operations are performed on such shared data. Additionally, the parties have some sort of previously created correlated randomness to speed the computation up.
An interesting advancement of the topic has been Boyle et al's function secret sharing where additionally various functions themselves has been secret-shared as a form of correlated randomness. These functions are not arbitrary functions but parametrized functions f_a where the parameter is hidden. (an example might be a function f_a(x) that is equal to 1 if x=a and is equal to 0 otherwise). Now Boyle et al have come forward with a paper where they apply their technique to various fixed-point related operations in https://eprint.iacr.org/2020/1392. In this project the student is expected to go through this paper (and possibly previous papers by Boyle et al. to get a better understanding) and summarize the results.
Level: Master/PhD
Janno Siim
Estonian I-Voting and an Attack
In a recent paper https://eprint.iacr.org/2021/1098, Olivier Pereira describes an attack against individual verifiability of the Estonian internet voting system. Aim of the project is to write a report which (1) gives a detailed summary of the current Estonian I-voting system (see for example https://research.cyber.ee/~janwil/publ/ivxv-evoteid.pdf), (2) explains the attack proposal, and (3) evaluates seriousness/practicality of the attack.
level: Master or PhD
Zero-Knowledge Proofs for Fun
A zero-knowledge proof is a cryptographic tool that allows to prove statements without leaking any information besides that the statement is true. For example, in cryptocurrencies, one might want to prove that a ciphertext contains a valid transaction without revealing the sender, receiver, or transaction size. However, in this project, we will study zero-knowledge proofs for completely non-practical and silly problems. There are several physical zero-knowledge proofs which are good for intuition for beginners and need almost no mathematical background:
- Proving that one knows a solution to a sudoku puzzle without revealing the solution. http://www.wisdom.weizmann.ac.il/~naor/PAPERS/sudoku.pdf
- Proving that Waldo exists on Where's Waldo? picture without leaking his location. http://www.wisdom.weizmann.ac.il/~naor/PAPERS/waldo.pdf
- Proving to a color-blind person that two objects have different colors. https://hackernoon.com/how-to-prove-that-you-know-something-without-revealing-it-zero-knowledge-proofs-zcash-ethereum-43ce35d4d1c5
… This project aims to collect all of these simple physical zero-knowledge proofs (as many as we can find) into a single document to form a type of "Zero-knowledge Proofs for Dummies" guide. Each example should be nicely described (and maybe even illustrated) and should also contain some analysis of the probability of cheating. This is a good project, especially for those who have no prior cryptography background.
Level: Bachelor or Master
Couteau-Hartmann transform
(assigned to Valeh Farzaliyev) Zero-knowledge proofs can be interactive (there’s back and forth communication between prover and verifier) or non-interactive (prover outputs a single message, and verifier will check it). Often non-interactive proofs are more convenient to use in practice, and they allow many different verifiers to verify the same proof. Couteau and Hartmann recently proposed a very simple but novel approach for making certain interactive proofs non-interactive by using pairing-based cryptography. The task is to read about their approach from https://eprint.iacr.org/2020/286 and to write a summary.
level: Master or Phd
Dominique Unruh
Quantum Relational Hoare Logic
(assigned to Evgenii Dolzhkov)