Software Implementation of Dumer’s Algorithm for Decoding Binary Linear Codes in Various Parallel Computing Models

Hao Zhai

Abstract


This paper investigates and implements parallel versions of Dumer’s algorithm for solving the NP-complete Syndrome Decoding Problem (SDP), which forms the security foundation of post-quantum code-based cryptosystems like McEliece. Despite its theoretical efficiency, the practical application of Dumer’s algorithm is limited by its high computational complexity. To overcome this barrier, four versions of the algorithm were developed and rigorously analyzed: a baseline sequential C++ implementation, a multi-threaded version using OpenMP for multi-core CPUs, a GPU-accelerated version based on CUDA, and a hybrid model combining the computational power of both CPUs and GPUs. The correctness of all implementations was verified using standardized test data from the decodingchallenge.org platform. Experimental results demonstrate that for small-scale matrices, the OpenMP implementation is the most effective, whereas for large-scale problems, the hybrid approach shows superior performance. This study significantly enhances the practical applicability of Dumer’s algorithm, greatly reducing the problem-solving time and allowing for a more accurate assessment of the real-world security of code-based cryptosystems.

Full Text:

PDF (Russian)

References


R. J. McEliece, «A public-key cryptosystem based on algebraic», Coding Thv, vol. 4244, pp. 114–116, 1978.

E. Berlekamp, R. McEliece, and H. Van Tilborg, «The inherent computational complexity of decoding», IEEE Transactions on Information Theory, 1978.

I. Dumer, «On minimum distance decoding of linear codes», in Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory, Moscow, 1991, pp. 50–52.

D. Wagner, «A generalized birthday problem», in Annual International Cryptology Conference, Springer, 2002, pp. 288–304.

E. Prange, «The use of information sets in decoding cyclic codes», IRE Transactions on Information Theory, 1962.

P. J. Lee and E. F. Brickell, «Some algorithms for soft-decision decoding», IEEE Transactions on Information Theory, 1988.

J. Stern, «A method for finding codewords of small weight», Coding Theory and Applications, 1989.

OpenMP Architecture Review Board, OpenMP application programming interface version 5.0, https://www.openmp.org/wp-content/uploads/OpenMP-APISpecification-5.0.pdf, Accessed: May 2025, 2018.

NVIDIA Corporation, CUDA C programming guide, https://docs.nvidia.com/cuda/cuda- c- programmingguide/, Version 12.3, Accessed: May 2025, 2023.

J. Nickolls, I. Buck, M. Garland, and K. Skadron, «Scalable parallel programming with CUDA», Queue, vol. 6, no. 2, pp. 40–53, 2008.

N. Aragon, J. Lavauzelle, and M. Lequesne, Decodingchallenge.org, 2019. [Online]. Available: http://decodingchallenge.org.

V. Volkov and J. W. Demmel, «Benchmarking GPUs to tune dense linear algebra», in SC’08: Proceedings of the 2008 ACM/IEEE Conference on Supercomputing, IEEE, 2008, pp. 1–11.

W. Gropp, E. Lusk, N. Doss, and A. Skjellum, «A high-performance, portable implementation of the MPI message passing interface standard», Parallel computing, vol. 22, no. 6, pp. 789–828, 1996.

T. Güneysu, «High-speed cryptography and cryptanalysis on FPGAs», in Applied Reconfigurable Computing, Springer, 2016, pp. 217–228.

J. Subhlok, S. Venkataramaiah, and A. Singh, «Automatic node selection for high performance applications on networks», pp. 163–172, 2001.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность ИБП для ЦОД СНЭ

ISSN: 2307-8162