A public‐key cryptosystem based on the difficulty of solving a system of nonlinear equations

Abstract

Abstract This paper proposes a new public‐key cryptosystem based on the difficulty of solving a system of nonlinear equations. The proposed cryptosystem has the following features: The public‐key is a nonlinear transform from a plaintext to a ciphertext in the form of rational functions. The complexity of both encryption and decryption is O ( m 2 ), where m is the plaintext length. Digital signature is possible. The two previously proposed systems based on the matrix decomposition and the squared matrix are special cases of the proposed system. The reliability of the cryptosystem when nonlinearity is limited to the polynomial form is discussed. Next, a publickey cryptosystem based on the difficulty of solving a system of nonlinear equations with rational functions is proposed, its decryption algorithm is studied, and the conditions for this cryptosystem to ensure reliability are derived. Finally, the computational complexity of encryption and decryption, the description volume of public and secret keys, and the possibility of digital signature are studied.