量子計算機でも解読困難となる新しい原理に基づく公開鍵暗号を開発

【概要】
　九州大学マス・フォア・インダストリ研究所の高木剛教授の研究グループは、量子計算機でも解読が困難な新しい原理に基づく公開鍵暗号を、東芝研究開発センター、北海道教育大学、産業技術総合研究所との共同研究で開発しました。この暗号は、量子計算機でも計算が困難と期待される非線形不定方程式の最小解問題に基づいて構成しており、この領域で有力な格子暗号と比較して同等またはそれ以上の安全性と計算効率性が期待できます。詳細については、８月１６日から１８日にオタワにて開催される国際学会ＳＡＣ２０１７で発表します。

【開発の背景】
　大手ＩＴ企業や政府による大規模な投資により、量子計算機の開発は急ピッチで進んでいます。量子計算機が開発されると、現行の公開鍵暗号が安全性の根拠としている素因数分解問題や離散対数問題が、量子計算の原理を用いて短時間に解け、暗号が解読されてしまうことから、量子計算機でも解読が困難な耐量子公開鍵暗号の研究開発が近年活発に行われています。耐量子公開鍵暗号は一般に高速ですが、公開鍵サイズが大きいという問題があり、これまで実用化に至っていません。格子暗号を中心に、公開鍵サイズを削減するための改良が継続的に行われていますが、いずれの方式も安全性評価の途上で、国際的に合意が取れた方式はまだ存在していません。

【本技術の特徴】
　そこで当研究グループは、格子暗号などの従来の耐量子公開鍵暗号が安全性の根拠としている線形方程式の求解問題よりも計算困難である非線形方程式の求解問題に安全性の根拠を求める新たな方式を開発しました。これにより、線形方程式に適用できていた有力な解法が直接的に適用できなくなるため、安全性の向上が期待できます。これまでの評価では、改良の進んだ格子暗号と同程度の公開鍵サイズ（約2KB）で安全性の確保が可能となっています。今後の改良で現行の公開鍵暗号と同程度の短い公開鍵で安全性が実現できれば、実用化に道を拓くことができ、量子計算機の出現に耐え得る長期的に安全なネットワークが実現できます。

図：量子計算機でも解読困難な新しい原理に基づく公開鍵暗号を開発