Highly Efficient Parallel Row-Layered Min-Sum MDPC Decoder for McEliece Cryptosystem
<|reference_start|>Highly Efficient Parallel Row-Layered Min-Sum MDPC Decoder for McEliece Cryptosystem: The medium-density parity-check (MDPC) code-based McEliece cryptosystem remains a finalist of the post-quantum cryptography standard. The Min-sum decoding algorithm achieves better performance-complexity tradeoff than other algorithms for MDPC codes. However, the prior Min-sum MDPC decoder requires large memories, whose complexity dominates the overall complexity. Besides, its actual achievable parallelism is limited. This paper has four contributions: For the first time, the row-layered scheduling scheme is exploited to substantially reduce the memory requirement of MDPC decoders; A low-complexity scheme is developed to mitigate the performance loss caused by finite precision representation of the messages and high column weights of MDPC codes in row-layered decoding; Constraints are added to the parity check matrix construction to enable effective parallel processing with negligible impacts on the decoder performance and resilience towards attacks; A novel parity check matrix division scheme for highly efficient parallel processing is proposed and the corresponding parallel row-layered decoder architecture is designed. The number of clock cycles for each decoding iteration is reduced by a factor of L using the proposed L-parallel decoder with very small memory overhead. For an example 2-parallel decoder, the proposed design leads to 26% less memory requirement and 70% latency reduction compared to the prior decoder.<|reference_end|>
@article{cai2024highly,
    title={Highly Efficient Parallel Row-Layered Min-Sum MDPC Decoder for McEliece
  Cryptosystem},
    author={Jiaxuan Cai and Xinmiao Zhang},
    journal={arXiv preprint arXiv:2407.12695},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.12695},
    primaryClass={cs.CR cs.AR}
}