Paper 2025/445

A proof of P≠NP (New symmetric encryption algorithm against any linear attacks and differential attacks)

Abstract

P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, whose encryption and decryption can be completed in linear time. For the attacker, in the case where only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations which contains at least one variable that cannot be solved, and the number of possible values for one variable is exponentially to the length of the key. To solve this system of equations, it is necessary to exhaustively search for at least one variable, thus proving that the computational complexity of cracking the key is exponential. So the decryption is a one-way function, and according to ``the existence of one-way function means P$\neq$NP", thus solving the unsolved problem of P vs NP. In addition, this paper delves into the underlying mathematical laws of this new encoding mechanism, and develops a right multiplication operation to binary. Based on this right multiplication operation, we further constructed a nonlinear operation and designed another block symmetric encryption algorithm that is resistant to all forms of linear and differential attacks.

@misc{cryptoeprint:2025/445,
      author = {Gao Ming},
      title = {A proof of P≠{NP} (New symmetric encryption  algorithm against any linear attacks and  differential attacks)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/445},
      year = {2025},
      url = {https://eprint.iacr.org/2025/445}
}