Fractal Analysis for Subset Sum Problems and its Applications to Cryptography

子集和问题的分形分析及其在密码学中的应用

基本信息

批准号：
19J00126
负责人：
鎌田祥一
金额：
$ 2.58万
依托单位：
Tokyo Metropolitan University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2019
资助国家：
日本
起止时间：
2019-04-25 至 2022-03-31
项目状态：
已结题

项目摘要

本年度も引き続き、ナップザック暗号の安全性評価の基礎となる部分和問題の求解困難性、特に、低密度攻撃に関する数学的研究を推し進めた。低密度攻撃は部分和問題の解を格子ベクトルに対応させ、最短ベクトル問題などの格子問題に対応させて解くことである。昨年度までに組合せ論（加法的組合せ論や極値組合せ論など）を意識し、部分和問題の解に対応する格子ベクトルをこれより短い格子ベクトルでカモフラージュするために必要な条件をヒューリスティックとして与えた。密度がより大きい場合の低密度攻撃による攻撃可能範囲が広がった。ただし、攻撃の計算時間は多項式時間とは限らず、効率的ではない可能性があることに注意する。これを量子公開鍵暗号として有名なOTU暗号に適用したところ低密度攻撃に耐性のある構成方法がないことがわかった。本年度はこの結果を国際会議CECC2021で発表を行った。この結果は学術雑誌に投稿中で査読結果待ちである。この結果に至るまでには1990年のCameronとErdosによる組合せ論的整数論の論文が参考になった。この論文では様々な特定性質を持った正の整数の集合の個数評価がHausdorff次元というフラクタル次元で特徴付けられることが記されている。このような個数評価はナップザック暗号の公開鍵の個数評価に直結し得る。この論文の紹介とCECC2021で発表した内容は第4回金沢暗号理論勉強会でも発表を行った。ナップザック暗号が安全となるための低密度攻撃の真の限界は純粋数学を意識してはじめて理解されるものと研究代表者は予想している。

今年，我们继续推进部分和问题求解难度的数学研究，这是评估背包密码安全性，特别是低密度攻击的基础。低密度攻击就是通过使其对应于一个格向量来解决部分和问题，并通过使其对应于格问题如最短向量问题来解决。到去年，我已经了解了组合学（加法组合学、极值组合学等），并提供了必要的条件作为启发式，用较短的晶格向量来伪装与部分和问题的解相对应的晶格向量。。当密度较大时，低密度攻击的攻击范围有所扩大。然而，应该注意的是，攻击的计算时间不一定是多项式时间，并且可能效率不高。当我们将其应用于以量子公钥密码系统而闻名的OTU密码学时，我们发现没有一种配置方法可以抵抗低密度攻击。今年，我们在国际会议CECC2021上展示了这一成果。结果已提交给学术期刊，正在等待同行评审结果。在得出这一结果时，参考了 Cameron 和 Erdos 1990 年发表的组合数论论文。本文描述了具有各种特定属性的一组正整数的数评估由称为豪斯多夫维数的分形维数来表征。这种数量评估可以直接与背包密码中的公钥的数量评估联系起来。本文的介绍以及在CECC2021上展示的内容也在第四届金泽密码学理论研究组上进行了展示。首席研究员预测，只有当考虑纯数学时，才能理解使背包密码安全的低密度攻击的真正极限。