Ergodic Matrices And Its Applications In Public Key Cryptography

Security is one of the most important problems in the communication and information system, while the cryptography is the basis for the security. The principal of public-key cryptography is exchanging information between parties without requiring a secure channel. Public-key systems are used for key exchange or distribution in symmetric cryptosystems. Except for the key exchange, other applications of public-key cryptography are digital signature and data authentication schemes. The security of cryptosystems widely used at the moment is based on the difficulty of solving three kinds of problems: the RSA scheme relis on the difficulty of factoring large integers, the EIGamal scheme is based on the discrete logarithms problem, while the hardness of solving elliptic curve discrete logarithms provide the basis for the Elliptic Curves scheme. However, the potential weaknesses of existing public key schemes are emerging. In particular techniques for factorization and solving discrete logarithm improve continually. For example, polynomial time quantum algorithms can be used to solve all above problems. So, research on new schemes based on other classes of problems is necessary. Beginning with the ergodic matrices, we have studied the property of ergodic matrices and its applications in public key cryptography. The main contents and conclusions in this dissertation can be summarized as follows:â… .The concept of ergodic matrices and its propertyThe ergodic matrices has a maximal generating set, and the result of multiplying a nonzero column vector on the left or multiplying a nonzero row vector on the right by the ergodic matrix is thoroughly divergent. Let be ergodic matrices, for , does corresponding transformatin to every column of A, while does corresponding transformatin to every row of A_。So, m₁ Am₂ may"disarrange"every element of A;This process can be repeated many times, i.e. , to get a complex transformation of A. Meanwhile,As a typical 1-ring, , its multiplication of matrices is noncommutative, but its multiplication of elements in is commutative. So, the property of commutative and noncommutative both exist in it. All these property of ergodic matrices can be used to construct the difficult problems, which is the foundation of public cryptography.â…¡. The difficult problem based on the ergodic matricesThe construction of difficult problems is very impotant, and directly related to the security of the public-key cryptosystem. In this paper, first, we proved that the bisectional multivariate quadratic equations problem on finite fields is NP-Complete; then a new diffuicult problem named two-side ergodic matrices exponentiation (TEME) is proposed, which is proved at least NP-Complete. Through analyzing we found, the difficulty of TEME is related to the choice of the middle matrix, when the middle matrix is a strong matrix, the TEME problem is difficult. In addition, based on the TEME problem, we proposed two one-way functions that can be used to construct public-key cryptosystem.â…¢. The applications of ergodic matrices in public-key cryptosystem(1) Public key encryption scheme is very important in public-key cryptosystem. Public key encryption schemes normally give two algorithms, one for encrypting which involves the user's public key, and one for decrypting which involves the user's secret or private key. The security of the public key encryption scheme can be divided into three kinds according to the target: one-way, indistinguishability and non-malleability. Now, the indistinguishability against adaptively chosen ciphertext attack (IND-CCA2) is essential in designing public key encryption schemes. To prove a public-key encryption scheme is IND-CCA2 secure, it's security should be strictly reduced to the assumption that it is based on. The model of proved security can be divided into two categories, one category is the random oracle model, and the other is the standard model. In this paper, we present a new public key encryption scheme based on ergodic matrices, and proved it is IND-CCA2 secure in the standard model.(2) Digital signature is an important application of public-key cryptosystem. A digital signature scheme is a type of asymmetric cryptography used to simulate the security properties of a handwritten signature on paper. Digital signature schemes normally give two algorithms, one for signing which involves the user's secret or private key, and one for verifying signatures which involves the user's public key. The output of the signature process is called the "digital signature." Attack on digital signature scheme in accordance with the purpose from the degree of difficulty to easy can be divided into: complete break, universal forgeability, selective forgeability and existential forgeability. Attack on digital signature scheme according to the computational resources an adversary can access is divided into: known public key attack, known message attack and adaptive chosen-message attack. Now, the existential unforgeability against adaptive chosen-message attack (EUF-CMA) is essential in designing digital signature schemes. To prove a digital signature scheme is EUF-CMA secure, it's security should be strictly reduced to the assumption that it is based on. The model of proved secure digital signature scheme can also be divided into two categories, one category is the random oracle model, and the other is the standard model. In this paper, we present a new digital signature scheme based on ergodic matrices, and proved it is EUF-CMA secure based on the TEME problem in the random oracle model.(3) Generally, key exchange protocols allow 2 parties who share no secret information to compute a sectect key via public communication. Generally, key exchange protocols allow 2 parties who share no secret information to compute a secret key via public communication. Authenticated key exchange (AKE) not only allows parties to compute the shared key but also ensures authenticity of the parties. For AKE protocols, there are a surprisingly large number of possible attack scenarios and there is no single security definition. A AKE protocol is secure only if it satisfy all these propertities: resistance to a key-compromise impersonation attack, resistance to a reflection attack, resistance to a replay attack, known-key security, session key security and perfect forward secrecy. In this paper, we present a new AKE protocol based on ergodic matrices, and we prove that our protocol meet the security attributes under the assumption that TEME problem is secure.