公開鍵暗号の安全性の根拠となる計算で世界記録を更新

暗号技術では、より大きな数字によって秘密情報を表現するほど安全性が向上する反面、処理性能の低下をきたすため、秘密情報を表現する適切な大きさを見積もることが重要となります。今回、我々は、今後普及が見込まれる公開鍵暗号方式のベースとなっている離散対数問題について、676ビット長の場合に、汎用コンピュータ18台で33日と、現実的な計算機環境と処理時間で計算できることを世界で初めて実証しました。本成果は、今後のコンピュータの処理能力の向上によって、現在広く使われている1024ビット長の暗号技術の安全性が2020年までに危うくなるという将来予測（CRYPTRECプロジェクトによる）で示されている経過を裏付けています。さらに、世界最長ビットに対する計算に成功したことは、我が国の暗号技術の評価能力が世界トップレベルにあることを示す結果といえます。

本成果は、公開鍵暗号に関する世界有数の国際会議であるPKC2010（5月26日?28日：パリ）で発表する予定です。また、CRYPTRECプロジェクトに報告し、CRYPTRECシンポジウム2010（3月2日～3日：東京）で紹介いたします。我々は今後も、安全な暗号利用を促進するための指針を提供するため、より精密な評価を実施してまいります。

ネットショッピングやネットバンキングなど、現代の情報システムでは機密情報を扱う場面が非常に多くなっています。そのため、様々な暗号技術を利用して情報セキュリティを十分に確保する必要があります

近年、従来の公開鍵暗号では実現困難だった、利便性が高く様々なサービスに応用可能なIDベース暗号などの基礎となる「ペアリング暗号」の研究が盛んに行われています。NICTと公立はこだて未来大学は、ペアリング暗号の安全性について共同研究を行ってきました。

ペアリング暗号は「有限体上の離散対数問題」の難しさを安全性の根拠としているため、安全性を正確に評価するためには、計算可能なビット数の検証・評価を行う必要があります。今回、我々が676ビットの計算に成功したことは、広く扱われている1000ビット程度の計算が、近い将来に可能になってしまう可能性を示唆しており、従ってより長いビット数に変更したペアリング暗号を採用すべき時期を見積るための技術的根拠となります。

有限体上の離散対数問題の計算は、従来から世界各国の様々なグループが挑戦してきました。主要なグループである、(1)「ドイツのボン大学数学研究所のグループ」、(2)「フランスの国防省およびレンヌ数学研究所のグループ」、そして(3)「NICTおよび公立はこだて未来大学」について、計算に成功したビット数を比較すると以下のようになります。このように、今回我々が計算に成功したビット数（676ビット）は、従来の計算記録（613ビット）を大きく上回る結果となっています。

今回扱った有限体上の離散対数問題の計算では、最も高速な解法として知られている「関数体ふるい法」を用いました。関数体ふるい法は、以下で詳述する「多項式選択」、「関係探索」、「線形代数計算」、「離散対数計算」の4ステップからなります。今回は特に、扱った問題の数学的構造を利用することで、関係探索、線形代数計算の2ステップについて高速に計算することに成功しました。利用した計算機はNICT のサーバ12台、公立はこだて未来大学のサーバ6台の計18台で、Xeon96コア分のCPUコアにより、およそ33日間で計算に成功しました。これは、Xeon 1コアで約9年の計算時間に相当します。

以下、今回の計算におけるそれぞれのステップの詳細を示します。

1. 多項式選択
   このステップは残りのステップの計算量を決める重要なステップですが、効率的な選択手法が提案されているため、計算をほとんど必要としません。今回は、特に有効であると考えられている二つの選択手法について比較実験を行い、後のステップの計算がより少ないと予想される選択手法を用いました。


2. 関係探索
   このステップは、4ステップ中最も多くの計算が必要となりますが、ほとんど通信を行わずに並列計算が可能であるため、多くの計算機を利用することでより高速に計算を行うことができます。今回の計算では、扱った問題の数学的構造を利用することでこのステップの計算を従来のおよそ8倍高速に行うことができました。このステップでは、計算に約18日かかりました。


3. 線形代数計算（連立方程式の解法）
   このステップも関係探索と同様に多くの計算を必要とするステップですが、並列計算を行う際には通信を行う必要があるため、単純に多くの計算機を利用するだけでは高速に計算を行うことができません。今回は、扱った問題特有の数学的構造を利用することで、このステップの計算を従来のおよそ36倍の高速に行うことに成功しました。これにより、従来は関係探索と同程度の計算が必要だったこのステップを、およそ12時間の計算で行うことができました。


4. 離散対数計算（連立方程式の解を用いた任意の元の離散対数の計算）
   この最後のステップでは、関係探索と同様の計算を行いますが、関係探索と比較すると計算量はさほど必要とはしません。公立はこだて未来大学のサーバ6台のみを利用し、14日かけて、解となる離散対数を計算することに成功しました。得られた解について以下に詳述します。