ADMM and Reproducing Sum-Product Decoding Algorithm Applied to QC-MDPC Code-based McEliece Cryptosystems

Kohtaro Watanabe; Motonari Ohtsuka; Yuta Tsukie

Paper 2022/1610

ADMM and Reproducing Sum-Product Decoding Algorithm Applied to QC-MDPC Code-based McEliece Cryptosystems

Kohtaro Watanabe, National Defense Academy of Japan

Motonari Ohtsuka, National Defense Academy of Japan

Yuta Tsukie, National Defense Academy of Japan

Abstract

QC-MDPC (quasi cyclic moderate density parity check) code-based McEliece cryptosystems are considered to be one of the candidates for post-quantum cryptography. Decreasing DER (decoding error rate) is one of important factor for their security, since recent attacks to these cryptosystems effectively use DER information. In this paper, we pursue the possibility of optimization-base decoding, concretely we examine ADMM (alternating direction method of multipliers), a recent developing method in optimization theory. Further, RSPA (reproducing sum-product algorithm), which efficiently reuse outputs of SPA (sum-product algorithm) is proposed for the reduction of execution time in decoding. By numerical simulations, we show that the proposing scheme shows considerable decrement in DER compared to the conventional decoding methods such as BF (bit-flipping algorithm) variants or SPA.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. to appear in IEEE Trans. Information Theory
Keywords: QC-MDPC code-based cryptosystem ADMM method reproducing sum-product algorithm McEliece cryptosystem
Contact author(s): wata @ nda ac jp
History: 2023-08-24: last of 4 revisions; 2022-11-18: received; See all versions
Short URL: https://ia.cr/2022/1610
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1610,
      author = {Kohtaro Watanabe and Motonari Ohtsuka and Yuta Tsukie},
      title = {ADMM and Reproducing Sum-Product Decoding Algorithm Applied to QC-MDPC Code-based McEliece Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1610},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1610}},
      url = {https://eprint.iacr.org/2022/1610}
}