Angebotene Arbeiten

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

- Knowledge about machine learning and gradient descent optimization

- Proficiency in Python and PyTorch

- Undergraduate statistics courses

- Prior knowledge about differential privacy is a plus

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 federated learning, a machine learning model shall be trained on private user data with the help of a central server, the so-called 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 information-theoretic solutions for privacy and security in federated learning.

• Information Theory
• Coding Theory (e.g., Channel Coding)
• Machine Learning (Theory and Practice)

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]--[3], and such that seek to mitigate the effects of defective memory cells once those appear in a device [4], [5].

Theses are available in extending either approach, as well as combining them.

[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 E. Yaakobi, "On the Capacity of Write-Once Memories," in IEEE Transactions on Information Theory, vol. 63, no. 8, pp. 5124-5137, Aug. 2017, doi: 10.1109/TIT.2017.2689034.

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

[4] V. Sidorenko, G. Schmidt, E. Gabidulin, M. Bossert and V. Afanassiev, "On polyalphabetic block codes," IEEE Information Theory Workshop, 2005., Rotorua, New Zealand, 2005, pp. 4 pp.-, doi: 10.1109/ITW.2005.1531889.

[5] Y. Yehezkeally, H. A. Kim, S. Puchinger and A. Wachter-Zeh, "Bounds on Mixed Codes with Finite Alphabets," 2023 IEEE Information Theory Workshop (ITW), Saint-Malo, France, 2023, pp. 389-394, doi: 10.1109/ITW55543.2023.10161655.

Contemporary global demand for storage capacity is increasing exponentially, even as traditional magnetic storage media has exhausted its potential for optimization, and requires unsustainable investments for both production and maintenance, in capital, energy and space.

One promising potential medium for archival data storage is DNA; it features high density, extreme longevity, convenient scalability and a lower maintenance footprint. Complete DNA-based storage ecosystems are in active development, raising multiple coding theoretic (as well as engineering, algorithmic, and biotechnological) challenges; correspondingly, increasing attention is recently given to the study of such systems, and they are drawing significant investments from both governments
and the private sector.

The following theses are available (other topics in this domain will also be entertained):

• The torn paper channel models the effects of DNA strand breakage in storage or processing. It has been studied from both an average-case and a worst-case [1] perspective, with several distinct adversarial models. Recently, the t-break model was studied [2] as a refinement of the previously studied min-max constraint. These developments open the way to study new problems in this setting.
• Reconstruction from substring spectra is a model motivated by the process of shot-gun sequencing, where short strands are drawn sufficiently many times to reconstruct a long information sequence. Adapting existing literature [3,4] to more realistic models is an open problem.
• Nanopore sequencing is a nascent technology that reads single-stranded DNA molecules by passing them through a narrow pore while passing electric current through it. More work studying its properties and designing codes capable of handling its relatively high error rate, extending existing literature [5,6], is necessary.
• Duplications are a type of mutation occurring in the process of cell replication, which may be responsible for large portions of our current genome. For data storage schemes in in vivo DNA (e.g., for watermarking research material) it is an error model that needs to be countered. We aim to extend and build upon existing literature [7,8].

[1] D. Bar-Lev, S. Marcovich, E. Yaakobi and Y. Yehezkeally, "Adversarial Torn-Paper Codes," in IEEE Transactions on Information Theory, vol. 69, no. 10, pp. 6414-6427, Oct. 2023, doi: 10.1109/TIT.2023.3292895.

[2] C. Wang, J. Sima and N. Raviv, "Break-Resilient Codes for Forensic 3D Fingerprinting," arXiv preprint arXiv:2310.03897v1 [cs.IT], Oct. 2023, doi: https://doi.org/10.48550/arXiv.2310.03897.

[3] Y. Yehezkeally, D. Bar-Lev, S. Marcovich and E. Yaakobi, "Generalized Unique Reconstruction From Substrings," in IEEE Transactions on Information Theory, vol. 69, no. 9, pp. 5648-5659, Sept. 2023, doi: 10.1109/TIT.2023.3269124.

[4] H. Wei, M. Schwartz, G. Ge, "Reconstruction from Noisy Substrings," arXiv preprint arXiv:2312.04790v1 [cs.IT], Dec. 2023, doi: 10.48550/arXiv.2312.04790.

[5] A. Banerjee, Y. Yehezkeally, A. Wachter-Zeh and E. Yaakobi, "Error-Correcting Codes for Nanopore Sequencing," in IEEE Transactions on Information Theory, doi: 10.1109/TIT.2024.3380615.

[6] A. Banerjee, Y. Yehezkeally, A. Wachter-Zeh and E. Yaakobi, "Correcting a Single Deletion in Reads from a Nanopore Sequencer," arXiv preprint arXiv:2401.15939v2 [cs.IT], May. 2024, doi: 10.48550/arXiv.2401.15939.

[7] S. Jain, F. Farnoud Hassanzadeh, M. Schwartz and J. Bruck, "Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms," in IEEE Transactions on Information Theory, vol. 63, no. 8, pp. 4996-5010, Aug. 2017, doi: 10.1109/TIT.2017.2688361.

[8] D. Goshkoder, N. Polyanskii and I. Vorobyev, "Codes Correcting Long Duplication Errors," in IEEE Transactions on Molecular, Biological, and Multi-Scale Communications, doi: 10.1109/TMBMC.2024.3403755.

Homomorphic encryption (HE) schemes are increasingly attracting attention in the era of large scale computing. While lattice-based approaches have been well-studied, recently first progress has been made towards establishing code-based alternatives. Preliminary results show that such alterative approaches might enable undiscovered functionalities not present in current lattice-based schemes. In this project, we particularily study novel code-based Partial/Somewhat HE schemes tailored to applications in artificial intelligence and federated learning.

After familiarizing with SotA methods in relevant fields (such as [1]), the student should analyze the requirements for use-cases at hand and explore suitable modifications to current schemes and novel approaches.

[1] Aguilar-Melchor, Carlos, Victor Dyseryn, and Philippe Gaborit, "Somewhat Homomorphic Encryption based on Random Codes," Cryptology ePrint Archive (2023).

- Strong foundation in linear algebra
- Channel Coding
- Security in Communications and Storage
- Basic understanding of Machine Learning concepts

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 federated learning, a machine learning model shall be trained on private user data with the help of a central server, the so-called 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 information-theoretic solutions for privacy and security in federated learning.

• Information Theory
• Coding Theory (e.g., Channel Coding)
• Machine Learning (Theory and Practice)

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]--[3], and such that seek to mitigate the effects of defective memory cells once those appear in a device [4], [5].

Theses are available in extending either approach, as well as combining them.

[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 E. Yaakobi, "On the Capacity of Write-Once Memories," in IEEE Transactions on Information Theory, vol. 63, no. 8, pp. 5124-5137, Aug. 2017, doi: 10.1109/TIT.2017.2689034.

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

[4] V. Sidorenko, G. Schmidt, E. Gabidulin, M. Bossert and V. Afanassiev, "On polyalphabetic block codes," IEEE Information Theory Workshop, 2005., Rotorua, New Zealand, 2005, pp. 4 pp.-, doi: 10.1109/ITW.2005.1531889.

[5] Y. Yehezkeally, H. A. Kim, S. Puchinger and A. Wachter-Zeh, "Bounds on Mixed Codes with Finite Alphabets," 2023 IEEE Information Theory Workshop (ITW), Saint-Malo, France, 2023, pp. 389-394, doi: 10.1109/ITW55543.2023.10161655.

Contemporary global demand for storage capacity is increasing exponentially, even as traditional magnetic storage media has exhausted its potential for optimization, and requires unsustainable investments for both production and maintenance, in capital, energy and space.

One promising potential medium for archival data storage is DNA; it features high density, extreme longevity, convenient scalability and a lower maintenance footprint. Complete DNA-based storage ecosystems are in active development, raising multiple coding theoretic (as well as engineering, algorithmic, and biotechnological) challenges; correspondingly, increasing attention is recently given to the study of such systems, and they are drawing significant investments from both governments
and the private sector.

The following theses are available (other topics in this domain will also be entertained):

• The torn paper channel models the effects of DNA strand breakage in storage or processing. It has been studied from both an average-case and a worst-case [1] perspective, with several distinct adversarial models. Recently, the t-break model was studied [2] as a refinement of the previously studied min-max constraint. These developments open the way to study new problems in this setting.
• Reconstruction from substring spectra is a model motivated by the process of shot-gun sequencing, where short strands are drawn sufficiently many times to reconstruct a long information sequence. Adapting existing literature [3,4] to more realistic models is an open problem.
• Nanopore sequencing is a nascent technology that reads single-stranded DNA molecules by passing them through a narrow pore while passing electric current through it. More work studying its properties and designing codes capable of handling its relatively high error rate, extending existing literature [5,6], is necessary.
• Duplications are a type of mutation occurring in the process of cell replication, which may be responsible for large portions of our current genome. For data storage schemes in in vivo DNA (e.g., for watermarking research material) it is an error model that needs to be countered. We aim to extend and build upon existing literature [7,8].

[1] D. Bar-Lev, S. Marcovich, E. Yaakobi and Y. Yehezkeally, "Adversarial Torn-Paper Codes," in IEEE Transactions on Information Theory, vol. 69, no. 10, pp. 6414-6427, Oct. 2023, doi: 10.1109/TIT.2023.3292895.

[2] C. Wang, J. Sima and N. Raviv, "Break-Resilient Codes for Forensic 3D Fingerprinting," arXiv preprint arXiv:2310.03897v1 [cs.IT], Oct. 2023, doi: https://doi.org/10.48550/arXiv.2310.03897.

[3] Y. Yehezkeally, D. Bar-Lev, S. Marcovich and E. Yaakobi, "Generalized Unique Reconstruction From Substrings," in IEEE Transactions on Information Theory, vol. 69, no. 9, pp. 5648-5659, Sept. 2023, doi: 10.1109/TIT.2023.3269124.

[4] H. Wei, M. Schwartz, G. Ge, "Reconstruction from Noisy Substrings," arXiv preprint arXiv:2312.04790v1 [cs.IT], Dec. 2023, doi: 10.48550/arXiv.2312.04790.

[5] A. Banerjee, Y. Yehezkeally, A. Wachter-Zeh and E. Yaakobi, "Error-Correcting Codes for Nanopore Sequencing," in IEEE Transactions on Information Theory, doi: 10.1109/TIT.2024.3380615.

[6] A. Banerjee, Y. Yehezkeally, A. Wachter-Zeh and E. Yaakobi, "Correcting a Single Deletion in Reads from a Nanopore Sequencer," arXiv preprint arXiv:2401.15939v2 [cs.IT], May. 2024, doi: 10.48550/arXiv.2401.15939.

[7] S. Jain, F. Farnoud Hassanzadeh, M. Schwartz and J. Bruck, "Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms," in IEEE Transactions on Information Theory, vol. 63, no. 8, pp. 4996-5010, Aug. 2017, doi: 10.1109/TIT.2017.2688361.

[8] D. Goshkoder, N. Polyanskii and I. Vorobyev, "Codes Correcting Long Duplication Errors," in IEEE Transactions on Molecular, Biological, and Multi-Scale Communications, doi: 10.1109/TMBMC.2024.3403755.

Homomorphic encryption (HE) schemes are increasingly attracting attention in the era of large scale computing. While lattice-based approaches have been well-studied, recently first progress has been made towards establishing code-based alternatives. Preliminary results show that such alterative approaches might enable undiscovered functionalities not present in current lattice-based schemes. In this project, we particularily study novel code-based Partial/Somewhat HE schemes tailored to applications in artificial intelligence and federated learning.

After familiarizing with SotA methods in relevant fields (such as [1]), the student should analyze the requirements for use-cases at hand and explore suitable modifications to current schemes and novel approaches.

[1] Aguilar-Melchor, Carlos, Victor Dyseryn, and Philippe Gaborit, "Somewhat Homomorphic Encryption based on Random Codes," Cryptology ePrint Archive (2023).

- Strong foundation in linear algebra
- Channel Coding
- Security in Communications and Storage
- Basic understanding of Machine Learning concepts