Seminare
NTRUEncrypt and NTRUSign
lattice-based cryptography
Beschreibung
NTRU is a well-known lattice-based cryptosystem that can be described using polynomial rings. The public-key encryption scheme NTRUEncrypt has the advantage of having short keys with fast encryption/decryption algorithms and is considered a viable candidate for post-quantum cryptography. There is also a signature scheme called NTRUSign, though its security is less trusted compared to NTRUEncrypt.
The task of the student is to understand and summarise how the two schemes work, the attacks against them in the literature and the countermeasures proposed to resist these attacks.
[1] J. Hoffstein, J. Pipher, and J. H. Silverman, ‘NTRU: A ring-based public key cryptosystem’. doi: 10.1007/BFb0054868.
[2] J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte, ‘NTRUSign: Digital Signatures Using the NTRU Lattice’. doi: 10.1007/3-540-36563-X_9.
[3] J. Hoffstein, N. Howgrave-Graham, J. Pipher, and W. Whyte, ‘Practical Lattice-Based Cryptography: NTRUEncrypt and NTRUSign’. doi: 10.1007/978-3-642-02295-1_11.
Voraussetzungen
- Security in Communications and Storage
Betreuer:
Number-Theoretic Transform
Beschreibung
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
Kontakt
anna.baumeister@tum.de
Betreuer:
Post-Quantum Cyptography based on Codes: Generalized (U|U+V) codes
post-quantum cryptography, code-based, concatenated codes, generalized concatenation
Beschreibung
Due to the recent advances in quantum computers, searching for cryptosystems that survive quantum attacks is of great interest. Code-based cryptography is a promising candidate since it is built on the NP-hard problem of decoding a random code [5].
Random-looking codes replace random codes for most cryptosystems to enable a trapdoor. McEliece originally proposed to use binary Goppa codes. Later, MDPC codes were successfully introduced.
More recently, it was suggested that generalized (U|U+V) codes be used, which belong to the class of generalized concatenated codes.
Concatenated codes play an important role in classical channel coding, but further research is required to evaluate which variants also form a promising basis for code-based cryptography.
The goal of this topic is to analyze constructions of generalized concatenated codes proposed for cryptographic applications, e.g., [1-4]:
- how do proposed constructions work?
- which properties do they have?
- is the secret structure well hidden?
The exact scope can be set depending on your interest.
Main Papers:
[1] Márquez-Corbella, Irene, and Jean-Pierre Tillich. "Using Reed-Solomon codes in the (U| U+ V) construction and an application to cryptography." 2016 IEEE International Symposium on Information Theory (ISIT). IEEE, 2016.
[2] Puchinger, S., Müelich, S., Ishak, K., & Bossert, M. (2017). Code-based cryptosystems using generalized concatenated codes. In Applications of Computer Algebra: Kalamata, Greece, July 20–23 2015 (pp. 397-423). Springer International Publishing.
[3] Debris-Alazard, T., Sendrier, N., & Tillich, J. P. (2018). Wave: A new code-based signature scheme.
[4] Cho, J., No, J. S., Lee, Y., Koo, Z., & Kim, Y. S. (2022). Enhanced pqsigRM: code-based digital signature scheme with short signature and fast verification for post-quantum cryptography. Cryptology ePrint Archive.
Further References:
[5] Weger, V., Gassner, N., & Rosenthal, J. (2022). A Survey on Code-Based Cryptography. arXiv preprint arXiv:2201.07119.
Voraussetzungen
Security in Communications and Storage
Channel Coding
Betreuer:
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
Beschreibung
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
Voraussetzungen
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.
Betreuer:
Random Walks for Decentralized Learning
Beschreibung
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.
Voraussetzungen
- Machine Learning and Statistics
- Information Theory
Betreuer:
Rank-Metric Codes and Their Applications
Beschreibung
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
Betreuer:
String Reconstruction from Substring Compositions: Application to Polymer-Based Storage
Polymer-based data storage, string reconstruction, composition errors, insertions, deletions
Beschreibung
Polymer-based storage involves storing information strings as a chain of molecules, the masses of which indicate whether the encoded bit is a 0 or 1. The readout mechanism requires tandem mass spectrometers which output compositions of all possible substrings, i.e. the number of 0s and 1s in a particular substring. The authors of [1] demonstrated that unique string reconstruction is only possible for specific string lengths, and also presented an algorithm for the same. In [2-5], code constructions were presented to facilitate this for all string lengths and also to correct substitution errors in the measured compositions.
[1] J. Acharya, H. Das, O. Milenkovic, A. Orlitsky, and S. Pan, “String
reconstruction from substring compositions,” SIAM Journal on Discrete
Mathematics, vol. 29, no. 3, pp. 1340--1371, 2015.
[2] S. Pattabiraman, R. Gabrys and O. Milenkovic, "Coding for Polymer-Based Data Storage", arXiv:2003.02121, 2020
[3] R.Gabrys, S.Pattabiraman, and O.Milenkovic, "Mass error-correction codes for polymer-based data storage,” IEEE International Symposium on Information Theory, ISIT 2020, Los Angeles, CA, USA, June 21-26, 2020, pp. 25--30, IEEE, 2020.
[4] S.~Pattabiraman, R.~Gabrys, and O.~Milenkovic, “Reconstruction and error-correction codes for polymer-based data storage,” in IEEE Information Theory Workshop, ITW 2019, Visby, Sweden, August 25-28,2019, pp. 1--5, IEEE, 2019.
[5] R. Gabrys, S. Pattabiraman and O. Milenkovic, "Reconstructing Mixtures of Coded Strings from Prefix and Suffix Compositions," 2020 IEEE Information Theory Workshop (ITW), 2021, pp. 1-5.