A public key cryptosystem based on data complexity under quantum environment  

作　　者：WU WanQing ZHANG HuanGuo WANG HouZhen MAO ShaoWu JIA JianWei LIU JinHui 

机构地区：[1]Computer School, Wuhan University [2]State Key Laboratory of Cryptology

出　　处：《Science China(Information Sciences)》2015年第11期44-54,共11页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.61303212,61303024,61170080);State Key Program of National Natural Science of China(Grant Nos.61332019,U1135004);Major State Basic Research Development Program of China(Grant No.2014CB340600);Foundation of Science and Technology on Information Assurance Laboratory(Grant No.KJ-14-002);Fundamental Research Funds for the Central Universities(Grant No.2012211020213)

摘　　要：Since the Shor algorithm showed that a quantum algorithm can efficiently calculate discrete logarithms and factorize integers, it has been used to break the RSA, EIGamal, and ECC classical public key cryptosystems. This is therefore a significant issue in the context of ensuring communication security over insecure channels. In this paper, we prove that there are no polynomial-size quantum circuits that can compute all Boolean functions（of which there are 2^2n cases） in the standard quantum oracle model. Based on this,we propose the notion of data complexity under a quantum environment and suggest that it can be used as a condition for post-quantum computation. It is generally believed that NP-complete problems cannot be solved in polynomial time even with quantum computers. Therefore, a public key cryptosystem and signature scheme based on the difficulty of NP-complete problems and the notion of data complexity are presented here. Finally,we analyze the security of the proposed encryption and signature schemes.Since the Shor algorithm showed that a quantum algorithm can efficiently calculate discrete logarithms and factorize integers, it has been used to break the RSA, EIGamal, and ECC classical public key cryptosystems. This is therefore a significant issue in the context of ensuring communication security over insecure channels. In this paper, we prove that there are no polynomial-size quantum circuits that can compute all Boolean functions（of which there are 2^2n cases） in the standard quantum oracle model. Based on this,we propose the notion of data complexity under a quantum environment and suggest that it can be used as a condition for post-quantum computation. It is generally believed that NP-complete problems cannot be solved in polynomial time even with quantum computers. Therefore, a public key cryptosystem and signature scheme based on the difficulty of NP-complete problems and the notion of data complexity are presented here. Finally,we analyze the security of the proposed encryption and signature schemes.

关 键 词：public key cryptography information security NP-complete problem complexity theory quantum computation 

分 类 号：TN918.4[电子电信—通信与信息系统]