Post-quantum cryptography secured by masked convolutional codes
Syndrome Trellis Decryption in Post-Quantum Cryptography
Cryptography and Security
Summary
Protecting digital communication against future quantum computers is a big challenge. This paper introduces a new method that hides secret codes inside complicated random-looking math puzzles, making it very hard for hackers to break in. At the same time, authorized users can unlock the messages efficiently, even when they are very long. The method improves on previous code-based cryptography by being both more secure and faster to decode. The new approach can also be implemented on hardware for quick, large-scale use.
What this means in practice
- •For cryptographic engineers: Build quantum-resistant public key encryption systems that decode efficiently for long messages at uniform per-bit cost.
- •For hardware security developers: Implement highly parallel syndrome-trellis decoders for fast, scalable post-quantum cryptography in hardware appliances.
Authors
Meir Ariel
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.