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

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