New perspectives for code locality in the rank metric
2026-07-27 • Information Theory
Information TheoryCryptography and Security
AI summaryⓘ
The authors propose a new way to define 'locality' for rank-metric codes, which are used to recover lost data efficiently by looking at only a small part of the remaining data. Their definition improves on previous work by allowing recovery of any part of the data’s support without needing to choose a specific basis. They study how to shorten and puncture these codes to better understand their structure, provide new examples and constructions, and establish a theoretical limit (Singleton-like bound) for these codes. They also show that a construction similar to known Tamo-Barg codes achieves this optimal bound.
localityrank-metric codescode puncturingcode shorteningsupportSingleton boundTamo-Barg codeslinear mapscoding theorylocal recovery
Authors
Camille Garnier, Julien Lavauzelle, Jade Nardi, Ilaria Zappatore
Abstract
In coding theory, local recovery enables the efficient recovery of some part of (lost) coded data by accessing only a small number of other data entries. Locality was mostly but intensively studied for the recovery of individual symbols, that is, in the context of the Hamming metric. In this work, we propose a new definition of locality for general rank-metric codes. This definition differs from a previous work of Kadhe, El Rouayheb, Duursma and Sprintson [IEEE Trans. Inf. Theory 2019], by allowing to efficiently recover any element of the support, and without relying on any choice of bases of the underlying vector spaces. Our work firstly relies on a precise study of code puncturing and shortening for codes viewed as spaces of linear maps. We then provide examples and general constructions, showing the difference between our notion and that of Kadhe et al. We then derive a Singleton-like bound for rank locally recoverable codes, and we finally prove that a construction similar to classical Tamo-Barg codes is optimal with respect to this bound.