Syndrome-trellis Decryption of Post-Quantum Code-based Cryptosystems

Meir Ariel School of Electrical and Computer Engineering, Faculty of Engineering, Tel Aviv University, Tel Aviv, Israel

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²⁰⁰. 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.

KEYWORDS

Code based cryptography, post quantum cryptography, convolutional codes, syndrome trellis.