Syndrome Trellis Decryption in Post-Quantum Cryptography

arXiv:2610.39873 · cs.CR · Submitted 2026-10-29 · Read on arXiv

cs.CR

Submitted: 2026-10-29

Updated: 2026-10-29

Comments: 21 pages, 6 figures

Journal ref: CRYPIS 2026 pp. 61-84

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

The gist: We present a novel post-quantum cryptographic framework based on masked high-memory convolutional codes in the Niederreiter paradigm.

Abstract

We present a novel post-quantum cryptographic framework based on masked high-memory convolutional codes in the Niederreiter paradigm. The public key is derived from a high-memory polynomial parity-check matrix augmented by dense random masking and additional invertible linear transformations. The resulting matrix exhibits strong random-like properties, effectively concealing its algebraic structure and resisting known structural and algebraic attacks. Legitimate recipients retain polynomial-time decoding capability, whereas adversaries appear to be limited to generic information-set decoding with exponential complexity. Under standard cryptanalytic estimates, the proposed construction achieves security margins exceeding those of classical McEliece- and Niederreiter-based systems by factors greater than 2 200. Beyond its enhanced security profile, the construction offers considerable design flexibility, supporting arbitrary plaintext lengths, linear-time decryption, and a uniform per-bit computational cost, enabling efficient scalability to very long messages. Practical implementation is facilitated by a parallel array of syndrome-trellis decoders, dynamically instantiated according to candidate syndrome values, enabling efficient hardware and software implementations with high throughput. Overall, the proposed scheme is a promising candidate for robust, scalable, quantum-resistant public-key cryptography.

Related papers