Design And Cryptanalysis Of Multivariate Public Key Schemes

Public key cryptography plays an important role in secure communication. The most widely used nowadays are the number theoretical based cryptosystems such as RSA, ECC. However, due to Shor’s Algorithm, such cryptosystems would become insecure if a large quantum computer is built. Recent progress made in this area makes this threat realer than ever before. Therefore, we have a very motivation to search for public key cryptosystems that resist quantum computers attacks, this cryptosystems was called post quantum cryptosystems. Multivariate public key cryptosystems is one of the main post quantum cryptosystems. Multivariate public key cryptosystems not only can resist quantum computers attacks but also can be used in devices with limited computing capacity, such an smart cards, wireless sensor networks, and active RFID tags. We should do more research on multivariate public key cryptosystems.This thesis investigates the multivariate public key cyptosystems, and obtains the following main results:1. In the last three decades, there are several attempts to build asymmetric pubic key encryption schemes based on multivariate polynomials of degree two over a finite field. However, most of them are insecure. The common defect in many of them comes from the fact that certain quadratic forms associated with their central maps have low rank, which makes them vulnerable to the MinRank attack. Therefore, some researchers believed that multivariate public key cryptosystems only can be used to signature and authentication and can not be used to encryption. Design a security and efficient multivariate public key encryption scheme is one of challenge in multivariate public key cryptography. In this paper, we propose a new simple and efficient multivariate pubic key encryption scheme based on matrix multiplication, which does not have such a low rank property. The new scheme will be called Simple Matrix Scheme or ABC in short. We also propose some parameters for practical and secure implementation.2. In the last three decades, many multivariate public key signature schemes have been proposed but most of them are broken, except UOV-based and HFE-based signature schemes. However, the UOV signature scheme is inefficient because it has at lest 3 times more variables than polynomials, and the HFE-based signature schemes are quite slow since they need to solve a univariate equation with big degree in a finite field. Design a security and efficient multivariate public key signature scheme is one of challenge in multivariate public key cryptography. In this paper, we propose a new construction of multivariate public key signature scheme. This schemes are more efficient than UOV scheme and HFEv scheme.3. We present a total attack on the multivariate public key cryptosystems from Diophantine equations by using the embedded surface attack. Let X= (x1,..,xn) and Y= (y1,...,ym) be a pair of corresponding plaintext and ciphertext for a cryptosystem. We define an embedded surface of this cryptosystem as any polynomial equation: which is satisfied by all such pairs. Thus we can get many independent quadratic equa-tions which help to break the cryptosystem.4. We present a new algorithm called extended Linearization and Exhaustive (XLE) algorithm for solving multivariate quadratic systems with n variables and m equations over a small finite field. It is a variant of XL algorithm. We show that the time complexity of XLE algorithm is where q is the number of elements in the finite field, r and D are chosen properly,2.3766≤ ω≤3.