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
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19J00126/
• 关键词: ナップザック暗号; 部分和問題; 低密度攻撃; 加法的組合せ論; 極値組合せ論; 組合せ論的整数論; 組合せ論; 加法的整数論; 格子問題; フラクタル次元解析; 多重フラクタル次元解析

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

今年，我们继续促进有关解决部分总和问题的难度的数学研究，这是对背包加密术的安全评估的基础，尤其是低密度攻击。低密度攻击涉及通过与晶格向量相对应的零件总和问题解决方案，并对应于晶格问题，例如最短的向量问题。直到去年，考虑到组合理论（添加剂组合理论，极值组合理论等），我们为伪装的晶格向量提供了与较短的晶格矢量相对应的晶格向量的必要条件。当密度较高时，可以通过低密度攻击攻击的攻击范围已扩大。但是，请注意，攻击的计算时间不一定是多项式时间，并且可能不会有效。当将其应用于以量子公共密钥密码学而闻名的OTU密码学时，发现没有配置方法可以抵抗低密度攻击。今年，结果是在国际会议CECC 2021上提出的。这些结果发布在学术期刊上，并正在等待同行评审结果。为此，Cameron和Erdos的1990年关于组合整数理论的论文很有用。本文指出，一组具有各种特定属性的正整数的数字评估为特征在于一个称为Hausdorff尺寸的分形维度。这样的数字评估可以直接链接到背包密码的公共钥匙的数量评估。第四卡纳泽密码研究小组也提出了本文的引入和CECC 2021中介绍的内容。首席研究人员预测，低密度攻击的真正限制以确保安全密码学的安全只能以纯数学的重点来理解。

项目成果

On hardness of subset sum problems and Hermite invariants of lattices

关于子集和问题的硬度和格子的埃尔米特不变量

• 发表时间: 2020
• 作者: 梅村尚樹;梅村尚樹;宋代史研究会;葛西 太一;葛西 太一;葛西 太一;葛西 太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西 太一;Shoichi Kamada;鎌田 祥一;鎌田 祥一;鎌田 祥一;鎌田祥一;鎌田祥一;鎌田祥一;鎌田祥一;鎌田祥一
• 通讯作者: 鎌田祥一

暗号理論における部分和問題と数理

密码学理论中的部分和问题与数学

• 发表时间: 2019
• 作者: 梅村尚樹;梅村尚樹;宋代史研究会;葛西 太一;葛西 太一;葛西 太一;葛西 太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西 太一;Shoichi Kamada;鎌田 祥一;鎌田 祥一;鎌田 祥一;鎌田祥一;鎌田祥一;鎌田祥一;鎌田祥一;鎌田祥一;Shoichi Kamada;鎌田祥一
• 通讯作者: 鎌田祥一

CameronとErdosの論文「On the number of sets of integers with various properties」 (1990) について (論文紹介)

关于 Cameron 和 Erdos 的论文《论具有各种性质的整数集的数量》（1990）（论文简介）

• 发表时间: 2021
• 作者: 梅村尚樹;梅村尚樹;宋代史研究会;葛西 太一;葛西 太一;葛西 太一;葛西 太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西 太一;Shoichi Kamada;鎌田 祥一;鎌田 祥一
• 通讯作者: 鎌田 祥一

ある公開鍵暗号の安全性: Szemeredi 型の言明と新しい数学の追究

某些公钥密码学的安全性：Szemeredi 型陈述和新的数学追求

• 发表时间: 2021
• 作者: 梅村尚樹;梅村尚樹;宋代史研究会;葛西 太一;葛西 太一;葛西 太一;葛西 太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西 太一;Shoichi Kamada;鎌田 祥一;鎌田 祥一;鎌田 祥一;鎌田祥一;鎌田祥一
• 通讯作者: 鎌田祥一

より広範囲のナップザック暗号の解読可能性と組合せ論的整数論の視点

更广泛的背包密码的可破解性和组合数论的视角

• 发表时间: 2021
• 作者: 梅村尚樹;梅村尚樹;宋代史研究会;葛西 太一;葛西 太一;葛西 太一;葛西 太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西太一;葛西 太一;Shoichi Kamada;鎌田 祥一;鎌田 祥一;鎌田 祥一;鎌田祥一;鎌田祥一;鎌田祥一;鎌田祥一
• 通讯作者: 鎌田祥一