基于矩阵作用问题的公钥密码体制抗量子攻击安全性分析

作     者：黄华伟 HUANG Huawei

作者机构：贵州师范大学数学科学学院贵州贵阳550025 

出 版 物：《通信学报》 (Journal on Communications)

年 卷 期：2023年第44卷第3期

页      面：220-226页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：国家自然科学基金资助项目(No.61462016) 贵州省科学技术基金资助项目(黔科合基础ZK一般313号)。 

主　　题：Shor算法 隐藏子群问题 半群作用问题 公钥密码 抗量子攻击 

摘      要：半群作用问题作为离散对数问题的推广,在公钥密码的设计中有着重要应用。通过分析基于整数矩阵乘法半群在交换群直积上的作用问题的公钥密码体制,将矩阵看作直积元素的指数,这类矩阵作用具有类似群的指数运算法则。首先证明了若矩阵作用是单射或隐藏子群的生成元个数小于或等于矩阵阶的平方,则这类矩阵作用问题可在多项式时间归约为矩阵加法群直和的隐藏子群问题。其次证明了交换矩阵作用问题一定可在多项式时间归约为矩阵加法群直和的隐藏子群问题。因此基于这类矩阵作用问题的公钥密码体制无法抵抗量子攻击,该结论对抗量子攻击的公钥密码设计有理论指导意义。