整数論及び組合せ論的アルゴリズム研究とその次世代公開鍵暗号への応用

数论与组合算法研究及其在下一代公钥密码中的应用

• 批准号: 18840035
• 负责人: 内山 成憲
• 金额: $ 1.73万
• 依托单位: Tokyo Metropolitan University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (Start-up)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18840035/
• 关键词: アルゴリズム; 暗号・認証; 量子コンピュータ

今年度は、昨年度に引き続き量子計算機を用いた攻撃に対して安全と期待される公開鍵暗号の安全性解析、また、関連するアルゴリズムを用いた新しい暗号方式の提案とその安全性解析について研究し、主に次の4つの結果を得た。まず、量子計算機に関して耐性があると思われる方式の安全性解析については、最初に、EUにおける暗号標準化組織であるNESSIE推奨の公開鍵暗号の1つであるディジタル署名SFLASHに対して、最も一般的な条件の下で効率的な攻撃が可能なことを実装実験により示した。(小椋直樹氏、中村憲氏(首都大学東京)との共同研究、2008年暗号と情報セキュリティシンポジウム(2008)にて口頭発表)。次に、代数曲面暗号の安全性評価として、昨年度研究代表者等により提案された攻撃手法と、後に、Volochにより提案された別の攻撃手法のその効率の比較を行い、研究代表者等によって提案された手法がある条件では効果的であることを実装実験によって示した。(福地弘之氏、徳永浩男氏(首都大学東京)との共同研究、平成20年日本応用数理学会研究部会連合発表会(2008)で口頭発表)3つ目は格子における最短ベクトルを求める問題の困難性に基づくナップザック暗号の安全性評価についてである。これは、昨年度に引き続きSampling Reductionと呼ばれるアルゴリズムの改良法の提案を行った。サイズが大きくなると計算量が増えてしまうので、実装実験できる範囲が限られてしまうのだが、ある条件の下では提案手法が高速であることを示した。(小泉賢洋氏、中村憲氏との共同研究、上記研究部会連合発表会(2008)で口頭発表)最後に、格子に関連するアルゴリズムを用いて安全性の解析を必要とする素因数問題の困難性に基づく公開鍵暗号で、1995年にVanstone等によって提案された、データ通信量を軽減する手法に対し、オリジナルの手法とは異なる法を用いた方式の提案およびその方式に対する安全性解析を行った。(金山直樹氏(筑波大学)との共同研究、IEICE Trans. Fund.(2007)に論文が掲載)

今年，我们将继去年的基础上，对有望抵御量子计算机攻击的公钥密码学的安全性分析进行研究，并提出使用相关算法的新加密方法及其安全性分析。 ，我们主要得到了以下四个结果。首先，关于被认为抵抗量子计算机的方法的安全性分析，我们首先分析了最常见的数字签名SFLASH方法，它是欧盟加密标准化组织NESSIE推荐的公钥密码系统之一。我们通过实施实验证明，在这种条件下有效的攻击是可能的。 （与 Naoki Ogura 和 Ken Nakamura（东京都立大学）的联合研究，在 2008 年密码学和信息安全研讨会上的口头报告（2008 年））。接下来，为了评估代数表面密码的安全性，我们将去年研究代表提出的攻击方法与后来Voloch提出的另一种攻击方法的效率进行了比较，并通过实现实验证明了所提出的方法在一定条件下是有效的。状况。 （与Hiroyuki Fukuchi和Hiroo Tokunaga（东京都立大学）的联合研究，在日本应用数学学会研究小组会议上的口头报告（2008年））第三个问题是寻找格子中最短向量的困难。基于性别的背包密码安全评估这是去年提出的称为“采样缩减”的算法改进方法的延续。随着规模的增加，计算量增加，这限制了实现实验的范围，但我们表明所提出的方法在某些条件下是快速的。 （与小泉健弘先生和中村健先生共同研究，在上述研究小组联合报告中进行口头报告（2008年））最后，我们将讨论需要使用格子相关算法进行安全分析的质因数问题的难度。针对 Vanstone 等人于 1995 年提出的使用基于性别的公钥密码来减少数据通信量的方法，我们提出了一种与原始方法不同的方法，并分析了该方法的安全性。 （与金山直树（筑波大学）共同研究，论文发表于 IEICE Trans. Fund. (2007)）

项目成果

代数曲面を用いた公開鍵暗号への効率的な攻撃法

利用代数面的公钥密码的高效攻击方法

• 发表时间: 2008
• 作者: 福地 弘之;内山 成憲;徳永 浩雄
• 通讯作者: 徳永 浩雄

Knapsack暗号への攻撃を効果的にするためのSampling Reductionの改良と考察

减少采样的改进和考虑，使背包加密攻击更加有效

• 发表时间: 2008
• 作者: 小泉 賢洋;内山 成憲;中村 憲
• 通讯作者: 中村 憲

The Vanstone-Zuccherato Schemes Revisited

重新审视 Vanstone-Zuccherato 计划

• 发表时间: 2007
• 期刊: IEICE Trans. Fundamentals E90-A
• 作者: 田中覚;中村憲;Kohatsu-Higa Arturo,.;Naoki Kanayama and Shigenori Uchiyama
• 通讯作者: Naoki Kanayama and Shigenori Uchiyama

SFLASH署名方式への攻撃法の実装について

关于SFLASH签名方法的攻击实现

• 发表时间: 2008
• 作者: 小椋 直樹;内山 成憲;中村 憲
• 通讯作者: 中村 憲