We present a quantum public-key cryptosystem based on a classical NP-complete problem related with finding a code word of a given weight in a linear binary code.
It is well known that Shor's quantum algorithm for integer factorization can break down the RSA public-key cryptosystem, which is widely used in many cryptographic applications. Thus, public-key cryptosystems in the quantum computational setting are longed for cryptology. In order to define the security notions of public-key cryptosystems, we have to model the power of the sender, receiver, adversary and channel. While we may consider a setting where quantum computers are available only to adversaries, we generally discuss what are the right security notions for (quantum) public-key cryptosystems in the quantum computational setting. Moreover, we consider the security of quantum public-key cryptosystems known so far.
We present a quantum public-key cryptography protocol for quantum message transmission. The private key of this protocol includes three classical matrices: a generator matrix of a Goppa code, an invertible matrix and a permutation matrix. The public key is product of these three matrices. The encryption and decryption algorithms are merely quantum computations related with the transformations between bases of the quantum registers. The security of this protocol is based on the hypothesis that there is no effective algorithm of NP-complete problem.
Abstract The NP-hardness of the Minimum Distance Decoding Problem (MDDP) is the core of the McEliece cryptosystem. The difficulty of decoding a received word to the closest codeword in a given arbitrary code is key to its security. Related to the MDDP is the Coset Leader Problem (CLP), which consists in finding a word of a given syndrome and minimum Hamming weight. Both can be modelled as optimization problems, and solved using the Quantum Approximate Optimization Algorithm (QAOA), a well-known hybrid quantum- classical algorithm. In this paper, we model both the MDDP and CLP for linear codes over arbitrary m−ary alphabets, we make the theoretical analysis of the first level for the binary CLP problem, and introduce some experiments to test its performance. The experiments were carried out on both quantum computer simulators and real quantum devices, and use codes of different lengths and different depths of the QAOA.