Toomas Krips
Failure modes of a shuffle. [taken]
Recently me along with Abdolmaleki, Fauzi and Siim published the paper "Shuffle Arguments Based on Subset-Checking". (https://eprint.iacr.org/2024/1056) In this paper we proposed a method of proofs-of-shuffling (A proof of a shuffle is the following problem. Suppose that there is a public list of (randomized) ciphertexts. A potentially malicious Prover will take these ciphertexts and rerandomize them and change their order and output this new vector of new ciphertexts. Now she will have to prove to a potentially malicious Verifier that she did everything correctly without the Verifier ). We proposed two versions of the same shuffle: the lite version, which makes certain somewhat unrealistic assumptions about the inputs, but is very efficient. The full version is secure under very realistic assumptions, but it is several times faster. The task would be to study what happens to the lite version of the algorithm when its unrealistic assumptions are somewhat broken and how badly will this effect the security of the whole algorithm. It is possible to model the unrealistic assumption as a small number of parties misbehaving - would then the problems be contained to the outputs of the misbehaving parties? This project could be also be a first step in a Masters thesis.
The projects are suitable for Masters or PhD level
Implementation of a shuffle
The student would familiarize themselves with the simple version of the scheme and implement it, using existing libraries. One would mainly have to work with cryptographic primitives that are similar to ElGamal encryptions, and also with combining existing zero-knowledge proofs, for which there are libraries.
This project is suitable at any level.
Implementation of a multipoint DPF scheme
This spring Erki Külaots defended his Masters thesis on the topic of multipoint distributed point functions. (a point function is a function that is nonzero at one point and zero everywhere else. a multipoint point function is a function that is nonzero at a few specific indices and zero everywhere else. a distributed multipoint function is a cryptographic primitive that allows two parties to evaluate, without communication, the multipoint function at any x, such that they obtain a secret-sharing of the value of that function at x, while not learning where the function is nonzero) This project would involve getting familiar with the scheme and implementing it. This protocol does not involve many cryptographic primitives, but requires an elementary understanding of linear algebra.
This project is suitable at any level.
Other MPC constructions
I am looking into some other ideas in the area of Secure Multiparty Computation. I have some other ideas on what to research, but these are larger in scope, and would be suited to being the first step in a thesis. If you are interested in these, let me know.
Helger Lipmaa
Zero-knowledge (ZK) proofs, especially zk-SNARKs (succinct non-interactive proofs of knowledge), are currently a very trendy topic, especially motivated by the application of privacy-preserving blockchain. Other applications include privacy-preserving machine learning (including the training), privacy-preserving image processing, etc. There is a multibillion-dollar industry. Zk-SNARKs allow one to prove that some large-scale computation was performed correctly with two additional objectives: (1) nothing is leaked about the private data, and (2) verifying the proof should be considerably more efficient than doing the computation itself. The area is currently very rich in theory (with hundreds of research papers annually) and practice (a few hundred active startups). Helger is also currently giving a course (https://courses.cs.ut.ee/2024/zk/fall/Main/HomePage) on ZK proofs.
ZKML
ZKML is the application of zero-knowledge proofs within machine learning. The idea is to allow someone to prove they ran a machine learning model on some data and got a specific result — without revealing either the data itself or the model’s inner workings. In more technical terms, zkML enables privacy-preserving inference and model verification:
- Privacy-preserving inference: You can run a machine learning model
on private data and prove that the model was run correctly without revealing the data or the model’s outputs.
- Model verification: You can prove that a model was trained in a
certain way or that its outputs are correct without disclosing the model’s parameters or the dataset used for training.
We expect the student to read through some papers in this field and write a survey on specific ZKML techniques. The survey should combine ML and ZK knowledge, explaining how to represent common ML tasks (like inference) in the form of amicable to efficient ZK proofs, and explain at least one ZK approach that is amicable to ZKML. Interested students are recommended to browse YouTube videos at https://www.youtube.com/results?search_query=zkml and especially for a more technical introduction. The topic is related to a joint grant between Helger Lipmaa and Meelis Kull. It suits an MSc student interested in finding an MSc topic and continuing to a PhD. Talented BSc students or PhD students are also welcome.
Code-Based zk-SNARKs (FRI) [taken]
The most influential post-quantum zk-SNARKs are based on simple cryptography (hash functions) and error-correcting codes. Among such schemes, FRI is the best known: it has beautiful math and has been marketed successfully by a company called StarkWare. Some good properties of FRI include being post-quantum, relying on the weakest possible assumptions, having no trusted setup, and having a fast prover. On the other hand, FRI's verifier is relatively inefficient.
We expect the student to read through some papers in this field and write a survey on FRI, which is understandable by non-specialists. The survey should combine cryptographic and code-theoretic knowledge, explaining how FRI's techniques relate to error-correcting codes' properties. Interested students are recommended to browse YouTube videos at https://www.youtube.com/results?search_query=fri+protocol, where gives a less-technical and
a more technical introduction. The topic is related to the
collaboration between Helger Lipmaa and our coding theory group. It suits an MSc student interested in finding an MSc topic and continuing to a PhD. Talented BSc students or PhD students are also welcome.
Sedat Akleylek
The projects are suitable for all degrees (BSc, MSc, PhD)
A Comparison of Post-Quantum Symmetric-based Signature Schemes
The task is to understand the symmetric-based signature schemes submitted to NIST Post-Quantum Cryptography Standardization Project. The signature schemes are Picnic, AIMer, Ascon-Sign, FAEST, SPHINCS, SPHINCS-Alpha [1,2]. At least 3 signature schemes are selected for both theoretical and practical comparison. The comparison includes performance analysis (running time, etc.) and the structural similarities/differences. [1] https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions [2] https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures
A Report on the Shortest Linear Program and Its Variants
Symmetric key cryptosystems have diffusion and confusion layers. The Shortest Linear Program (SLP) problem is the number of linear operations necessary to compute a set of linear forms. In this project, the task is to understand and implement the circuit minimization algorithms for linear/permutation layers of symmetric key cryptosystems. [1,2] are the code examples for the Boyar-Peralta algorithm. [3] explains the Boyar-Peralta algorithm. In the report, the basic workflow of the circuit minimization algorithms, their comparison, implementation results on the linear layers, and discussion on them are given. [1] https://bitbucket.org/anubhab001/boyar-peralta-xor3/src/master/ [2] https://github.com/thomaspeyrin/XORreduce [3] https://doi.org/10.1007/s00145-012-9124-7
Experimental Results on OpenFHE
The task is to run open-source fully homomorphic encryption (FHE) libraries, which have the implementations of several FHE schemes and provide a detailed comparison. The focus will be given to CKKS scheme. [1] https://eprint.iacr.org/2022/915 [2] https://github.com/snucrypto/HEAAN [3] https://github.com/homenc/HElib
Polynomial Multiplication Methods for Lattice-based Cryptographic Schemes
In this project, the aim is to present a survey on the state-of-the-art for polynomial multiplication methods in lattice-based cryptography.
A Survey on Lattice Sieving and Enumeration Algorithms
Lattice-based cryptography has been used to get efficient quantum secure cryptographic primitives. The hardness of the underlying lattice problems, such as the shortest vector problem (SVP) and closest vector problem (CVP), is evaluated with the enumeration and sieving algorithms. In this project, the aim is to present a survey on the state-of-the-art for the lattice sieving and enumeration algorithms by considering time and area complexity.
Graph-based vulnerability and risk assessment models
IoT devices and systems are vulnerable to attacks due to their characteristics. There are various attack and vulnerability assessment studies in the literature to bring persistent and applicable solutions for security concerns in IoT. These studies provide different approaches in terms of network representation and solution techniques. The graph model is one of these representations and technical approaches. An attack graph model shows all possible attack path sequences from the source to the target. Therefore, graph-based models can offer systematic, formal, and strong directions to determine vulnerable points, and they can help to design defense mechanisms. In this seminar, the main goal is to give a literature review with comparison of available models.
Cybersecurity in Aviation [taken]
Over the past few years, information on hundreds of millions of aviation customers has been stolen in cyber-attacks. In addition to data breaches, airports and aviation applications have also been targeted in ransomware attacks where information and services are made unavailable until a ransom is paid. Aviation experts have expressed concern over potential vulnerabilities in aviation technologies that communicate information between aircraft and with air traffic control and ground services without any authentication or encryption. This could allow the injection of false messages and ghost aircraft. In this seminar, the main goal is to give a literature review with comparison of available models.
Arnis Paršovs
Applied cyber security topics
Applied cyber security group offers research seminar supervision on various cyber security-related topics for students who are interested in more applied research that may involve hands-on activities as well. Various hardware can be provided to students for experiments. Students who are doing applied research must still describe the research they have performed in a seminar report and convince the supervisor that the work done is worth 3 ECTS (~78 hours of work). Students are welcome to contact Arnis Paršovs (arnis.parsovs@ UT) with their seminar topic ideas.
Recommended prerequisites: Applied Cryptography (MTAT.07.017) / Wireless Technologies and Security (LTAT.04.009)
Level:BSc, MSc or PhD
Vitaly Skachek
Encryption from Random Quasi-Cyclic Codes
We will study a framework for constructing efficient code-based encryption schemes that do not hide any structure in their public matrix. There are two cryptosystems instantiated within this framework: the Hamming QuasiCyclic cryptosystem (HQC), based on the Hamming metric, and the Rank Quasi-Cyclic cryptosystem (RQC), based on the rank metric. In the project we will study and analyze those schemes.
Based on the paper: Aguilar, C., Blazy, O., Deneuville, J. C., Gaborit, P., & Zémor, G. (2016). Efficient encryption from random quasi-cyclic codes. arXiv preprint arXiv:1612.05572.
Suitable for MSc and PhD level students.
A Circuit Approach to Constructing Blockchains on Blockchains
Since the creation of Bitcoin 15 years ago, there has been an explosion in the number of permissionless blockchains. Each of these blockchains provides an open ledger that anyone can read from and write to. In this multi-chain world, an important question emerges: how can we build a more secure overlay blockchain by reading from and writing to a given set of blockchains? Drawing an analogy with switching circuits, we approach the problem by defining two basic compositional operations between blockchains, serial and triangular compositions, and use these operations as building blocks to construct general overlay blockchains. In this project, we will study and analyze this approach.
Based on the paper: Tas, E. N., Tse, D., & Wang, Y. (2024). A Circuit Approach to Constructing Blockchains on Blockchains. arXiv preprint arXiv:2402.00220.
Sven Laur
Low-level network simulator for MPC
Design of efficient cryptographic protocols is difficult as there are many trade-offs to consider. The aim of the project is to create low-level network simulator that given a set of instruction logs describing protocol would simulate network behavior and time individual instructions. The aim is to use a simple two part probabilistic model for computing arrival times of individual messages together with linear instruction log to estimate total running time and detect network bottlenecks.
Combinatorial optimisation of pooling layers in neural networks
Secure evaluation of neural network layers on top of MPC frameworks is extremely costly. More importantly GPU style parallelisation does not work as all computations are network bound. Therefore, operation minimisation is much more relevant than in the unprotected setting. Pooling layers reduce the size of a tensor by aggregating values over moving window. Aggregations of different windows can share intermediate results. This can be used to reduce the number of operation needed to evaluate the entire layer. The aim of the project is to study pooling mechanisms (max pooling) and find a way to minimise the number of low-level operations for 1D, 2D and 3D tensors with small window sizes. Ideally, one should give a matching lower bound on the operations. This is pure combinatorial optimisation task. No knowledge of cryptography is required.
Since the creation of Bitcoin 15 years ago, there has been an explosion in the number of permissionless blockchains. Each of these blockchains provides an open ledger that anyone can read from and write to. In this multi-chain world, an important question emerges: how can we build a more secure overlay blockchain by reading from and writing to a given set of blockchains? Drawing an analogy with switching circuits, we approach the problem by defining two basic compositional operations between blockchains, serial and triangular compositions, and use these operations as building blocks to construct general overlay blockchains. In this project, we will study and analyze this approach.
Based on the paper: Tas, E. N., Tse, D., & Wang, Y. (2024). A Circuit Approach to Constructing Blockchains on Blockchains. arXiv preprint arXiv:2402.00220.
Suitable for MSc and PhD level students.