Seminars
Key Attacks on the GPT Cryptosystem
rank-metric finite-field coding-theory cryptography
Description
The McEliece cryptosystem is a well-known public-key encryption scheme using Goppa codes in the Hamming metric. The GPT cryptosystem is the rank-metric counterpart of this scheme using Gabidulin codes. While this promises much better message security than McEliece, it has been subject to several successful key attacks, most prominent of which is known as Overbeck's attack [1, 2].
The task of the student is to understand the different proposed versions of the GPT cryptosytem and how they were attacked. Further, the student will look at a more recent version of this scheme [3] which has so far resisted Overbeck's attack.
[1] R. Overbeck, “Public Key Cryptography based on Coding Theory,” phd, Technische Universität Darmstadt, Darmstadt, 2007. Accessed: Oct. 01, 2024. [Online]. Available: https://tuprints.ulb.tu-darmstadt.de/823/
[2] R. Overbeck, “Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes,” J Cryptol, vol. 21, no. 2, pp. 280–301, Apr. 2008, doi: 10.1007/s00145-007-9003-9.
[3] P. Loidreau, “A New Rank Metric Codes Based Encryption Scheme,” in Post-Quantum Cryptography, T. Lange and T. Takagi, Eds., Cham: Springer International Publishing, 2017, pp. 3–17. doi: 10.1007/978-3-319-59879-6_1.
Prerequisites
- Channel Coding
- Familiarity with the rank metric is beneficial (either from the course "Security in Communications and Storage" or "Coding Theory for Storage and Networks")
Supervisor:
Codes for absorption channels
Description
The absorption channel is a novel communication model inspired by neuronal information transmission. This model is particularly relevant to in-vivo nano-machines, emerging medical applications, and brain-machine interfaces that communicate via the nervous system.
Specifically, an absorption error occurs when a transmitted symbol is completely lost or "absorbed" during communication, rather than being substituted or distorted. This means the receiver gets fewer symbols than were originally sent, creating a form of synchronization error.
?[1] focusses on developing error-correcting codes tailored to address absorption errors within this channel. It also proposes specific constructions to correct a single absorption error for alphabets of size three or more. Additionally, the paper applies syndrome compression techniques with pre-coding to develop subcodes capable of correcting multiple absorption errors while maintaining low redundancy. Efficient encoding and decoding algorithms are provided for each proposed code, enhancing their practical applicability in communication systems affected by absorption errors. ?
[2] extends this work by introducing novel methods for constructing non-binary error-correcting codes tailored to address absorption errors. The authors propose novel code constructions that effectively correct single and multiple absorption errors while minimizing redundancy. Their approach involves partitioning codewords into segments and applying specialized coding techniques to each segment, enabling efficient detection and correction of absorption errors.
[1] Z. Ye, W. Yu, and O. Elishco, “Codes Over Absorption Channels,” IEEE Trans. Inform. Theory, pp. 1–1, 2024, doi: 10.1109/TIT.2023.3346882.
[2] T. T. Nguyen, K. Cai, T. Q. S. Quek, and K. A. S. Immink, “Efficient Constructions of Non-Binary Codes Over Absorption Channels,” in 2024 IEEE International Symposium on Information Theory (ISIT), Athens, Greece: IEEE, Jul. 2024, pp. 1718–1723. doi: 10.1109/ISIT57864.2024.10619179.
Supervisor:
Partial Key Exposure Attacks
Cryptography, Side-Channel Attacks
Description
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
Don Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities, https://link.springer.com/article/10.1007/s001459900030
Supervisor:
Homomorphic Encryption
Homomorphic Encryption, GSW13
Description
Homomorphic Encryption (HE) is a type of encryption that allows calculations to be performed on the ciphertexts [1]. If any kind of operation is allowed, it is called Fully Homomorphic Encryption (FHE). This concept offers many opportunities regarding data protection for cloud services. This technology allows users to keep their data secret, while still being able to outsource calculations on this data to a server. For example, in the field of machine learning, the training can be carried out on private data.
The first fully homomorphic encryption system was introduced by Gentry in 2009 [2]. Since then, there have been various other schemes and optimizations. For a first overview [3] and [4] are recommended.
The goal of the seminar would be to give an overview of Homomorphic Encryption, including the variants and definitions, and to present a concrete instantiation of some FHE scheme, such as for example the GSW13 [5] or DGHV10 [6] scheme.
[1] Rivest, Ronald L., Len Adleman, and Michael L. Dertouzos. "On data banks and privacy homomorphisms." Foundations of secure computation 4.11 (1978): 169-180.
[2] Gentry, Craig. "Fully homomorphic encryption using ideal lattices." Proceedings of the forty-first annual ACM symposium on Theory of computing. 2009.
[3] Vaikuntanathan, Vinod. "Computing blindfolded: New developments in fully homomorphic encryption." 2011 IEEE 52nd annual symposium on foundations of computer science. IEEE, 2011.
[4] Brakerski, Zvika. "Fundamentals of fully homomorphic encryption-a survey." Electronic Colloquium on Computational Complexity (ECCC). Vol. 25. 2018.
[5] Gentry, Craig, Amit Sahai, and Brent Waters. "Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based." Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I. Springer Berlin Heidelberg, 2013.
[6] Van Dijk, Marten, et al. "Fully homomorphic encryption over the integers." Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29. Springer Berlin Heidelberg, 2010.
Supervisor:
Minimal Random Coding for Stochastic Federated Learning
Description
Communication efficiency is a major and well-studied premise in federated learning (FL). Various compression schemes have been proposed to alleviate prohibitively high communication costs. In stochastic formulations of FL, principled approaches to compression can substantially improve existing measures. Minimal random coding (MRC), introduced in [1], leverages side information, common randomness, and tools from importance-sampling. The authors of [2] proposed to use MRC for stochastic FL and show substantial improvements in various domains.
The task of the student is to understand the principles of the proposed compression schemes and their application to stochastic FL for different learning narratives. The student should analyze where the substantial communication improvements originate from, and what open problems remain.
[1] Marton Havasi, Robert Peharz, and Jose Miguel ´ Hernandez-Lobato. Minimal random code learning: ´ Getting bits back from compressed model parameters. In International Conference on Learning Representations, 2019.
[2] Berivan Isik, Francesco Pase, Deniz Gunduz, Sanmi Koyejo, Tsachy Weissman, and Michele Zorzi. Adaptive compression in federated learning via side information. In International Conference on Artificial Intelligence and Statistics, pp. 487–495, 2024.
Supervisor:
Single-Server Private Information Retrieval
Description
In single-server Private Information Retrieval (PIR), a server stores a database from which a user wants to download a specific entry.
While the database is public — allowing the user to learn additional entries — the server should not learn any information about which file the user is interested in.
This problem appears in numerous applications, such as safe browsing.
A trivial solution is downloading the entire database, which is, however, highly inefficient. Cryptographic techniques offer more practical solutions that significantly reduce communication costs.
This project will survey existing constructions for efficient single-server PIR. The goal is to categorize these constructions based on their underlying hardness assumptions, the use of preprocessing, and key techniques used. The project requires reading and understanding several references; a good starting point can be the following works:
[1] Zhou, Mingxun, et al. "Piano: extremely simple, single-server PIR with sublinear server computation." IEEE Symposium on Security and Privacy, 2024.
[2] Li, Baiyu, et al. "Hintless single-server private information retrieval." Annual International Cryptology Conference, 2024.
Prerequisites
- lecture "Security in COmmunication and Storage"
Supervisor:
Two-Deletion Correcting Codes
Description
Background:
This seminar explores the design of error-correcting codes capable of correcting two deletions—a natural yet significantly challenging progression from single-deletion codes. The study of deletion (and insertion) correcting codes dates back to the early 1960s. Levenshtein’s work [3] showed that VT codes [5], originally designed for asymmetric error correction, also handle single deletion/insertion errors with near-optimal redundancy of at most log?(n) bits. This elegant construction spurred extensive research to extend these ideas to correct multiple deletions. However, extending VT codes to the two-deletion scenario has proven difficult; natural augmentations with additional check equations have not achieved the desired performance.
Modern Relevance & DNA Data Storage:
Deletion-correcting codes have gained practical importance in emerging fields like DNA data storage, where sequencing errors often manifest as deletions. In these applications, efficient and low-redundancy codes are crucial for reliable data retrieval, highlighting the importance of advancements in two-deletion correcting codes.
Seminar Focus:
Recent years have seen renewed interest in this topic, with several works proposing two-deletion correcting codes that achieve good asymptotic redundancy [1][2][4]. The goal of this seminar is to deeply understand two of these approaches. The student will develop detailed examples and illustrations to explain the code constructions, followed by an analysis comparing the redundancy of the two codes for various code lengths
Expected Outcomes:
- Detailed Examples: Step-by-step encoding and decoding demonstrations for two codes, illustrating the underlying principles.
- Visual Illustrations: Graphics that clearly depict the error-correcting capabilities.
- Comparative Analysis: A discussion comparing the two approaches, supported by quantitative analysis and visual data showing redundancy for different code lengths.
References:
[1] R. Gabrys and F. Sala, “Codes Correcting Two Deletions,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 965–974, Feb. 2019, doi: 10.1109/TIT.2018.2876281.
[2] V. Guruswami and J. Håstad, “Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound,” IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6384–6394, Oct. 2021, doi: 10.1109/TIT.2021.3069446.
[3] V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals,” in Soviet physics doklady, Soviet Union, 1966, pp. 707–710.
[4] J. Sima, N. Raviv, and J. Bruck, “Two Deletion Correcting Codes From Indicator Vectors,” IEEE Trans. Inform. Theory, vol. 66, no. 4, pp. 2375–2391, Apr. 2020, doi: 10.1109/TIT.2019.2950290.
[5] R. R. Varshamov and G. M. Tenengolts, “Codes which correct single asymmetric errors (in Russian),” Automatika i Telemkhanika, vol. 161, no. 3, pp. 288–292, 1965.
Prerequisites
- Channel Coding course completed
- Very good understanding of linear algebra and combinatorics
Supervisor:
Oblivious Transfer and Garbled Circuits
oblivious transfer, garbled circuits
Description
Oblivious transfer is a cryptographic protocol between a sender and a receiver. The server has multiple pieces of information, and according to which he/she has initially chosen, the receiver obtains only one of them. The sender remains oblivious to which information the receiver got.
Garbled circuits is the name of a cryptographic technique used for secure multi-party computation. It allows multiple parties to jointly compute a function on their private inputs, while preserving the privacy of the parties.
The task of the student is to understand the concept of garbled circuits ([4], [6]) based on oblivious transfer ([1], [2], [3], [5]).
References:
[1] W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, November 1976.
[2] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 26:96–99, 1978.
[3] Michael Rabin. How to exchange secrets with oblivious transfer. 1981.
[4] Andrew C. Yao. Protocols for secure computations. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 160–164, 1982.
[5] S. Even, O. Goldreich, and A. Lempel, “A randomized protocol for signing contracts,” Commun. ACM, vol. 28, pp. 637–647, 01 1985.
[6] Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 162–167, 198.
Prerequisites
Security in Communications and Storage
Supervisor:
Graph Entropy in Combinatorics
Description
Information theory and combinatorics are deeply intertwined. Beyond the use of combinatorics in coding theory and compression, there are many -sometimes surprising- connections.
One such connection is the use of graph entropy in combinatorial existence proofs.
This seminar topic is about explaining the proof technique introduced in [1] and [2] and applied in [3]. The goal is a tutorial-style paper with the focus on clear exposition through well chosen worked examples and visualizations.
[1] M. Fredman, and J. Komlós, On the Size of Separating Systems and Perfect Hash Functions, SIAM J. Alg. Disc. Meth., 5 (1984), pp. 61-68.
[2] J. Körner, Fredman-Komlós bounds and information theory, SIAM J. on Algebraic and Discrete Meth., 4(7), (1986), pp. 560–570.
[3] N. Alon, E. Fachini, and J. Körner, Locally Thin Set Families, Combinatorics, Probability and Computing, vol. 9 (Nov. 2000), pp. 481–488.
Supervisor:
Multi-round privacy in federated learning
Description
Federated learning allows to train a machine learning model in a distributed manner, i.e., the training data are collected and stored locally by users such as mobile devices or multiple institutes. The training is under the coordination of a central server and performed iteratively. In each iteration, the server sends the current global model to the users, who update their local model and send the local updates to the server for aggregation.
FL is proposed to protect user's sensitive data since these training data never leave the user devices. However, works have shown that the local updates still leaks information about the local datasets. To deal with this leakage, SecAgg[1] is proposed. Secure aggregation is to make sure that the server only obtains the aggregation of the local updates rather than each individual update.
However, recent work [2] has shown that, SecAgg only preserves privacy of the users in a single training round. Due to user selection in federated learning, by observing the aggregated models over multiple training rounds, the server is able to recoverindividual local models of the users.
The goal of this seminar is to study and understand SecAgg [1], the multi-round privacy leakage it suffers and how is this problem solved in [2].
[1]. Bonawitz, Keith, et al. "Practical secure aggregation for privacy-preserving machine learning." proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.
[2]. So, Jinhyun, et al. "Securing secure aggregation: Mitigating multi-round privacy leakage in federated learning." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 8. 2023.
Supervisor:
Understanding Guarantees and Pitfalls of Differential Privacy
Description
Many popular applications, such as recommender systems, data mining, or machine learning require the collection and processing of large datasets. In view of the ubiquitous data collecting, users claim for privacy, but guaranteeing privacy while providing useful data is challenging. Differential Privacy (DP) [1] has become a popular notion for data privacy, which quantifies the ability of a curious data analyst to identify the value of sensitive data points. To use DP in practical systems, it is important to understand the fundamental guarantees of a system that claims to ensure DP.
While it is sometimes believed that DP guarantees hold unconditionally and even in the presence of arbitrary side information, it has been shown that it is not possible to provide privacy and utility without making assumptions about how the data are generated [2]. In particular, dependence (correlation) between different database entries can be exploited to break the alleged privacy guarantees [3].
In this seminar topic, the student will familiarize herself with the definition and formal guarantees of DP and study the issues and pitalls of DP, particularly with a focus on dependent data distributions. The student will summarize the findings in the form of a scientific presentation and a scientific article, based on her own reading of scientific papers. These can include but are not necessarily limited to the recommended references [1-3].
[1] C. Dwork and A. Roth, “The Algorithmic Foundations of Differential Privacy,” TCS, 2014.
[2] D. Kifer and A. Machanavajjhala, "No free lunch in data privacy," Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data (SIGMOD '11).
[3] C. Liu, S. Chakraborty, and P. Mittal, “Dependence Makes You Vulnerable: Differential Privacy Under Dependent Tuples,” in Proceedings of the Network and Distributed System Security Symposium, 2016.
Contact
Luis Maßny (luis.massny@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:
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