本文關(guān)鍵詞：理想格問題的局部—整體算法研究

  更多相關(guān)文章： SVP CVP 理想格 局部域 整體域

【摘要】：理想格問題在全同態(tài)保密計算(FHE)方案中扮演了相當重要的角色,理想格問題的計算難解性為許多創(chuàng)新性的公鑰加密方案提供了理論依據(jù)。本文設(shè)計了一種全新的算法來解決數(shù)域的任意n度相對擴展L/K中理想格的最短格向量(SVP)和最近格向量(CVP)問題,其中L為實數(shù)域。此算法通過利用局部數(shù)域和整體數(shù)域之間關(guān)聯(lián),將求解數(shù)域L中理想A的SVP(或CVP)轉(zhuǎn)化為求解一系列子域Li中理想Ai,其中1≤nn且∑ni=n。此算法的空間復(fù)雜度為多項式復(fù)雜度,和而其時間復(fù)雜相關(guān)于數(shù)域擴展的維度n也是時間多項式復(fù)雜度。更為準確的說,此算法的時間復(fù)雜度為poly(n,|S|, NPG,NPT, Nd, Ni)其中|S|是輸入數(shù)據(jù)位數(shù),而NPG、NPT、Nd、Nl為調(diào)用一些相關(guān)簡單問題的啟發(fā)器(oracles)的次數(shù)(他們其中的一些已經(jīng)是確定的)如此的特性預(yù)示著如果全部相關(guān)的啟發(fā)器可以被在多項式時間算法實現(xiàn)(在一些特殊情況下的確如此),則局部整體算法可以在在多項式時間內(nèi)有效的解決SVP和CVP。即使這些啟發(fā)器不能被有效的實現(xiàn),此算法的時間復(fù)雜度也可能會顯著地低于其他針對一般格問題的算法,因為這些啟發(fā)器可能被低次冪的指數(shù)時間復(fù)雜度的算法實現(xiàn)。
【關(guān)鍵詞】：SVP CVP 理想格 局部域 整體域
【學位授予單位】：大連理工大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O153.1;TN918.4
【目錄】：

• 摘要4-5
• Abstract5-8
• 1 緒論8-16
• 1.1 格的基本性質(zhì)8-9
• 1.2 格問題的難解性9-10
• 1.3 格問題相關(guān)工作10-11
• 1.4 模形式方法求解格問題11-13
• 1.5 格在密碼學中的應(yīng)用13-14
• 1.5.1 基于最壞情況下的安全保障13
• 1.5.2 格與量子計算13-14
• 1.6 多項式分解14-15
• 1.7 本文結(jié)構(gòu)15-16
• 2 理想格的“局部-整體”理論16-26
• 2.1 格,SVP和CVP16-18
• 2.2 數(shù)域和理想格18-20
• 2.3 更為普遍的模型：相對擴張和素理想分解20-21
• 2.4 賦值,P-進數(shù)完備化和局部-整體關(guān)系21-26
• 3 局部-整體算法：邏輯框架26-31
• 3.1 問題表述26-27
• 3.2 算法整體設(shè)計27-31
• 4 局部-整體算法：詳細設(shè)計31-39
• 4.1 Step#2子問題的處理算法31-32
• 4.2 Step#3子問題的處理算法32-33
• 4.3 Step#4子問題的處理算法33-34
• 4.4 Step#1子問題的處理算法34-36
• 4.5 計算復(fù)雜度分析36-39
• 5 基于Miller-Rabin素性檢測的多項式分解算法39-54
• 5.1 基礎(chǔ)知識與符號的約定39-40
• 5.2 有限域內(nèi)多項式分解40-45
• 5.2.1 CZ算法框架40-41
• 5.2.2 改進的有限域內(nèi)多項式分解算法41-45
• 5.3 代數(shù)數(shù)域內(nèi)多項式分解45-50
• 5.3.1 求解Berlekamp代數(shù)子集元素45-46
• 5.3.2 隨機二分搜索分解46-48
• 5.3.3 任意擴展域內(nèi)多項式分解48-49
• 5.3.4 算法失效概率上限的證明49-50
• 5.4 算法復(fù)雜度分析50-54
• 5.4.1 有限域內(nèi)多項式分解算法的時間復(fù)雜度51
• 5.4.2 代數(shù)數(shù)域內(nèi)多項式分解算法的時間復(fù)雜度51-53
• 5.4.3 時間復(fù)雜度比較53-54
• 結(jié)論54-55
• 參考文獻55-59
• 攻讀碩士學位期間發(fā)表學術(shù)論文情況59-60
• 致謝60-61

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 張慶德;模糊(左,右)理想格的結(jié)構(gòu)[J];模糊系統(tǒng)與數(shù)學;2000年01期

2 張玉琦;完備集環(huán)是理想格的充分必要條件[J];內(nèi)蒙古師范大學學報(自然科學漢文版);2004年02期

3 雷天德;黃文平;;四元數(shù)環(huán)及其若干性質(zhì)[J];陜西師大學報(自然科學版);1989年02期

4 魏仕民,趙樹廉;BCl-代數(shù)的理想格[J];淮北煤師院學報(自然科學版);1993年03期

5 秦學成;劉春輝;;正則剩余格的fuzzy ⊙-理想格[J];山東大學學報(理學版);2011年08期

6 杜現(xiàn)昆,齊毅;環(huán)的右ad理想格[J];吉林大學自然科學學報;2000年04期

7 趙秀蘭;方捷;;平衡擬補Ockham代數(shù)的理想格[J];華南師范大學學報(自然科學版);2007年02期

8 劉春輝;;正則Fuzzy蘊涵代數(shù)的理想格[J];內(nèi)蒙古師范大學學報(自然科學漢文版);2009年01期

9 陳昌南,朱彬;強分次環(huán)上全矩陣環(huán)的一類子環(huán)的理想格[J];懷化師專學報(自然科學);1990年02期

10 ;[J];;年期

中國碩士學位論文全文數(shù)據(jù)庫 前2條

1 孫榮辛;理想格問題的局部—整體算法研究[D];大連理工大學;2015年

2 賽煒;基于理想格的公鑰密碼中模多項式的應(yīng)用研究[D];西安電子科技大學;2014年

，

本文編號：637478