Abstract:
Maximum likelihood decoding is an extensively used technique for digital communication systems. The hardness of the maximum likelihood decoding problem is the fundamental basis of the security justification for code-based cryptography. The study of code-based cryptography algorithms is considered as one of the main directions in the development of post-quantum cryptography. Nevertheless, it is known relatively little about the hardness of the maximum likelihood decoding problem. In this paper, we present an alternative proof of the NP-completeness of the maximum likelihood decoding problem that provides additional evidence for the security of cryptographic algorithms based on Classic McEliece. Also, we consider the counting variant of the maximum likelihood decoding problem, an important tool for finding collisions. We obtain a parsimonious reduction from the perfect matching problem and a weakly parsimonious reduction from the simple Max Cut problem. As a consequence, we obtain the $\#$P-completeness of the counting variant of the maximum likelihood decoding problem. Also, we consider some counting variants of the maximum likelihood decoding problem for classes of computational complexity that are of interest from the point of view of quantum computing and post-quantum cryptography. In particular, we obtain completeness results for classes WPP, C$_=$P, and PP.
Keywords:computational complexity, maximum likelihood decoding problem, perfect matching problem, Max Cut problem.
Fulltext:
PDF file (665 kB)