ブロックチェーンエンジニアのびりあるです。
データベースの検索内容をサーバ側に知られることなく検索ができる「Private Information Retrieval (以下PIR)」という暗号技術があるのですが、既存の実装ではシングルコアかつCPUでしか計算できるものがなく、実用的な範囲の計算時間では大規模化が難しいという課題がありました。
そこで、独自の研究開発を重ね、並列化がCPUもりも難しいGPUを用いて非常に高い効率で並列化ができるアルゴリズムを考案し、その試験実装を行った結果、家庭向けの安価なGPU (NVIDIA GeForce RTX 3080) 一台のみで、従来実装と比べて実実行時間性能ベースで約100倍程度の改善を行うことができました。
本研究結果をもとにし、特許と商標権の出願を行いましたのでその道のりを解説します。
Private Information Retrieval (PIR) とは？
一般的な検索エンジンでは (SSLを使って通信途中は暗号化されるものの) サーバ側では平文で検索クエリが送信されるため、検索エンジン側には何を検索したのかがすべて分かってしまいます。
行きたいお店の住所などを調べたら、検索エンジンはその人がそのお店にこれから行くであろうことを学習します。
もっと直感的な例だと、エロい単語を検索することってありますよね？？？
あなたの性癖は検索エンジンにもろバレです。
こうした問題を解決するのがPIRです。
PIRでは検索クエリをクライアント側の鍵ペアで暗号化し送受信するため、秘密鍵を知らないサーバは解読することが原理上不可能です。
PIRを用いることで、あなたの検索内容をまったく知られることなく検索を行うことができます。
Torじゃダメなの？
多くのケースではTorでも十分ではあります。
Torは三つ（以上）のサーバを経由してネットワークパケットを送信することで、送信元IPを秘匿化してくれる技術です。
そうすると、経由したサーバの入口（entry）と出口（exit）のノードを同一の組織が運営していた場合には通信内容はもろバレです。
NSAがTorネットワーク上に多数のノードを挿入することでTorネットワーク上のパケットを傍受しているなどの噂もあり、数学や暗号学的に保証されたセキュリティは提供できません。
また、プライベートAPIなどのログインが必要なエンドポイントにアクセスする際には、いくら送信元IPアドレスを隠したからといって、通信先のサーバには認証の資格情報から誰からアクセスしたか分かってしまいます。
これでは完全な匿名化を提供しているとは到底言えません。
下調べ
PIRは非常にマイナーな暗号技術であり、論文を検索してもあまり活発に研究がされていないようです。
とはいえ古いものも含めれば論文はいくつかありまして、いろいろ調べたところ大まかに
- 互いに結託して情報を漏洩しない複数のサーバで処理する方法 (⇦ 本当に結託していないか確認できないのでNG)
- Quadratic Residuosity Problem (QRP) と呼ばれる数学的に困難とされている問題を利用する方法 (⇦ 1ビットしか送れないので非常に効率が悪い)
- 準同型暗号 (Homomorphic Encryption; HE) を用いた方法 (⇦ 情報量の問題は解決するが、Learning With Errors (LWE; 格子暗号) を利用しているため並列化ができない)
という流れで研究が発展していっていることが分かりました。
実際に研究論文を書くための試験実装 (僕が一番試したのは当時最新だった Microsoft の SealPIR というもの) が GitHub で公開されているのですが、バックエンドとして使っている準同型暗号ライブラリの Microsoft Seal のアルゴリズムの改良によりバージョンが上がって最新バージョンではビルドできないみたいな状況で、実用化している人は皆無でした。
SealPIR は古いバージョンの Seal を使っていて、最新の高速になったバージョンでは動きません。
そして Seal は、マルチコア化の議論自体はありそうでしたが、研究していた当時は並列化ができていませんでした（たぶん今でもシングルコアです）。
CPUのシングルコア性能は、ISAの改良やL1/L2キャッシュメモリの増加、演算回路の最適化などにより年々上がっているものの、ムーアの法則よりは遥かに遅いスピードです。
そのため、CPUメーカーはコアをたくさん増やすことでトータルの演算性能の増強を図っていく方向にシフトしているというのが現状です。
またAI技術の後押しも相まって、GPUの性能は飛躍的に向上しており、GPUなどの総合的な計算能力の高いメニーコア・プロセッサでも動作する PIR アルゴリズムが必要であるという考えに至りました。
研究の時間
LWE (格子暗号) の並列化なども検討しましたが、LWE は非常に高い次元の多項式を取り扱う必要があるという関係上、どうしてもGPUのように各コアのもつレジスタメモリサイズが限られており、コア間通信がコア内の計算速度に比べると非常に遅い計算デバイスでは並列化が困難です。
巨大な多項式を複数コアで処理しようとすると、大量のコア間通信が発生しますのでプログラミングの難易度もかなり高いですし、コア間通信がボトルネックとなってしまい大した性能がでない、というのが予想されました。
そこで僕はそもそも暗号アルゴリズム自体を変えてしまえばいいのではないか、と考えました。
LWE は足し算も掛け算もできる「完全」準同型暗号ですが、PIR の計算においてはスカラーと暗号文の掛け算と、暗号文同士の足し算しか発生しません。
スカラーと暗号文の掛け算については、繰り返し自乗法を用いることで暗号文同士の足し算ができれば効率的に実装できます。
つまり、利用する暗号方式は「完全」準同型暗号である必要はなく、足し算（加法）だけができる「加法部分準同型暗号 (Additionally Partially Homomorphic Encryption)」であれば十分です。
加法部分準同型暗号には様々な方式がありますが、僕が注目したのは「ElGamal暗号」特にその楕円曲線 (Elliptic Curve; EC) 版である「EC-ElGamal暗号」です。
ElGamal暗号はかなり古い部類の公開鍵暗号方式であり、特に楕円曲線版のものは鍵長256ビットでも十分安全であるとされており（RSAなどは最低でも2,048ビットが推奨です）、非常に短い暗号文となることが特徴です。
暗号文が短ければ短いほど、GPUなどの限られたメモリ資源でも効率的に計算できますし、クライアントとサーバ間の通信量も節約できます。
またLWEは比較的新しい暗号アルゴリズムであり、その安全性が確かなものであるかどうかはまだまだ議論の余地がありそうですが、ElGamal暗号は離散対数問題 (Discrete Logarithm Problem; DLP) という非常に長い歴史の中で議論され続け、解くのが困難であると多くの研究者から信じられているものにしか依拠していません。
SSL で用いられている Diffie-Hellman (DH) 鍵共有やECDSA、EdDSAなど現在主流の暗号方式は概ねこの DLP の困難性を安全性の担保としています。
実装の時間
さて、方針が決まればあとは試験的な実装をして実実行時間を検証するだけです。
しかし楕円曲線ライブラリも、ElGamal暗号のライブラリも、GPU向けのものはほとんどなく苦労しました。
楕円曲線としては現在最も効率や安全性のバランスがよいと思われる Ed25519 で用いられている曲線 (Curve25519) を利用しました。
幸い、libsodiumというプロジェクトがC言語でEd25519を実装していましたので、楕円曲線の計算をする部分だけを切り出し、OpenCLで動作するように移植しました。
またElGamal暗号の処理については、ElGamal暗号自体が残念ながらメジャーではなく（RSA暗号などと比べると計算効率や暗号文のメッセージサイズが悪いからだと思います）、信頼できる実装は発見できませんでしたので自前で実装しました。
またGPUでも効率的に並列化できる工夫とか、EC-ElGamal暗号固有の楕円曲線計算の最適化技法などもいろいろと駆使し、かなり最適化はできたと思います。
とまぁ実装は最初考えていたよりも時間がかかりましたが、無事正しく動く実装が完成しました。
実際に動かしてみたところ、既存のPIRアルゴリズムが100万データベース要素で2秒くらいの計算性能だったところ、家にあった家庭向けのハイエンドGPU (NVIDIA GeForce 3080) でも一億データベース要素で2.6秒と、約77倍の性能が出たときは本当に嬉しかったです。
家にGPUが一台しかなく、複数枚での実装も性能評価もまだできていませんが、今回発明したアルゴリズムは基本的にコア間通信が発生しませんので、GPUの枚数を増やせばその分だけ速くなると思われます。
特許出願
暗号アルゴリズムについては、あまり特許を取るのは得策ではなかったりします。
例えば Schnorr 署名は開発者の Schnorr さんが特許を取得していたためほとんど利用されていませんでしたが、特許が切れてからは非常に広く利用されるようになりました。
Schnorr 署名は EdDSA やビットコインなどで利用されています。
とはいえ、「なんか特許とか持ってたら一流の研究者みたいな気がしてくるし、嬉しくない？」みたいな軽いノリで特許取得に動き出しました。
まぁ既に特許はひとつ持っていたのですが、ニつ目ということで。
そもそもこれは基礎暗号技術の特許になるため、数学と同じですぐに実用化できるような代物ではなく、特許で収益をあげられるとは思っていません。
知り合いの紹介で特許事務所に問い合わせたのですが、「ちょっとその内容は難しくてできないですね……」と言われてしまいました（泣）
ですが他の事務所を何件かあたり、数学科を卒業した優秀な弁理士さんのいる特許事務所を見つけることができ、無事特許出願ができました（まだ権利化はしていません）。
商標
最近はオンラインで簡単に商標出願ができるサービスがいくつかあり、それを利用しました。
費用としては10万円代くらいでしょうか。
いまは特許庁の審査待ちですが「EllipticPIR」という名前で出願したので、まぁ他と被ることはないと思いますので拒絶査定になることはないでしょう。
今後の展開
既に述べましたが、基礎暗号技術なので、すぐに需要が見つかるとは思っていません。
10年後ぐらいに売上が立てばいいかな、くらいのスタンスで副業としてやっていきます。
まずは利用企業が自社のデータベースをアップロードして利用できるクラウド (SaaS) サービス「EllipticPIR Cloud」を提供したいと思っています。
ですが、開発には労力がかかりますし、どういったユースケースがあるのか分からないと詳細なサービス設計もできませんので、当面の課題は利用していただける企業様を見つけること（営業）かな〜、と思っています。
そんな感じなので、もしこの記事を読んでいただいて「自社サービスで使えるかも？」と思った企業の担当者様がいらっしゃいましたらぜひ僕あてにご連絡をください！
技術的な詳細とか説明させていただきます。
誰か使ってくれる人がいたら嬉しいな！と思いながら引き続きアルゴリズムや実装の改良などを続けていきます💪