求解子集和问题的采样格归约算法
作者:
作者单位:

作者简介:

曹金政(1998-),男,硕士生,主要研究领域为公钥密码,格密码;史闻博(1980-),男,博士,教授,博士生导师,主要研究领域为信息安全;程庆丰(1979-),男,博士,教授,博士生导师,主要研究领域为公钥密码,密码协议;鲁宁(1984-),男,博士,副教授,博士生导师,主要研究领域为网络安全.

通讯作者:

程庆丰,E-mail:qingfengc2008@sina.com

中图分类号:

TP301

基金项目:

国家自然科学基金(61872449,62072092,62072093)


Sampling-based Lattice Reduction Algorithm for Subset Sum Problem
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    子集和问题是计算机科学中的重要问题,也是构建多种公钥密码体制的基础.提出了采样归约算法,使用随机采样方法降低问题维度,将原问题分解并归约为多个更小规模的格上最短向量,降低了构造格的半径,从而提高求解的效率,得到原问题的精确解或提高近似解的逼近程度.给出了理论上采样归约算法最差情况的成功率.更进一步地,在目标解重量较低的情况下,可以进行分段采样,对问题增加限定条件,提高解题效率.实验结果表明,对于高维度的子集和问题,与CJLOSS等已有的格归约子集和问题方法相比,该算法可以更高效地求解出问题的精确解,而且可以提高近似解的逼近程度,输出近似解的平均长度达到了CJLOSS算法的0.55倍、DR算法的0.64倍.

    Abstract:

    The subset sum problem is an important problem in computer science and the basis for constructing many public key cryptosystems. A random sampling method is proposed, so the dimension of the problem can be reduced by decomposing the original problem into multiple smaller subsets sum problems, reducing the radius of the constructed lattice, thereby improving the efficiency of solving SVP, and then reaching the solution. The theoretically worst-case success rate of the algorithm is given, and a possible method to improve the success rate of the algorithm is given based on the 0-1 distribution of the solution vector, when the weight of target solution is low, the solution vector is divided into sectors, thus applying restrictive conditions to the problem to improve the efficiency of problem-solving. Experimental results show that for high-dimensional subsets and problems, compared with the existing lattice reduction subsets and problem methods such as CJLOSS, the proposed algorithm can solve the exact solution of the problem more efficiently, and can improve the approximation degree of the approximate solution, the average length of the output approximate solution is 0.55 times that of the CJLOSS algorithm and 0.64 times that of the DR algorithm.

    参考文献
    相似文献
    引证文献
引用本文

曹金政,程庆丰,史闻博,鲁宁.求解子集和问题的采样格归约算法.软件学报,2022,33(11):3917-3929

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-12-07
  • 最后修改日期:2021-02-08
  • 录用日期:
  • 在线发布日期: 2022-11-11
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号