🔢 mathematics

Search-to-Decision Reductions for the Linear and General Code Equivalence Problems

This paper presents efficient search-to-decision reductions for the Linear and General Code Equivalence problems by recovering the permutation component via a decision oracle and determining the diagonal and field automorphism components in deterministic polynomial time using the Engel-Schneider algorithm.

Original authors: Abhinaba Mazumder

Published 2026-08-12

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Abhinaba Mazumder

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 a detective trying to solve a mystery, but instead of fingerprints or footprints, your clues are made of numbers. You are working in the world of cryptography, the science of secret codes. In this world, a "code" isn't just a secret message; it's a specific pattern of numbers arranged in a grid, designed to protect information. For decades, scientists have worried that super-powerful quantum computers (which don't exist yet but are coming soon) might be able to crack these codes instantly. To stay safe, cryptographers are building new locks based on math problems that are incredibly hard to solve, even for quantum machines.

One of the most promising types of locks relies on a puzzle called "Code Equivalence." Imagine you have two grids of numbers. The puzzle asks: "Are these two grids secretly the same, just shuffled and stretched?" You can shuffle the columns (like rearranging books on a shelf) and stretch the numbers (like changing the font size or color), but you can't change the underlying story the numbers tell. If you can prove they are the same, you've cracked the lock. If you can't, the secret remains safe. This is the foundation of a new generation of digital signatures that could protect our future internet.

For a long time, there was a gap in our understanding of how to solve these puzzles. We had a "decision" tool: a magical oracle that could simply say "Yes" or "No" to the question, "Are these two grids equivalent?" But in the real world, we need more than a yes or no; we need the actual solution. We need to know exactly how the books were shuffled and how much they were stretched. This is called the "search" problem. Until now, we knew how to turn a "Yes/No" answer into a solution for the simplest version of the puzzle (where you can only shuffle), but the more complex versions (where you can also stretch numbers or change the rules of the number system itself) remained a mystery.

This paper, written by Abhinaba Mazumder, solves that mystery. The author presents a clever, step-by-step method to turn that simple "Yes/No" oracle into a full-blown detective that can find the exact solution for the most complex versions of the puzzle. The paper proves that if you can decide whether two codes are equivalent, you can also efficiently find the specific shuffling and stretching instructions that make them match. This is a major step forward, showing that the "search" problem is no harder than the "decision" problem for these specific types of codes. The author provides a clear, deterministic recipe (an algorithm) that works every time, proving that we can reconstruct the secret key from the simple yes/no answer in a reasonable amount of time.

The Detective's Toolkit: Shuffling and Stretching

To understand how the paper works, let's break down the puzzle pieces using a simple analogy. Imagine you have a deck of cards, but instead of suits and numbers, the cards have patterns of dots.

The Puzzle: You have two decks, Deck A and Deck B. You suspect Deck B is just Deck A that has been:

Shuffled: The order of the cards is changed.
Stretched: The dots on some cards are multiplied by a secret number (like zooming in on the image).
Twisted: (In the most complex version) The rules of how the dots interact are slightly changed by a "field automorphism," which is like a secret rule that turns a '2' into a '3' and a '3' into a '2' in a specific pattern.

The "Decision" problem is like asking a referee: "Are these decks the same?" The referee just says "Yes" or "No."
The "Search" problem is like asking: "Show me the exact list of moves to turn Deck A into Deck B."

The Magic Trick: Pinning Down the Shuffle

The paper's first big breakthrough is figuring out how to find the shuffle (the permutation) using only the "Yes/No" referee.

Imagine you want to know if the first card in Deck A (let's call it the "Ace") was moved to the 5th position in Deck B. You can't just ask the referee, "Is the Ace at position 5?" because the referee might say "Yes" even if the Ace is actually at position 6, just because there are other ways to make the decks match.

So, the author uses a clever trick called "Projective Classes." Think of this as grouping cards that look the same, just with different colors. If the Ace and the King have the same pattern of dots (just different sizes), they belong to the same "class."

The detective's strategy is to pin the cards.

The detective takes the first card of Deck A and makes 100 copies of it, sticking them all at the end of the deck.
Then, they take a candidate card from Deck B (say, the one at position 5) and make 100 copies of it, sticking those at the end of Deck B too.
They ask the referee: "Are these new, huge decks equivalent?"

If the referee says "No," it means the candidate card (position 5) was the wrong choice. The "Ace" couldn't have been moved there.
If the referee says "Yes," it's a strong hint that the "Ace" was moved to position 5.

Why does this work? Because the referee can only say "Yes" if the entire structure matches. By adding 100 identical copies, you create a massive "fingerprint" that is hard to fake. If the candidate is wrong, the fingerprints won't match, and the referee will say "No." If the candidate is right, the fingerprints align, and the referee says "Yes."

The paper proves that by doing this for every card, one by one, you can reconstruct the entire shuffle list. It's like solving a jigsaw puzzle by testing one piece at a time, but instead of trying to fit it, you ask a magic mirror if the picture looks right.

The Second Step: Finding the Stretch

Once the shuffle is known, the puzzle becomes much easier. The "stretching" part (the diagonal matrix) is like finding the secret multipliers for each card.

The author shows that once you know the order of the cards, you don't need the magic referee anymore. You can use standard math (linear algebra) to figure out exactly how much each card was stretched. The paper uses a method called the Engel-Schneider algorithm.

Imagine you have a set of equations: "Card A (stretched by 2) equals Card B." If you know Card A and Card B, you can just divide to find the "2." The paper explains that this is exactly what happens here. The author converts the problem into a network of clues (a graph) and walks through it to find the secret multipliers. This step is fast, deterministic, and doesn't require any more "Yes/No" questions.

The Final Boss: The "Twist" (Field Automorphism)

The most complex version of the puzzle involves a "twist" where the rules of the number system itself change (a field automorphism). This is like if the referee suddenly decided that in Deck B, the number 2 actually means 3.

The paper shows that this twist doesn't mess up the "Projective Classes" (the grouping of similar cards). Because the grouping stays the same, the detective can use the exact same "pinning" trick from the first step to find the shuffle, even with the twist involved.

Once the shuffle is found, the detective simply tries every possible "twist" (there are only a few, specifically $\log_p q$ of them). For each possible twist, they run the "stretching" math from the second step. If the math works out perfectly, they've found the secret twist. If it doesn't, they try the next one. Since there are very few twists to try, this is still very fast.

What This Means

The paper proves two main things:

For Linear Code Equivalence (LCE): If you have a tool that can say "Yes/No" to whether two codes are equivalent, you can build a tool that finds the exact solution in a reasonable amount of time.
For Generalized Code Equivalence (GCE): This works even for the most complex version with the "twist."

The author explicitly rules out the idea that these problems are fundamentally harder to solve (search) than to decide. The paper proves that the "search" problem is not a separate, harder mountain to climb; it's just a path that naturally follows the "decision" mountain.

The confidence here is high because the author provides a proof, not just a guess or a simulation. The method is deterministic, meaning it will always work and give the right answer, not just "probably" work. The paper also notes that while this solves the puzzle for these specific codes, a similar solution for "Matrix Code Equivalence" (a different type of code used in other systems) is still missing, leaving that as a challenge for future detectives.

In short, this paper hands us the master key. It shows that the "Yes/No" oracle is powerful enough to unlock the entire secret, turning a vague confirmation into a precise, actionable solution. This is a crucial piece of the puzzle for building secure, quantum-proof digital signatures for our future.

Technical Summary: Search-to-Decision Reductions for Linear and General Code Equivalence

Problem Statement

The paper addresses the Code Equivalence (CE) problem, which asks whether two linear codes are identical up to a specific set of metric-preserving transformations. The author focuses on two specific variants:

Linear Code Equivalence (LCE): Determining if two codes $C_1$ and $C_2$ (with generator matrices $G$ and $F$ ) satisfy $SGM = F$ for some invertible matrix $S \in GL_k(\mathbb{F}_q)$ and monomial matrix $M \in Mon_n$ .
Generalised Code Equivalence (GCE): Extending LCE to include field automorphisms, asking if $S \alpha(G) M = F$ for some $\alpha \in Aut(\mathbb{F}_q)$ .

While recent work [4] established a search-to-decision reduction for Permutation Code Equivalence (PCE), the extension to the linear and generalized cases remained an open problem. This paper resolves that gap, providing efficient reductions from the search versions of LCE and GCE to their decision counterparts.

Methodology

The proposed methodology adapts the framework used for PCE in [4] but introduces necessary modifications to handle the scaling and field automorphism components inherent in LCE and GCE. The reduction proceeds in two primary stages:

1. Recovery of the Permutation Component

The first step involves recovering the permutation $\pi$ associated with the monomial matrix $M = PD$.

Projective Classes: Instead of relying on identical columns (as in PCE), the author utilizes projective classes. Two columns $g_i$ and $g_j$ belong to the same class if they are proportional ( $g_i \sim g_j$ ). A key lemma establishes that any field automorphism $\alpha$ preserves these projective classes.
Oracle Queries: The algorithm iteratively determines the image $\pi(t)$ $π (t)$ for each index $t$ $t$ . It constructs query instances by appending multiple copies of specific columns to the generator matrices $G$ $G$ and $F$ $F$ .
- If a column's projective class is already "represented" (mapped), the image is determined without oracle calls by leveraging the bijection of class sizes.
- If the class is unrepresented, the algorithm tests candidate images $i$ by appending $(\ell+1)m$ copies of column $t$ to $G$ and column $i$ to $F$ . The decision oracle determines if a valid equivalence exists.
Uniqueness: By carefully controlling the number of appended columns based on class sizes, the algorithm ensures that any valid equivalence found by the oracle must map the specific target column to the tested candidate, effectively "pinning" the permutation.

2. Recovery of the Diagonal and Automorphism Components

Once the permutation $P$ is recovered, the problem reduces to finding the diagonal matrix $D$ (and the automorphism $\alpha$ for GCE).

Reduction to Diagonal Equivalence: With $P$ known, the equation $SGM = F$ becomes $S(GP)D = F$. By transforming the matrices into systematic form (using an information set), the problem is reduced to solving $D_I^{-1} A'' D_J = F''$ , where $A''$ and $F''$ are submatrices. This is an instance of the Diagonal Equivalence problem.
Engel-Schneider Algorithm: The author employs the deterministic Engel-Schneider algorithm [8] to solve the diagonal equivalence problem. This involves constructing a bipartite graph based on non-zero entries and using a breadth-first search to determine the scaling factors. This step is performed in deterministic polynomial time without further oracle access.
Handling GCE: For the Generalised case, since field automorphisms preserve projective classes, the permutation recovery step remains identical. The algorithm then iterates through all possible field automorphisms (of which there are $\log_p q$ ). For each candidate $\alpha$ , it attempts to solve the LCE instance for $(\alpha(G), F)$ . If a solution exists, the correct $\alpha$ is identified.

Key Contributions and Results

The paper presents the following main results:

Theorem I.1: There is an efficient reduction from search-LCE to LCE. The reduction uses at most $O(n^2)$ oracle calls. The oracle queries involve codes of length at most $n + \frac{2}{27}n^3 + O(n^2)$ .
Theorem I.2: There is an efficient reduction from search-GCE to GCE. This follows naturally from the LCE result, as the permutation recovery is invariant under field automorphisms, and the remaining components are solved by iterating through the cyclic group of automorphisms.
Deterministic Polynomial Time: The recovery of the diagonal and automorphism components is achieved deterministically in time polynomial in $n$ , $k$ , and $\log q$ , relying on the Engel-Schneider algorithm.

Significance and Claims

The author claims that their work resolves open problems highlighted in recent surveys [9] and the PCE reduction paper [4]. The primary significance is the constructive conversion of any decision solver for LCE or GCE into a search solver in polynomial time.

Completeness of the Framework: The paper demonstrates that the search-to-decision reduction for PCE naturally extends to the more complex linear and generalized settings, provided one leverages the structure of projective classes and existing algorithms for diagonal equivalence.
Cryptographic Implications: By establishing these reductions, the paper reinforces the understanding of the hardness landscape for these problems, which are foundational for post-quantum cryptographic schemes like the Linear Equivalence Signature Scheme (LESS) [3].
Limitations and Future Work: The author modestly notes that they do not provide a reduction from search-LCE to GCE (or vice versa) in the reverse direction, though enumerating automorphisms provides a reduction from GCE to LCE. Furthermore, they identify that an analogous search-to-decision reduction for Matrix Code Equivalence (MCE), used in the MEDS scheme [5], remains an open problem.

The paper concludes that the search-to-decision reductions for the Hamming metric variants (PCE, LCE, GCE) are now settled, providing a complete theoretical toolkit for these specific equivalence problems.