抗量子本原格上高效的身份基消息恢复签名方案

Quantum-resistant Efficient Identity-based Signature Scheme with Message Recovery over Primitive Lattices

随着量子算法的提出和量子计算机的快速发展,基于传统数论设计的各类数字签名方案受到严重的潜在威胁。基于格理论的身份基消息恢复签名方案是抗量子的网络信息安全认证的重要方法。然而,已有的两个格上身份基消息恢复签名方案的共同缺点是,在私钥提取阶段采用原像抽样算法,导致方案的整体运行效率较低。针对这一问题,文章在私钥提取阶段引入本原格上新的抽样算法,通过特殊的线性变换和矩阵分解简化抽样过程,并通过在身份签名阶段采用无陷门随机抽样技术,提出一个本原格上高效的身份基消息恢复签名方案。在随机预言机模型下,文章证明了方案在小整数解问题困难性条件下满足适应性选择身份和选择消息攻击下的存在性不可伪造性。理论分析表明,在保证安全性的前提下,方案在私钥提取阶段的抽样时间复杂度和抽样空间复杂度明显优于已有的两个格上身份基消息恢复签名方案,方案的整体运行效率更具有优势。

With the development of quantum algorithms and quantum computers, all kinds of digital signature schemes based on the traditional number theory are seriously threatened. The signature scheme with message recovery using lattice-based theory is an important quantumresistant method of network information security authentication. However, the two existing identity-based signature schemes with message recovery over lattices have a common drawback that these schemes are inefficient using the preimage sampleable algorithm in the private key extraction phase. To solve this problem, this paper proposes an efficient identity-based signature scheme with message recovery over the primitive lattices. In the new scheme, the private key is extracted by using a new sampling algorithm over the primitive lattices. The scheme describes a specific choice of linear transformations and matrix decompositions that simplifies the sampling process, and uses a random sampling technology without trapdoors in the identity signature stage. The scheme achieves existential unforgeability against adaptive chosen identity and message under the small integer solution assumption in the random oracle model. Compared with the prior two schemes from the lattice assumptions, the scheme has higher efficiency on the time complexity and space complexity of the sampling process in the private key extraction phase. So the scheme has the advantage of the high efficiency in the all running phase.