IBMの準同型暗号が75倍高速化

IBM は C++ 準同型暗号化ライブラリを書き直し、速度が最大 75 倍になったと主張しています。

準同型暗号は、暗号化されたデータを復号せずに操作する技術です。これにより、機密性の高い操作の安全性が大幅に向上します。例えば、企業はクラウドでホストされているデータベースを暗号化し、レコードを平文に戻すことなく操作できるようになります。

IBM は長い間準同型暗号化に取り組んでおり、3 年前に HElib C++ ライブラリの最初のバージョンをリリースしましたが、2016 年に報告したように、このテクノロジは常にパフォーマンスの大きなペナルティに悩まされてきました。

IBMが最初に準同型暗号を試みた際、発明者のクレイグ・ジェントリー氏の手による処理速度は平文処理の「100兆倍」と低かった。その後、16コアのサーバー上で動作し、200万倍の高速化を実現した。

そのため、Big BlueはHElibの開発を続けています。GitHubでリリースされた最新バージョンでは、「準同型線形変換の再実装」によってパフォーマンスが向上し、15～75倍の高速化を実現しています。

国際暗号研究協会のこの論文では、IBM の Shai Halevi 氏と Victor Shoup 氏 (後者はニューヨーク大学に所属) が、速度をどのように向上させたかを説明しています。

「現在HElibに実装されている線形変換アルゴリズムでは、暗号化されたベクトルのスロット間でデータを移動するのに時間の大部分が費やされている」と彼らは書いている。

これは「特殊な自己同型」（オブジェクトをそれ自身にマッピングする数学的演算）を使用して行われ、計算コストは​​自己同型を何回ループする必要があるかによって決まります。

「このような自己同型を暗号文に適用する際の主なコストは、実は『鍵交換』である。自己同型を暗号文の各環要素に適用すると（これは実は非常に低負荷な操作である）、最終的に『間違った』秘密鍵に関連する暗号化が得られる。この特定の自己同型に固有の公開鍵のデータ、いわゆる『鍵交換行列』を使用することで、暗号文を『正しい』秘密鍵に関連する暗号化に戻すことができる」と論文には記されている。

「したがって、パフォーマンスを向上させる主な目標は、自己同型性の数を減らし、各自己同型性のコストを削減することです。」

もっと分かりやすく言うと、新しいライブラリはそれらの自己同型を計算​​するための新しい戦略を実装し（15～20 倍の高速化を実現）、研究者は必要な計算の多くをリファクタリングし、計算の一部はライブラリのメイン ループからシフトされます（6～8 倍の高速化を実現）。

準同型暗号の公開鍵構築方法も、前述の鍵交換行列のためにコストがかかります。各行列は公開鍵に数メガバイトを追加し、HElibでは公開鍵に数百のこのような行列が含まれる可能性があります。研究者らは、一般的な操作において、行列のサイズを33～50%削減できたと述べています。

HElibはまだ研究レベルのプロジェクトです。GitHubページには次のように記載されています。「現時点では、このライブラリは主に高等教育とその利用に関する研究者を対象としています。また、現時点ではかなり低レベルであり、『高等教育用アセンブリ言語』と考えるのが適切でしょう。つまり、低レベルのルーチン（設定、加算、乗算、シフトなど）を提供し、可能な限りの最適化機能も提供しています。将来的には、より高レベルのルーチンも提供できるようになることを期待しています。」®