论文部分内容阅读
基于格的公钥密码体制被广泛认为能抵抗量子攻击，目前是后量子时代公钥密码体制的主要候选之一，而格算法作为格密码中的重要组成部分，在密钥生成，加解密以及安全性分析方面发挥着重要作用。因此对格算法的研究具有重大的理论价值和现实意义。 在本文中，我们首先给出了一个计算整数矩阵Hermite标准型的新算法。Hermite标准型作为整数矩阵的一种标准型，不仅在理论上，而且在算法中都有非常广泛的应用。例如，我们能用Hermite标准型来计算整数矩阵的核空间和像空间，求整数格的交和求解整数规划问题等。特别地，Hermite标准型在基于格的公钥密码体制中被建议用作公钥，以增加效率和安全性。但是，目前求解Hermite标准型的算法在实际中运行比较慢。因此寻找实际中运行较快的计算Hermite标准型的算法有着重大意义。我们的算法与目前计算Hermite标准型理论上最快的算法有着相同的时间复杂度。 我们的第二项工作是提出了整格的两类特殊的近似正交格基，并给出了相应的格基约化算法。格基约化算法被广泛地应用在求解格的计算问题上，其目的是寻找某些近似正交的格基。我们发现，整格存在两类特殊的近似正交格基:对于秩大于1的整格，存在这样一组格基，满足任意两个格基向量之间的夹角都在π/3到2π/3之间;而对于秩大于2的整格，存在这样的格基，我们总可以将该格基分成两个元素个数大致相等的集合，使得每个集合中的格向量两两正交。我们同时给出了相应的算法来计算这两类格基。与其他的格基约化算法相比，我们的算法通常能输出长度更短的格基。 最后，我们对使用Babai的最近平面算法的GGH型签名体制提出了一个密钥恢复攻击。Nguyen和Regev等人在2006年欧密会上对使用round-off算法的GGH签名体制和NTRUSign给出了一个成功的密钥恢复攻击。但是他们并没有进一步分析使用最近平面算法的GGH型签名体制的安全性。对于这类体制的安全性，之前并没有一个确定的结论。我们对这类体制成功给出了一个密钥恢复攻击。理论分析和实验结果表明使用最近平面算法的GGH型签名体制也是不安全的。