Abstract
As post-quantum cryptography (PQC) transitions from theoretical research to standardization, the security of code-based cryptosystems remains a critical area of study. Interleaved codes have been proposed to reduce the large key sizes typically associated with these systems. However, their security relies on the hardness of the Interleaved Decoding (ID) problem. This paper introduces "Interleaved Prange," a novel generic decoding algorithm that exploits the multi-row structure of interleaved codes. By generalizing classical Information Set Decoding (ISD), the authors demonstrate that Interleaved Prange achieves a lower asymptotic complexity than standard reduction-based approaches, providing a more precise security benchmark for future code-based primitives.
Introduction
In the landscape of post-quantum cryptography, code-based systems like Classic McEliece are considered highly secure but suffer from the practical drawback of massive public key sizes. To address this, researchers have turned to interleaved codes. These codes consist of matrices where each row is a codeword from the same underlying linear code, and all rows share the same error positions—often referred to as burst errors in a multi-dimensional context.
The security of these proposals rests on the computational difficulty of the Interleaved Decoding (ID) problem: recovering the original codewords from a noisy interleaved matrix. While efficient algebraic decoders exist for scenarios with a high interleaving order, the regime where the number of rows $\ell$ is small relative to the number of errors $t$ (i.e., $\ell \ll t$) has lacked a dedicated, optimized attack. This paper fills that gap by introducing the Interleaved Prange algorithm.
The Interleaved Decoding Problem
Standard Information Set Decoding (ISD) algorithms, such as those proposed by Prange or Stern, are designed to find a single error vector in a linear code. When faced with interleaved codes, a "naive" approach is to apply these classical algorithms to a single row of the received matrix, ignoring the shared error support across other rows. Alternatively, one could reduce the ID problem to a standard Syndrome Decoding (SD) problem over a larger field, but this often fails to capture the specific structural weaknesses of interleaving.
The Interleaved Prange approach recognizes that the shared error support across multiple codewords is a significant lever. If multiple rows are corrupted at the same positions, the collective rank properties of those rows can be exploited to identify error locations more efficiently than analyzing any single row in isolation.
The Interleaved Prange Algorithm
Interleaved Prange generalizes Eugene Prange’s 1962 ISD algorithm by considering the entire received matrix $R$ and the generator matrix $G$ simultaneously. The algorithm operates through the following steps:
- Submatrix Selection: The algorithm selects a set of $k + \ell$ columns, where $k$ is the code dimension and $\ell$ is the number of rows (interleaving order).
- Rank Deficiency Check: If the chosen columns are mostly free of errors, the resulting submatrix is likely to be rank-deficient.
- Null Space Computation: The algorithm computes the left null space of this augmented submatrix. Any vector in this null space represents a linear combination of the rows that effectively "cancels out" the code component, leaving a low-weight error vector.
- Error Identification: This low-weight vector allows the attacker to identify the error positions and subsequently decode the entire matrix.
By focusing on the left null space, the algorithm avoids the exponential cost of searching through all possible linear combinations of rows, a significant improvement over previous iterative methods.
Performance and Complexity Analysis
The authors evaluated Interleaved Prange using both theoretical asymptotic analysis and simulations on random interleaved codes over finite fields (specifically $\mathbb{F}_q$ with $q=7$).
Complexity Exponents
In ISD research, complexity is often expressed as an exponent $e$ in the form $q^{ne}$. The results indicate a clear advantage for the interleaved-specific approach:
- Standard Random Prange: Simulated exponent of 0.07848.
- Interleaved Prange: Simulated exponent of 0.06832.
Even when compared against more sophisticated algorithms like Stern’s (when used in a reductionist manner), the relatively simple Interleaved Prange maintains a lower complexity bound. This proves that a "native" interleaved decoder is asymptotically more efficient than any strategy that treats the rows as independent entities.
NP-Completeness
Beyond the algorithm itself, the paper provides a formal proof that the Interleaved Syndrome Decoding problem is NP-complete. This result is dual-edged: it confirms that the problem is a robust foundation for cryptographic primitives, while Interleaved Prange establishes the current "best-case" efficiency for a potential adversary.
Conclusion and Future Work
Interleaved Prange represents a significant step forward in understanding the security of interleaved code-based systems. It demonstrates that the shared structure of interleaved codes is a measurable weakness in the small-$\ell$ regime.
However, several avenues for future research remain. The authors note that comparing Interleaved Prange to "Codeword Finding" (CF) algorithms is difficult due to the complex failure probabilities of the latter. Additionally, while this work focuses on random codes, practical cryptosystems often utilize structured codes (such as Goppa or MDPC codes). Determining how Interleaved Prange might be optimized to exploit these specific algebraic structures is a vital next step for the cryptographic community. Finally, identifying the exact crossover point where algebraic decoders become more efficient than Interleaved Prange as $\ell$ increases remains an open question.
Summary updated