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 (standardized as ML-KEM).

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 

The security of cryptosystems is often evaluated by how hard it is to break them (forge a valid plaintext/ciphertext or message/signature pair) under the assumption that the secret key remains hidden.

In this seminar topic, we study leakage robustness, i.e., the property of a cryptosystem to remain secure even when part of the secret key is revealed. 

The student should read and understand the main paper by D'Alconzo et al., which studies the leakage robustness of three signature schemes in the rank metric that are currently under consideration for standardization by NIST.

Main Paper:

Sneaking up the Ranks: Partial Key Exposure Attacks on Rank-Based Schemes, https://eprint.iacr.org/2024/2070.pdf

Additional Reading:

Elena Kirshanova and Alexander May. Breaking Goppa-Based McEliece with Hints, https://eprint.iacr.org/2022/525.pdf

Don Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities, https://link.springer.com/article/10.1007/s001459900030

In this thesis, we want to investigate the list decoding complexity of random (linear) codes in the sum-rank metric.

List decoding is a technique to decode beyond the unique decoding radius of a code at the cost of obtaining a list of candidate solutions. The sum-rank metric [1] is a relatively novel metric where the weight of a vector is given by the sum of the ranks of its component blocks.

As a starting point, the student should familiarize themselves with the concept of the sum-rank metric. Then, the list decoding behavior of a random SR code should be investigated, perhaps along the lines of these papers [2,3] that have some similar results on random rank metric codes. It would also be nice to investigate if this other technique [4] can be applied to the sum-rank metric.

Resources:

[1] https://arxiv.org/pdf/2102.02244 (this is not the paper where this metric was first studied, but it has a very nice overview of existing results)

[2] https://arxiv.org/abs/1401.2693

[3] https://arxiv.org/abs/1710.11516

[4] https://arxiv.org/abs/1704.02420

Prerequisites