Bachelor's Theses
Coding with Feedback
Description
In paper
"Correcting a Single Error in Feedback Channels" the problem of correcting a single error with feedback was investigated. It was mainly devoted to binary channels, namely, binary symmetric and asymmetric channels. A general theorem, which allows constructing strategies with one feedback, was proved. For the symmetric channel with one error, it was proved that with two feedbacks one can transmit as many messages as with complete feedback. For the asymmetric channel, some strategies for small lengths have been proposed. Later some results for the binary symmetric channel have been generalized for the qary symmetric channel. (These results are not published yet, I can send the draft).
There are multiple ways, how this research can be continued:
 One can try to generalize the results from mentioned paper for the case of 2 errors or a constant number of errors.
 The methods developed in the paper "Correcting a Single Error in Feedback Channels" allow us to construct optimal codes for the asymmetric channel with complete feedback and compute their sizes. However, it requires a lot of time. It would be interesting to prove a general formula for the size of such optimal codes.
 Another direction is to consider nonsymmetric qary channels.
Supervisor:
Coding theory in different metrics
Description
In this thesis, the student will study the mathematics of codes in diffent metrics such as the Hamming metric, (sum)rank metric, column/rowcover metric, etc.
The focus can lie on similar mathematical ideas shared across different metrics, such as bounds on codes, good code constructions, decoding algorithms, applications.
Supervisor:
Codebased Cryptography
Description
In this thesis, the student will study the mathematics of linear codes and how they can be used to design cryptosystems.
Supervisor:
[identification] Idnetification and Secrecy with PhysicallyUnclonableFunctions (PUFs)
PUF secrecy identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
From previous work we have a fairly efficient implementation based ReedMuller code which can be found at
Secrecy in this identification codes has also been implemented in unpublished work. Furthermore, the theoretical work on Identification with PUF's has been done in
The goal of the project will be to bridge the three topics and create practical and efficient secret identification codes in the PUF setting.
The working language will be in English.
Environment: this is a project in collaboration with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
Statistical Decoding
codebased cryptography, decoding attack
Description
Due to the recent advances in quantum computers, the search for cryptosystems that survive quantum attacks is of great interest. Codebased cryptography is a promising candidate, since it is build on the NPhard problem of decoding a random code [1].
In order to solve the generic decoding problem, algorithms from the information set decoding (ISD) family can be used.
During the last 60 years, small improvements to this approach were made. During this time, other algorithms, such as statistical decoding [2], were proposed, but failed to achieve the performance of ISD [3].
Recently, a variant of statistical decoding was proposed that claims to perfom better than the best ISD variants for low code rates [4].
If you are interested, please write an email, then we'll discuss the details.
Main Paper:
Carrier, K., DebrisAlazard, T., MeyerHilfiger, C., & Tillich, J. P. (2022). Statistical Decoding 2.0: Reducing Decoding to LPN. arXiv preprint arXiv:2208.02201.
References:
[1] Weger, V., Gassner, N., & Rosenthal, J. (2022). A Survey on CodeBased Cryptography. arXiv preprint arXiv:2201.07119.
[2] Jabri, A. A. (2001, December). A statistical decoding algorithm for general linear block codes. In IMA International Conference on Cryptography and Coding (pp. 18). Springer, Berlin, Heidelberg.
[3] DebrisAlazard, T., & Tillich, J. P. (2017, June). Statistical decoding. In 2017 IEEE International Symposium on Information Theory (ISIT).
[4] Carrier, K., DebrisAlazard, T., MeyerHilfiger, C., & Tillich, J. P. (2022). Statistical Decoding 2.0: Reducing Decoding to LPN. arXiv preprint arXiv:2208.02201.
Prerequisites
Channel coding
Security in Communications and Storage
Probability theory and statistics
Supervisor:
Private and Secure Federated Learning
Description
In federated learning, a machine learning model shall be trained on private user data with the help of a central server, the socalled federator. This setting differs from other machine learning settings in that the user data shall not be shared with the federator for privacy reasons and/or to decrease the communication load of the system.
Even though only intermediate results are shared, extra care is necessary to guarantee data privacy. An additional challenge arises if the system includes malicious users that breach protocol and send corrupt computation results.
The goal of this work is to design, implement and analyze coding and informationtheoretic solutions for privacy and security in federated learning.
Prerequisites
 Coding Theory (e.g., Channel Coding)
 Information Theory
 Machine Learning Basics
Supervisor:
[identification] PseudoRandom Identification
random pseudo identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy tradeoffs between the error and the codes sizes.
The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
One advantage can be gained by using pseudo randomness to generate both the input and the code itself.
Your task will be implementing the identification codes described in the attached pdf (an english translation of a paper published in russian in a russian journal) aiming at the fastest implementation and smallest collisions, and testing their performance in comparison to other current implementations.
For reference, our previous work on identification based on ReedSolomon and ReedMuller code can be found at
The coding will be in Python/Sagemath.
The working language will be in English.
Environment: we collaborate with LTI from TUM and CeTI from TU Dresden, the latter having already some preliminary implementation of pseudorandom identification using various pseudorandom generators. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
Error Correcting Codes for Memories with (Partially) Defects
Linear Codes, Algebraic Codes, Error Correction , Masking Defects, Flash Memories, PhaseChange Memories
Description
For different applications, the demand for reliable memory solutions in particular for nonvolatile memories such as phasechange memories (PCMs) is rapidly increasing. PCM cells may become defective (also called stuck) either fully or partially if they fail in switching their states, and therefore these cells can only hold a single phase. In response to these defects, combined masking and errorcorrecting code constructions have been proposed, where masking is for hiding the defects while errorcorrecting is to compromise potential addedchannel errors. We want to investigate further code constructions such that less overall redundancy is required to handle these two types of errors. As an alternate, work for combined erasure errors and masking code constructions could be investigated.
Prerequisites
 Basic principle of Linear Algebra
 Channel Coding/Coding Theory
 Basic knowledge in Information Theory
Contact
M.Eng. Haider Al Kim
Doctoral Researcher
Technical University of Munich
Department of Electrical and Computer Engineering /
Coding and Cryptography (COD) Group
Email: haider.alkim@tum.de
Supervisor:
Deterministic KIdentification For The DMC With Power Constraint
Identification via channel, Kidentification, deterministic codes
Kidentification capacity of a DMC is derived.
Description
The student attempt to study the deterministic identification capacity
of a DMC subject to power constraint and generalize it for the Kidentification.
Prerequisites
Basics of Information Theory and Channel Coding.
Familiarity with the fundamentals of Identification Theory
Supervisor:
[identification] Implementation of identification with universal hash functions
universal hash identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy tradeoffs between the error and the codes sizes.
The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
Your task will be implementing the identification codes described in
aiming at the fastest implementation, and testing their performance in comparison to other current implementations.
For reference, our previous work on identification based on ReedSolomon and ReedMuller code can be found at
The coding will be in Python/Sagemath.
The working language will be in English.
Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
Master's Theses
Efficient Block Propagation in Cryptocurrency Networks
Description
Cryptocurrencies like Bitcoin and Ethereum use a decentralized ledger called Blockchain to track transactions. Whenever a new block is added to the Blockchain, the change is spread through the network using a gossiplike protocol. This process is known as block propagation.
To increase scalability, the efficiency of block propagation is crucial. This thesis aims to explore the information theoretic limits of block propagation, derive realistic models based on real data, and investigate innovative and efficient techniques for block propagation.
The thesis will be conducted at the Institute of Communications and Navigation at DLR (German Aerospace Center) in Oberpfaffenhofen.
Prerequisites
Required qualifications are
 basic knowledge of information theory
 programming experience in Matlab, C, or python.
 Interest in cryptocurrencies.
Contact
Interested applicants may contact Dr. Francisco Lázaro via email at francisco.lazaroblasco@dlr.de.
Supervisor:
Channel Coding: Efficient Decoding for GC Codes and General Codes
channel coding, efficient decoding, generalized concatenated codes
We develop efficient decoders for short block codes.
Description
Arising applications, such as machinetomaschine communication require errorcorrection codes with short information length.The design of such codes and efficient decoders is an open problem [1].
Recently, ReedMuller codes have gained a lot of interest, because of thier good errorcorrection capability and their structure, which allows for lowcomplexity decoders, see, e.g., [2].
It has been known for quite some time that ReedMuller codes belong to a more general class of codes: the Generalized Concatenated (GC) Codes [3].
This class allows for more flexible code design, e.g., with respect to the information rate of the code.
Hence, by transfering and refining results for ReedMuller codes to GC codes, one could improve over existing solutions.
Another approach to obtain good results in the shortlength regime is using the bestknown codes [4].
Since these codes do usually not have a structure that enables efficient decoding, one has to perform decoding of a general linear code. The most efficient approaches are variants of Ordered Statistics Decoding (OSD) [5]. The idea for improving over stateoftheart varaints is to encorporate recent improvements from another field of research: Information Set Decoding.
If you are interested in either of the directions (or have some other direction in mind), please write an email, then we'll discuss the details.
References:
[1] Co?kun, M. C., Durisi, G., Jerkovits, T., Liva, G., Ryan, W., Stein, B., & Steiner, F. (2019). Efficient errorcorrecting codes in the short blocklength regime. Physical Communication, 34, 6679.
[2] Geiselhart, M., Elkelesh, A., Ebada, M., Cammerer, S., & ten Brink, S. (2021). Automorphism ensemble decoding of Reed–Muller codes. IEEE Transactions on Communications, 69(10), 64246438.
[3] Schnabl, G., & Bossert, M. (1995). Softdecision decoding of ReedMuller codes as generalized multiple concatenated codes. IEEE Transactions on Information Theory, 41(1), 304308.
[4] Markus Grassl. "Bounds on the minimum distance of linear codes and quantum codes." Online available at http://www.codetables.de.
[5] Fossorier, M. P., & Lin, S. (1995). Softdecision decoding of linear block codes based on ordered statistics. IEEE Transactions on Information Theory, 41(5), 13791396.
Prerequisites
Channel coding
Supervisor:
Coding with Feedback
Description
In paper
"Correcting a Single Error in Feedback Channels" the problem of correcting a single error with feedback was investigated. It was mainly devoted to binary channels, namely, binary symmetric and asymmetric channels. A general theorem, which allows constructing strategies with one feedback, was proved. For the symmetric channel with one error, it was proved that with two feedbacks one can transmit as many messages as with complete feedback. For the asymmetric channel, some strategies for small lengths have been proposed. Later some results for the binary symmetric channel have been generalized for the qary symmetric channel. (These results are not published yet, I can send the draft).
There are multiple ways, how this research can be continued:
 One can try to generalize the results from mentioned paper for the case of 2 errors or a constant number of errors.
 The methods developed in the paper "Correcting a Single Error in Feedback Channels" allow us to construct optimal codes for the asymmetric channel with complete feedback and compute their sizes. However, it requires a lot of time. It would be interesting to prove a general formula for the size of such optimal codes.
 Another direction is to consider nonsymmetric qary channels.
Supervisor:
Codebased Cryptography: digital signatures
codebased cryptography, digital signatures
Description
Due to the recent advances in quantum computers, the search for cryptosystems that survive quantum attacks is of great interest. Codebased cryptography is a promising candidate, since it is build on the NPhard problem of decoding a random code [1].
The McEliece cryptosystem is a promising candidate for asymmetric encryption.
However, many attempts at constructing a codebased signature scheme have resulted in impractical parameters or security problems.
NIST's announcement of a competetion dedicated to standardizing postquantum signatures has lead to the publication of several new codebased schemes
In this work we pick one of the proposals and analyse its (in)security [2,3,4].
If you are interested, please write an email, then we'll discuss the details.
References:
[1] Weger, V., Gassner, N., & Rosenthal, J. (2022). A Survey on CodeBased Cryptography. arXiv preprint arXiv:2201.07119.
[2] Cho, J., No, J. S., Lee, Y., Koo, Z., & Kim, Y. S. (2022). Enhanced pqsigRM: CodeBased Digital Signature Scheme with Short Signature and Fast Verification for PostQuantum Cryptography. Cryptology ePrint Archive.
[3] Baldi, M., Chiaraluce, F., & Santini, P. (2022). SPANSE: combining sparsity with density for efficient onetime codebased digital signatures. arXiv preprint arXiv:2205.12887.
[4] Barenghi, A., Biasse, J. F., Persichetti, E., & Santini, P. (2022). On the computational hardness of the code equivalence problem in cryptography. Cryptology ePrint Archive.
Prerequisites
Channel coding
Security in Communications and Storage
Supervisor:
Codebased Cryptography: Information Set Decoding
codebased cryptography, information set decoding
Description
Due to the recent advances in quantum computers, the search for cryptosystems that survive quantum attacks is of great interest. Codebased cryptography is a promising candidate, since it is build on the NPhard problem of decoding a random code [1].
In order to solve the generic decoding problem, algorithms from the information set decoding (ISD) family can be used.
During the last 60 years, small improvements to this approach were made.
Recently, new variants of the classical decoding problem were proposed [2,3,4].
This work adapts strategies for the classical problem to one of the new settings.
The goal is to develop decoding algorithms, analyse their complexity and do a (proof of concept) implementation.
There is also a webpage which provides instances that we can attempt to solve.
If you are interested, please write an email, then we'll discuss the details.
References:
[1] Weger, V., Gassner, N., & Rosenthal, J. (2022). A Survey on CodeBased Cryptography. arXiv preprint arXiv:2201.07119.
[2] Bricout, R., Chailloux, A., DebrisAlazard, T., & Lequesne, M. (2020). Ternary syndrome decoding with large weight. In Selected Areas in Cryptography–SAC 2019: 26th International Conference, Waterloo, ON, Canada, August 12–16, 2019, Revised Selected Papers 26 (pp. 437466). Springer International Publishing.
[3] Weger, V., Khathuria, K., Horlemann, A. L., Battaglioni, M., Santini, P., & Persichetti, E. (2020). On the hardness of the Lee syndrome decoding problem. arXiv preprint arXiv:2002.12785.
[4] Baldi, M., Battaglioni, M., Chiaraluce, F., HorlemannTrautmann, A. L., Persichetti, E., Santini, P., & Weger, V. (2020). A new path to codebased signatures via identification schemes with restricted errors. arXiv preprint arXiv:2008.06403.
Prerequisites
Channel coding
Security in Communications and Storage
Supervisor:
[identification] Idnetification and Secrecy with PhysicallyUnclonableFunctions (PUFs)
PUF secrecy identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
From previous work we have a fairly efficient implementation based ReedMuller code which can be found at
Secrecy in this identification codes has also been implemented in unpublished work. Furthermore, the theoretical work on Identification with PUF's has been done in
The goal of the project will be to bridge the three topics and create practical and efficient secret identification codes in the PUF setting.
The working language will be in English.
Environment: this is a project in collaboration with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
Capacity upper Bounds for ISI Channels with Direct Detection
Description
We are interested in computing upper bounds (on capacity) for frequencyselective channels with a memoryless nonlineary at the transmitter/receiver.
One application for these bounds are shortreach fiberoptic communication systems with a single photodiode at the receiver. The photodiode is a memoryless nonlinearity, as it produces an output that is proportional to the squared magnitude of the input signal.
A simple upper bound for the above model is given in [Sec. III D, 2].
D. Plabst et al., "Achievable Rates for ShortReach FiberOptic Channels With Direct Detection," in Journal of Lightwave Technology, vol. 40, no. 12, pp. 36023613, 15 June15, 2022, doi: 10.1109/JLT.2022.3149574.
Prerequisites
Information Theory
Linear System Theory
Supervisor:
Private and Secure Federated Learning
Description
In federated learning, a machine learning model shall be trained on private user data with the help of a central server, the socalled federator. This setting differs from other machine learning settings in that the user data shall not be shared with the federator for privacy reasons and/or to decrease the communication load of the system.
Even though only intermediate results are shared, extra care is necessary to guarantee data privacy. An additional challenge arises if the system includes malicious users that breach protocol and send corrupt computation results.
The goal of this work is to design, implement and analyze coding and informationtheoretic solutions for privacy and security in federated learning.
Prerequisites
 Coding Theory (e.g., Channel Coding)
 Information Theory
 Machine Learning Basics
Supervisor:
[identification] PseudoRandom Identification
random pseudo identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy tradeoffs between the error and the codes sizes.
The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
One advantage can be gained by using pseudo randomness to generate both the input and the code itself.
Your task will be implementing the identification codes described in the attached pdf (an english translation of a paper published in russian in a russian journal) aiming at the fastest implementation and smallest collisions, and testing their performance in comparison to other current implementations.
For reference, our previous work on identification based on ReedSolomon and ReedMuller code can be found at
The coding will be in Python/Sagemath.
The working language will be in English.
Environment: we collaborate with LTI from TUM and CeTI from TU Dresden, the latter having already some preliminary implementation of pseudorandom identification using various pseudorandom generators. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
[quantum] Quantum Machine Learning for Communication
physical, layer, quantum, machine learning, nonlinear
Description
As part of an ongoing project with Huawei we are looking into quantum machine learning algorithms applied to decoding at the end of an optical fiber in the nonlinear regime.
So far we have tried only the quantum version of kmean clustering, however the goal is to test further quantum algorithms, in particular quantum support vector machines next, and their classical quantuminspired counterpart.
The projects will involve reading the literature on quantum machine learning algorithms and quantuminspired algorithms, find or come up with an implementation (this will involve the use of quantum libraries, in particular so far we have use qiskit), and benchmark the performance.
Prerequisites
Knowledge of quantum mechanics or quantum information is highly recommended.
Supervisor:
Error Correcting Codes for Memories with (Partially) Defects
Linear Codes, Algebraic Codes, Error Correction , Masking Defects, Flash Memories, PhaseChange Memories
Description
For different applications, the demand for reliable memory solutions in particular for nonvolatile memories such as phasechange memories (PCMs) is rapidly increasing. PCM cells may become defective (also called stuck) either fully or partially if they fail in switching their states, and therefore these cells can only hold a single phase. In response to these defects, combined masking and errorcorrecting code constructions have been proposed, where masking is for hiding the defects while errorcorrecting is to compromise potential addedchannel errors. We want to investigate further code constructions such that less overall redundancy is required to handle these two types of errors. As an alternate, work for combined erasure errors and masking code constructions could be investigated.
Prerequisites
 Basic principle of Linear Algebra
 Channel Coding/Coding Theory
 Basic knowledge in Information Theory
Contact
M.Eng. Haider Al Kim
Doctoral Researcher
Technical University of Munich
Department of Electrical and Computer Engineering /
Coding and Cryptography (COD) Group
Email: haider.alkim@tum.de
Supervisor:
[identification] Implementation of identification with algebraicgeometry (Goppa) codes
goppa algebraic geometry codes identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy tradeoffs between the error and the codes sizes.
The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
Your task will be implementing identification with Goppa codes, aiming at the fastest implementation, and testing their performance in comparison to other current implementations. The reference articles for this implementation are:
For reference, our previous work on identification based on ReedSolomon and ReedMuller code can be found at
The coding will be in Python/Sagemath.
The working language will be in English.
Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
[identification] Implementation of identification with universal hash functions
universal hash identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy tradeoffs between the error and the codes sizes.
The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
Your task will be implementing the identification codes described in
aiming at the fastest implementation, and testing their performance in comparison to other current implementations.
For reference, our previous work on identification based on ReedSolomon and ReedMuller code can be found at
The coding will be in Python/Sagemath.
The working language will be in English.
Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
[identification] Applications of Identification Codes in V2X Communications
sumo, ns3, ns3, vehicular, communication, identification, c++, ReedMuller
Description
As part of the NewCom Project, new communication paradigms are investigated from an experimental perspective in order to construct proofofconcept implementations that demonstrate the theoretical results obtained for PostShannon Communication schemes. In particular, this MSc thesis focuses on Identification Codes and their integration into a simulation environment where vehicular networks are modelled.
For this, the master student will first conduct a review of the stateoftheart use cases for identification in the scientific literature and in form of patents, with an emphasis on V2X communications. By using an opensource V2X implementation based on LDR’s Simulation of Urban Mobility (SUMO) framework integrated with ns3’s implementation of the ITSG5 and LTE standards and conducting simulation in specific scenarios, the student will gain a first impression of the performance of the system using traditional transmission schemes. The integration of existing implementation of identification codes culminates this thesis, where KPIs will be defined in order to compare the advantages of using identification instead of transmission in the context of V2X communications.
Details about the C++ tools/libraries
The software used for the simulation of the vehicular network communication is ezCar2x
which build on and integrates the NS3 (network simulation) and SUMO (traffic simulation) libraries
For the identification part and identification code based on ReedMuller codes needs to be reimplemented (work in progress) from Python into C++ using the Givaro library
Prerequisites

Knowledge of communications engineering, mobile communications, wireless channel models, signal processing, and channel coding techniques (experience in LTE/5G cellular networks is a plus)

Interest in novel communication concepts as well in their practical implementation

Software experience: MATLAB, C++ and Python (experience with ns3 or SUMO is a plus)

Comfortable working with Linux operative systems and distributed version control tools (e.g., gitlab)

Goaloriented and structured work style
Contact
To apply, Please send your application by email to Roberto Ferrara (roberto.ferrara@tum.de) and Luis TorresFigueroa (luis.torres.figueroa@tum.de) with the following documents:

Curriculum vitae

Academic transcript

Short motivation (0.5 – 1 page)
Supervisor:
[security] Practical implementation of physicallayer semantic security
semantic, security, secrecy, programming, implementation
Description
The goal of this project is to implement in Python/Sagemath the security functions (at least one of four) described in https://arxiv.org/abs/2102.00983
Sagemath contains libraries for mosaics, BIBDs, etc, that can be used for the project.
Motivation:
There are various types of security definitions.
The mutual information based types, in increasing order of security requirement are
 Weak secresy asks that the average mutual information of the eavesdropper I(M:E)/n goes to 0 for a uniform message M (average here means averaged over the blocklength n, an additional average over M is implicit in the mutual information)
 Strong secrecy asks that the total mutual information I(M:E) goes to 0,
 Semantic security asks that the total mutual informaiton I(M:E) goes to 0 for any distribution of the message M (and thus in particular for all distributions that pick any of two chosen messages with 1/2 probabilty)
Then there are the almostequivalent respective indistiguishablity types of security requirements (below PQ_1 is the statistical distance and Exp_M is expectation value over M)
 average indistinguishability 1/n Exp_M  P_{EM}  P_E _1 for a uniform message M goes to 0 (again average refers over the blocklegth n, clearly there is also the average over M)
 total indistiguishability Exp_M  P_{EM}  P_E _1 for a uniform message M goes to 0
 indistinguishability P_{Em}  P_{Em'}_1 for any two messages m and m' goes to 0.
Each of the indistiguishabilities can also be written using KL digvergence instead of statistical distance, in which case the conditions are exactly equivalent to their mutual information versions.
Strong secrecy is the standard security requirement considered in informationtheoretic security, while semantic security is the minimum requirement considered in computational security.
Informationtheoretic (physicallayer) security differs from computational security in that the secrecy is guaranteed irrespective of the power of the adversary, while in computational security E is computationally bounded. Computational security also assumes that the message is at least of a certain length for the schemes to work, and thus if the message to be secured is too small it needs to be padded to a larger message.
In practice, information theoretic security is expensive, because the messages that can be secured can be only as long as the keys that can be generated. However, in identification only a very small part of the message needs to be secured, which in computational security triggers padding and thus waste, but on the other side makes informationtheoretic security accessible and not so expensive.
At the same time, the security of identification implicitly requires semantic security. It has been known for a while that hash functions provide informationtheoretic strong secrecy. However, because the standard for informationtheoretic security has been strong secrecy, before https://arxiv.org/abs/2102.00983 no efficient functions where known to provide informationtheoretic semantic security.
We need an implementation of these type of functions so that we can integrate informationtheoretic security into our identification project.
Supervisor:
[quantum] Realignment criterion and upper bounds in deviceindependent QKD
Description
This paper uses the partial transpose as a tool to derive upper bounds on deviceindependent QKD
https://arxiv.org/abs/2005.13511
In this project the goal is to try to generalize the above to the other tools like the reallignment criterion:
https://arxiv.org/abs/quantph/0205017
https://arxiv.org/abs/0802.2019
Prerequisites
basics of quantum information/quantum formalism
Supervisor:
[quantum] Semantic security of infinitedimensional classicalquantum channels
Description
Generalize semantic security of classicalquantum channels to infinite dimensional channel (not necessarily gaussian)
 [1] finite dimensional classicalquantum case
https://arxiv.org/abs/2001.05719  finite and infinite dimensional classical case
https://arxiv.org/abs/1811.07798  [this subpoint can be a project by itself] the finite dimesional case needs to be recast into smoothmax information (instead than Lemma 5.7 of [1]) as the classical case does, this paper proves properties of the smoothmaxinf in finite dimension that we would need for that
https://arxiv.org/abs/2001.05719  papers regarding the capacity for infinite dimensional channels
http://arxiv.org/abs/quantph/9912067v1
http://arxiv.org/abs/quantph/0408009v3
http://arxiv.org/abs/quantph/0408176v1
Prerequisites
quantum information theory
Supervisor:
[quantum] Asymptotic continuity of restricted quantum relative entropies under general channels
quantum, relative entropy, Pinsker, reverse, inequality, information thoery, asymptotic, continuity
Description
Asypmtotic continuity is a property in the form of inequalities (classically known also as inequalities of the reversePinker type) that is necessary to prove upper bounds on operational capacities.
The (quantum) relative entropy (also known as quantum divergence and classically also known as KullbacktLeibler divergence), can be used to define various entanglment measures many of which have a proven asymptotic continuity.
Of particular interest are the restricted quantum relative entropies defined by Marco Piani (https://arxiv.org/abs/0904.2705), many of which satisfy asymptotic continuity (A.S.)
 https://arxiv.org/abs/quantph/9910002
 https://arxiv.org/abs/quantph/0203107
 https://arxiv.org/abs/quantph/0507126
 https://arxiv.org/abs/1210.3181
 https://arxiv.org/abs/1507.07775
 https://arxiv.org/abs/1512.09047
In the above there are maybe 23 different proof styles.
We can group the results in the above as follows:
 A.S. for entropy, conditional entropies, mutual information, conditional mutual information
 A.S. for relative entropies with infimum over states on the second argument
 A.S. relative entropies with infimum over state *and maximization over measurement channels*
The goal of the project is to generalize the last case to asymptotic continuity for relative entropies with infimum over state and maximization over *general* channels.
 Partial results toward this goal can be found in the appendix of my PhD thesis: http://web.math.ku.dk/noter/filer/phd18rf.pdf
 Such a result would have immediate applications to this paper: https://arxiv.org/abs/1801.02861
Possible new proof directions are
 using Renyi αrealtive entropies with the limit α>1
 using Kim's operator inequality from
https://arxiv.org/abs/1210.5190
to get an operator inequality looking like a reverse strong subadditivity (see https://www.youtube.com/watch?v=P3xI1u1Y2s for a good overview and in particular at minute 31:20 for the reverse SSA)
Prerequisites
Knowledge of quantum information is highly recommended/required.
Knowledge of matrix analysis will be a strong advantage.
Contact
roberto.ferrara@tum.de
Supervisor:
[quantum] Practical protocols for quantum synchronization in classical network
quantum, network, synchronization
Description
relevant papers
https://arxiv.org/abs/1310.6043
https://arxiv.org/abs/1304.5944
https://arxiv.org/abs/1310.6045
https://arxiv.org/abs/1703.05876
https://arxiv.org/abs/1303.6357
background papers
https://ieeexplore.ieee.org/document/7509657
Prerequisites
Knowledge of quantum theory as provided by the course Algorithms in Quantum Theory or similar
Supervisor:
[quantum] Entanglementmeasures upper bounds on deviceindependent distillable key
quantum, qkd, entanglement
Description
The goal of this work is to try to upper bound the deviceindependent distillable key in terms of locally restricted relative entropy of entanglement (an entanglement measure).
The following are relevant works/articles
 works toward even *a definition* of device independent distillable key
https://arxiv.org/abs/2005.13511
https://arxiv.org/abs/2005.12325
https://arxiv.org/abs/1810.05627  works relating distillable entanglement and distillable key to locally restricted relative entropy measures
https://arxiv.org/abs/1609.04696
https://arxiv.org/abs/1402.5927  the first definition of restricted relative entropies
https://arxiv.org/abs/0904.2705  important properties of restricted relative entropies, and some overview of entanglement measures
https://arxiv.org/abs/1210.3181  my PhD thesis
http://web.math.ku.dk/noter/filer/phd18rf.pdf
Prerequisites
Strong background in quantum theory is required, preferably in quantum information theory, which is not covered by the course Algorithms in Quantum Theory
Supervisor:
Research Internships (Forschungspraxis)
Channel Coding: Efficient Decoding for GC Codes and General Codes
channel coding, efficient decoding, generalized concatenated codes
We develop efficient decoders for short block codes.
Description
Arising applications, such as machinetomaschine communication require errorcorrection codes with short information length.The design of such codes and efficient decoders is an open problem [1].
Recently, ReedMuller codes have gained a lot of interest, because of thier good errorcorrection capability and their structure, which allows for lowcomplexity decoders, see, e.g., [2].
It has been known for quite some time that ReedMuller codes belong to a more general class of codes: the Generalized Concatenated (GC) Codes [3].
This class allows for more flexible code design, e.g., with respect to the information rate of the code.
Hence, by transfering and refining results for ReedMuller codes to GC codes, one could improve over existing solutions.
Another approach to obtain good results in the shortlength regime is using the bestknown codes [4].
Since these codes do usually not have a structure that enables efficient decoding, one has to perform decoding of a general linear code. The most efficient approaches are variants of Ordered Statistics Decoding (OSD) [5]. The idea for improving over stateoftheart varaints is to encorporate recent improvements from another field of research: Information Set Decoding.
If you are interested in either of the directions (or have some other direction in mind), please write an email, then we'll discuss the details.
References:
[1] Co?kun, M. C., Durisi, G., Jerkovits, T., Liva, G., Ryan, W., Stein, B., & Steiner, F. (2019). Efficient errorcorrecting codes in the short blocklength regime. Physical Communication, 34, 6679.
[2] Geiselhart, M., Elkelesh, A., Ebada, M., Cammerer, S., & ten Brink, S. (2021). Automorphism ensemble decoding of Reed–Muller codes. IEEE Transactions on Communications, 69(10), 64246438.
[3] Schnabl, G., & Bossert, M. (1995). Softdecision decoding of ReedMuller codes as generalized multiple concatenated codes. IEEE Transactions on Information Theory, 41(1), 304308.
[4] Markus Grassl. "Bounds on the minimum distance of linear codes and quantum codes." Online available at http://www.codetables.de.
[5] Fossorier, M. P., & Lin, S. (1995). Softdecision decoding of linear block codes based on ordered statistics. IEEE Transactions on Information Theory, 41(5), 13791396.
Prerequisites
Channel coding
Supervisor:
Coding with Feedback
Description
In paper
"Correcting a Single Error in Feedback Channels" the problem of correcting a single error with feedback was investigated. It was mainly devoted to binary channels, namely, binary symmetric and asymmetric channels. A general theorem, which allows constructing strategies with one feedback, was proved. For the symmetric channel with one error, it was proved that with two feedbacks one can transmit as many messages as with complete feedback. For the asymmetric channel, some strategies for small lengths have been proposed. Later some results for the binary symmetric channel have been generalized for the qary symmetric channel. (These results are not published yet, I can send the draft).
There are multiple ways, how this research can be continued:
 One can try to generalize the results from mentioned paper for the case of 2 errors or a constant number of errors.
 The methods developed in the paper "Correcting a Single Error in Feedback Channels" allow us to construct optimal codes for the asymmetric channel with complete feedback and compute their sizes. However, it requires a lot of time. It would be interesting to prove a general formula for the size of such optimal codes.
 Another direction is to consider nonsymmetric qary channels.
Supervisor:
Codebased Cryptography: digital signatures
codebased cryptography, digital signatures
Description
Due to the recent advances in quantum computers, the search for cryptosystems that survive quantum attacks is of great interest. Codebased cryptography is a promising candidate, since it is build on the NPhard problem of decoding a random code [1].
The McEliece cryptosystem is a promising candidate for asymmetric encryption.
However, many attempts at constructing a codebased signature scheme have resulted in impractical parameters or security problems.
NIST's announcement of a competetion dedicated to standardizing postquantum signatures has lead to the publication of several new codebased schemes
In this work we pick one of the proposals and analyse its (in)security [2,3,4].
If you are interested, please write an email, then we'll discuss the details.
References:
[1] Weger, V., Gassner, N., & Rosenthal, J. (2022). A Survey on CodeBased Cryptography. arXiv preprint arXiv:2201.07119.
[2] Cho, J., No, J. S., Lee, Y., Koo, Z., & Kim, Y. S. (2022). Enhanced pqsigRM: CodeBased Digital Signature Scheme with Short Signature and Fast Verification for PostQuantum Cryptography. Cryptology ePrint Archive.
[3] Baldi, M., Chiaraluce, F., & Santini, P. (2022). SPANSE: combining sparsity with density for efficient onetime codebased digital signatures. arXiv preprint arXiv:2205.12887.
[4] Barenghi, A., Biasse, J. F., Persichetti, E., & Santini, P. (2022). On the computational hardness of the code equivalence problem in cryptography. Cryptology ePrint Archive.
Prerequisites
Channel coding
Security in Communications and Storage
Supervisor:
Codebased Cryptography: Information Set Decoding
codebased cryptography, information set decoding
Description
Due to the recent advances in quantum computers, the search for cryptosystems that survive quantum attacks is of great interest. Codebased cryptography is a promising candidate, since it is build on the NPhard problem of decoding a random code [1].
In order to solve the generic decoding problem, algorithms from the information set decoding (ISD) family can be used.
During the last 60 years, small improvements to this approach were made.
Recently, new variants of the classical decoding problem were proposed [2,3,4].
This work adapts strategies for the classical problem to one of the new settings.
The goal is to develop decoding algorithms, analyse their complexity and do a (proof of concept) implementation.
There is also a webpage which provides instances that we can attempt to solve.
If you are interested, please write an email, then we'll discuss the details.
References:
[1] Weger, V., Gassner, N., & Rosenthal, J. (2022). A Survey on CodeBased Cryptography. arXiv preprint arXiv:2201.07119.
[2] Bricout, R., Chailloux, A., DebrisAlazard, T., & Lequesne, M. (2020). Ternary syndrome decoding with large weight. In Selected Areas in Cryptography–SAC 2019: 26th International Conference, Waterloo, ON, Canada, August 12–16, 2019, Revised Selected Papers 26 (pp. 437466). Springer International Publishing.
[3] Weger, V., Khathuria, K., Horlemann, A. L., Battaglioni, M., Santini, P., & Persichetti, E. (2020). On the hardness of the Lee syndrome decoding problem. arXiv preprint arXiv:2002.12785.
[4] Baldi, M., Battaglioni, M., Chiaraluce, F., HorlemannTrautmann, A. L., Persichetti, E., Santini, P., & Weger, V. (2020). A new path to codebased signatures via identification schemes with restricted errors. arXiv preprint arXiv:2008.06403.
Prerequisites
Channel coding
Security in Communications and Storage
Supervisor:
Distributed Noise Generation for Secure OvertheAir Computation with Applications in Federated Learning
OvertheAir (OtA) computation is a promising approach with the potential to drastically reduce the communication overhead of wireless distributed dataprocessing systems (e.g. Federated Learning). Since this method, however, is prone to eavesdropping, artificial noise can be employed to secure the communication. An open problem however, is the distributed design of artifical noise among different users.
Description
Novel use cases for mobile communication networks include the aggregation of large amounts of data, which is stored in a distributed manner across network users. For instance, Federated Learning requires the aggregation of machine learning model updates from contributing users.
OvertheAir (OtA) computation is an approach with the potential to drastically reduce the communication overhead of wireless distributed dataprocessing systems (e.g. Federated Learning). It exploits the multipleaccess property and linearity of the wireless channel to compute sums of preprocessed data by the channel. This important property at the same time opens great opportunities for eavesdroppers to learn about the transmitted signal. If the legitimate receiver shall have exclusive access to the computation result, it is crucial to employ additional security measures.
Artificial noise can be employed to secure the communication. This noise is either generated by dedicated users jamming the communication [3], or by jointly designing the noise contribution of each user, [1][2]. The latter approach makes it possible to minimize the distortion at the legitimate receiver, but requires a centrally coordinated noise design. Therefore, an open problem is how to allow for the distributed design of artifical noise.
[1] Maßny, Luis, and Antonia WachterZeh. "Secure OvertheAir Computation using ZeroForced Artificial Noise." arXiv preprint arXiv:2212.04288 (2022).
[2] Liao, Jialing, Zheng Chen, and Erik G. Larsson. "OvertheAir Federated Learning with Privacy Protection via Correlated Additive Perturbations." arXiv preprint arXiv:2210.02235 (2022).
[3] Yan, Na, et al. "Toward Secure and Private OvertheAir Federated Learning." arXiv preprint arXiv:2210.07669 (2022).
Prerequisites
 basic knowledge in statistics and estimation theory
 basic knowledge about linear wireless channels
Supervisor:
[identification] Idnetification and Secrecy with PhysicallyUnclonableFunctions (PUFs)
PUF secrecy identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
From previous work we have a fairly efficient implementation based ReedMuller code which can be found at
Secrecy in this identification codes has also been implemented in unpublished work. Furthermore, the theoretical work on Identification with PUF's has been done in
The goal of the project will be to bridge the three topics and create practical and efficient secret identification codes in the PUF setting.
The working language will be in English.
Environment: this is a project in collaboration with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
Capacity upper Bounds for ISI Channels with Direct Detection
Description
We are interested in computing upper bounds (on capacity) for frequencyselective channels with a memoryless nonlineary at the transmitter/receiver.
One application for these bounds are shortreach fiberoptic communication systems with a single photodiode at the receiver. The photodiode is a memoryless nonlinearity, as it produces an output that is proportional to the squared magnitude of the input signal.
A simple upper bound for the above model is given in [Sec. III D, 2].
D. Plabst et al., "Achievable Rates for ShortReach FiberOptic Channels With Direct Detection," in Journal of Lightwave Technology, vol. 40, no. 12, pp. 36023613, 15 June15, 2022, doi: 10.1109/JLT.2022.3149574.
Prerequisites
Information Theory
Linear System Theory
Supervisor:
Statistical Decoding
codebased cryptography, decoding attack
Description
Due to the recent advances in quantum computers, the search for cryptosystems that survive quantum attacks is of great interest. Codebased cryptography is a promising candidate, since it is build on the NPhard problem of decoding a random code [1].
In order to solve the generic decoding problem, algorithms from the information set decoding (ISD) family can be used.
During the last 60 years, small improvements to this approach were made. During this time, other algorithms, such as statistical decoding [2], were proposed, but failed to achieve the performance of ISD [3].
Recently, a variant of statistical decoding was proposed that claims to perfom better than the best ISD variants for low code rates [4].
If you are interested, please write an email, then we'll discuss the details.
Main Paper:
Carrier, K., DebrisAlazard, T., MeyerHilfiger, C., & Tillich, J. P. (2022). Statistical Decoding 2.0: Reducing Decoding to LPN. arXiv preprint arXiv:2208.02201.
References:
[1] Weger, V., Gassner, N., & Rosenthal, J. (2022). A Survey on CodeBased Cryptography. arXiv preprint arXiv:2201.07119.
[2] Jabri, A. A. (2001, December). A statistical decoding algorithm for general linear block codes. In IMA International Conference on Cryptography and Coding (pp. 18). Springer, Berlin, Heidelberg.
[3] DebrisAlazard, T., & Tillich, J. P. (2017, June). Statistical decoding. In 2017 IEEE International Symposium on Information Theory (ISIT).
[4] Carrier, K., DebrisAlazard, T., MeyerHilfiger, C., & Tillich, J. P. (2022). Statistical Decoding 2.0: Reducing Decoding to LPN. arXiv preprint arXiv:2208.02201.
Prerequisites
Channel coding
Security in Communications and Storage
Probability theory and statistics
Supervisor:
MABBased Efficient Distributed ML on the Cloud
Distributed Machine Learning (ML), MultiArmed Bandits (MABs), Cloud Simulations (AWS, GCP, ...)
Description
We consider the problem of running a distributed machine learning algorithm on the cloud. This imposes several challenges. In particular, cloud instances may have different performances/speeds. To fully leverage the performance of the instances, we want to characterize their speed and potentially use the fastest ones. To explore the speed of the instances while exploiting them (assigning computational tasks), we use the theory of multiarmed bandits (MABs).
The goal of the research intership is to start by implementing existing theoretical algorithms [1] and possibly adapting them based on the experimental observations.
[1] M. Egger, R. Bitar, A. WachterZeh and D. Gündüz, Efficient Distributed Machine Learning via Combinatorial MultiArmed Bandits, submitted to IEEE Journal on Selected Areas in Communications (JSAC), 2022.
Prerequisites
 Information Theory
 Machine Learning Basics
 Python (Intermediate Level)
Supervisor:
Private and Secure Federated Learning
Description
In federated learning, a machine learning model shall be trained on private user data with the help of a central server, the socalled federator. This setting differs from other machine learning settings in that the user data shall not be shared with the federator for privacy reasons and/or to decrease the communication load of the system.
Even though only intermediate results are shared, extra care is necessary to guarantee data privacy. An additional challenge arises if the system includes malicious users that breach protocol and send corrupt computation results.
The goal of this work is to design, implement and analyze coding and informationtheoretic solutions for privacy and security in federated learning.
Prerequisites
 Coding Theory (e.g., Channel Coding)
 Information Theory
 Machine Learning Basics
Supervisor:
[identification] PseudoRandom Identification
random pseudo identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy tradeoffs between the error and the codes sizes.
The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
One advantage can be gained by using pseudo randomness to generate both the input and the code itself.
Your task will be implementing the identification codes described in the attached pdf (an english translation of a paper published in russian in a russian journal) aiming at the fastest implementation and smallest collisions, and testing their performance in comparison to other current implementations.
For reference, our previous work on identification based on ReedSolomon and ReedMuller code can be found at
The coding will be in Python/Sagemath.
The working language will be in English.
Environment: we collaborate with LTI from TUM and CeTI from TU Dresden, the latter having already some preliminary implementation of pseudorandom identification using various pseudorandom generators. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
Dimension of sLifted ReedSolomon Codes
Description
In the work [1], we developed a method to analyze the dimension of quadraticcurvelifted ReedSolomon codes and its asymptotic behavior. The method gives tighter bound on the dimension compared to the estimation given in [2], which defines a more general class of lifted ReedSolomon codes with regard to curves of higher degree.
In this work, the student is expected to extended the method in [1] to the general class of codes in [2] to analyse the dimension and its asymptotic behavior.
Supervisor:
[quantum] Quantum Machine Learning for Communication
physical, layer, quantum, machine learning, nonlinear
Description
As part of an ongoing project with Huawei we are looking into quantum machine learning algorithms applied to decoding at the end of an optical fiber in the nonlinear regime.
So far we have tried only the quantum version of kmean clustering, however the goal is to test further quantum algorithms, in particular quantum support vector machines next, and their classical quantuminspired counterpart.
The projects will involve reading the literature on quantum machine learning algorithms and quantuminspired algorithms, find or come up with an implementation (this will involve the use of quantum libraries, in particular so far we have use qiskit), and benchmark the performance.
Prerequisites
Knowledge of quantum mechanics or quantum information is highly recommended.
Supervisor:
[identification] Implementation of identification with algebraicgeometry (Goppa) codes
goppa algebraic geometry codes identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy tradeoffs between the error and the codes sizes.
The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
Your task will be implementing identification with Goppa codes, aiming at the fastest implementation, and testing their performance in comparison to other current implementations. The reference articles for this implementation are:
For reference, our previous work on identification based on ReedSolomon and ReedMuller code can be found at
The coding will be in Python/Sagemath.
The working language will be in English.
Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
[identification] Implementation of identification with universal hash functions
universal hash identification
Description
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy tradeoffs between the error and the codes sizes.
The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.
Identification codes can be achieved by first removing the errors from the channel with regular transmission channel coding, and then sending a challenge though the corrected channel. For every identity i, The channenge is generated by picking a random input m and computing the corresponding output T_i(m) using a function T_i that depends on the identity. The challenge is then the pair m,T_i(m) and the receiver wanting to verify an identity j will verify whether j=i by testing the challenge. This is done by recomputing the output with T_j and verifying whether T_j(m)= T_i(m). The errors are reduced by ensuring that the various functions collide on a small fraction of the possible inputs.
It turns out that choosing good sets of funtions {T_i} is the same as choosing errorcorrection codes {c_i} with large distance, where now each codeword c_i defines a function by mapping positions m (sometimes called code locators) to symbols c_im of the codeword.
We can thus construct identification codes by choosing errorcorrection codes where we are only interested in the performance of the error correction encoders (we are not interested in the errorcorrection decoder or errorcorrection codes).
Your task will be implementing the identification codes described in
aiming at the fastest implementation, and testing their performance in comparison to other current implementations.
For reference, our previous work on identification based on ReedSolomon and ReedMuller code can be found at
The coding will be in Python/Sagemath.
The working language will be in English.
Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Supervisor:
[quantum] Realignment criterion and upper bounds in deviceindependent QKD
Description
This paper uses the partial transpose as a tool to derive upper bounds on deviceindependent QKD
https://arxiv.org/abs/2005.13511
In this project the goal is to try to generalize the above to the other tools like the reallignment criterion:
https://arxiv.org/abs/quantph/0205017
https://arxiv.org/abs/0802.2019
Prerequisites
basics of quantum information/quantum formalism
Supervisor:
On the Equivalence of Identification and Authentication
Identification via channel, identification codes, authentication, authentication codes
A Certain equivalence of identification and authentication would be shown.
Description
It would be shown that under suitable formulations (preserving all salient features) the two problem of Identification (Ahlswede and Dueck, 1989) and Authentication (Simmons, G. J. 1984) are in essence very close to each other. This equivalency was conjectured first by M. S. Pinsker. In this research internship the student is expected to address this conjecture. Both problems must be studied separately and then the similar essence of them should be drawn out. In particular the identification codes and authentication codes along with theire relation will be investigated.
Prerequisites
 Background in Information Theory and Channel Coding
 Familiarity with fundamentals of Identification Theory
References:
 Simmons, G. J. 1984, “Message authentication: a game on hypergraphs,” Congressus Numer. 45:161192.
 Simmons, G. J. 1982, “A game theory model of digital message authentication,” Congressus Numer., 34, 413424
 Simmons, G. J. 1985, “Authentication theory/coding theory,” in: Advances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, vol. 196, SpringerVerlag, Berlin, pp. 411432.
 E. Gilbert, F. J. MacWilliams and N.J. A. Sloane, 1974, “Codes which detect deception,” Bell System Tech. J., 53, 405424.
 R. Ahlswede and G. Dueck, “Identification via channels,” in IEEE Trans. on Inf. Theory, vol. 35, no. 1, pp. 1529, Jan. 1989, doi: 10.1109/18.42172.
 L. A. Bassalygo, M. V. Burnashev, “Authentication, Identification, and Pairwise Separated Measures”, Problems Inform. Transmission, 32:1 (1996), 33–39
Supervisor:
Internships
Coding with Feedback
Description
In paper
"Correcting a Single Error in Feedback Channels" the problem of correcting a single error with feedback was investigated. It was mainly devoted to binary channels, namely, binary symmetric and asymmetric channels. A general theorem, which allows constructing strategies with one feedback, was proved. For the symmetric channel with one error, it was proved that with two feedbacks one can transmit as many messages as with complete feedback. For the asymmetric channel, some strategies for small lengths have been proposed. Later some results for the binary symmetric channel have been generalized for the qary symmetric channel. (These results are not published yet, I can send the draft).
There are multiple ways, how this research can be continued:
 One can try to generalize the results from mentioned paper for the case of 2 errors or a constant number of errors.
 The methods developed in the paper "Correcting a Single Error in Feedback Channels" allow us to construct optimal codes for the asymmetric channel with complete feedback and compute their sizes. However, it requires a lot of time. It would be interesting to prove a general formula for the size of such optimal codes.
 Another direction is to consider nonsymmetric qary channels.