基于量子計算的Hash安全性研究
發(fā)布時間:2020-12-28 23:38
Hash函數(shù)在很多密碼安全協(xié)議中起著非常重要的作用,它作為數(shù)字簽名的基石,不僅用于檢測網(wǎng)絡通信信息是否被篡改,而且是保障數(shù)字指紋,身份認證等多種密碼系統(tǒng)安全的關鍵技術。目前針對Hash函數(shù)的分析都是基于數(shù)論難題來進行分析設計的,均是在經(jīng)典計算的基礎上對Hash函數(shù)進行的,無法評估其對抗量子計算機攻擊的能力,探索量子計算在Hash函數(shù)中的安全研究十分重要。隨著量子信息技術的發(fā)展,基于量子特性,量子信息技術可以突破現(xiàn)有信息極速的物理極限,在信息處理速度,信息安全性,計算能力等方面將會發(fā)揮出極大的作用。量子信息技術為信息科學的發(fā)展開拓新原理,新方法,將會對人類社會產(chǎn)生深刻的影響。基于量子計算進行密碼分析的研究不僅擴展了量子計算和量子算法的應用范圍和價值,同時也為現(xiàn)代密碼協(xié)議在后量子密碼中的應用提供研究價值,對未來的信息安全和量子計算機的發(fā)展都有著十分重要的意義和價值。論文著重研究了量子算法對Hash函數(shù)的抗原像性和抗碰撞性問題。本文首先分析了量子線路的組成原理,并根據(jù)Hash函數(shù)所需要的邏輯操作設計相對應的量子門電路,并給出對應的線路圖和仿真驗證。在分析Hash函數(shù)的抗原像性上,對現(xiàn)有的Gr...
【文章來源】:深圳大學廣東省
【文章頁數(shù)】:81 頁
【學位級別】:碩士
【部分圖文】:
同時計算f(0)和f(1)的量子線路
基于量子計算的Hash安全性研究11圖2-2同時計算f(0)和f(1)的量子線路圖2-2給出了整個量子操作的線路圖[53]。數(shù)據(jù)寄存器的初始疊加狀態(tài)()0+12,可以由狀態(tài)0經(jīng)過H門變換后得到,于是應用fU門變換可以得到:0,(0)1,(1)=2ffψ+(2-9)從狀態(tài)ψ中可以看到該狀態(tài)同時包含f(0)和f(1),看起來似乎同時對x的兩個值進行了計算。與經(jīng)典計算機不同的是,在經(jīng)典計算機中需要運行f(x)函數(shù)對應的電路兩次,而在量子計算機中,只需要運行一次量子線路即可同時計算出兩個x對應的函數(shù)值,通過測量目標寄存器即可得到。2.3量子算法2.3.1Deutsch算法在1985年,Deutsch提出了第一個體現(xiàn)量子并行計算的量子算法Deutsch算法[52]。該算法解決的問題是:給定一個布爾類型的函數(shù)f(x):{0,1}→{0,1},需要確定該函數(shù)是平衡函數(shù)還是常數(shù)函數(shù)。在經(jīng)典計算機中,需要計算兩次f(x)的值才能確定該函數(shù)的類型,即如果f(1)=f(0)=1/0,則判定該函數(shù)是常數(shù)函數(shù),當f(1)=0,f(0)=1或者f(1)=1,f(0)=0,則判定該函數(shù)是平衡函數(shù)。但是Deutsch算法中,只需要經(jīng)過一次函數(shù)計算就能得到這個函數(shù)的全局性,即該函數(shù)的類型。該算法的量子線路圖如圖所示[53]:圖2-3Deutsch量子線路圖
基于量子計算的Hash安全性研究132.3.2Deutsch-Jozsa算法Deutsch-Jozsa算法是Deutsch和Jozsa在1992年提出來的,該算法是對原始Deutsch算法在更高維度的拓展[30]。該算法的問題定義為:給定一個n比特的函數(shù)():{0,1}{0,1}nfx→,該函數(shù)如果是平衡函數(shù),則有一半的輸入輸出結(jié)果為0,另一半輸出結(jié)果為1,若是常數(shù)函數(shù),則所有輸出結(jié)果為0或1。在經(jīng)典計算機中,在最壞情況下,我們需要計算2/21n+次才能確定函數(shù)f(x)是平衡函數(shù)還是常數(shù)函數(shù),該問題是Deutsch問題由1個比特到n個比特的拓展。相應的,Deutsch-Jozsa算法能夠通過一次函數(shù)就能判定函數(shù)f(x)的性質(zhì),這相比于經(jīng)典算法是一個指數(shù)級的加速。我們給出該算法量子線路圖如圖所示[53]:圖2-3Deutsch-Jozsa算法量子線路圖該算法的初始輸入狀態(tài)可看做兩個寄存器組成,初始狀態(tài)為0的數(shù)據(jù)寄存器和初始狀態(tài)為1的輔助寄存器,初始化狀態(tài)可以表示為:001nψ=(2-16)對初始狀態(tài)應用Hn1+變換,可以得到狀態(tài)1ψ為:1{0,1}0122nnxxψ∈=∑(2-17)狀態(tài)1ψ經(jīng)過fB酉操作后,我們將得到狀態(tài)3ψ表示為:
本文編號:2944581
【文章來源】:深圳大學廣東省
【文章頁數(shù)】:81 頁
【學位級別】:碩士
【部分圖文】:
同時計算f(0)和f(1)的量子線路
基于量子計算的Hash安全性研究11圖2-2同時計算f(0)和f(1)的量子線路圖2-2給出了整個量子操作的線路圖[53]。數(shù)據(jù)寄存器的初始疊加狀態(tài)()0+12,可以由狀態(tài)0經(jīng)過H門變換后得到,于是應用fU門變換可以得到:0,(0)1,(1)=2ffψ+(2-9)從狀態(tài)ψ中可以看到該狀態(tài)同時包含f(0)和f(1),看起來似乎同時對x的兩個值進行了計算。與經(jīng)典計算機不同的是,在經(jīng)典計算機中需要運行f(x)函數(shù)對應的電路兩次,而在量子計算機中,只需要運行一次量子線路即可同時計算出兩個x對應的函數(shù)值,通過測量目標寄存器即可得到。2.3量子算法2.3.1Deutsch算法在1985年,Deutsch提出了第一個體現(xiàn)量子并行計算的量子算法Deutsch算法[52]。該算法解決的問題是:給定一個布爾類型的函數(shù)f(x):{0,1}→{0,1},需要確定該函數(shù)是平衡函數(shù)還是常數(shù)函數(shù)。在經(jīng)典計算機中,需要計算兩次f(x)的值才能確定該函數(shù)的類型,即如果f(1)=f(0)=1/0,則判定該函數(shù)是常數(shù)函數(shù),當f(1)=0,f(0)=1或者f(1)=1,f(0)=0,則判定該函數(shù)是平衡函數(shù)。但是Deutsch算法中,只需要經(jīng)過一次函數(shù)計算就能得到這個函數(shù)的全局性,即該函數(shù)的類型。該算法的量子線路圖如圖所示[53]:圖2-3Deutsch量子線路圖
基于量子計算的Hash安全性研究132.3.2Deutsch-Jozsa算法Deutsch-Jozsa算法是Deutsch和Jozsa在1992年提出來的,該算法是對原始Deutsch算法在更高維度的拓展[30]。該算法的問題定義為:給定一個n比特的函數(shù)():{0,1}{0,1}nfx→,該函數(shù)如果是平衡函數(shù),則有一半的輸入輸出結(jié)果為0,另一半輸出結(jié)果為1,若是常數(shù)函數(shù),則所有輸出結(jié)果為0或1。在經(jīng)典計算機中,在最壞情況下,我們需要計算2/21n+次才能確定函數(shù)f(x)是平衡函數(shù)還是常數(shù)函數(shù),該問題是Deutsch問題由1個比特到n個比特的拓展。相應的,Deutsch-Jozsa算法能夠通過一次函數(shù)就能判定函數(shù)f(x)的性質(zhì),這相比于經(jīng)典算法是一個指數(shù)級的加速。我們給出該算法量子線路圖如圖所示[53]:圖2-3Deutsch-Jozsa算法量子線路圖該算法的初始輸入狀態(tài)可看做兩個寄存器組成,初始狀態(tài)為0的數(shù)據(jù)寄存器和初始狀態(tài)為1的輔助寄存器,初始化狀態(tài)可以表示為:001nψ=(2-16)對初始狀態(tài)應用Hn1+變換,可以得到狀態(tài)1ψ為:1{0,1}0122nnxxψ∈=∑(2-17)狀態(tài)1ψ經(jīng)過fB酉操作后,我們將得到狀態(tài)3ψ表示為:
本文編號:2944581
本文鏈接:http://www.sikaile.net/kejilunwen/xinxigongchenglunwen/2944581.html
最近更新
教材專著