A public key cryptosystem based on data complexity under quantum environment

• 作 者: WU WanQing ZHANG HuanGuo WANG HouZhen MAO ShaoWu JIA JianWei LIU JinHui
• 机 构: Computer School, Wuhan University,State Key Laboratory of Cryptology,
• 出 处: Science China(Information Sciences)
• 发表日期: 2015年11期
• 关键词: cryptosystem signature integers polynomial oracle compute difficulty notion Bool

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 22ncases) 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 22 ncases) 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 can not be solved in polynomial time even with quantum computers. Thus, 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 encrypti on and signature schemes.