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

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

• 批准号: 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 and last year, the quantum computing machine used to attack the security system. We look forward to the public release of the code for security analysis, security analysis and security research. In this paper, the quantum computing machine is used to analyze the security of the system. The EU code code is used to standardize the organization. The NESSIE makes it public. 1. It is signed by the SFLASH computer. Under the most general conditions, the attack rate of the system may be displayed. (Nakamura Nakamura (Capital University) and Nakamura (Capital University) co-study, 2008 code word: 2008

项目成果

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

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

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