完全準同型暗号（FHE）

解きたい問題：鍵を渡さず計算を委託する

クラウドに重い計算を任せたいが、データは見せたくない。従来これは矛盾でした。計算するには平文が要り、平文をサーバーに置けば管理者も攻撃者も読めてしまう。ストレージの暗号化（保存時暗号化）はデータを守りますが、計算する瞬間には必ず復号するため、処理中のデータは無防備になります。

**完全準同型暗号（Fully Homomorphic Encryption, FHE）**が解くのはこの「計算中のデータ保護」です。暗号化したまま加算も乗算も任意回数実行でき、サーバーは中身を一切知らないまま結果の暗号文を返す。復号鍵はデータ所有者だけが持ち、最後に自分で復号して答えを得ます。公開鍵暗号の前提は 暗号の基礎 を、FHE と対をなす多者間の秘匿計算 MPC は 準同型暗号と秘密計算（MPC） を参照してください。本稿は FHE の内部動作を掘り下げます。

準同型性：暗号文のまま演算する

準同型（homomorphic）とは、平文への演算と暗号文への演算が「対応する」性質です。暗号化を Enc、復号を Dec とすると、暗号文上のある演算に対して次が成り立ちます。

Dec( Enc(a) ⊕ Enc(b) ) = a + b      # 加法準同型
Dec( Enc(a) ⊗ Enc(b) ) = a × b      # 乗法準同型

つまり復号鍵を持たない者が暗号文だけを操作し、平文の和や積に対応する暗号文を作れる。どこまでの演算を許すかで準同型暗号は三段階に分かれ、これが「部分」から「完全」への発展の軸になります。

部分準同型の代表が Paillier 暗号で、Enc(a)・Enc(b) mod n^2 = Enc(a+b) という加法準同型を持ち、電子投票の集計や秘匿統計で実用されています。教科書的 RSA は Enc(a)・Enc(b) = Enc(a×b) の乗法準同型を持ちますが、いずれも片方の演算しかできないため、加算と乗算を混在させる一般の計算には使えません。「加算と乗算の両方を、しかも何度でも」を実現することが FHE への課題でした。

完全準同型（FHE）：LWE とノイズ

加算と乗算を両方とも任意回数できれば任意計算が可能になる――この構成が長く未解決で、2009 年に Craig Gentry が初めて実現可能性を示しました。現代の FHE はほぼすべて**格子問題 LWE（Learning With Errors）を土台にします。LWE 暗号文は意図的に小さなノイズ（誤差項）**を含む形で作られ、このノイズの存在こそが安全性の源です（LWE の詳細は ポスト量子暗号 を参照）。

概念的には、平文 m を鍵ベクトル s との内積に埋め込み、小さな誤差 e を加えて隠します。

暗号文 ≈ (a, b),  b = <a, s> + m + e      （a はランダム、e は小さいノイズ）
復号: m ≈ b - <a, s>  … 残る e が閾値以下なら m を正しく取り出せる

ノイズ e が小さいうちは復号で丸めて除去でき、正しい平文が得られます。問題は、暗号文どうしを演算するたびにこのノイズが増大することです。

加算: ノイズはおおむね足し算で増える（緩やか）
乗算: ノイズはおおむね掛け算で増える（急激）
→ 演算を重ねるとノイズが許容上限を超え、復号しても正しい平文が得られなくなる

ここに部分準同型では起きなかった FHE 固有の壁があります。演算できる回数がノイズ上限で頭打ちになる。ノイズが閾値を超える前で止めるのが**やや準同型（Somewhat/leveled HE）**で、計算の深さ（乗算の段数）が事前に分かっているなら、それに合わせてパラメータを大きく取れば FHE を使わずに済みます。実務では leveled のほうが高速で、機械学習の固定深さ推論などで広く使われます。

ブートストラップ：ノイズを暗号文の中で消す

Gentry のブレークスルーが**ブートストラップ（bootstrapping）**です。発想は逆説的で、復号処理そのものを準同型に評価することでノイズをリフレッシュします。

ブートストラップは「ノイズを一定水準までリセットする操作」だと捉えると分かりやすい。計算を進めてノイズが上限に近づいたらブートストラップで下げ、また計算を進める、を繰り返せば無制限に深い回路を評価できます。代償は重さで、ブートストラップは FHE 最大の計算コスト要因です。1 回に数十ミリ秒から数秒を要する実装もあり、深い計算ではこれが支配的になります。

FHE スキームの系統

FHE には用途別の系統があり、扱うデータ型と得意な演算が異なります。

性能の要が **SIMD バッチング（packing）**です。1 つの暗号文に多数の平文スロットを詰め込み、1 回の準同型演算で全スロットを並列に処理できます。数千スロットをまとめて扱えば、暗号文 1 個あたりのコストを実質的にスロット数で割れるため、CKKS が機械学習で好まれる大きな理由になっています。TFHE は逆に 1 ビット単位の高速ブートストラップに振り、任意のブール回路を組み立てやすくしています。

実用上の性能課題

FHE は理論的には何でも計算できますが、「可能」と「実用的な速度で可能」は別問題です。壁は大きく三つあります。

• 計算オーバーヘッド：平文計算に比べ数千〜数万倍、用途により数百万倍の演算量がかかります。とくにブートストラップを含む深い回路は重く、リアルタイム処理には遠い領域が多い。
• 暗号文の肥大化（ciphertext expansion）：1 ビットの平文が数 KB の暗号文になり、通信量とメモリを圧迫します。SIMD バッチングはこれをスロット数で薄める緩和策でもあります。
• 深さとパラメータのトレードオフ：leveled 運用では扱える乗算段数を増やすほど格子の次元やモジュラスを大きく取る必要があり、暗号文もノイズ余裕も増大します。深い計算ほどパラメータが膨らみ、さらに遅くなります。

現状の実用化は、秘匿推論（暗号化した入力に学習済みモデルを適用し暗号化した推論結果を返す）や、暗号化データベースへの限定的な集計クエリなど、計算の深さと形が事前に分かる用途に絞られています。GPU・専用ハードウェアによる高速化、ブートストラップの改良、バッチングの最適化が研究の主戦場で、汎用の高速 FHE はなお発展途上です。

まとめ

FHE は暗号化したまま任意の計算を実行する暗号で、鍵を渡さずに計算をクラウドへ委託できます。準同型性は平文と暗号文の演算の対応で、加算か乗算の一方だけの部分準同型、回数制限付きのやや準同型、任意回数の完全準同型へと発展しました。現代の FHE は格子問題 LWE のノイズ付き暗号文で作られ、演算のたびに増えるノイズが復号を妨げるという固有の壁を、ブートストラップ――復号回路を暗号文の中で準同型評価してノイズを一定水準に戻す操作――で乗り越えて任意回数の演算を可能にします。

スキームは整数厳密の BGV/BFV、実数近似で機械学習向きの CKKS、ブール回路と高速ブートストラップの TFHE に分かれ、SIMD バッチングが性能を左右します。ただし平文計算の数千〜数百万倍のコストと暗号文の肥大化が残り、実用化は深さの決まった秘匿推論などに絞られる段階です。土台の格子問題は ポスト量子暗号、多者間で秘密を持ち寄る対の技術は 準同型暗号と秘密計算（MPC） と併せて押さえると、プライバシー保護計算の地図が描けます。