クラウド向け暗号技術の安全性評価で世界新記録を達成

～暗号化したままデータを処理する“格子暗号技術”の実用化に向けて～

2013年1月21日

独立行政法人情報通信研究機構（以下「NICT」、理事長：宮原秀夫）は、暗号化したままデータを処理する技術である「完全準同型暗号」の安全性を支える「格子の最短ベクトル問題」の解析を行い、世界で初めて、825次元もの高い次元の問題を解くことに成功しました。

「完全準同型暗号」を利用すると、他へ機密データの内容を一切知らせることなく計算作業を託すことが可能となるなど、クラウド・コンピューティング等でのセキュリティ確保のためにこの暗号が活用されることが期待されています。「格子の最短ベクトル問題」の評価は、完全準同型暗号を安全に利用するために不可欠であり、実用化に向けた第一歩となるものです。

背景

クラウド・コンピューティングの発展により、従来は組織内サーバで行っていた情報処理を、外部の計算機資源で行う流れが進み、機密データについても安心してクラウドを活用できる技術が求められています。2009年に米IBM社から発表された「完全準同型暗号」は、格子理論を利用し、データを暗号化したまま様々な演算が可能となる技術として注目を集めています。この暗号技術の安全性を支える根拠の一つが、「格子の最短ベクトル問題」と呼ばれる難問です。この問題は、現在広く利用されている公開鍵暗号の安全性評価に活用されているほか、量子コンピュータ実現後も高い安全性が保たれる格子暗号の安全性の根拠となっていることから、極めて重要な問題として世界の多くの研究機関で精力的に研究が進められています。

今回の成果

図1　格子の最短ベクトル問題の難しさ

「完全準同型暗号」を安全に利用するためには、「格子の最短ベクトル問題」がどの次元まで解けるのかを評価することが必要となります。

このたび、NICTと株式会社日立製作所（代表執行役執行役社長：中西宏明）は共同で、「格子の最短ベクトル問題」の難しさの評価を行いました。我々はこの問題を解くために、現在知られている最も効率の良いアルゴリズムに改良を加え、パラメータを最適化したプログラムを開発しました。

この改良プログラムを実証するため、ドイツのダルムシュタット工科大学が主催し、世界の著名な暗号研究者がしのぎを削っている解読コンテスト「TU Darmstadt Lattice Challenge」に挑戦しました。その結果、これまで1年以上更新がなされていなかった世界記録を更新し、825次元の格子の最短ベクトル問題を、市販の汎用サーバ(CPU: AMD Opteron 6276 (2.3GHz/16Core)×4, メモリ: 64GB)を用いて、わずか5.5日で解くことに成功しました。

今後の展望

クラウド上での秘匿情報処理の実用化に向け、より高速な解読アルゴリズムを開発し、さらに大規模な実験により安全性を検証してまいります。なお、本成果は、平成25年1月22日（火）～25日（金）に京都で開催される「2013年暗号と情報セキュリティシンポジウム(SCIS2013)」で発表します。

補足資料

格子暗号のしくみ

格子暗号の概念図を図3に示します。ここでは、メッセージ送信者が受信者に対して、1文字のひらがなを送る場合を考えます。文章の送信は、この手続きを繰り返すことで実現できます。まず、メッセージ送信者が受信者に対して、格子暗号で文字を送ることを伝えます。メッセージ受信者は格子模様を用意し、交点に文字を書き込み（図3-①）、それを斜め上から写真に撮ったものをメッセージ送信者に送ります（図3-②）。写真を受け取ったメッセージ送信者は、自分が送りたい文字の近くに印を付けて、受信者に送り返します。この印が、文字を暗号化したものになります。このとき、印と文字が近過ぎると、写真を盗み見た人にメッセージが分かってしまうので、適度に離しておきます。最後に、返信された写真の印を手元の格子模様に写し、印に一番近い交点の文字を読みます。

図3　格子暗号の概念図

図3において、写真を盗み見た人が格子の最短ベクトル問題を解くことができれば、写真に付けられた印の位置からもとの文字を読み取れることが分かっています。そのため、この問題の難しさを評価し、たとえ写真を盗み見られても安全であるようなパラメータを見積もることが必要になります。

完全準同型暗号のしくみ

上に紹介した例では、ひらがなを送っていましたが、同様の原理で数字を送ることも可能です（図4左）。さらに、2009年にクレイグ・ジェントリーの発明した完全準同型暗号方式を用いると、数字同士を暗号化したまま加算と乗算が行えます。例えば、図4右では数字の“1”を暗号化した印（赤い＊）と数字の“3”を暗号化した印（青い＊）を足すことで、新しい印（緑の＊）ができます。これを上に紹介した方式と同様に復元すれば、数字の“4”が出てきます。印同士の乗算を考えることで、数字を暗号化したままで乗算をすることもできます。

図4　完全準同型暗号の概念図

今回の成果のポイント

格子の最短ベクトル問題は難しい問題ですが、BKZアルゴリズムと呼ばれる、問題を少しずつ簡単なものに変換していくタイプのアルゴリズムを何回か繰り返すと、最終的に最短ベクトルを計算することができます。我々は、パラメータの最適化や無駄な処理の削減により、この変換処理を高速化しました。また、（近似）最短ベクトル問題を解くための、具体的な計算時間を予測する手法を開発しました。

この改良プログラムを用いて、ドイツのダルムシュタット工科大学が主催している、格子の最短ベクトル問題のコンテスト「TU Darmstadt Lattice Challenge」に挑戦し、これまでの世界記録を更新しました。世界記録のランキングが、図5に示すホームページに掲載されています。

図5　格子最短ベクトル問題チャレンジ
（TU Darmstadt Lattice Challenge.)

用語解説

完全準同型暗号 (Fully Homomorphic Encryption)

データを暗号化したままの状態で、もとのデータの加算と乗算の演算が行える暗号方式。2009年に米IBM社の暗号研究者、クレイグ・ジェントリーが格子理論を利用して、初めて完全準同型暗号の開発に成功した。

格子の最短ベクトル問題 (Shortest Lattice Vector Problem)

図2　2次元格子の例

格子とは、図 2に示すような空間内の規則正しく並んだ点(ベクトル)の集合である。コンピュータの内部では、格子は基底と呼ばれるベクトルの集合によって表現される。図の例では、v1, v2の2本のベクトルが基底となり、その組み合わせの全体が格子（図中の青い点）となる。2本のベクトルで構成されているので、これを2次元格子と呼ぶ。

格子の最短ベクトル問題は、格子の基底が与えられたときに、原点以外で、最も原点に近い格子点を見つける問題である。図2の例では、v2が最短ベクトルであるが、大きな次元の格子では最短ベクトルを求める問題は非常に難しい。

公開鍵暗号 (Public Key Cryptography)

1976年に米国の暗号研究者、ディフィーとヘルマンにより提案された暗号方式で、メッセージを暗号化するための鍵と復号するための鍵を別々に用意する。それまでの暗号化方式では、メッセージの送信者と受信者以外に鍵を知られてはならないという制約から、暗号化通信の準備段階での鍵の共有に多大な手間がかかっていた。これに対し、公開鍵暗号方式では、暗号化に使う鍵から復号に使う鍵を容易に計算できないという性質があるために、暗号化に使う鍵を一般に公開する形でメッセージの送信者に知らせることができるので、暗号化通信の準備が格段に楽になる。代表的な方式として、RSA暗号や楕円曲線暗号等があり、WebブラウザやパスポートのICチップに組み込まれて個人情報のやり取りなどに使われている。

格子暗号　(Lattice-based Cryptography)

格子の最短ベクトル問題など、格子理論における難しい問題を安全性の根拠とする暗号方式。量子コンピュータが実現すると、現在広く利用されている公開鍵暗号のほとんどの安全性が低下するのに対し、格子暗号は量子コンピュータ実現後も高い安全性が保たれるため、長期間利用可能な次世代の暗号として期待されている。

格子最短ベクトル問題チャレンジ (TU Darmstadt Lattice Challenge)

ドイツのダルムシュタット工科大学が2008年より主催している、格子の最短ベクトル問題のコンテスト。この問題の難しさを検証するため、500次元から2000次元までのチャレンジ問題が25次元刻みで出題されており、この分野の著名な研究者がより大きな次元、より短いベクトルの探索を目指してしのぎを削っている。