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. Cryptography algorithms used in practice are all based on short key, and the security of the short key mechanism is ultimately based on “one-way” assumption, that is, it is assumed that a one-way function exists. In fact, the existence of one-way function can directly lead to the important conclusion P ! = NP. In this paper, we originally constructed a short-key block cipher algorithm. The core feature of this algorithm is that for any block, when a plaintext-ciphertext pair is known, any key in the key space can satisfy the plaintext-ciphertext pair, that is, for each block, the plaintext-ciphertext pair and the key are independent, and the independence between blocks is also easy to construct. This feature is completely different from all existing short-key cipher algorithms. Based on the above feature, we construct a problem and theoretically prove that the problem satisfies the properties of one-way functions, thereby solving the problem of the existence of one-way functions, that is, directly proving that P ! = NP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Shannon, C.E.: Communication theory of secrecy systems. Bell Syst. Techn. J. 28(4), 656–715 (1945)
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Advances in cryptology: EUROCRYPT’ 93, LNCS, vol. 765, pp. 386–397. Springer (1993). https://doi.org/10.1007/3-540-48285-7_33
Kaliski, B.S., Robshaw, M.J.B.: Linear Cryptanalysis Using Multiple Approximations[C] Annual International Cryptology Conference. Springer, Berlin, Heidelberg (1994)
Biryukov, A., De Cannière, C., Quisquater, M.: On Multiple Linear Approximations. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 1–22. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_1
Cho, J.Y., Hermelin, M., Nyberg, K.: A New Technique for Multidimensional Linear Cryptanalysis with Applications on Reduced Round Serpent. In: Lee, P.J., Cheon, J.H. (eds.) ICISC 2008. LNCS, vol. 5461, pp. 383–398. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00730-9_24
Eli Biham, Adi Shamir. Differential Cryptanalysis of the Data Encryption Standard[M]. Springer-Verlag, 1993
Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 12–23. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_2
Tsunoo, Y., Tsujihara, E., Shigeri, M., et al.: Cryptanalysis of CLEFIA using multiple impossible differentials. In: 2008 International Symposium on Information Theory and Its Applications—ISITA 2008. IEEE, pp. 1–6 (2008)
Arora, S., Barak, B.: Computational Complexity: A Modern Approach (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Ming, G. (2023). A Proof of P ! = NP: New Symmetric Encryption Algorithm Against Any Linear Attacks and Differential Attacks. In: Arai, K. (eds) Advances in Information and Communication. FICC 2023. Lecture Notes in Networks and Systems, vol 652. Springer, Cham. https://doi.org/10.1007/978-3-031-28073-3_41
Download citation
DOI: https://doi.org/10.1007/978-3-031-28073-3_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-28072-6
Online ISBN: 978-3-031-28073-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)