Theses in Progress

Modellierung eines digitalen Kommunikationssystems.

This thesis explores the concept of DNA as a medium for molecular computation, focusing on the design and implementation of fundamental computational circuits using DNA strands. By leveraging reactions of DNA molecules, such as strand displacement and transcription, the research demonstrates how logic gates, arithmetic operations, and basic control mechanisms can be encoded and executed at the molecular level. The work highlights the potential of DNA computing for genetic circuits, parallel processing and other applications.

We investigate SCL-decoded polar codes for dirty-paper coding scenarios.

DNA Data Storage

Data storage on DNA molecules is a promising approach for archiving massive data.

In classical DNA storage systems, binary information is encoded into sequences consisting of the four DNA bases {A, C, G, T}. The encoded sequences are used to generate DNA molecules called strands using the biochemical process of DNA synthesis. The synthesized strands are stored together in a tube. To retrieve the binary information, the strand must be read via DNA sequencing and decoded back into the binary representation.

The synthesis and the sequencing procedures are error-prone, and with the natural degradation of DNA they introduce errors to the DNA strands. To ensure data reliability, the errors have to be corrected by algorithms and error-correcting codes (ECCs).

A 5min video with an overview of DNA storage: https://youtu.be/r8qWc9X4f6k?si=Yzm5sOW-a6VDnBu3

Composite DNA

Recently, to allow higher potential information capacity, [1,2] introduced the DNA composite synthesis method. In this method, the multiple copies created by the standard DNA synthesis method are utilized to create composite DNA symbols, defined by a mixture of DNA bases and their ratios in a specific position of the strands. By defining different mixtures and ratios, the alphabet can be extended to have more than 4 symbols. More formally, a composite DNA symbol in a specific position can be abstracted as a quartet of probabilities {p_A, p_C, p_G, p_T}, in which p_X, 0 ≤ p_X ≤ 1, is the fraction of the base X in {A, C, G, T} in the mixture and p_A+p_C+ p_G+ p_T =1. Thus, to identify composite symbols it is required to sequence multiple reads and then to estimate p_A, p_C, p_G, p_T in each position.

Problem description

ECCs for DNA data storage differ in many aspects from classical error correction codes. In this model, new error type gain relevance, like deletions and insertions which affect the synchronization of the sequences. 

Another important error model, especially for long-term storage, is dealing with breaks in the DNA sequence. The problem of identifying fragments caused by a single break is addressed using marker sequences, which help determine if a resulting DNA fragment is a prefix or suffix of the original sequence. Marker sequences are inserted at the beginning and end of DNA strands to locate breaks and reconstruct the original sequence. To prevent marker sequences from appearing within the data, Run-Length Limited (RLL) coding is used, which limits consecutive identical symbols and ensures marker sequences do not occur in the data part. The goal is to reconstruct the original random composite matrix from individual fragments after a single break, restoring the stored information by identifying the position of each fragment and capturing base frequencies to restore the original distribution for each column of the DNA sequence.

References

[1] L. Anavy, I. Vaknin, O. Atar, R. Amit, and Z. Yakhini, “Data storage in DNA with fewer synthesis cycles using composite DNA letters,” Nat Biotechnol, vol. 37, no. 10, pp. 1229–1236, Oct. 2019, doi: 10.1038/s41587-019-0240-x.

[2] Y. Choi et al., “High information capacity DNA-based data storage with augmented encoding characters using degenerate bases,” Sci Rep, vol. 9, no. 1, Art. no. 1, Apr. 2019, doi: 10.1038/s41598-019-43105-w.

[3] I. Shomorony and A. Vahid, “Torn-Paper Coding,” IEEE Transactions on Information Theory, vol. 67, no. 12, pp. 7904–7913, Dec. 2021, doi: 10.1109/TIT.2021.3120920.

[4] D. Bar-Lev, E. Yaakobi, Y. Yehezkeally, and S. Marcovich, “Adversarial Torn-paper Codes,” IEEE Trans. Inform. Theory, pp. 1–1, 2023, doi: 10.1109/TIT.2023.3292895.

[5] W. Zhang, Z. Chen, and Z. Wang, “Limited-Magnitude Error Correction for Probability Vectors in DNA Storage,” in ICC 2022 - IEEE International Conference on Communications, Seoul, Korea, Republic of: IEEE, May 2022, pp. 3460–3465. doi: 10.1109/ICC45855.2022.9838471.

In this thesis, the student will study and summarize the most recent code-based digital signature schemes based on the syndrome decoding problem

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.

• https://ieeexplore.ieee.org/document/42172
• https://ieeexplore.ieee.org/document/42173

The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy trade-offs 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 error-correction 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 error-correction codes where we are only interested in the performance of the error correction encoders (we are not interested in the error-correction decoder or error-correction codes).

Your task will be implementing the identification codes described in

• https://ieeexplore.ieee.org/abstract/document/782144

aiming at the fastest implementation, and testing their performance in comparison to other current implementations.

For reference, our previous work on identification based on Reed-Solomon and Reed-Muller code can be found at

• https://arxiv.org/abs/2107.07649
• https://arxiv.org/abs/2107.06801
• https://arxiv.org/abs/2007.06372

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.

Federated learning is a machine learning paradigm where decentralized entities (clients) collaboratively learn using their private data. A central server acts as a coordinator of the learning process. Due to the sensitivity of the private data involved,  the data cannot be transferred. A salient problem of federated learning is the presence of malicious clients, which are clients that try to destroy the learning process. Malicious clients can do this by corrupting their data and/or by modifying their local model updates. The goal of this project is to understand how model poisoning attacks and defense strategies perform under different scenarios of federated learning using experiments. 

References: 

[1]- https://www.ndss-symposium.org/wp-content/uploads/ndss2021_6C-3_24498_paper.pdf

[2]- https://arxiv.org/pdf/1903.03936.pdf

[3]- https://arxiv.org/pdf/2304.00160.pdf

Prerequisites

DiVincenzo in 2000, provides a comprehensive framework for identifying the necessary requirements to achieve successful quantum computation. In this project, we search for ideal conditions necessary for buidling distributed quantum devices. 

In this thesis, the student will study the mathematics of linear codes and how they can be used to design cryptosystems. 

-

-

Develop an iterative detection and decoding scheme for XPM compensation in nonlinear WDM fiber-optic links.

Laser linewidth measurement is crucial for characterizing the spectral properties of lasers, particularly in applications requiring high precision. It involves determining the range of frequencies over which the laser emits coherent light. The student will perform experimental techniques to measure the linewidth. Understanding laser linewidth is essential for optimizing laser performance in communication, sensing, and metrology applications.

(External Master Thesis) With the emergence of quantum computing, cryptographic protocols like IPsec/IKEv2 must transition to post-quantum cryptographic (PQC) algorithms. This thesis focuses on integrating PQC into IPsec/IKEv2 for embedded systems, leveraging FPGA-based acceleration to optimize performance and resource usage.
Thesis includes evaluation of suitable PQC algorithms to create a hardware/software codesign concept, implementing critical cryptographic operations in FPGA hardware, and integrating them into an embedded software stack. The goal is to achieve a balanced co-design where FPGA handles computationally expensive tasks while maintaining flexibility in software.

Due to the recent advances in quantum computers, searching for cryptosystems that survive quantum attacks is of great interest. Lattice- and code-based hardness assumptions are promising candidates, both of which are built on the hardness of solving noisy linear equations [3].

The close relationship between codes and lattices has contributed to advances in both research areas: state-of-the-art solvers employ similar techniques (see, e.g. [4]), and constructions often follow analogous approaches (see, e.g. [5]).
However, not all lattice (or code) concepts currently have couterparts in the other domain.

In this thesis, the concepts of Learning with Rounding (LWR) [1] and Learning with Quantization (LWQ) [2] are applied to codes.
The LWR and LWQ problems are variants of the Learning with Errors (LWE) problem on lattices, where the small error ensuring the hardness of the problem, is replaced by a deterministic rounding or quantization procedure. Due to the similarity of the lattice-based LWE problem and the code-based Syndrome Decoding (SD) problem, it should be investigated, if the reductions from LWE to LWR and LWQ can be transferred to the SD problem, introducing the concept of Syndrome Decoding with Rounding for codes, and how this can be used in code-based cryptography.

Main Papers:

[1] Alwen, J., Krenn, S., Pietrzak, K., & Wichs, D. (2013, August). Learning with rounding, revisited: New reduction, properties and applications. In Annual Cryptology Conference (pp. 57-74). Berlin, Heidelberg: Springer Berlin Heidelberg.

[2] Lyu, S., Liu, L., & Ling, C. (2024). Learning with Quantization, Polar Quantizer, and Secure Source Coding. Cryptology ePrint Archive.

References:

[3] Weger, V., Gassner, N., & Rosenthal, J. (2022). A Survey on Code-Based Cryptography. arXiv preprint arXiv:2201.07119.

[4] Debris-Alazard, T., Ducas, L., & van Woerden, W. P. (2022). An algorithmic reduction theory for binary codes: Lll and more. IEEE Transactions on Information Theory, 68(5), 3426-3444.

[5] Melchor, C. A., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J. C., ... & Bourges, I. C. (2018). Hamming quasi-cyclic (HQC). NIST PQC Round, 2(4), 13.

This thesis aims to provide a novel approach for all-digital clock synchronization aimed at free-space optical communication systems by combining Lee algorithm, a feed-forward timing error detector, with a Kalman filter followed by an interpolator. The approach combines information from the channel conditions under which the timing error measurement was made with the estimate based on physical model and previous measurements. 

Federated learning is a machine learning paradigm that aims to learn collaboratively from decentralized private data owned by entities referred to as clients. However, due to its decentralized nature, federated learning is susceptible to poisoning attacks, where malicious clients try to corrupt the learning process by modifying their data or local model updates. Moreover, the updates sent by the clients might leak information about the private data involved in the learning. This thesis aims to investigate and combine existing robust aggregation techniques in FL with differential privacy techniques.

References:

[1] - https://arxiv.org/pdf/2304.09762.pdf

[2] - https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9757841

[3] - https://dl.acm.org/doi/abs/10.1145/3465084.3467919

Prerequisites

DNA Data Storage

Data storage on DNA molecules is a promising approach for archiving massive data.

In classical DNA storage systems, binary information is encoded into sequences consisting of the four DNA bases {A, C, G, T}. The encoded sequences are used to generate DNA molecules called strands using the biochemical process of DNA synthesis. The synthesized strands are stored together in a tube. To retrieve the binary information, the strand must be read via DNA sequencing and decoded back into the binary representation.

The synthesis and the sequencing procedures are error-prone, and with the natural degradation of DNA they introduce errors to the DNA strands. To ensure data reliability, the errors have to be corrected by algorithms and error-correcting codes (ECCs).

A 5min video with an overview of DNA storage: https://youtu.be/r8qWc9X4f6k?si=Yzm5sOW-a6VDnBu3

Composite DNA

Recently, to allow higher potential information capacity, [1,2] introduced the DNA composite synthesis method. In this method, the multiple copies created by the standard DNA synthesis method are utilized to create composite DNA symbols, defined by a mixture of DNA bases and their ratios in a specific position of the strands. By defining different mixtures and ratios, the alphabet can be extended to have more than 4 symbols. More formally, a composite DNA symbol in a specific position can be abstracted as a quartet of probabilities {p_A, p_C, p_G, p_T}, in which p_X, 0 ≤ p_X ≤ 1, is the fraction of the base X in {A, C, G, T} in the mixture and p_A+p_C+ p_G+ p_T =1. Thus, to identify composite symbols it is required to sequence multiple reads and then to estimate p_A, p_C, p_G, p_T in each position.

Problem description

ECCs for DNA data storage differ in many aspects from classical error correction codes. In this model, new error type gain relevance, like deletions and insertions which affect the synchronization of the sequences. Especially for composite DNA data storage, these error types received only little attention.

The most related work to this problem was recently studied by Zhang et al. in [6]. The authors initiated the study of error-correcting codes for DNA composite. They considered an error model for composite symbols, which assumes that errors occur in at most t symbols, and their magnitude is limited by l. They presented several code constructions as well as bounds for this model. In this thesis, we want to analyse a different way to model the composite synthesis method and studies additional error models. We already have some results for substitution and single deletion errors. This thesis should focus on evaluating more error models in the channel model. 

This should only roughly introduce the problem. No need to review all references. If you are interested, please reach out to me, and we can discuss a suitable direction for you.

References

[1] L. Anavy, I. Vaknin, O. Atar, R. Amit, and Z. Yakhini, “Data storage in DNA with fewer synthesis cycles using composite DNA letters,” Nat Biotechnol, vol. 37, no. 10, pp. 1229–1236, Oct. 2019, doi: 10.1038/s41587-019-0240-x.

[2] Y. Choi et al., “High information capacity DNA-based data storage with augmented encoding characters using degenerate bases,” Sci Rep, vol. 9, no. 1, Art. no. 1, Apr. 2019, doi: 10.1038/s41598-019-43105-w.

[3] 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.

[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] I. Smagloy, L. Welter, A. Wachter-Zeh, and E. Yaakobi, “Single-Deletion Single-Substitution Correcting Codes,” IEEE Transactions on Information Theory, pp. 1–1, 2023, doi: 10.1109/TIT.2023.3319088.

[6] W. Zhang, Z. Chen, and Z. Wang, “Limited-Magnitude Error Correction for Probability Vectors in DNA Storage,” in ICC 2022 - IEEE International Conference on Communications, Seoul, Korea, Republic of: IEEE, May 2022, pp. 3460–3465. doi: 10.1109/ICC45855.2022.9838471.

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

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

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

Resources:

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

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

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

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

Prerequisites

.

We investigate code construction algorithms for SC list decoding of polar codes [1] based on methods like [2].

• [1] https://doi.org/10.1109/TIT.2015.2410251
• [2] https://doi.org/10.1109/TCOMM.2021.3120274

This work shall deal with post-quantum secure schemes utilizing the Lee metric. The student's task is to get familiar with this metric and to design a signature scheme. The student shall show that known attacks in the Hamming metric are not applicable for the Lee metric.

Prerequisites

In theory, the check nodes operations of belief propagation rely on tanh() and arctanh() functions which require high computational power. Hence, in most of the practical applications, an approximation called “MinSum” is used. This method aims to exploit the structure of tanh() function where the absolute value of output sufficiently converges to 1 with increasing absolute value of input. Hence, in a series multiplication of absolute outputs, the most dominant effect comes from the minimum element and other contributions are considered negligible. However, neglection of other attenuation factors cause overcalculated outputs in “MinSum” algorithm which can accumulated by multiple iterations. This drawback can be compensated through adding attenuation or/and offset factors. These factors are mostly iteration specific and intuitively determined, which means one factor which is determined by educated guess is applied to all leaving edges. However, every edge in an unfolded Tanner graph has its own unique identity corresponding to the previous nodes and edges that the message is transmitted.

In addition to approach aiming to close the performance gap between main algorithm and “MinSum ” approximation, we can intend to improve the qualities of main algorithm. Even though belief propagation decoding in LDPC codes is considered as highly successful, it is still a “suboptimal” method compared to very expensive but accurate Maximum A posteriori Probability (MAP) estimation. It means there might be some room for improvement in performance. Additionally, belief propagation requires multiple iterations to converge and the required number of iterations can dramatically increase by decreasing signal-to-noise ratio (SNR). Additional correction weights imposed on iterated messages can be a candidate to improve performance in overall.

5G specification for channel coding is using protograph based LDPC codes. Every node duplicated from same base matrix node is keen to show similar properties, it may be possible to use same weights for these nodes by preserving the good decoding results. This detail can help us to using additional correction weights by minimum additional memory burden.

In this project the student should calculate the zero-error capacity for 

a multi-user model with feedback.

Prerequisites

-

A homomorphic encryption (HE) scheme enables performing operations on plaintexts in their encrypted form. Depending on its construction and constraints, an HE scheme can allow a limited or an unlimited number of operations, i.e. additions and/or multiplications.

The goal of this project is to investigate the scheme from [1] and to analyze its strengths and weaknesses to be able to adapt it for efficient implementations of specific operations such as dot product, vector-matrix multiplication and  linear combinations of vectors. Depending on the findings, the scheme can be applied for other operations as well.

References:

[1] C. Aguilar-Melchor, V. Dyseryn, and P. Gaborit, “Somewhat Homomorphic Encryption based on Random Codes,” 2023. Publication info: Preprint.

Non-volatile memories (NVMs) are electronic data-storage technologies that do not require a continuous power supply to retain data; unlike traditional magnetic or optical media, they do not utilize mechanically movable components and can therefore offer better performance, and allow for three-dimensional scaling of storage devices. Under most realistic workloads, they also offer better energy efficiency.

However, these technologies also feature imbalances in behavior, performance and consequences, between the processes of reading data and writing it. To wit, in memory cells which represent data by the level of held charge (traditionally allowing for representation of several logical levels), the process of charge-injection is a simple and efficient, whereas charge-depletion is both technically complex (requiring the depletion of entire blocks of cells) and destructive, a main driver of cell-degradation over the device's life cycle.

Different coding theoretic approaches have been explored to alleviate this imbalance, including coding schemes that delay charge-depletion cycles [1], [2]. This project will build on the work done in [2], by calculating the asymptotic behavior of the number of realizable permutation sequences, when those are restricted to belong to a single Kendall-tau error-detecting code. Possible extensions will be general error-correction capabilities, as well as general window-lengths.

[1] A. Jiang, R. Mateescu, M. Schwartz and J. Bruck, "Rank Modulation for Flash Memories," in IEEE Transactions on Information Theory, vol. 55, no. 6, pp. 2659-2673, June 2009, doi: 10.1109/TIT.2009.2018336.

[2] M. Horovitz and T. Etzion, "Local Rank Modulation for Flash Memories," in IEEE Transactions on Information Theory, vol. 65, no. 3, pp. 1705-1713, March 2019, doi: 10.1109/TIT.2018.2859403.

Design of the hardware-software interface of a real-time intradyne FSOC transceiver to evaluate different signal processing architectures to enable logging and visualization of high-speed data streams from the FPGA as well as configuration and calibration of the signal processing algorithms.

Forschungspraxis

.

.

.

.

the students should translate functions from Matlab and C to julia. the functions involve calculation of infomation theoretic quantities to basic function of a discrete time transmission chain.

The students task is to learn julia and matlab to a extend that the translation from one to the other language is possible. We furthermore expect the student to learn how to use git and gitlab for managing larger projects.

Prerequisites

.