Seminars
Number-Theoretic Transform
Description
The number-theoretic transform (NTT) is a generalization of the discrete Fourier transform over a ring or finite field. In a similar fashion to the FFT algorithm, the NNT efficiently computes the circular convolution of an integer sequence. An application of the NTT is the multiplication of two polynomials over a finite field, which is often used in cryptosystems based on lattices like CRYSTALS-KYBER.
Tasks:
- Understand the NTT and inverse NTT and how it relates to the FFT,
- study applications of NTT in post-quantum cryptosystems using the paper provided
Main papers:
Number Theoretic Transform and Its Applications in Lattice-based Cryptosystems: A Survey
Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations
A nice primer on the NTT with examples can also be found in this blog
Contact
anna.baumeister@tum.de
Supervisor:
Indistinguishability Obfuscation (iO)
Fully Homomorphic Encryption, Circular Security, Learning with Errors
The student's task is to survey the literature to understand the formal definition, properties and applications of indistinguishability obfuscation (iO). More specifically, the student should aim to explain a recent construction [1] achieving this notion and the underlying hardness assumptions. [1] Brakerski, Z., Döttling, N., Garg, S., & Malavolta, G. (2020). Factoring and pairings are not necessary for io: Circular-secure lwe suffices. Cryptology ePrint Archive. https://eprint.iacr.org/2020/1024
Description
There are scenarios where we wish to enable public access to a program (a function) without giving away any information about how the function is implemented.
For general circuits, this notion called virtual black box obfuscation is known to be impossible.
However, a weaker notion called indistinguishability obfuscation (iO) can be achieved.
Here, the obfuscations of two similarly-size circuits realizing the same function should be computationally indistinguishable from each other and reveal no more than some canonical form of the underlying function.
In some sense this is even the strongest achievable form of function obfuscation.
As of today, iO is too inefficient for almost all practical applications.
However, recent research has shown it may be used to build most cryptographic constructions of interest (assuming the existence of a one-way function).
For some of these it is even the only currently known way.
The student's task is to survey the literature to understand the formal definition, properties and applications of indistinguishability obfuscation (iO). More specifically, the student should aim to explain a recent construction [1] achieving this notion and the underlying hardness assumptions.
[1] Brakerski, Z., Döttling, N., Garg, S., & Malavolta, G. (2020). Factoring and pairings are not necessary for io: Circular-secure lwe suffices. Cryptology ePrint Archive. https://eprint.iacr.org/2020/1024
Prerequisites
Any prior knowledge of modern cryptography such as notions of security based on computational indistinguishability as well as an elementary understanding of the concept of homomorphic encryption (based on lattices) will be useful for this task.
Supervisor:
Random Walks for Decentralized Learning
Description
Fully decentralized schemes do not require a central entity and have been studied in [1, 2]. These works aim to reach consensus on a desirable machine learning model among all clients. We can mainly distinguish between i) gossip algorithms [3] where clients share their result with all neighbors, naturally leading to high communication complexities, and ii) random walk approaches like [4, 5] where the model is communicated only to a specific neighbor until matching certain convergence criteria. Such random walk approaches are used in federated learning to reduce the communication load in the network and at the clients’ side.
The main task of the student is to study the work in [5], which additionally accounts for the heterogeneity of the clients’ data. Further, drawbacks and limitations of the proposed approach should be determined.
[1] J. B. Predd, S. B. Kulkarni, and H. V. Poor, “Distributed learning in wireless sensor networks,” IEEE Signal Process. Mag., vol. 23, no. 4, pp. 56–69, 2006.
[2] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein et al., “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., vol. 3, no. 1, pp. 1–122, 2011.
[3] S. S. Ram, A. Nedi ?c, and V. V. Veeravalli, “Asynchronous gossip algorithms for stochastic optimization,” in IEEE Conf. Decis. Control. IEEE, 2009, pp. 3581–3586.
[4] D. Needell, R. Ward, and N. Srebro, “Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm,” Adv. Neural Inf. Process. Syst., vol. 27, 2014.
[5] G. Ayache, V. Dassari, and S. E. Rouayheb, “Walk for learning: A random walk approach for federated learning from heterogeneous data,” arXiv preprint arXiv:2206.00737, 2022.
Prerequisites
- Machine Learning and Statistics
- Information Theory
Supervisor:
Rank-Metric Codes and Their Applications
Description
Rank-matric codes are codes that live in a vector space that is endowed with a different metric than the Hamming metric: in the rank-metric the distance between two codewords, represented as matrices over a smaller field, is defined as the rank of their difference.
The theory of rank-metric codes has interesting connections to many topics in discrete mathematics and promissing applications to code-based cryptography and network coding.
In this seminar work, the student will study properties and constructions of rank-metric codes and one or more applications. The goal is to understand and summarize parts of the following papers:
[1] H. Bartz, L. Holzbaur, H. Liu, S. Puchinger, J. Renner, A. Wachter-Zeh (2022). “Rank-Metric Codes and Their Applications”. arXiv: 2203.12384 https://arxiv.org/pdf/2203.12384.pdf
[2] K. Marshall, (2016). “A study of cryptographic systems based on Rank metric codes”, Dissertation, University of Zurich https://www.zora.uzh.ch/id/eprint/127105/1/Diss%20Kyle.pdf
[3] T. Randrianarisoa, (2018). “Rank metric codes, codes using linear complexity and applications to public key cryptosystems”, Dissertation, University of Zurich https://www.zora.uzh.ch/id/eprint/153545/1/153545.pdf
[4] E. Gorla (2019). “Rank-metric codes”. arXiv: 1902.02650 https://arxiv.org/pdf/1902.02650.pdf
[5] E. Gorla and A. Ravagnani. (2018). “Codes endowed with the rank metric”. In: Network Coding and Subspace Designs. Springer. 3–23. https://link.springer.com/content/pdf/10.1007/978-3-319-70293-3.pdf