Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 15

Proceedings of the 2018 Federated Conference on Computer Science and Information Systems

MDPC decoding algorithms and their impact on the McEliece cryptosystem

DOI: http://dx.doi.org/10.15439/2018F99

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 1085–1089 ()

Full text

Abstract. In recent years, research has been conducted aimed at finding alternative asymmetric systems other than traditional systems such as RSA and ECC. One of the most promising is code-based cryptosystems since their security is based on well-known NP-hard problems. Especially, the most interesting cryptosystem is system proposed by Misoczki et al. based on QC-MDPC codes which use the modified BitFlip algorithm as the decoding algorithm. This work presents a~comparison of different variants of MDPC decoding algorithms and their impact on the cryptosystem. I present a~complete analysis of modification of this algorithm and new results of the likelihood of correct word decoding for security systems which ensure security level $2^{128}$ and $2^{256}$.

References

  1. Julia Chaulet and Nicolas Sendrier. “Worst case QC-MDPC decoder for McEliece cryptosystem”. In: Information Theory (ISIT), 2016 IEEE International Symposium on. IEEE. 2016, pp. 1366–1370.
  2. Nir Drucker and Shay Gueron. “A toolbox for software optimization of QC-MDPC code-based cryptosystems”. In: (2017).
  3. Robert Gallager. “Low-density parity-check codes”. In: IRE Transactions on Information Theory 8.1 (1962), pp. 21–28.
  4. Qian Guo, Thomas Johansson, and Paul Stankovski. “A key recovery attack on MDPC with CCA security using decoding errors”. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer. 2016, pp. 789–815.
  5. Stefan Heyse, Ingo Von Maurich, and Tim Güneysu. “Smaller keys for code-based cryptography: QC-MDPC McEliece implementations on embedded devices”. In: International Workshop on Cryptographic Hardware and Embedded Systems. Springer. 2013, pp. 273–292.
  6. W. Cary Huffman and Vera Pless. Fundamentals of Error-correcting Codes. Cambridge University Press, 2010.
  7. Ingo Von Maurich, Tobias Oder, and Tim Güneysu. “Implementing QC-MDPC McEliece Encryption”. In: ACM Transactions on Embedded Computing Systems (TECS) 14.3 (2015), p. 44.
  8. Robert J McEliece. “A public-key cryptosystem based on algebraic”. In: Coding Thv 4244 (1978), pp. 114–116.
  9. Rafael Misoczki et al. “MDPC-McEliece: New McEliece variants from moderate density parity-check codes”. In: Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on. IEEE. 2013, pp. 2069–2073.
  10. Peter W Shor. “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”. In: SIAM review 41.2 (1999), pp. 303–332.
  11. Atsushi Yamada et al. “QC-MDPC KEM: A Key Encapsulation Mechanism Based on the QC-MDPC McEliece Encryption Scheme - First Round Submission in NIST Post-Quantum Cryptography Standardization”. In: (2017).