耐量子計算機暗号の安全性評価で世界記録を達成 ~解読が困難な"多変数公開鍵暗号"の実用化に向けて~
国立研究開発法人情報通信研究機構(NICT)
公立大学法人首都大学東京
耐量子計算機暗号の安全性評価で世界記録を達成
~量子コンピュータを使用しても解読が困難な"多変数公開鍵暗号"の実用化に向けて~
【ポイント】
■ 耐量子計算機暗号の一つとされる多変数公開鍵暗号の安全性評価のコンテストで世界記録達成
■ 従来の解読方法より計算が5倍速く、メモリ使用量を8分の1に削減することに成功
■ 量子コンピュータ時代でも安全かつ高速な暗号技術の実用化に期待
国立研究開発法人情報通信研究機構(NICT、理事長: 徳田 英幸)サイバーセキュリティ研究所と首都大学東京(学長: 上野 淳)の研究グループは共同で、量子コンピュータを使用しても解読が困難な"多変数公開鍵暗号"の安全性の根拠とされている連立二次多変数代数方程式を解くコンテスト(Fukuoka MQ Challenge プロジェクト)において、Type II及びIIIに分類される方程式について、まだ誰にも解かれていない37という多くの変数の方程式を、世界で初めて解くことに成功しました。
多変数公開鍵暗号は効率的な暗号処理方法を持つことから、実用的な耐量子計算機暗号として期待されています。今回の成果は、多変数公開鍵暗号を安全に運用するために必要な変数の個数の算出に利用されます。
【背景】
公開鍵暗号は、現代の情報通信システムの安全性を支える基盤技術であり、具体的には、RSA 暗号及び楕円曲線暗号が広く使用されています。しかし、実用的な量子コンピュータが開発されると、これらの公開鍵暗号の安全性が大きく低下することが懸念されています。そのため、量子コンピュータでも、現在のコンピュータでも、解読が困難な暗号が必要とされており、そのような暗号技術は、耐量子計算機暗号と呼ばれています。
特に近年、世界各国及び国内において耐量子計算機暗号の研究開発及び標準化に向けた準備が進められています。耐量子計算機暗号の有力な候補の一つに多変数公開鍵暗号があり、その安全性の根拠とされる連立二次多変数代数方程式を解く研究が重要な課題として活発に進められています。
【今回の成果】
【画像: https://kyodonewsprwire.jp/img/201906267997-O1-Z9LfoJq9 】
図1 連立二次多変数代数方程式の求解の難しさ
多変数公開鍵暗号を安全に利用するためには、連立二次多変数代数方程式が何変数まで解けるのかを評価する必要があります。
量子コンピュータを使用しても解読が困難な"多変数公開鍵暗号"の安全性の根拠とされている連立二次多変数代数方程式を解くコンテストFukuoka MQ Challengeにおいて、6タイプ(Type I~VI)の方程式が設定されており、各タイプにおいて解かれた最大の変数の個数が報告されています。
NICTサイバーセキュリティ研究所の伊藤琢真研究員、篠原直行主任研究員と首都大学東京大学院理学研究科の内山成憲教授は共同で、Fukuoka MQ Challengeにおいて、Type II及びIIIに分類される連立二次多変数代数方程式に特化したアルゴリズムとプログラムを開発し、従来よりも計算が約5倍速く、メモリ使用量を最良の場合では8分の1に節約することに成功しました。本手法を使用して、まだ誰にも解かれていない37変数の問題に挑戦しました。この37変数の問題を解くためには、MQ Challengeの資料を参考にすると、23変数の問題を解く場合の約15万倍の時間がかかり、汎用ソフトを使用した場合は4~16年はかかると考えられます。
しかし、我々の開発したアルゴリズムとプログラムを汎用サーバ(CPU: Intel® Xeon® CPU E5-4669 v4 (2.20GHz/22Core)×4、メモリ: 1TB)で使うことで、Type IIの37変数については75.7日、Type IIIの37変数については56.1日で解くことに成功し、3年近く更新されていなかった世界記録を更新しました。
【今後の展望】
今後は、多変数公開鍵暗号の実用化に向けて、他のタイプの連立二次多変数代数方程式についても解読アルゴリズムを開発し、安全性の評価を実施していきます。
なお、本研究成果について、2019年8月28日(水)から30日(金)に開催される情報セキュリティに関する国際会議IWSEC2019(The 14th International Workshop on Security)にて発表する予定です。
元NHK31歳アナ、ライン浮き出るニット3連発「くっそエロい」「大人なお姉さん」コメ欄悩殺
武藤敬司が人工股関節手術から退院報告、向かいの病室に大物タレント「お先に失礼します!」
「不作83年組」57歳がアイドル時代の水着写真を公開「超恥ずかしかったー、な笑」に拍手喝采
キケ・ヘルナンデス妻、日本の思い出は長女ペネロペちゃんの“初雪”「特別で予想外だったわ」
大谷翔平のド軍ユニホームを着てバスケ界のレジェンドが驚きの試合会場入り MLB公式が公開
巨人2軍の新球場「ジャイアンツタウンスタジアム」で首都大開幕 選手ら「新鮮」と好印象
【ソフトバンク】誕生20周年記念しタカの飛来ショー 歴代監督王貞治氏ら出席 選手は特別ユニ
【日本酒・焼酎250種類以上が楽しめる注目イベント!】クラフトサケ醸造所が出店決定!「混祭2025」開催
【TGCin万博】みちょぱがウエンツ瑛士イジり「『ウエンツ』と『瑛士』がいるんだよ」
コスモスが謝罪、「無断駐車」警告は誤り 共用駐車場の認識不足が原因
多部未華子(30)結婚の裏事情あまりにも恐ろしすぎると話題に!
中居正広氏、14年前に脳科学者が「女性におぼれて芸能界追放」と“予言” X騒然「すごい」
「中居正広」Xトレンド入り、第三者委員会の調査報告書にツッコミ殺到「こりゃ酷い」の声
二階堂ふみが結婚!?お相手が衝撃的過ぎてネット民「マジか・・・」
有吉弘行、「感謝祭」で永野芽郁に暴走突撃の江頭2:50について“たったひと言”で言及
「もう会えなくなるけど、こんな女がいたことも忘れないでね」ヒコロヒー“永久出禁”受け吐露
笠井信輔アナ、飲食店で隣席の女性に叱責され謝ったのに「自らのストレスを他人に向けて…」
伝説のロックバンドドラマー、中居正広氏めぐるテレビ番組報道に「ハッキリ言います!」
日清食品どん兵衛CM、「アンミカ起用」で不買運動の動き
中居正広氏「ひと段落かな」B氏「動きます」女性A退職時の文面公開されX「最悪」「ヘド出る」
多部未華子(30)結婚の裏事情あまりにも恐ろしすぎると話題に!
二階堂ふみが結婚!?お相手が衝撃的過ぎてネット民「マジか・・・」
堀江貴文氏、炎上ストリートピアノ騒動に“たった5文字”で反応しX賛同多数
中居正広氏、14年前に脳科学者が「女性におぼれて芸能界追放」と“予言” X騒然「すごい」
「中居正広」Xトレンド入り、第三者委員会の調査報告書にツッコミ殺到「こりゃ酷い」の声
楽しんご、銭湯での男性へのわいせつ行為で逮捕された中孝介容疑者に“8文字”でずばり私見
【おすすめアニメ50選】完結済み!定番から最新作まで!
小澤征悦と再婚した桑子真帆アナ(34)黒い過去が流出、衝撃の過去にネット騒然
万引き逮捕の米田哲也容疑者を「ご親族かどなたか助けてあげられないのか」紀藤正樹氏「悲しい」
堺正章が60歳タレントと“禁断の”共演「確かに昔干したよ」「本気でした」激白しスタジオ騒然

元NHK31歳アナ、ライン浮き出るニット3連発「くっそエロい」「大人なお姉さん」コメ欄悩殺
武藤敬司が人工股関節手術から退院報告、向かいの病室に大物タレント「お先に失礼します!」
「不作83年組」57歳がアイドル時代の水着写真を公開「超恥ずかしかったー、な笑」に拍手喝采
キケ・ヘルナンデス妻、日本の思い出は長女ペネロペちゃんの“初雪”「特別で予想外だったわ」
大谷翔平のド軍ユニホームを着てバスケ界のレジェンドが驚きの試合会場入り MLB公式が公開
【ソフトバンク】誕生20周年記念しタカの飛来ショー 歴代監督王貞治氏ら出席 選手は特別ユニ
巨人2軍の新球場「ジャイアンツタウンスタジアム」で首都大開幕 選手ら「新鮮」と好印象
【日本酒・焼酎250種類以上が楽しめる注目イベント!】クラフトサケ醸造所が出店決定!「混祭2025」開催
【TGCin万博】みちょぱがウエンツ瑛士イジり「『ウエンツ』と『瑛士』がいるんだよ」
コスモスが謝罪、「無断駐車」警告は誤り 共用駐車場の認識不足が原因