Graph neural network improves decoding in post quantum encryption
Recurrent Bipartite Graph Neural Networks for QC-MDPC Error Decoding in McEliece Cryptosystems
Cryptography and SecurityMachine Learning
Summary
Classical encryption methods are at risk from future quantum computers, so new ways to secure data are needed. One approach uses special error-correcting codes called QC-MDPC, but current methods to decode them often fail and can leak secret information. The authors propose a new kind of neural network that learns to decode these codes more reliably by overcoming common problems in the decoding process. Their method reduces failures significantly and works faster than traditional techniques.
What this means in practice
- •For cryptography engineers: Increase the reliability and speed of decoding QC-MDPC codes used in post-quantum encryption schemes to reduce key leakage risks.
- •For error correction system developers: Integrate recurrent graph neural networks to improve decoding of dense parity-check codes beyond classical iterative methods.
Authors
Parth Rajeshkumar Tandel, Elisabeth Fink
Abstract
As the advent of large-scale quantum computing threatens classical encryption, Quasi-Cyclic Moderate Density Parity-Check (QC-MDPC) codes have emerged as a foundational element of Post-Quantum Cryptography (PQC). However, decoding these relatively dense codes using classical Belief Propagation algorithms often leads to failures caused by short graph cycles that stall the decoder. In cryptographic applications, these failures are severe security vulnerabilities that leak secret key information. To address this, this paper proposes a Recurrent Bipartite Graph Neural Network (R-BGNN) as proof of concept. By integrating Gated Recurrent Units (GRUs) into the message-passing framework and employing a multi-topology curriculum training strategy, the R-BGNN actively learns to break limit-cycle oscillations. Evaluated across 20 unseen matrix topologies, the proposed architecture significantly outperforms classical Bit-Flipping and Min-Sum baselines, reducing the Decoding Failure Rate (DFR) by 63.7\% at moderate noise levels ($t=10$) while converging in fewer iterations.