Seminar Themen

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 

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

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.

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.

- Machine Learning and Statistics
- Information Theory

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 

In cryptography, an oblivious transfer (OT) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred.   Often seen as an enemy, noise turned out to be a good ally of cryptographers. While a noiseless channel, from a cryptographic point of view, is a sterile medium where information theoretical security cannot be achieved for two parties, noise provides us with oblivious transfer (OT), the most powerful two-party primitive.   https://link.springer.com/chapter/10.1007/978-3-642-36899-8_6   https://ieeexplore.ieee.org/document/4529286   https://ieeexplore.ieee.org/document/8000673

Information theory

the capacity of optical transmission system is limitted by the nonlinear effects in the fiber.

the digital back propagation(DBP) is a method to sovle this problem.

By reading some papers, student can get the principle of this method and its advantage.

it's better for student to have some basic knowledge about optical transmission system, nonlinear effects and digital signal processing.

Digital coherent optical receivers have revolutionized optical transmission system design through the integration of advanced subsystems and algorithms. This paper presents a comprehensive analysis of these components, including the optical front end, analog-to-digital converter (ADC), and digital signal processing (DSP) algorithms that contribute to the performance of the system. The paper delves into the methods used to compensate for transmission impairments, both static and dynamic, with a particular focus on dynamic-channel equalization.

[1] S. J. Savory, "Digital Coherent Optical Receivers: Algorithms and Subsystems," in IEEE Journal of Selected Topics in Quantum Electronics, vol. 16, no. 5, pp. 1164-1179, Sept.-Oct. 2010.

Recommended Courses:

   - Digital Signal Processing for Optical Communication Systems

   - Optical Communication Systems