K-Means LSH优化格中最短向量问题解决方法
需积分: 0 152 浏览量
更新于2024-08-04
收藏 4.57MB PDF 举报
"利用K-Means LSH加速求解格中的最短向量问题.pdf"
本文探讨的主题是利用K-Means Locality Sensitive Hashing (LSH) 对求解格上的最短向量问题(SVP)进行加速。最短向量问题在密码学、计算机科学以及数学领域都有重要的应用,特别是在格基密码学中,它是一个基础且关键的难题。SVP是指在给定的格中找到非零向量的最短长度,这在密码系统安全性分析和破译中扮演着重要角色。
2015年,Laarhoven提出了将位置敏感哈希(LSH)技术应用于筛法,创建了一种基于LSH的高斯筛法框架来处理SVP。LSH是一种数据结构和算法,它可以高效地检测数据集中的近似最近邻,其核心思想是将高维空间的数据映射到低维空间,使得相似的数据点更可能被映射到相同的哈希桶中。
金悦祺和胡红钢在此基础上进一步研究,引入了K-Means聚类算法的变体——K-Means LSH函数,对原有的筛法进行了优化。K-Means是一种常用的无监督机器学习算法,用于将数据集划分为K个簇,目标是使得每个簇内的数据点尽可能接近,而不同簇之间的数据点尽可能远离。K-Means LSH结合了K-Means的聚类能力,能够更准确地识别和处理相似的向量,从而提升筛法的效率。
实验结果表明,采用K-Means LSH的优化筛法在性能上有显著优势,能够更快地找出格中的最短向量。相比于Laarhoven的原始方法,优化后的算法不仅效率更高,而且因为引入了一个额外的参数,使得算法更具灵活性,适应不同的问题规模和场景,具有更高的实用价值。
该文在密码学报上发表,展示了密码学与机器学习的交叉应用,为解决复杂计算问题提供了新的思路。其对SVP的优化方案对于提高格基密码系统的安全性和效率有着积极的意义,同时也为未来相关领域的研究提供了一个有力的工具和参考。
2019-09-15 上传
2019-09-13 上传
2023-04-24 上传
2023-04-25 上传
2023-06-02 上传
2023-06-08 上传
2023-06-07 上传
2023-04-10 上传
2023-04-24 上传
![](https://profile-avatar.csdnimg.cn/16af1eb09ac24d298545c429a26293d8_weixin_70923796.jpg!1)
米朵儿技术屋
- 粉丝: 1905
- 资源: 123
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析:故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全:高效编程的秘密武器
- 网页制作入门:常用代码详解
- TX2440A开发板网络远程监控系统移植教程:易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析:Socket基础与应用
- 掌握Struts1:Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全:字体、文本、列表样式详解
- Proteus元件库大全:从基础到高级组件
- 74HC08芯片:高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题:设置字符集为GB2312
- C语言的诞生与演进:从汇编到系统编程的革命