Dagstuhl Seminar 18511
Algebraic Coding Theory for Networks, Storage, and Security
( Dec 16 – Dec 21, 2018 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/18511
Organizers
- Martin Bossert (Universität Ulm, DE)
- Eimear Byrne (University College Dublin, IE)
- Antonia Wachter-Zeh (TU München, DE)
Contact
- Michael Gerke (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Schedule
The main aim of coding theory is to ensure reliable data transmission and data storage. Data is encoded, introducing redundancy, which is required for resilience to errors, malicious interference and packet loss. In addition, code-based cryptography can ensure privacy of the data and provide a means for authentication of the users.
The purpose of this Dagstuhl Seminar is bringing together young and experienced researchers with backgrounds in coding theory, network coding, storage coding and code-based security. The discussions will address similarities and differences between the various methods for the three applications (network coding, storage coding, security).
A major paradigm shift in coding theory occurred with the advent of network coding. The seminal work of Ahlswede et al in 2000 has shown that in order to reach network capacity, the transmitted data packets must be algebraically combined at intermediate nodes of the network. The unpredictability and/or complex topology of networks means that traditional coding methods must be drastically revised to be effective. Rank-metric codes have proved to offer many solutions in the network coding domain, both for error propagation control and wire-tap protection. Coded caching techniques, exploiting low congestion periods of data traffic and local storage hubs point to vast potential in content delivery services for large files such as multi-media.
In Today’s era of cloud and distributed storage, a central problem is how to efficiently maintain reliable storage of data. In multi-disk systems, if a disk fails, data must be recoverable from the remaining stored data, to provide reliability. On one hand it is empirically clear that disk failure is the norm rather than an exception, so that redundancy is a current storage requirement; on the other hand, the sheer scale of data involved means that redundancy must be added as efficiently as possible. To minimize the overhead required to ensure a certain reliability, it is proposed that data should be stored redundantly by employing coding.
An important aspect of user access in distributed storage is private information retrieval so that users who are remotely accessing files can do so without storage servers knowing what they have accessed. Attempts to efficiently solve this problem come from coding theory and combinatorics.
Privacy and security are a major challenge in our modern connected world. Schemes that address the confidentiality of messages as well as the integrity of the data are required. Public-key cryptography is the foundation of multi-party communication as well as for key exchange of symmetric cryptosystems. With the threat of a capable quantum computer, post-quantum secure systems have recently turned into the research focus, especially for devices that are hard to update and have very long-life cycles. As soon as a quantum computer will become available, traditional public-key cryptosystems such as RSA will become insecure. Code-based cryptography provides post-quantum secure public-key systems.
Creative Commons BY 3.0 DE
Martin Bossert, Eimear Byrne, and Antonia Wachter-Zeh
Algebraic Coding Theory for Networks, Storage, and Security was the fourth in a series of seminars exploring applications of coding theory in modern communications theory (see also Dagstuhl Seminars 16321 (2016), 13351 (2013) and 11461 (2011)). The seminar brought together 50 mathematicians, engineers and computer scientists with expertise in coding theory, network coding, storage coding, cryptography and code-based security to participate in dissemination and collaboration within the seminar themes.
The main focus of this workshop was to explore novel results in coding theory for application in data storage management, cryptography and privacy. The impact of novel coding techniques across these domains was discussed and explored. Particular emphasis was placed on new applications of coding theory in public key cryptography, coding techniques for privacy in distributed storage and on practical schemes using coding theory for content delivery. These novel coding applications continue to have a significant impact on changing focus and broadening of coding theory fundamentals.
Overview talks were given by Philippe Gaborit (Recent Results for Cryptography Based on Rank Metric), Emina Soljanin, (Service Rates of Codes), Eitan Yaakobi, (Private Proximity Retrieval), Sacha Kurz, (Multisets of Subspaces and Divisible Codes), Heide Gluesing-Luerssen (On Ferrers Diagram Codes) and Salim El Rouayheb (GASP Codes for Secure Distributed Matrix Multiplication). In addition, several short talks were given by other participants based on current research interests with a view to stimulating collaboration. Presentations on system cybersecurity, private information retrieval, locally recoverable codes, adversarial channels and various aspects of rank metric codes were given. The remaining seminar time was allocated to discussion groups, including those in code-based cryptography, private computation, service rates of codes, algebraic geometry codes and adversarial channels. Aside from the working group discussions, particpants took the opportunity to engage in specific collaborations with co-authors.
We summarize some of the content of the working group discussions below. It has been well documented that redundancy is a basic requirement for stability of distributed data storage systems. Algebraic codes have been identified as having applications in providing efficiency in this domain far exceeding replication. Coding theory methods allow information retrieval minimizing disc access, storage size, local recoverability, data repair and data retrieval. Consequently, the area of storage coding has seen an exponential growth. An important aspect of user access in distributed storage is privacy of information retrieval so that users who are remotely accessing files can do so without storage servers knowing what they have accessed. Attempts to efficiently solve this problem come from coding theory.
An important application of secret sharing schemes is distributed storage of private data, where each party is a storage node and all parties wish to store a secret securely and reliably. Secret sharing is a fundamental cryptographic primitive and is used as a building block in numerous secure protocols. In our discussions we focussed on secret sharing schemes for the threshold access structure and on secret sharing with errors/attacks in a broader context. Fuzzy vaults and secret sharing over networks were discussed. A motivation for this area is for example biometric authentication in the presence of adversaries.
Another aspect of distributed storage is the service rate of codes. Emerging applications, such as distributed learning and fog computing, add yet another use for coding. In these applications, the goal is to maximize the number of users that can be simultaneously served by the system. One such service is simultaneous download of different jointly coded data blocks by many users competing for the system's resources. Here, coding affects the rates at which users can be served. The achievable service rate region is the set of request rates for each file that can be supported by the system. A variety of approaches to open problems about service rate were discussed. In particular, we addressed the question of code constructions that serve all requests for fixed rate constraints on file and the problem of how to determine the achievable service rate region for certain families of codes.
Privacy and security present formidable challenges in our modern connected world. Public-key cryptography is the foundation of multi-party communication as well as for key exchange of symmetric cryptosystems. With the increasing likelihood of a capable quantum computer, post-quantum secure systems have recently turned into the research focus, especially for devices that are hard to update and have very long life cycles. Code-based cryptography provides post-quantum secure public-key systems.
The working group on code-based-cryptography discussed the importance of security reduction arguments and went through several examples of these in relation to coding theory in cryptography. This discussion was a great benefit to the participants, many of whom have expertise in coding theory and keen to broaden their understanding of cryptography. The group also focussed on McEliece-like systems based on quasi-cyclic moderate density parity-check (QC-MDPC) codes and on low-rank parity-check (LRPC) codes. Distinguisher attacks were discussed, as well as possible modifications to the broken Gabidulin based cryptosystem.
Reliable communication across a channel in the presence of an adversary is a very general channel model that arises in many applications. Coding strategies for data transmission and authentication across the arbitrarily varying channel (where an adversary may alter the channel statistics) and for covert communication were discussed. A framework for linear systems under attack, such as the scenario where a restricted number of sensor measurements is vulnerable to adversarial attacks, was introduced and coding theoretic arguments used for attack detection and correction strategies.
There were about 20 PhD and postdoctoral researchers in attendance, who reported a very positive experience and satisfaction at being give the opportunity to explore new collaborations with more senior researchers and to get exposure to new problems in coding theory. All participants welcomed the time made available to them to take part in discussion groups and in more focussed collaborations. All were very pleased with the quality of the facilities and administrative support offered by staff at Schloss Dagstuhl, which made for a very productive meeting. Andreas Lenz and Rawad Bitar organised an afternoon excursion to Trier for the group. Giuseppe Cotardo collected and compiled data for the final published report.
Martin Bossert, Eimear Byrne, and Antonia Wachter-Zeh
- Gianira Nicoletta Alfarano (Universität Zürich, CH)
- Iryna Andriyanova (University of Cergy-Pontoise, FR) [dblp]
- Daniel Augot (INRIA Saclay - Île-de-France, FR) [dblp]
- R. B. (Rutgers University - Piscataway, US) [dblp]
- Allison Beemer (Arizona State University - Tempe, US) [dblp]
- Jessalyn Bolkema (SUNY - Oswego, US) [dblp]
- Martin Bossert (Universität Ulm, DE) [dblp]
- Eimear Byrne (University College Dublin, IE) [dblp]
- Giuseppe Cotardo (University College Dublin, IE)
- Marwa Dammak (University of Cergy-Pontoise, FR) [dblp]
- Salim El Rouayheb (Rutgers University - Piscataway, US) [dblp]
- Tuvi Etzion (Technion - Haifa, IL) [dblp]
- Alexey Frolov (Skoltech - Moscow, RU) [dblp]
- Philippe Gaborit (University of Limoges, FR) [dblp]
- Heide Gluesing-Luerssen (University of Kentucky, US) [dblp]
- Oliver Wilhelm Gnilke (Aalborg University, DK) [dblp]
- Marcus Greferath (Aalto University, FI) [dblp]
- Daniel Heinlein (Aalto University, FI) [dblp]
- Lukas Holzbaur (TU München, DE) [dblp]
- Anna-Lena Horlemann-Trautmann (Universität St. Gallen, CH) [dblp]
- Sidharth Jaggi (The Chinese University of Hong Kong, HK) [dblp]
- Jörg Kliewer (NJIT - Newark, US) [dblp]
- Stanislav Kruglik (Skoltech - Moscow, RU) [dblp]
- Margreta Kuijper (The University of Melbourne, AU) [dblp]
- Sascha Kurz (Universität Bayreuth, DE) [dblp]
- Julien Lavauzelle (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Hunter Lehmann (University of Kentucky, US)
- Andreas Lenz (TU München, DE) [dblp]
- Julia Lieb (University of Aveiro, PT) [dblp]
- Pierre Loidreau (University of Rennes, FR) [dblp]
- Felice Manganiello (Clemson University, US) [dblp]
- Carolyn Mayer (Worcester Polytechnic Institute, US) [dblp]
- Sihem Mesnager (University of Paris VIII, FR) [dblp]
- Alessandro Neri (Universität Zürich, CH) [dblp]
- Cornelia Ott (Universität Ulm, DE) [dblp]
- Mario Osvin Pavcevic (University of Zagreb, HR) [dblp]
- Sven Puchinger (TU München, DE) [dblp]
- Alberto Ravagnani (University College Dublin, IE) [dblp]
- Julian Renner (TU München, DE) [dblp]
- Joachim Rosenthal (Universität Zürich, CH) [dblp]
- Ronny Roth (Technion - Haifa, IL)
- John Sheekey (University College Dublin, IE) [dblp]
- Carmen Sippel (Universität Ulm, DE) [dblp]
- Emina Soljanin (Rutgers University - Piscataway, US) [dblp]
- Razane Tajeddine (Aalto University, FI) [dblp]
- Violetta Weger (Universität Zürich, CH) [dblp]
- Eitan Yaakobi (Technion - Haifa, IL) [dblp]
- Yiwei Zhang (Technion - Haifa, IL) [dblp]
- Jens Zumbrägel (Universität Passau, DE) [dblp]
Related Seminars
Classification
- data structures / algorithms / complexity
- networks
- security / cryptology
Keywords
- distributed storage
- network coding
- coding theory
- cryptography
- privacy
