P vs. NP问题研究状态及其对密码学的意义

介绍P vs.NP问题的研究状态以及P vs.NP问题的研究对于密码学的意义。主要内容包括关于证明P≠NP的主要研究方法和相关工作,关于证明P=NP的主要研究方法和相关工作,关于求解NP完全问题的相关方法,以及P vs.NP问题研究与密码学的关系。由于现代密码学建立在未知密钥情况下不存在有效的算法将明文消息从密文中提取出来的假定之上,因此安全加密算法存在的一个必要条件是P≠NP。如果P=NP,根据Cook的观点,现代密码体制将崩溃。依据P=NP的假定,给出一个可能的密码分析模型。

The Status of the P Versus NP Problem and its Relationship with Cryptology

This paper introduces the status of the P versus NP problem and its impact on cryptology,including the methods and related work about proving P≠NP and P=NP,as well as how to solve NP-complete problems.It is also discussed the relations between the P versus NP problem and cryptology.Modern cryptography is based on the assumption that there＇s not an effective algorithm to induce the plaintexts from the ciphertexts if people knowing nothing about decryption key.So the existence of the safe encryption algorithm depends on P≠NP,and the consequence of a feasible proof that P=NP is that complexity-based cryptography would fail.Assuming P=NP,we shall give a possible model of cryptanalysis.