格中短向量的y-稀疏表示和最短向量问题的算法研究

发布时间：2020-06-30 17:04

【摘要】：近年来,学术界对量子计算机的研究逐渐深入,大素数分解问题(Prime Factorization)和离散对数问题(Discrete Logarithm)因此开始变得不再那么困难。然而,当今广泛使用的公钥密码体制的安全大都依赖于这两个问题的困难性,因此,设计抗量子计算机攻击的“后量子时代”密码体制吸引了密码学界越来越多的研究兴趣。在已经提出的几种“后量子时代”密码体制中,格密码体制逐渐成为近年来顶级密码会议和期刊上的研究热点。最短向量问题(Shortest Vector Problem,简称SVP)是格理论(或者说,数的几何)中最重要的问题之一,几种基于格的公钥密码体制(Lattice-Based Cryptography)的安全性都依赖于最短向量问题(SVP)问题的困难性。本文围绕最短向量问题(SVP)展开深入研究,提出了格中短向量在BKZ约化基下的y-稀疏表示,然后利用这种短向量表示的稀疏性提出了解决最短向量问题(SVP)的若干算法,包括SVP遗传算法,SVP模拟退火算法,SVP分段枚举算法,以及SVP随机采样算法。本文的创新点主要包括:?首先,本文提出了在BKZ约化基下的格中短向量的整数y-稀疏表示,同时通过理论证明得到格中短向量的这种表示中各个整数分量的上界及其稀疏性;这种格中短向量的稀疏性具有独立的研究价值。?其次,本文首次将“遗传算法”和“模拟退火算法”等计算智能(Computational Intelligence)的思想应用于最短向量问题(SVP),通过马尔科夫分析和实验验证,这两种算法在解决最短向量问题(SVP)方面收到良好的效果。?最后,本文基于格中短向量的y-稀疏表示提出了分段的概念,利用分段情况下的短向量稀疏表示中非零分量个数的升序排列,提出了SVP分段枚举算法。实验显示,与当前著名SVP枚举算法相比,这种SVP分段枚举算法是目前较为快速而有效的SVP枚举算法。
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O413;TN918

【相似文献】

相关期刊论文 前10条

1 高志荣;熊承义;笪邦友;;改进的基于残差加权的稀疏表示人脸识别[J];中南民族大学学报(自然科学版);2012年03期

2 陈才扣;喻以明;史俊;;一种快速的基于稀疏表示分类器[J];南京大学学报(自然科学版);2012年01期

3 耿耀君;张军英;;一种基于投影稀疏表示的基因选择方法[J];哈尔滨工程大学学报;2011年08期

4 熊承义;汪淑贤;高志荣;;基于字典优化的稀疏表示人脸识别[J];中南民族大学学报(自然科学版);2014年02期

5 戴平阳;洪景新;李翠华;詹小静;;一种基于稀疏表示的判别式目标跟踪算法[J];厦门大学学报(自然科学版);2014年04期

6 赵佳佳;唐峥远;杨杰;刘尔琦;周越;;基于图像稀疏表示的红外小目标检测算法[J];红外与毫米波学报;2011年02期

7 柯激情;祝磊;厉力华;韩斌;郑智国;孟旭莉;;基于稀疏表示算法的蛋白质质谱数据特征选择[J];生物物理学报;2012年08期

8 王立国;刘丹凤;赵亮;;基于高光谱图像稀疏表示的彩色可视化模型(英文)[J];Applied Geophysics;2013年02期

9 宋琳;程咏梅;赵永强;;基于稀疏表示模型和自回归模型的高光谱分类[J];光学学报;2012年03期

10 罗燕龙;刘伟盛;戴平阳;李翠华;;基于局部稀疏表示模型的海上红外目标跟踪方法[J];厦门大学学报(自然科学版);2013年03期

相关会议论文 前3条

1 何爱香;刘玉春;魏广芬;;基于稀疏表示的煤矸界面识别研究[A];虚拟运营与云计算——第十八届全国青年通信学术年会论文集（上册）[C];2013年

2 樊亚翔;孙浩;周石琳;邹焕新;;基于元样本稀疏表示的多视角目标识别[A];2013年中国智能自动化学术会议论文集（第五分册）[C];2013年

3 葛凤翔;任岁玲;郭鑫;郭良浩;孙波;;微弱信号处理及其研究进展[A];中国声学学会水声学分会2013年全国水声学学术会议论文集[C];2013年

相关博士学位论文 前10条

1 李进明;基于稀疏表示的图像超分辨率重建方法研究[D];重庆大学;2015年

2 王亚宁;基于信号稀疏表示的电机故障诊断研究[D];河北工业大学;2014年

3 姚明海;视频异常事件检测与认证方法研究[D];东北师范大学;2015年

4 黄国华;蛋白质翻译后修饰位点与药物适应症预测方法研究[D];上海大学;2015年

5 王瑾;基于稀疏表示的数据收集、复原与压缩研究[D];北京工业大学;2015年

6 李涛;遥感影像稀疏表示中的字典学习算法及其应用[D];华中科技大学;2015年

7 丁丹;格中短向量的y-稀疏表示和最短向量问题的算法研究[D];清华大学;2015年

8 李小薪;稀疏表示的分段匹配寻踪方法[D];华南理工大学;2009年

9 何艳敏;稀疏表示在图像压缩和去噪中的应用研究[D];电子科技大学;2011年

10 宋相法;基于稀疏表示和集成学习的若干分类问题研究[D];西安电子科技大学;2013年

相关硕士学位论文 前10条

1 吴丽璇;基于稀疏表示的微聚焦X射线图像去噪方法[D];华南理工大学;2015年

2 赵孝磊;基于图像分块稀疏表示的人脸识别算法研究[D];南京信息工程大学;2015年

3 黄志明;基于辨别式稀疏字典学习的视觉追踪算法研究[D];华南理工大学;2015年

4 张铃华;非约束环境下的稀疏表示人脸识别算法研究[D];南京信息工程大学;2015年

5 贺妍斐;基于稀疏表示与自适应倒易晶胞的遥感图像复原方法研究[D];南京信息工程大学;2015年

6 杨烁;电能质量扰动信号的稀疏表示/压缩采样研究[D];西南交通大学;2015年

7 应艳丽;基于低秩稀疏表示的目标跟踪算法研究[D];西南交通大学;2015年

8 梁晓捷;基于网络摄像头与稀疏表示分类法的实时人脸识别系统应用研究[D];五邑大学;2015年

9 张宏乐;语音信号稀疏表示方法研究[D];太原理工大学;2016年

10 崔保良;基于稀疏表示的协同入侵检测[D];广东工业大学;2011年

本文编号：2735566