基于编码的数字签名综述

宋永成，黄欣沂，伍玮，陈海霞

基于编码的数字签名综述

宋永成1,2，黄欣沂1，伍玮3，陈海霞1

（1. 福建师范大学计算机与网络空间安全学院福建省网络安全与密码技术重点实验室，福建 福州 350117；2. 密码科学技术国家重点实验室，北京 100878；3. 福建师范大学数学与统计学院，福建 福州 350117）

量子计算理论和实践的快速发展导致基于传统数论困难问题的密码安全性存在很大不确定性。编码困难问题是公认的NP完全问题，求解复杂度呈指数级增长，且目前未发现量子计算对基于编码密码算法的威胁。因此，基于编码的密码算法有望抵抗量子算法攻击，是抗量子密码的主流方向之一。设计安全高效的基于编码的数字签名一直是公开问题。多年来，国内外学者使用经典方法和新方法构造基于编码的数字签名，但现存的构造存在安全性弱或性能差的不足。对当前基于编码的数字签名进行了综述，分析和评价了各类基于编码的数字签名，并指出未来的研究方向。

抗量子密码；基于编码的密码学；数字签名；身份认证

1 引言

RSA、ECDSA等经典密码算法的安全性主要基于分解大整数、求解离散对数等传统困难问题。但随着量子计算理论和实践的快速发展，基于传统困难问题密码算法的安全性存在很大不确定性。例如，Shor量子算法[1]可以有效求解离散对数问题和分解大整数问题。Grover量子算法[2]可以加速（最多二次方）求解困难问题。因此，研究安全高效的抗量子密码算法成为学术界和工业界的共识。……