后量子密码替代传统密码算法

郁　昱

上海交通大学电子信息与电气工程学院

特别研究员

1　经典密码算法到后量子密码的演化

1.1　传统密码算法不具有量子安全性

传统的经典密码的安全性一般基于标准的图灵机模型和冯诺依曼体系结构的计算机，目前采用的密码（特别是公钥密码）算法标准大多基于以离散对数（Discrete Logarithm）、大数分解（RSA）、椭圆曲线（Elliptic Curves Cryptography）等为代表的数论困难问题。早在20世纪90年代初，数学家Peter Shor就提出了量子模型（见图1），多项式时间内有效解决针对离散对数。随着量子计算机技术的发展和日益成熟，基于以上这些数论问题的传统密码算法（如密钥协商协议和公钥加密方案等）将逐步被后量子密码（post-quantum cryptography）算法替代。

图1　Shor算法的量子部分（来自Wikipedia）

1.2　新的后量子安全的密码算法

后量子密码是以格密码、学习困难问题（如LWE、LPN等）为代表的新型可抵抗量子计算机分析的密码算法（见图2）。这些新型密码算法不仅支持信息保密性的保护，而且具有高效、并发、支持全同态加密（fully homomorphic encryption）和不经意传输（oblivious transfer）的功能，料将为数据库隐私保护、安全多方计算等密码学应用提供理论支持和技术保障。

图2　D-Wave公司制造的颇具争议的所谓的量子计算机（来自D-Wave Systems官网）

2　应用意义与前景

目前Diffie-Hellman、RSA等传统算法广泛应用于互联网保密通信、磁盘加密存储、智能安全芯片等信息保密性保护的应用，其被后量子密码算法替代将不是一蹴而就的过程。现有的互联网协议（如SSL / TLS、IPSec等）的新版本将逐步加入后量子密码算法作为选项，而传统的密码算法将随着协议的版本更新渐进式地淡出信息保密存储和通讯等密码应用。新的加密算法将标准化成为新的国际和国家标准，与之同步的是新的密码产品与芯片的更新换代。同时，LPN、LWE等后量子算法轻量级的特性，也将进一步提高未来密码算法的实现效率。目前，全同态加密、不可区分混淆等密码应用效率相对较低，引入后量子安全的困难问题有助于进一步解决这些算法实现的效率问题，为最终实用化奠定基础。我国密码学工作者也将为后量子密码算法的更新换代做出更多应有的贡献。