面向格基密码体制的高效硬件实现研究综述*
2021-03-03何诗洋李凤华
何诗洋, 李 晖, 李凤华,3
1. 大数据安全教育部工程研究中心, 西安 710126
2. 西安电子科技大学网络与信息安全学院, 西安 710126
3. 中国科学院信息工程研究所, 北京 100093
1 引言
随着人类计算能力的迅速提升, 特别是量子计算机的不断突破(如中国科技大学潘建伟科研团队构建量子计算原型机“九章”[1]等), 基于大质因数分解、离散对数困难问题的传统密码体制, 如公钥加密、数字签名、密钥交换等方案的安全性都将面临巨大威胁和挑战[2]. 这种威胁和挑战一方面体现在计算能力增强导致暴力破解成功率提升, 另一方面, 量子计算机和量子算法[3,4]能够在多项式时间内解决传统密码体制依赖的困难问题.
面对这一严峻形势, 研究后量子密码(post-quantum cryptography, PQC) 显得极为紧迫和重要. 目前, 能够抵抗量子攻击的主流密码体制有[5]: 基于编码的密码体制(code-base cryptography)、基于哈希函数的密码体制(hash-based cryptography)、基于格的密码体制(lattice-based cryptography)、多变量密码体制(multivariate cryptography) 等.
相较于其他后量子密码体制, 基于格的密码体制具有明显优势. 主要体现在: 第一, Ajtai 等人[6,7]证明了格中某些平均情况下的困难问题与NP 困难问题的难度等价, 具有较强的安全性[8]. 第二, 基于格的密码体制不仅能够应用于传统的安全场景如哈希函数[9]、公钥加密[10]、数字签名[11]、密钥交换[12]等, 而且还具有良好的同态特性[13–15]. 第三, 基于格的密码体制主要涉及矩阵向量之间的运算, 易于计算和实现. 第四, 基于格的密码体制与硬件实现相结合, 可部署场景广泛, 既可应用于资源丰富的……
