そのクラウド、信用できますか? 〜プログラムを暗号化したまま実行する〜

この文章では「2019年度未踏IT人材発掘・育成事業」に採択された 「準同型暗号によるバーチャルセキュアプラットフォームの開発」について解説します。 可能な限り事前知識を仮定せずに書きましたので、ぜひご一読ください。 なお表示上の執筆者は「艮鮟鱇」となっていますが、実際の執筆はプロジェクトの採択メンバー全員に よります。

「クラウド」という言葉が市民権を獲得して久しくなりました。 一口に「クラウド」と言っても様々ですが、その多くは「他者に処理を移譲する仕組み」と 簡潔にまとめられます。例えば、GPUを使う機械学習のプログラムを書いたが手元にはGPUが無い。 そこでGPUが搭載されたクラウド上のマシンを 借りて代わりに実行してもらう、といったケースが分かりやすいでしょう。

(画像は全てクリックで拡大します)

このとき、処理を実行するにあたって必要なプログラムとデータは、 もちろんクラウドに送信する必要があります。しかし、もしこのプログラムやデータを秘匿したいと すればどうでしょうか。そうやすやすとクラウド上に置くことはできません。 「クラウド」というふわっとした言葉ですが、 その実体は地球上のどこかに設置されたコンピュータです。そのマシンの在り処を知っている クラウドの管理者であれば、そのマシンに直接接続して情報を抜き出すことが可能です。 あるいは、そのマシンを構成している機器自体に脆弱性があり、外部の人間がデータを盗聴することを 許してしまうかもしれません。 このように、自分の管理下にないマシンでは「ハードウェアが脆弱であることによる情報の漏洩」が 起こりえます。ハードウェアを信用している限り、この問題は常につきまといます。

この問題を解決するためには「ハードウェアを信用せずにプログラムを実行する」必要があります。 これはつまり「プログラムが実行される際にハードウェア中を流れる電気信号を 読み取ったとしても、実行されている内容が分かることはない」ということです。 このような動作を可能にする一つの手段は、ハードウェア中を流れる信号をすべて暗号化して しまうことです。しかしプログラム自体も電気信号ですから、これはすなわち 「プログラムを暗号化したまま実行し、暗号化された結果を取得する」ということを意味します。 しかし、「プログラムを暗号化したまま実行する」などということは可能なのでしょうか。

これを可能にするのが「準同型暗号」と呼ばれる特殊な暗号です。 準同型暗号を使用すると次の図のような演算が可能になります。すなわち、暗号化した値を〈足し算〉した上で復号化すると、 暗号化する前の値を直接足し算した結果と一致します。同様に〈掛け算〉も行うことができます。

ここで、暗号化した値同士の演算を〈足し算〉・〈掛け算〉と山括弧付きで表記しました。 実は、この〈足し算〉・〈掛け算〉の処理は暗号化していない数値の加算・乗算とは全く異なる操作で、 処理には大変時間がかかります。このことは後ほど詳述します。

さてこの準同型暗号がどのようにプログラムの実行と関係するのでしょうか。 すぐに思いつくことは「プログラム中の演算を準同型暗号の演算に変換すれば、 暗号化したままプログラムを実行できる」というものです。 すなわちプログラム中での数値の足し算を準同型暗号の〈足し算〉に、 掛け算を〈掛け算〉に変換すれば、準同型暗号上でそのままプログラムを実行できるように思えます。 しかしこの手法には重大な欠点があります。現在発見されている準同型暗号で行うことができる演算にはいくらか制限があり、特に「場合分け」をそのまま処理できるような準同型暗号はまだ見つかっていません。というのも場合分けは通常「値が1のときは足し算、2のときは掛け算……」といったふうに値に依存して何を行うか決める必要がありますが、暗号上でこれを行うことはとりもなおさず値を復号化することにつながってしまうからです。

この問題を解決するためには、準同型暗号についてもう少し知る必要があります。ここまで「準同型暗号」という言葉を使いまるで1つの暗号かのように扱ってきましたが、実は準同型暗号には様々な種類があり、扱うことができる演算も各々異なります。その中に論理演算を扱うことができる準同型暗号があります。論理演算というのはいわゆる電気回路を構成する演算でXORやANDといった種類があります。すなわち先程の〈足し算〉や〈掛け算〉のように〈XOR〉や〈AND〉を計算できる暗号というわけです。

さて、通常プログラム(をコンパイルして得た機械語)はプロセッサ(CPU)という大きな論理回路の上で実行されます。 大きい、とはいっても論理回路ですから、論理演算によって構成されることに変わりはありません。 そこでプロセッサ自体を準同型暗号上に構築し、その上でプログラムを実行することで「プログラムを暗号化したまま実行する」ことが可能になります。

stack

上記の構成を概念的に表すと上図のようになります。まずこのシステム自体は通常のCPU上で動作しています(下から1段目)。そのCPU上で〈XOR〉や〈AND〉といった準同型暗号の計算を行います(2段目)。その計算によって、プロセッサの論理回路が準同型暗号上で構築されます(3段目)。このプロセッサは暗号化したプログラムを受け取り、その内容を暗号化したまま実行します(4段目)。

完璧に思える準同型暗号ですが、一つ大きな欠点があります。 それはとてつもなく処理が遅いということです。現在知られている最速の実装でも、 1つの論理演算を評価するのに約0.13ミリ秒(=13万ナノ秒)かかります。 電気回路で使用する論理ゲートの出力は通常数ナノ秒で行われますから、 およそ10万倍遅いというわけです。

技術的な制約による速度低下も考慮し、 我々は目標とするプロセッサの動作周波数を60Hzとしました。60MHzでも60KHzでもありません。 今私がこの記事を書いているPCにはIntel Core i7-8700が搭載されており 動作周波数は4.6GHzとのことなので、およそ10億倍の差があることになります。 黎明期のコンピュータで1940年ごろに開発された ABC(アタナソフ&ベリー・コンピュータ) の基本動作周波数が60Hzとのことなので、いい勝負かもしれません。

しかし準同型暗号上で動くプロセッサの開発は他にほとんど例がなく、 まさに黎明期と言っていい状態です。我々のプロジェクトではこのアイデアの概念証明(PoC)を行うことを 主目的とし、速度に関しては今後の暗号学の発展に期待したいと考えています。

デモと成果報告会について

2019年度未踏事業における上記のような我々の取り組みは既にある程度成功しており、実際に動作するデモを GitHub上で公開しています(Linux環境等必須)。その利便性や速度の点において課題は山積していますが、残りの未踏期間(及びその後の活動)にて解決できればと考えています。

未踏事業における最終的な成果は、2020年2月に実施される「2019年度(第26回)未踏IT人材発掘・育成事業成果報告会」にて発表予定です。例年YouTubeでのライブ配信が行われるため、ぜひご視聴ください。

参考文献