Post-Quantum Key Encapsulation Mechanism Based on the McEliece-RRNS Cryptosystem

Abstract

Key encapsulation mechanisms are a fundamental primitive for establishing shared secrets in modern secure communication systems. NIST SP 800-227 defines a KEM as a three-stage construction consisting of key generation, encapsulation, and decapsulation, and emphasizes that correctness, implementation security, and deployment security are all necessary for practical protection. At the same time, FIPS 203 standardized ML-KEM as the first NIST post-quantum KEM, highlighting the broader importance of efficient and reliable post-quantum key establishment. This paper presents a post-quantum KEM based on the McEliece-RRNS cryptosystem, where error-control coding is implemented using a redundant residue number system rather than binary Goppa codes. The study focuses on three experimentally measurable properties of the proposed construction: the influence of parameters (n, k, r, t) on behavior, the probability of decapsulation failure, and the execution time of encapsulation and decapsulation. A prototype implementation is evaluated for several RRNS parameter sets, and the obtained results are interpreted as a trade-off between redundancy, reliability, and computational cost. The analysis shows that McEliece-RRNS can serve as a feasible basis for a code-based post-quantum KEM, provided that its parameters are selected to balance error-correction capability and runtime overhead.