ERC Project Description: Coding for Security and DNA Storage

inCREASE Grant agreement ID: 801434 (Funded under: H2020-EU.1.1)

Communication and data storage systems are indispensable parts of our every-day life. However, these systems deal with severe challenges in security and reliability. Security is important whenever a user communicates or stores sensitive data, e.g., medical information; reliability has to be guaranteed to be able to transmit or store information while noise occurs. Algebraic codes (ACs) are a powerful means to achieve both.

Within inCREASE, I will construct and evaluate special codes for security applications and DNA storage.
The tasks are structured into three work packages: (1) post-quantum secure code-based cryptosystems, (2) secure key regeneration based on ACs, (3) ACs for DNA-based storage systems. The focus of inCREASE
lies on innovative theoretical concepts.

The goal of work package (1) is to investigate and design code-based cryptosystems; one promising idea is to apply insertion/deletion correcting codes. The security of these systems will be analysed from two points of view: structural attacks on the algorithms and hardware implementations with side-channel attacks.

Secure cryptographic key regeneration is the goal of (2) and can be achieved by physical unclonable functions (PUFs). Here, ACs are necessary to reproduce the key reliably. This project will study the error patterns that occur in PUFs, model them theoretically, and design suitable coding schemes.

The investigation on (3) will start with a study of the data of existing DNA storage systems. The outcome will be an error model that will include insertions, deletions, substitutions, and duplications. Therefore, inCREASE will design ACs for these error types. This will be especially challenging regarding the mathematical concepts. These codes will be evaluated by simulations and using data sets of DNA storage systems.

This project is high risk/high gain with impact not only to storage and security, but to the methodology as well as other areas such as communications.

Project Team

• Antonia Wachter-Zeh (PI)

• Sven Puchinger (Senior researcher)
• Vladimir Sidorenko (Senior researcher)
• Yonatan Yehezkeally (Senior researcher)

• Anisha Banerjee (PhD student)
• Andreas Lenz (PhD student)
• Julian Renner (PhD student)
• Lorenz Welter (PhD student)

 

Selected Publications

Work Package 1: Code-based Cryptography

• A.-L. Horlemann, S. Puchinger, J. Renner, T. Schamberger, and A. Wachter-Zeh, “Information-Set Decoding with Hints,” in CBCrypto, Jul. 2021.
• J. Renner, S. Puchinger, and A. Wachter-Zeh, “LIGA: A Cryptosystem Based on the Hardness of Rank-Metric List and Interleaved Decoding,” Designs, Codes, and Cryptography, 2021.
• T. Jerkovits, V. Sidorenko, and A. Wachter-Zeh, “Decoding of Space-Symmetric Rank Errors,” in IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2021, Melbourne, Australia.
• S. Puchinger, J. Renner, A. Wachter-Zeh, and J. Zumbrägel, “Efficient Decoding of Gabidulin Codes over Galois Rings,” in IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2021, Melbourne, Australia.
• J. Renner, S. Puchinger, and A. Wachter-Zeh, “Decoding High-Order Interleaved Rank-Metric Codes,” in IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2021, Melbourne, Australia.
• G. Maringer, S. Puchinger, and A. Wachter-Zeh, “Higher Rates and Information-Theoretic Analysis for the RLWE Channel,” in IEEE Information Theory Workshop, 2020.
• J. Lavauzelle, and J. Renner, "Cryptanalysis of a system based on twisted Reed–Solomon codes," Designs, Codes, and Cryptography, 2020.
• T. Schamberger, J. Renner, A. Wachter-Zeh, and G. Sigl, “A Power Side-Channel Attack on the CCA2-Secure HQC KEM,” CARDIS 2020, Nov. 2020.
• J. Kunz, J. Renner, G. Maringer, T. Schamberger, and A. Wachter-Zeh, “On Software Implementations of Gabidulin Decoders,” International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), Oct. 2020.
• J. Renner, S. Puchinger, A. Wachter-Zeh, C. Hollanti, and R. Freij-Hollanti, “Low-Rank Parity-Check Codes over the Ring of Integers Modulo a Prime Power,” IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2020, Los Angeles, CA, USA.
• S. Puchinger, J. Renner, and J. Rosenkilde, "Generic Decoding in the Sum-Rank Metric," IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2020, Los Angeles, CA, USA.
• J. Renner, T. Jerkovits, H. Bartz, S. Puchinger, P. Loidreau, and A. Wachter-Zeh, “Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius,” in International Conference on Post-Quantum Cryptography (PQCrypto), 2020, Paris, France.
• J. Renner, S. Puchinger, and A. Wachter-Zeh, “Interleaving Loidreau’s Rank-Metric Cryptosystem,” in International Symposium on Problems of Redundancy in Information and Control Systems 2019, Oct. 2019, Moscow, Russia.

Work Package 2: Physical Unclonable Functions

• L. Holzbaur, H. Liu, A. Neri, S. Puchinger, J. Rosenkilde, V. Sidorenko, and A. Wachter-Zeh, “Success Probability of Decoding Interleaved Alternant Codes,” in IEEE Information Theory Workshop, 2020.
• O. Günlü, P. Trifonov, M. Kim, R. F. Schaefer, and V. Sidorenko, "Randomized Nested Polar Subcode Constructions for Privacy, Secrecy, and Storage," in IEEE International Symposium on Information Theory and Applications, October 2020.
• T. Jerkovits, O. Günlü, V. Sidorenko, and G. Kramer, "Nested Tailbiting Convolutional Codes for Secrecy, Privacy, and Storage," in ACM Workshop on Information Hiding and Multimedia Security, Denver, CO, USA, June 2020.
• V. Immler, M. Hiller, L. Qinzhi, A. Lenz, and A. Wachter-Zeh, “Variable-Length Bit Mapping and Error- Correcting Codes for Higher-Order Alphabet PUFs,” Journal of Hardware and Systems Security, 2019.

Work Package 3: Coding for DNA Storage

• A. Lenz, R. Bitar, A. Wachter-Zeh, and E. Yaakobi, “Function-Correcting Codes,” in IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2021, Melbourne, Australia.
• L. Welter, R. Bitar, A. Wachter-Zeh, and E. Yaakobi, “Multiple Criss-Cross Deletion-Correcting Codes,” in IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2021, Melbourne, Australia.
• A. Lenz, Y. Liu, C. Rashtchian, P. Siegel, A. Tan, A. Wachter-Zeh, and E. Yaakobi, “Codes for Cost-Efficient DNA Synthesis,” in Non-Volantile Memories Workshop (NVMW), Feb. 2021, San Diego, USA.
• A. Lenz, I. Maarouf, L. Welter, A. Wachter-Zeh, E. Rosnes, and A. Graell i Amat, “Concatenated Codes for Recovery From Multiple Reads of DNA Sequences (Invited Paper),” in IEEE Information Theory Workshop, 2020.
• L. Welter, R. Bitar, A. Wachter-Zeh, and E. Yaakobi, “Multiple Criss-Cross Deletion-Correcting Codes,” (submitted to) IEEE Trans. Inform. Theory, 2021.
• A. Lenz, R. Bitar, A. Wachter-Zeh, and E. Yaakobi, “Function-Correcting Codes,” (submitted to) IEEE Trans. Inform. Theory, 2021.
• T. Shinkar, E. Yaakobi, A. Lenz, and A. Wachter-Zeh, “Clustering-Correcting Codes,” (in revision for) IEEE Trans. Inform. Theory, 2021.
• R. Bitar, L. Welter, I. Smagloy, A. Wachter-Zeh, and E. Yaakobi, “Criss-Cross Insertion and Deletion Correcting Codes,” (accepted for) IEEE Trans. Inform. Theory, 2021.
• A. Lenz, C. Rashtchian, P. Siegel, E. Yaakobi, "Covering Codes using Insertions or Deletions," IEEE Trans. Inform. Theory, 2020.
• A. Lenz, P. Siegel, A. Wachter-Zeh, and E. Yaakobi, “Coding over Sets for DNA Storage,” IEEE Trans. Inform. Theory, vol. 66, no. 4, pp. 2331–2351, Apr. 2020.
• R. Bitar, I. Smagloy, L. Welter, A. Wachter-Zeh, and E. Yaakobi, “Criss-Cross Deletion Correcting Codes,” IEEE International Symposium on Information Theory and its Applications (ISITA), Oct. 2020, Hawaii, USA.
• I. Smagloy, L. Welter, A. Wachter-Zeh, and E. Yaakobi, “Single-Deletion Single-Substitution Correcting Codes,” IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2020, Los Angeles, CA, USA.
• A. Lenz, Y. Liu, C. Rashtchian, P. Siegel, A. Wachter-Zeh, and E. Yaakobi, “Coding for Efficient DNA Synthesis,” IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2020, Los Angeles, CA, USA.
• A. Lenz, and N. Polyanskii, N, "Optimal Codes Correcting a Burst of Deletions of Variable Length," IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2020, Los Angeles, CA, USA.
• A. Lenz, P. Siegel, A. Wachter-Zeh, and E. Yaakobi, “Achieving the Capacity of the DNA Storage Channel (Invited Paper),” in International Conference on Acoustics, Speech, and Signal Processing (ICASSP), May 2020, Barcelona, Spain.
• A. Lenz, P. Siegel, A. Wachter-Zeh, and E. Yaakobi, “An Upper Bound on the Capacity of the DNA Storage Channel,” in IEEE Information Theory Workshop (ITW), Aug. 2019, Visby, Sweden.
• T. Shinkar, E. Yaakobi, A. Lenz, and A. Wachter-Zeh, “Clustering-Correcting Codes,” in IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2019, Paris, France.
• A. Lenz, P. Siegel, A. Wachter-Zeh, and E. Yaakobi, “Anchor-Based Correction of Substitutions in Indexed Sets,” in IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2019, Paris, France.