论文部分内容阅读
量子计算因其具有经典计算无可比拟的优势受到了广泛的关注,其发展对当今密码学的安全构成了威胁。众所周知,Shor算法可以在多项式时间内破解多种公钥密码方案,如RSA和ECC。近些年来,一些应用于对称密码体制分析中的量子算法得到了研究,如Grover算法、Simon算法、Bernstein-Vazirani(BV)算法,以及它们的衍生算法。本文主要研究两种应用于对称密码体制分析的量子算法:量子周期查找算法和量子布尔函数代数正规型学习算法。量子周期查找算法已经被广泛用于对称密码体制分析,如3阶Feistel结构和Even-Mansour结构可以通过利用量子周期查找算法在多项式时间内被打破。本文中,首先提出了一种仅需要O(n)次量子查询的求解向量值函数周期的新算法,该算法以BV算法作为子例程的其中一步。然后,将该算法与Simon算法进行了比较。当算法应用于某些场景时,如Even-Mansour结构和满足Simon的允诺的向量值函数等,上述算法在量子存储和时间的权衡方面比Simon算法效率更高。此外,结合了该算法与Grover算法,用于FX结构上的密钥恢复攻击。与Leander和May在17年的亚密会上提出的Grover-Meets-Simon算法相比,新算法需要较少的量子存储。线性布尔函数的代数正规型可以直接用BV算法恢复,而对于更一般的布尔函数的代数正规型的量子学习算法目前相关研究还很少。本文研究了二次布尔函数代数正规型的量子学习算法。首先,求得了二次布尔函数中变量的影响力,使BV算法能够在其上运行。然后,研究了将二次布尔函数中的一些变量取反或置零后的函数,展示了其量子oracle的构造方法。接着,引入了“团”的概念以把出现在二次项中的变量分组,并研究了团的性质。此外,给出了一种利用纠缠度量检查退化变量的方法。在此基础上,提出了一系列二次布尔函数代数正规型的学习算法。特别地,所提出的最优算法相比于经典算法提供了O(n)的加速,且量子查询次数与退化变量无关。