🔢 mathematics

The Code Distortion Problem

This paper introduces the Code Distortion Problem (CDP) as a generalization of linear code equivalence, establishing its NP-hardness to approximate, its membership in $\Sigma_2^P$ , and providing single-exponential-time approximation algorithms while adapting key lattice techniques to the coding theory domain.

Original authors: Huck Bennett, Matthew Fox, Bryant Morrell

Published 2026-07-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Huck Bennett, Matthew Fox, Bryant Morrell

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message across a noisy room. To make sure the message arrives without getting garbled, you don't just shout the words; you wrap them in a special pattern, like a secret code made of light switches that are either on or off. In the world of computers, these patterns are called linear error-correcting codes. They are the unsung heroes that keep your Wi-Fi stable and your bank transactions secure. But here's the tricky part: sometimes, two different teams might invent two different codes that look nothing alike on paper, yet they actually do the exact same job. It's like having two different maps of the same city: one might be drawn with the streets running north-south, while the other is rotated so they run east-west. If you can rotate and stretch one map to perfectly match the other, they are "equivalent."

For a long time, computer scientists have been obsessed with a specific question: Can we tell if two codes are just different versions of the same thing? This is known as the Linear Code Equivalence Problem. It's a bit like a high-stakes puzzle that keeps hackers busy; if you can solve it quickly, you might be able to crack secret codes used to protect digital signatures. But what if the codes aren't perfectly equivalent? What if they are just "close enough"? Maybe one code stretches distances a little bit more than the other, or shrinks them in a weird way. This is where the idea of distortion comes in. Think of distortion as a "messiness score." A score of 1 means the codes are perfect twins. A score of 100 means they are cousins who look vaguely similar but have very different personalities. The big question is: How messy can two codes get before we can no longer say they are related? And more importantly, how hard is it to calculate that messiness score?

This paper, titled "The Code Distortion Problem," dives deep into that messy middle ground. The authors, Huck Bennett, Matthew Fox, and Bryant Morrell, introduce a new challenge called the Code Distortion Problem (CDP). Instead of just asking "Are these codes the same?", they ask, "What is the least amount of distortion needed to turn one code into another?" They treat codes like elastic sheets: you can stretch, shrink, and twist them, but you want to find the transformation that keeps them as close to their original shape as possible.

The team discovers that calculating this "messiness score" is incredibly difficult. In fact, they prove that for any constant level of accuracy you might hope for, figuring out the distortion is NP-hard. To put that in everyday terms: if you tried to write a computer program to find the perfect, least-distorted map between two complex codes, you would likely wait longer than the age of the universe for an answer. It's not just that the problem is hard; it's hard to even get a "good enough" guess. The authors show that even if you are willing to accept an answer that is off by a huge factor, the computer still can't do it efficiently.

However, the story isn't all bad news. The authors also show that while the problem is a nightmare for computers to solve exactly, it's not impossible to get a rough estimate. They designed a clever algorithm that runs in "single-exponential time." Imagine a task that takes 2 steps for a small code, 4 steps for a slightly bigger one, 8 for the next, and so on. While this still gets big fast, it's much better than the alternative. Their method uses a concept they call successive minima bases, which is like finding the "skeleton" of the code—the most efficient, shortest building blocks that make it up. By matching these skeletons, they can create a map between the codes that is guaranteed to be within a certain factor of the best possible map. For general codes, their map might be off by a factor of $k^2$ (where $k$ is the size of the code's dimension), but for a special type of binary code where all the building blocks are the same size, they can tighten that error down to roughly $(\frac{2k+1}{3})^2$ .

The paper also tackles a fascinating mystery about where this problem lives in the grand hierarchy of computer science. Usually, problems that are this hard are either in a category called NP (where you can check a solution quickly if someone hands it to you) or even harder. But the authors prove that the Code Distortion Problem sits in a slightly different, more complex category called $\Sigma_2^P$ . This is because checking if a proposed solution is actually the best one is itself a nightmare; it requires verifying that no other map could possibly be better, which is a double-layered logic puzzle. They suspect the problem might be even harder than they proved, potentially sitting at the very top of this complexity mountain, but they leave that as an open question for future explorers.

In the end, this paper doesn't just solve a puzzle; it maps the terrain of a new, difficult landscape. It tells us that while we can't perfectly measure the "distance" between two complex codes without waiting forever, we can build a ladder to climb up and get a decent approximation. This work is crucial for the future of cryptography, especially as we move toward a "post-quantum" world where old security methods might fail. By understanding how much codes can be distorted, we get a better handle on how secure our digital locks really are, and just how hard it is for a hacker to pick them.

Technical Summary: The Code Distortion Problem

Problem Definition

This work introduces and studies the Code Distortion Problem (CDP), a generalization of the Linear Code Equivalence Problem (LCE). While LCE asks whether two linear error-correcting codes $C_1, C_2 \subseteq \mathbb{F}_q^n$ are related by a linear isometry (a distance-preserving map involving coordinate permutations and scalings), CDP seeks to quantify the "similarity" between two codes when they are not perfectly equivalent.

Formally, for two $[n, k]_q$ codes $C_1$ and $C_2$ , the distortion of a linear map $T$ such that $T(C_1) = C_2$ is defined as:
$D_T(C_1, C_2) := \left( \max_{x \in C_1 \setminus \{0\}} \frac{\|Tx\|_0}{\|x\|_0} \right) \Bigg/ \left( \min_{x \in C_1 \setminus \{0\}} \frac{\|Tx\|_0}{\|x\|_0} \right)$
where $\|\cdot\|_0$ denotes the Hamming weight. The Code Distortion $D(C_1, C_2)$ is the minimum distortion over all such linear maps $T$ . The decisional version, GapCDP, asks whether $D(C_1, C_2) \leq D$ or $D(C_1, C_2) > \gamma D$ for a given threshold $D$ and approximation factor $\gamma$ .

The problem is motivated by the cryptographic importance of LCE (e.g., in the LESS cryptosystem) and the desire to understand the structural distance between codes that are not strictly equivalent.

Methodology and Techniques

The authors employ techniques analogous to those used in the Lattice Distortion Problem (LDP) by Bennett, Dadush, and Stephens-Davidowitz (2016), while introducing several new concepts specific to coding theory:

Successive Minima Bases for Codes: Adapted from lattice theory, the $i$ -th successive minimum $\lambda_i(C)$ is the smallest weight $r$ such that $C$ contains $i$ linearly independent vectors of weight at most $r$ . A successive minima basis is a generator matrix where the $i$ -th column has weight exactly $\lambda_i(C)$ . The authors prove such bases always exist for codes and can be computed in $O^*(q^k)$ time.
Matrix $0 \to 0$ Norm: The paper analyzes the "norm" $\|T\|_{0 \to 0} = \max_{x \neq 0} \|Tx\|_0 / \|x\|_0$ . While the unrestricted norm is efficiently computable, the restricted norm (maximized over a subspace/code) is shown to be coNP-hard to approximate.
Reductions:
- Hardness: The authors adapt the Goldreich-Micciancio-Safra-Seifert (GMSS) reduction from the Shortest Vector Problem (SVP) to the Closest Vector Problem (CVP) on lattices, creating an analogous reduction from the Minimum Distance Problem (GapMDP) to the Nearest Codeword Problem (GapNCP) on codes. This is then reduced to GapCDP.
- Approximation: The core algorithmic approach involves computing successive minima bases for both input codes and mapping the basis vectors of one to the other.

Key Contributions and Results

1. Complexity and Hardness of Approximation

NP-Hardness: The paper proves that for any constant distortion threshold $D > 1$ , the decisional GapCDP is NP-hard to approximate within any constant factor $\gamma$ . This contrasts with the case $D=1$ (LCE), which is in coAM and not believed to be NP-hard.
Complexity Class: GapCDP is shown to be in $\Sigma_2^P$ (the second level of the polynomial hierarchy). The authors note that it is not immediately clear if the problem is in NP, primarily because verifying a witness (a low-distortion map) requires computing the restricted matrix $0 \to 0$ norm, which is coNP-hard.
Matrix Norm Hardness: As a byproduct, the paper establishes that approximating the matrix $0 \to 0$ norm restricted to a subspace is coNP-complete.

2. Approximation Algorithms

The authors provide single-exponential time approximation algorithms based on successive minima bases:

General Case: For any $[n, k]_q$ codes, there is an algorithm running in $O^*(q^k)$ time that achieves a $k^2$ -approximation. The algorithm computes successive minima bases $G_1, G_2$ and maps $G_1 \to G_2$ .
Special Case (Binary, Uniform Minima): For binary codes where all successive minima are equal ( $\lambda_1 = \dots = \lambda_k$ ), the approximation factor improves to $\left(\frac{2k+1}{3}\right)^2$ . This analysis is shown to be tight via a constructive example where the distortion between two generator matrices of the same code achieves this bound.

3. Exact Algorithm

A brute-force exact algorithm is presented with a running time of $O^*(q^{k(k+1)})$ , which essentially enumerates all generator matrices of the target code. The authors note that improving this to a single-exponential exact algorithm remains an open challenge.

Significance and Claims

The paper claims to establish the fundamental computational landscape of the Code Distortion Problem:

Generalization: It successfully generalizes the well-studied LCE to a quantitative metric of code similarity, bridging concepts from metric embeddings and lattice theory.
Hardness Barrier: It demonstrates that even slight deviations from perfect equivalence ( $D > 1$ ) render the problem computationally intractable (NP-hard to approximate), suggesting that finding "nearly equivalent" codes is difficult.
Algorithmic Limits: It provides the first non-trivial approximation algorithms for CDP, showing that while exact solutions are expensive, good approximations are achievable in single-exponential time using successive minima bases.
Theoretical Tools: The introduction of successive minima bases for codes and the analysis of the restricted $0 \to 0$ norm are presented as concepts of independent interest, potentially useful for future research in coding theory and complexity.

The authors conclude by noting that the relationship between CDP and the Lattice Distortion Problem (LDP) warrants further investigation, as does the possibility of basing cryptographic security on the hardness of approximate CDP, similar to the reliance on LCE in the LESS cryptosystem.