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

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

• 批准号: 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)に論文が掲載)

This year, the quantum computer was launched in the middle of the attack on security and expectations, public key password security analysis, correlation, and use of new password proposals, security analysis, research, and secondary results were obtained. The security analysis of quantum computer related to tolerance is carried out in the first place, in the EU, in the NESSIE push public key password, in the first place, in the EU, in the most general conditions, in the most effective attack probability. (Joint research by Naoki Otaru and Kenji Nakamura (Tokyo Capital University), oral presentation of the 2008 Code of Information (2008)) The security evaluation of secondary and algebraic surfaces, the comparison of the effectiveness of different attack methods, the research representatives, etc. (Fukuchi Hironoshi and Tokunaga Hiroo (Tokyo Capital University)) Joint research, Japan Applied Mathematics Society Research Committee Joint Report Meeting (2008) Oral presentation)3 Code lattice This is the first time that we have proposed an improved method for Sampling Reduction. The amount of calculation is increased, the range of installation is limited, and the method of proposal is high speed. (Koizumi Kenyo, Nakamura Kenji joint research, the above research department joint report meeting (2008), oral presentation), finally, the grid related to the use of security analysis, necessary factors, the difficulty of the problem, the basis of the open key code, Vanstone et al., 1995, the proposal, the method of reducing traffic, etc. The security analysis of different methods and methods of application (Kanayama Naoki (University of Tsukuba) Joint Research, IEICE Trans. Fund. (2007) The paper was published.

项目成果

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

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

• 发表时间: 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
• 作者: 小椋 直樹;内山 成憲;中村 憲
• 通讯作者: 中村 憲