赵 博, 秦贵和, 赵永哲, 杨文迪

(1.吉林大学 计算机科学与技术学院，长春 130012;2.华东师范大学 计算机科学与软件工程学院，上海 200062)

0 引 言

1976年，Diffie和Hellman[1]发表了著名文章《密码学的新方向”，文章引入了“公钥密码”的概念，并提出基于“陷门单向函数(Trapdoor one-way function)”来构造公钥密码的思想。不久，第一批公钥密码方案便被提了出来，它们分别是Merkle和Hellman基于背包问题的MH密码体制[2]以及Rivest、Shamir和Adelman基于整数分解问题的RSA密码体制[3]。随后Rabin、ElGamal、ECC等公钥密码体制也相继问世。

进入到21世纪，现有公钥密码(RSA、ElGamal、ECC等)日益受到量子计算的威胁[4,5]，为了应对挑战，国际密码学界提出了“后量子密码学(Post-quantum cryptography，PQC)”的新学科方向。PQC的主要目标便是研究能抵抗量子计算的公钥密码(Quantum resistant public key cryptography)，目前主要基于量子计算机不擅长计算的数学难题(比如NPC问题)来设计密码，该类密码主要有如下几个研究方向：基于格上困难问题的密码[6]、基于纠错码译码问题的密码[7]、基于多变量的密码[8]、基于辫子群(Braid Group)的密码[9]以及基于背包问题的密码[2,10]。

但目前所提出的抗量子计算公钥密码方案中的绝大多数都已被证明是不安全的。尽管不断有新方案被提出，但从构造方法来看，这些方案不外乎两大类：其一是基于“陷门单向函数”，这类公钥密码占绝大多数，其关键在于如何设计陷门。其二则是基于“非对称密钥交换”，其关键在于如何实现非对称的密钥交换，这往往要用到“单向函数”。一般说来，寻找单向函数要比寻找陷门单向函数容易得多，但单向函数不可逆，故不能直接用来实现公钥密码。……