理想格问题的局部—整体算法研究

发布时间：2017-08-08 01:00

  本文关键词：理想格问题的局部—整体算法研究

  更多相关文章： SVP CVP 理想格 局部域 整体域

【摘要】：理想格问题在全同态保密计算(FHE)方案中扮演了相当重要的角色,理想格问题的计算难解性为许多创新性的公钥加密方案提供了理论依据。本文设计了一种全新的算法来解决数域的任意n度相对扩展L/K中理想格的最短格向量(SVP)和最近格向量(CVP)问题,其中L为实数域。此算法通过利用局部数域和整体数域之间关联,将求解数域L中理想A的SVP(或CVP)转化为求解一系列子域Li中理想Ai,其中1≤nn且∑ni=n。此算法的空间复杂度为多项式复杂度,和而其时间复杂相关于数域扩展的维度n也是时间多项式复杂度。更为准确的说,此算法的时间复杂度为poly(n,|S|, NPG,NPT, Nd, Ni)其中|S|是输入数据位数,而NPG、NPT、Nd、Nl为调用一些相关简单问题的启发器(oracles)的次数(他们其中的一些已经是确定的)如此的特性预示着如果全部相关的启发器可以被在多项式时间算法实现(在一些特殊情况下的确如此),则局部整体算法可以在在多项式时间内有效的解决SVP和CVP。即使这些启发器不能被有效的实现,此算法的时间复杂度也可能会显著地低于其他针对一般格问题的算法,因为这些启发器可能被低次幂的指数时间复杂度的算法实现。
【关键词】：SVP CVP 理想格 局部域 整体域
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O153.1;TN918.4
【目录】：

• 摘要4-5
• Abstract5-8
• 1 绪论8-16
• 1.1 格的基本性质8-9
• 1.2 格问题的难解性9-10
• 1.3 格问题相关工作10-11
• 1.4 模形式方法求解格问题11-13
• 1.5 格在密码学中的应用13-14
• 1.5.1 基于最坏情况下的安全保障13
• 1.5.2 格与量子计算13-14
• 1.6 多项式分解14-15
• 1.7 本文结构15-16
• 2 理想格的“局部-整体”理论16-26
• 2.1 格,SVP和CVP16-18
• 2.2 数域和理想格18-20
• 2.3 更为普遍的模型：相对扩张和素理想分解20-21
• 2.4 赋值,P-进数完备化和局部-整体关系21-26
• 3 局部-整体算法：逻辑框架26-31
• 3.1 问题表述26-27
• 3.2 算法整体设计27-31
• 4 局部-整体算法：详细设计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 计算复杂度分析36-39
• 5 基于Miller-Rabin素性检测的多项式分解算法39-54
• 5.1 基础知识与符号的约定39-40
• 5.2 有限域内多项式分解40-45
• 5.2.1 CZ算法框架40-41
• 5.2.2 改进的有限域内多项式分解算法41-45
• 5.3 代数数域内多项式分解45-50
• 5.3.1 求解Berlekamp代数子集元素45-46
• 5.3.2 随机二分搜索分解46-48
• 5.3.3 任意扩展域内多项式分解48-49
• 5.3.4 算法失效概率上限的证明49-50
• 5.4 算法复杂度分析50-54
• 5.4.1 有限域内多项式分解算法的时间复杂度51
• 5.4.2 代数数域内多项式分解算法的时间复杂度51-53
• 5.4.3 时间复杂度比较53-54
• 结论54-55
• 参考文献55-59
• 攻读硕士学位期间发表学术论文情况59-60
• 致谢60-61

【相似文献】

中国期刊全文数据库 前10条

1 张庆德;模糊(左,右)理想格的结构[J];模糊系统与数学;2000年01期

2 张玉琦;完备集环是理想格的充分必要条件[J];内蒙古师范大学学报(自然科学汉文版);2004年02期

3 雷天德;黄文平;;四元数环及其若干性质[J];陕西师大学报(自然科学版);1989年02期

4 魏仕民,赵树廉;BCl-代数的理想格[J];淮北煤师院学报(自然科学版);1993年03期

5 秦学成;刘春辉;;正则剩余格的fuzzy ⊙-理想格[J];山东大学学报(理学版);2011年08期

6 杜现昆,齐毅;环的右ad理想格[J];吉林大学自然科学学报;2000年04期

7 赵秀兰;方捷;;平衡拟补Ockham代数的理想格[J];华南师范大学学报(自然科学版);2007年02期

8 刘春辉;;正则Fuzzy蕴涵代数的理想格[J];内蒙古师范大学学报(自然科学汉文版);2009年01期

9 陈昌南,朱彬;强分次环上全矩阵环的一类子环的理想格[J];怀化师专学报(自然科学);1990年02期

10 ;[J];;年期

中国硕士学位论文全文数据库 前2条

1 孙荣辛;理想格问题的局部—整体算法研究[D];大连理工大学;2015年

2 赛炜;基于理想格的公钥密码中模多项式的应用研究[D];西安电子科技大学;2014年

，

本文编号：637478