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

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

• 批准号: 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推荐的公共密钥密码学之一。 （与Ogura Naoki和Nakamura Nori（东京都会大学）的联合研究，以及2008年Crypto和信息安全研讨会（2008）的口头介绍。接下来，为了评估代数表面密码学的安全性，我们比较了去年首席研究人员提出的攻击方法的效率，以及沃克后来提出的另一种攻击方法，并通过实施实验证明了它在某些条件下是有效的。 （与2008年日本应用数学研究协会（2008年）的福库奇·海洛伊基（Fukuchi Hiroyuki）和托库纳加·海鲁（Tokunaga Hiroo）（东京大都会大学）和口头介绍的联合研究（2008年），第三个是关于基于查找较短载体的问题的背包加密术的安全评估。这是从去年的财政年度开始的，并提出了一种改进方法，以减少采样算法。随着大小的增加，计算量增加，实施实验的范围受到限制，但是我们已经表明，在某些条件下，所提出的方法很快。 （与Koizumi Kenhiro和Nakamura Nori的合作研究，上述研究小组委员会联合会联合会联合会（2008）的口头介绍（2008年））最后，我们提出了一种使用与原始方法不同的方法进行的方法，并进行了安全分析，以减少数据通信的方法，该方法是VANSTONE等人。 1995年，以及减少数据通信的方法。 （与Kanayama Naoki（Tsukuba University）的联合研究发表在IEICETrans。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
• 作者: 小椋 直樹;内山 成憲;中村 憲
• 通讯作者: 中村 憲