论文部分内容阅读
量子信息与量子计算领域中两个著名的研究成果——BB84密钥分配协议(Bennett-Brassard protocol proposed in 1984)和Shor的质因子分解算法——均对现有的密码体系产生了深远的影响。然而,更具广泛应用前景的Grover迭代算法在穷举搜索之外的密码学应用还未经充分研究。此外,另一类典型的量子迭代运算过程——量子随机行走——的非马尔科夫模式(或具有记忆的量子行走算法)在密码学领域的应用价值也未曾被探索。为了进一步补充和完善这两种迭代型量子算法在密码学方面的运用价值,以下工作分别从密码分析、密文搜索和单向函数构建三个角度给出了相应的量子密码方案。
首先,将基于Grover算法的量子极值搜索框架与量子计数算法相结合,构建了一种量子化版本的差分分析方案。该方案先利用量子计算的天然并行性加速各个候选密钥的正确明文对计数过程,然后又通过多次Grover搜索更快的过滤出具有最多正确明文对的密钥值,从而能以更少的计算复杂度完成差分分析主程序。相比原有的经典差分分析过程,量子差分分析在运算效率上具有二次规模的提升,且在存储复杂度上也有较大的优势。
其次,以基于量子一次一密的量子同态计算为前提,设计了一种面向密文叠加态的量子同态搜索协议,并通过小规模的数值模拟验证了该协议的有效性和正确性。该协议首次将Grover搜索算法与基于量子一次一密的量子同态计算协议相结合,并对数据项中的搜索区域实施双重加密,从而能够使量子服务器在无法得知明文数据以及相应的原始搜索条件的情况下为没有足够量子计算能力的客户端搜索出目标数据项的密文索引值。由于Grover搜索线路包含指数规模的T门,其同态运算仅能以交互或高通信复杂度的方式来执行;为了减小客户端的通信负担,该协议将同态搜索过程中的通信和密钥更新任务交给一个增加了少量量子操作能力的可信第三方完成,从而在保证完美安全性的条件下将客户端从繁琐的量子搜索细节中解放出来。此外,论文还构建了一个与量子同态搜索相对的,面向不包含T门的Clifford量子线路的同态运算协议。该协议将密钥更新交由服务器同态地执行,而对应于同态密钥更新的简化的经典密钥更新则由客户端按照服务器提供的指令编码来完成。由于输入量子态和数据加密密钥均由满足完美安全性的量子一次一密来保护,且同态计算过程不涉及交互,而简化的经典密钥更新的复杂度仅为Clifford线路的输入长度的多项式规模,所以此Clifford同态运算协议既满足量子密码方案常有的绝对安全性又具备同态加密所要求的紧凑性。
然后,以具有一步记忆的一维量子行走过程为基础,定义了一种具有两步记忆的一维量子行走模型,并利用路径积分法和组合学理论详细地推导出了这种新的量子行走过程的量子幅表达式。尽管具有两步记忆的量子行走以具有一步记忆的量子行走为扩展原型,但其所形成的概率分布并不具备一步记忆量子行走的局域性。最后,以具有一步记忆和两步记忆的一维量子行走模型为基础,构造了一种新的量子哈希函数,并针对该函数执行了哈希测试。测试结果显示,输入消息中单个比特的改变会平均导致输出哈希值中半数以上的比特发生变化,说明这种新的量子哈希函数具有较好的消息敏感性。
首先,将基于Grover算法的量子极值搜索框架与量子计数算法相结合,构建了一种量子化版本的差分分析方案。该方案先利用量子计算的天然并行性加速各个候选密钥的正确明文对计数过程,然后又通过多次Grover搜索更快的过滤出具有最多正确明文对的密钥值,从而能以更少的计算复杂度完成差分分析主程序。相比原有的经典差分分析过程,量子差分分析在运算效率上具有二次规模的提升,且在存储复杂度上也有较大的优势。
其次,以基于量子一次一密的量子同态计算为前提,设计了一种面向密文叠加态的量子同态搜索协议,并通过小规模的数值模拟验证了该协议的有效性和正确性。该协议首次将Grover搜索算法与基于量子一次一密的量子同态计算协议相结合,并对数据项中的搜索区域实施双重加密,从而能够使量子服务器在无法得知明文数据以及相应的原始搜索条件的情况下为没有足够量子计算能力的客户端搜索出目标数据项的密文索引值。由于Grover搜索线路包含指数规模的T门,其同态运算仅能以交互或高通信复杂度的方式来执行;为了减小客户端的通信负担,该协议将同态搜索过程中的通信和密钥更新任务交给一个增加了少量量子操作能力的可信第三方完成,从而在保证完美安全性的条件下将客户端从繁琐的量子搜索细节中解放出来。此外,论文还构建了一个与量子同态搜索相对的,面向不包含T门的Clifford量子线路的同态运算协议。该协议将密钥更新交由服务器同态地执行,而对应于同态密钥更新的简化的经典密钥更新则由客户端按照服务器提供的指令编码来完成。由于输入量子态和数据加密密钥均由满足完美安全性的量子一次一密来保护,且同态计算过程不涉及交互,而简化的经典密钥更新的复杂度仅为Clifford线路的输入长度的多项式规模,所以此Clifford同态运算协议既满足量子密码方案常有的绝对安全性又具备同态加密所要求的紧凑性。
然后,以具有一步记忆的一维量子行走过程为基础,定义了一种具有两步记忆的一维量子行走模型,并利用路径积分法和组合学理论详细地推导出了这种新的量子行走过程的量子幅表达式。尽管具有两步记忆的量子行走以具有一步记忆的量子行走为扩展原型,但其所形成的概率分布并不具备一步记忆量子行走的局域性。最后,以具有一步记忆和两步记忆的一维量子行走模型为基础,构造了一种新的量子哈希函数,并针对该函数执行了哈希测试。测试结果显示,输入消息中单个比特的改变会平均导致输出哈希值中半数以上的比特发生变化,说明这种新的量子哈希函数具有较好的消息敏感性。