Research On Theory Of Posting Quantum Computational Cryptography Based On Data Complexity

At presently, the mathematical hard problem in the public key cryptosystems, including RSA cryptography, Discrete logarithm cryptography, elliptic curve cryptog-raphy, are the factorization problem and the discrete logarithm problem. The Shor algorithm makes the cryptosystems, which based on large integer factorization and dis-crete logarithm, is no longer safe. But there is no effectively quantum algorithm to solve some problems on non-abelian groups at now. In 2000 Ko-Lee proposes a public cryp-tography based on brain group. In 2002 Magliveras proposes a no message expansion cryptographic system based on non abelian group. In 2009 Lempken proposes a new public-key cryptosystems, based on covers and logarithmic signatures of non-abelian groups, and so on. But, the security level and efficiency of the exiting schemes have not reached the level of classical cryptography, which needs further study.The emergence of quantum computing is a threat for the traditional public key cryptography based on the difficulty problem in mathematics, and it is also a difficult task to designing a public key cryptography for posting quantum computation. It is known that computational complexity theory is one of the theoretical foundations of public key cryptography. But, the most commonly design methods are based on time complexity. Because the quantum computer has exponential computing power, it is difficult to posting quantum attack by increasing the complexity of the computation time. Therefore, it is necessary to adding some new difficulties. Combining the time complexity and space complexity to posting the quantum attack for ensuring the safety of the public key cryptosystem.According to the above research background, this paper studies the design theory of public key cryptography which can post quantum computation. In cryptography, people design some public key cryptosystems based on the time complexity. We propose a method to designing a public key cryptosystems based on the combinations of data complexity, time complexity and space complexity. The concept of data complexity is firstly used in the differential attacks on DES. The key of differential attacks is the number of plaintext and ciphertext pairs. In quantum environment, we present some NPC difficult problems. We propose two public key cryptosystems based on these problems, and one of these schemes can be used for signing. The presented schemes have nested structures, the traditional public key cryptosystems RSA, ELGamal, ECC can be is nested into our schemes. This can be combined with the traditional cryptosystems, and it can inherit the research results of the traditional public key cryptography.In addition, this paper presents an efficient quantum algorithm for finding the linear structure and cycle of linear transformation. As an application, we present quantum algorithm for finding the linear structure of the MD hash function, and finding the cycle of linear transformation based on finite associative algebra.To sum up, the main conclusions of this paper are as follows:1, The quantum complexity theory is summarized, and the concept of data com-plexity is presented in this paper.2, In this paper, we propose an efficient quantum algorithm to calculate the period of linear transformation. As an application, we point out that the MOR public key cryptography is not safe based on finite associative algebra. In this paper, we propose an efficient quantum algorithm to calculate the linear structure of the most Boolean functions. The linear structure of the MD hash function is calculated by using the extended algorithm.3, We present some NPC problems, and propose a public key cryptosystem for posting the quantum computation. Then, we analysis the security of this scheme using the Grover algorithm and Shor algorithm. It shows that the cryptosystem is safe in computer and quantum computer environments. In this paper, the cryptosystem can be as a security "shield". The traditional public key cryptosystem can be use in quantum computing, through nesting it with the traditional public key cryptosystems.4, We present a public key cryptosystem based on the algebraic multiplication table.