暗号学には多くのエレガントなアイデアがある。完全準同型暗号（FHE）は、実際に機能する中で最も奇抜なものかもしれない。
そのアイデアはこうだ。自分のデータを暗号化して他者に渡し、その人がデータに対して計算を行い、結果を返す。その結果を復号化すると、正しい答えが得られる。計算を行った人はあなたのデータを一切見ていない。加工されたバージョンでもなく、ハッシュでもない。実際の元の値が、1マイクロ秒たりとも露出することはない。
Craig Gentryは2009年にこれが可能であることを証明した。暗号学コミュニティは、それ以前の約30年間、これが実現可能かどうかを問い続けていた。
FHEの仕組み
通常の暗号化は一方通行の扉だ。データを鍵でかけると、それを使いたい人はまず鍵を開けなければならない。FHEは扉を施錠したまま、外側から家具を並べ替えることができる。
より正確に言うと、FHEスキームは暗号文に対して2つの演算を定義する。一般的に準同型加算と準同型乗算と呼ばれるものだ。これらは元の平文に対する同じ演算に対応する。2つの暗号化された値を加算すると、その結果を復号化したとき、元の値の和と等しくなる。乗算も同様だ。
この2つの演算があれば、コンピュータが計算できるあらゆる関数を構築できる。（2値体上の加算と乗算はANDゲートとXORゲートを生み出し、それが任意の回路を実現する。）これが「暗号化された数値に対する2つの演算」から「暗号化されたデータに対する任意の計算」への架け橋だ。
問題はノイズだ。FHEの演算を行うたびに、暗号文にわずかな誤差が加わる。演算を重ねるとノイズが信号を圧倒し、復号化できなくなる。Gentryの主要な貢献は、ブートストラッピングと呼ばれる技術だ。暗号文がまだ暗号化された状態のまま、その上で復号化回路を実行し、ノイズレベルをリセットする方法だ。深く考えると非常に奇妙に感じる。復号化関数が……暗号化の内部で復号化するのだ。これこそがこのスキームを「やや」準同型ではなく「完全」準同型たらしめる理由だ。
やや準同型暗号（SHE）は、ノイズが致命的になる前に固定数の演算を処理できる。レベル準同型暗号（LHE）は、あらかじめ決められた回路深度を処理できる。FHEはブートストラッピングにより処理を継続できるため、任意の回路を無制限に処理できる。
FHEが現在利用可能な分野
ほとんどのアプリケーションにとって、FHEはまだ処理が遅すぎる。しかし「ほとんど」には明確な例外がある。現在、実際に稼働しているデプロイメントも存在する。
プライベートな機械学習推論。クライアントは機密性の高い入力データを持ち、サーバーは独自のモデルを持っている。どちらも自分が持っているものを相手に開示したくない。FHEを使うと、サーバーはクライアントの暗号化された入力に対してモデルを評価し、クライアントが復号化できる暗号化された結果を返すことができる。サーバーは入力を一切見ない。クライアントはモデルの重みを一切見ない。特定のモデルアーキテクチャに対して、この仕組みを導入した企業もある。回路深度が有界で予測可能なため、このワークロードはFHEの現在の制約に適合している。
プライベートなゲノム計算。 ゲノムデータは社会保障番号をはるかに超えるセンシティブな情報だ。親族に影響を及ぼし、永続的であり、参照データベースが拡大するにつれてプライバシーリスクが複合的に増大する。研究者たちはFHEを使って、計算を行う側に元の配列を開示することなく、疾病リスクスコアや遺伝的比較を計算してきた。iDASHコンペティションは2014年からこのユースケースのベンチマークを行っている。
プライベートなデータベースクエリ。何を検索しているかを明かさずにデータベースを照会したい場合がある。キーワード検索、範囲クエリ、集合メンバーシップテストのいずれも、FHEによる構成が存在する。オーバーヘッドはまだ大きいが、低頻度・高価値のクエリであれば管理可能だ。
プライバシー保証付きの連合計算。複数の病院が、記録を共有することなく、統合された患者データでモデルを訓練したいとする。FHE（多くの場合、セキュアマルチパーティ計算と組み合わせる）を使えば、データを統合することなく結合計算を実現できる。
FHEと他のプライバシー保護アプローチの比較
FHEは単独で存在するわけではない。以下を含むスタックの中の1つのツールだ。
セキュアマルチパーティ計算（MPC）：複数の当事者が互いの入力を開示することなく、共同で関数を計算する。MPCは特定の関数においてFHEよりも速いことが多く、共謀しない複数の当事者が必要だ。FHEは単一のサーバーで動作する。
差分プライバシー（DP）：出力に調整されたノイズを加えることで、攻撃者がデータセット内の個人について推測できる範囲を制限する。DPは集計結果に対する推論攻撃から守るが、プライベートな入力に対する計算を提供するわけではない。
トラステッド実行環境（TEE）：オペレーティングシステムが読み取れないシールドされたメモリ領域でコードを実行するハードウェアエンクレーブ（Intel SGX、AMD SEV）。TEEはハードウェアベンダーを信頼し、実装に欠陥がないことを前提とする。FHEは数学を信頼することを前提とする。
ゼロ知識証明（ZKP）：なぜ真であるかを明かさずに、ある命題が真であることを証明できる。ZKPは性質を証明し、FHEはプライベートな値に対して計算を行う。両者は補完的な関係にある。
ハイブリッドシステムはますます一般的になっている。FHEが機密性の高い計算を担い、ZKPが計算が正しく行われたことを検証し、MPCが信頼を分散させる。複数の技術から同時に特性を必要とするシステムを構築する実践者が増えるにつれ、これらの技術の境界は溶け合っている。
