耐量子計算機暗号の安全性評価で世界記録を達成 ~解読が困難な"多変数公開鍵暗号"の実用化に向けて~
国立研究開発法人情報通信研究機構(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)にて発表する予定です。
香川照之、再び激変!シルバーヘアからセンター分けにイメチェン「永野かと」の声
大原櫻子、ガーシー暴露後初のSNS投稿に賛否の声「イメージ最悪になった」
大スターの息子、新幹線指定席で「車両がほぼ全席修学旅行生」体験 学生の配慮に「嬉しい」
熊本のバス・鉄道5社、全国ICカードから初の離脱 理由は費用
藤井名人、4勝1敗で初防衛 タイトル戦22連覇で最長記録更新
高橋一生、好きになったら一直線 本気すぎる趣味に共演陣「ガチですよ」「すごない?」
元AKB柏木由紀、ランジェリー3連発!ピンク、黒のレース、ベージュどれがお好み?
大谷翔平、同僚ベッツらに1厘差で首位打者維持の4打数1安打 左太もも裏には今もアザ残る
シェルシュールから「モイスチャーマトリックスCC」が登場
塚地武雅、大人気韓国アイドルグループのライブ観戦もメンバー父と勘違いされ「すごい飛躍して」
何があった!?「エアコン」が想定外の壊れ具合!投稿者に話を聞いた
小倉優子、不自然な“二重ライン”にネット騒然「やっぱり整形?」
元めちゃイケメンバーの三中元克(32)現在は何をしているのか調べてみた!
玉置浩二の妻、青田典子(53)の現在がとんでもない事になっていると話題に
ユーチューバーもこう氏、元彼女・成海瑠奈について赤裸々告白
トミーズ健、父が遺した口座解約で銀行とトラブルも…「真実」にガックリ
藤田ニコル「初めてした日」ゆうちゃみ「体位とかも全部」親に明かしたギャル的「性事情」に騒然
ガーシーが綾野剛のLINE公開でネット騒然「ショック」「すごいエンタメ」
田中美久、ビキニ姿でヒップラインと“美背中”大放出!美しすぎるにもほどがある
大原櫻子、ガーシー暴露後初のSNS投稿に賛否の声「イメージ最悪になった」
何があった!?「エアコン」が想定外の壊れ具合!投稿者に話を聞いた
玉置浩二の妻、青田典子(53)の現在がとんでもない事になっていると話題に
岡本夏生(56)、1600日ぶりにブログを更新した現在が衝撃
ユーチューバーもこう氏、元彼女・成海瑠奈について赤裸々告白
元めちゃイケメンバーの三中元克(32)現在は何をしているのか調べてみた!
ヒカル、浮気相手とのLINE流出にドン引きの声「キモすぎる」「吐きそう」
TikTokを賑わす「フエラムネごめんなサイダー味」がセブンイレブンで再販!じゅるるマスカットも買うなら今!
ガーシーが綾野剛のLINE公開でネット騒然「ショック」「すごいエンタメ」
小倉優子、不自然な“二重ライン”にネット騒然「やっぱり整形?」
完全にダマされた! 『ラヴィット!』あのちゃん“事故レベル”大暴走は『水ダウ』遠隔操作のしわざだった ネットも納得
香川照之、再び激変!シルバーヘアからセンター分けにイメチェン「永野かと」の声
大スターの息子、新幹線指定席で「車両がほぼ全席修学旅行生」体験 学生の配慮に「嬉しい」
熊本のバス・鉄道5社、全国ICカードから初の離脱 理由は費用
藤井名人、4勝1敗で初防衛 タイトル戦22連覇で最長記録更新
高橋一生、好きになったら一直線 本気すぎる趣味に共演陣「ガチですよ」「すごない?」
元AKB柏木由紀、ランジェリー3連発!ピンク、黒のレース、ベージュどれがお好み?
大谷翔平、同僚ベッツらに1厘差で首位打者維持の4打数1安打 左太もも裏には今もアザ残る
シェルシュールから「モイスチャーマトリックスCC」が登場
塚地武雅、大人気韓国アイドルグループのライブ観戦もメンバー父と勘違いされ「すごい飛躍して」
夏に活躍するアロマで“涼”を感じて心地よく過ごそう