基于量子计算的Hash安全性研究
发布时间：2020-12-28 23:38
Hash函数在很多密码安全协议中起着非常重要的作用,它作为数字签名的基石,不仅用于检测网络通信信息是否被篡改,而且是保障数字指纹,身份认证等多种密码系统安全的关键技术。目前针对Hash函数的分析都是基于数论难题来进行分析设计的,均是在经典计算的基础上对Hash函数进行的,无法评估其对抗量子计算机攻击的能力,探索量子计算在Hash函数中的安全研究十分重要。随着量子信息技术的发展,基于量子特性,量子信息技术可以突破现有信息极速的物理极限,在信息处理速度,信息安全性,计算能力等方面将会发挥出极大的作用。量子信息技术为信息科学的发展开拓新原理,新方法,将会对人类社会产生深刻的影响。基于量子计算进行密码分析的研究不仅扩展了量子计算和量子算法的应用范围和价值,同时也为现代密码协议在后量子密码中的应用提供研究价值,对未来的信息安全和量子计算机的发展都有着十分重要的意义和价值。论文着重研究了量子算法对Hash函数的抗原像性和抗碰撞性问题。本文首先分析了量子线路的组成原理,并根据Hash函数所需要的逻辑操作设计相对应的量子门电路,并给出对应的线路图和仿真验证。在分析Hash函数的抗原像性上,对现有的Gr...
【文章来源】：深圳大学广东省
【文章页数】：81 页
【学位级别】：硕士
【部分图文】：
同时计算f(0)和f(1)的量子线路
基于量子计算的Hash安全性研究11图2-2同时计算f(0)和f(1)的量子线路图2-2给出了整个量子操作的线路图[53]。数据寄存器的初始叠加状态()0+12，可以由状态0经过H门变换后得到，于是应用fU门变换可以得到：0,(0)1,(1)=2ffψ+(2-9)从状态ψ中可以看到该状态同时包含f(0)和f(1)，看起来似乎同时对x的两个值进行了计算。与经典计算机不同的是，在经典计算机中需要运行f(x)函数对应的电路两次，而在量子计算机中，只需要运行一次量子线路即可同时计算出两个x对应的函数值，通过测量目标寄存器即可得到。2.3量子算法2.3.1Deutsch算法在1985年，Deutsch提出了第一个体现量子并行计算的量子算法Deutsch算法[52]。该算法解决的问题是：给定一个布尔类型的函数f(x):{0,1}→{0,1}，需要确定该函数是平衡函数还是常数函数。在经典计算机中，需要计算两次f(x)的值才能确定该函数的类型，即如果f(1)=f(0)=1/0，则判定该函数是常数函数，当f(1)=0,f(0)=1或者f(1)=1,f(0)=0，则判定该函数是平衡函数。但是Deutsch算法中，只需要经过一次函数计算就能得到这个函数的全局性，即该函数的类型。该算法的量子线路图如图所示[53]：图2-3Deutsch量子线路图
基于量子计算的Hash安全性研究132.3.2Deutsch-Jozsa算法Deutsch-Jozsa算法是Deutsch和Jozsa在1992年提出来的，该算法是对原始Deutsch算法在更高维度的拓展[30]。该算法的问题定义为：给定一个n比特的函数():{0,1}{0,1}nfx→，该函数如果是平衡函数，则有一半的输入输出结果为0，另一半输出结果为1，若是常数函数，则所有输出结果为0或1。在经典计算机中，在最坏情况下，我们需要计算2/21n+次才能确定函数f(x)是平衡函数还是常数函数，该问题是Deutsch问题由1个比特到n个比特的拓展。相应的，Deutsch-Jozsa算法能够通过一次函数就能判定函数f(x)的性质，这相比于经典算法是一个指数级的加速。我们给出该算法量子线路图如图所示[53]：图2-3Deutsch-Jozsa算法量子线路图该算法的初始输入状态可看做两个寄存器组成，初始状态为0的数据寄存器和初始状态为1的辅助寄存器，初始化状态可以表示为：001nψ=(2-16)对初始状态应用Hn1+变换，可以得到状态1ψ为：1{0,1}0122nnxxψ∈=∑(2-17)状态1ψ经过fB酉操作后，我们将得到状态3ψ表示为：
本文编号：2944581
【文章来源】：深圳大学广东省
【文章页数】：81 页
【学位级别】：硕士
【部分图文】：
同时计算f(0)和f(1)的量子线路
基于量子计算的Hash安全性研究11图2-2同时计算f(0)和f(1)的量子线路图2-2给出了整个量子操作的线路图[53]。数据寄存器的初始叠加状态()0+12，可以由状态0经过H门变换后得到，于是应用fU门变换可以得到：0,(0)1,(1)=2ffψ+(2-9)从状态ψ中可以看到该状态同时包含f(0)和f(1)，看起来似乎同时对x的两个值进行了计算。与经典计算机不同的是，在经典计算机中需要运行f(x)函数对应的电路两次，而在量子计算机中，只需要运行一次量子线路即可同时计算出两个x对应的函数值，通过测量目标寄存器即可得到。2.3量子算法2.3.1Deutsch算法在1985年，Deutsch提出了第一个体现量子并行计算的量子算法Deutsch算法[52]。该算法解决的问题是：给定一个布尔类型的函数f(x):{0,1}→{0,1}，需要确定该函数是平衡函数还是常数函数。在经典计算机中，需要计算两次f(x)的值才能确定该函数的类型，即如果f(1)=f(0)=1/0，则判定该函数是常数函数，当f(1)=0,f(0)=1或者f(1)=1,f(0)=0，则判定该函数是平衡函数。但是Deutsch算法中，只需要经过一次函数计算就能得到这个函数的全局性，即该函数的类型。该算法的量子线路图如图所示[53]：图2-3Deutsch量子线路图
基于量子计算的Hash安全性研究132.3.2Deutsch-Jozsa算法Deutsch-Jozsa算法是Deutsch和Jozsa在1992年提出来的，该算法是对原始Deutsch算法在更高维度的拓展[30]。该算法的问题定义为：给定一个n比特的函数():{0,1}{0,1}nfx→，该函数如果是平衡函数，则有一半的输入输出结果为0，另一半输出结果为1，若是常数函数，则所有输出结果为0或1。在经典计算机中，在最坏情况下，我们需要计算2/21n+次才能确定函数f(x)是平衡函数还是常数函数，该问题是Deutsch问题由1个比特到n个比特的拓展。相应的，Deutsch-Jozsa算法能够通过一次函数就能判定函数f(x)的性质，这相比于经典算法是一个指数级的加速。我们给出该算法量子线路图如图所示[53]：图2-3Deutsch-Jozsa算法量子线路图该算法的初始输入状态可看做两个寄存器组成，初始状态为0的数据寄存器和初始状态为1的辅助寄存器，初始化状态可以表示为：001nψ=(2-16)对初始状态应用Hn1+变换，可以得到状态1ψ为：1{0,1}0122nnxxψ∈=∑(2-17)状态1ψ经过fB酉操作后，我们将得到状态3ψ表示为：
本文编号：2944581
本文链接：https://www.wllwen.com/kejilunwen/xinxigongchenglunwen/2944581.html
