Masked high-memory convolutional code scheme claims >2^200 security over McEliece
The claim
The proposed Niederreiter-based construction achieves security margins exceeding classical McEliece/Niederreiter systems by factors greater than 2^200
Published as: “Syndrome Trellis Decryption in Post-Quantum Cryptography”
So what
If the security estimates hold, the scheme offers substantially higher resistance to ISD attacks while keeping decryption fast and scalable, making it a strong candidate for practical post-quantum public-key deployment.
The five-minute version
The paper claims that its masked high-memory parity-check construction raises the estimated ISD attack complexity by factors of over 2200 against classical adversaries and about 2100 against quantum adversaries, far surpassing Classic McEliece and Niederreiter baselines. It supports arbitrary-length plaintexts with linear-time decryption whose per-bit cost is a constant 220 ACS operations in the example. The security analysis is theoretical, based on ISD complexity formulas, and the authors acknowledge that decryption can occasionally fail (≈1.6×10−6 per window) requiring retransmission.
What they found 4
- Security margin improvement over classic code-based schemes
“security margins exceeding those of classical McEliece- and Niederreiter-based systems by factors greater than 2200.”
- Linear-time decryption with constant per-bit ACS cost
“the total number of ACS operations per decrypted ciphertext bit is 2l+p = 220”
- Estimated ISD complexity increase by a factor of ~2371 over Goppa code
“This corresponds to an estimated increase in ISD attack complexity by a factor of approximately CISD(MPC) CISD(Goppa) ≈0.52×10112≈2371”
- Very low decoding-failure probability
“the probability of this event is approximately 1.6×10-6 Over 274 windows, corresponding to a ciphertext length of approximately 8,200 bits, the probability of successful decoding is therefore (1 - 1.6×10-6)274≈ 0.9995”
What undercuts it the paper’s own results
- Correct decryption, however, is not guaranteed, since localized clusters of errors may occasionally cause decoding failure.
- The probability of decoding failure per window is approximately 1.6×10−6, leading to a non-zero overall failure chance.
Stated limits 2
- Correct decryption, however, is not guaranteed, since localized clusters of errors may occasionally cause decoding failure.
- As in the Classic McEliece cryptosystem, this assumption is not supported by a formal proof but by the absence of any known efficient structural attacks.
What’s new here 4
- Uses dense, randomly masked high-memory parity-check matrices for a Niederreiter-type scheme, unlike prior Goppa-based constructions.
- Introduces syndrome-trellis directed-graph decoders that enable polynomial-time decryption with linear per-bit cost.
- Employs fully random error injection with unknown weight, adding uncertainty for ISD attacks.
- Provides a design that scales to very long messages while keeping decryption complexity independent of message length.
Threat model stated by the source
Artifacts & methods 6
- masked high-memory parity-check matrix (Ĥ)primitive
- random masking matrix H̃primitive
- high-memory polynomial q(x)primitive
- syndrome-trellis decoder arraysystem
- information-set decoding (ISD) complexity analysisevaluation
- random error injection with probability εprimitive