準同型暗号と秘密計算（MPC）の原理

解きたい問題：「見せずに計算する」

通常、データを計算するにはまず復号して平文に戻す必要があります。クラウドに重い計算を委託するなら、サーバーは平文を読める。複数の病院が患者データを持ち寄って統計を出すなら、互いに生データを見せ合う。これがプライバシーと有用性のトレードオフで、医療・金融・行政のデータ連携を阻む最大の壁です。

この矛盾を暗号で解くのが準同型暗号（Homomorphic Encryption, HE）と秘密計算（Secure Multi-Party Computation, MPC）です。両者は「平文を一切露出させずに計算結果だけを得る」という同じゴールを、異なる前提で達成します。HE は1 人がデータを暗号化して 1 つのサーバーに計算を委ねる形、MPC は複数者が各自の秘密入力を持ち寄って協調計算する形に向きます。基礎となる公開鍵暗号の考え方は 暗号の基礎 を前提とします。

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

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

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

つまり復号鍵を持たない者が、暗号文だけを操作して、平文の和や積に対応する暗号文を作れる。サーバーは中身を一切知らないまま計算を代行できます。どこまでの演算を許すかで、HE は三段階に分かれます。

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

完全準同型（FHE）：ノイズとの戦い

加算「と」乗算を両方とも任意回数できれば、論理ゲート（AND/XOR は乗算と加算で表せる）を組めるので、原理的にどんな計算も暗号文上で実行できます。これが FHE で、2009 年に Craig Gentry が初めて構成可能性を示しました。

現代の FHE はほぼすべて**格子問題 LWE（Learning With Errors）を土台にします。LWE 暗号文は意図的に小さなノイズ（誤差項）**を含む形で作られ、このノイズの存在が安全性の源です（詳細は ポスト量子暗号 の LWE 解説を参照）。問題は、暗号文を演算するたびにこのノイズが増大することにあります。

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

ノイズが閾値を超える前なら正しく復号できる――この「許容回数の範囲内」で止めるのが**やや準同型（SHE / leveled HE）**です。あらかじめ計算の深さ（乗算の段数）が分かっているなら、それに合わせたパラメータを選べば FHE を使わずに済み、実務では SHE のほうが高速で広く使われます。

FHE スキームには用途別の系統があります。BGV / BFV は整数の厳密な演算（剰余演算）に向き、CKKS は実数・複素数の近似演算を許す代わりに機械学習のベクトル計算に適し、TFHE はビット単位のブール回路評価と高速 bootstrapping に強みがあります。SIMD バッチング（1 つの暗号文に多数の平文スロットを詰めて並列演算する）も性能の要で、CKKS が機械学習で好まれる理由の一つです。

MPC：複数者で秘密を持ち寄る

HE が「1 人のデータを 1 つのサーバーに委ねる」のに対し、MPC（Secure Multi-Party Computation）は複数の参加者が各自の秘密入力を持ち寄り、関数の出力だけを全員で計算する枠組みです。古典的な例が百万長者問題――2 人がどちらが裕福かを、互いの正確な資産額を明かさずに判定する、というものです。

MPC が満たすべき安全性は次の二点に集約されます。プライバシー＝各参加者は最終出力から推測できること以外、他者の入力を一切学習しない。正当性＝出力は正しい関数値になる。攻撃者モデルとして、プロトコルに従いつつ盗み見る semi-honest（honest-but-curious） と、勝手に逸脱する malicious を区別し、後者に耐えるには追加コストがかかります。MPC には大きく二つの系統があります。

秘密分散ベースの MPC

一つ目が**秘密分散（Secret Sharing）**を土台とする方式です。秘密を複数の「シェア」に分割し、各参加者（またはサーバー）に配ります。シェア単体からは秘密が一切漏れず、規定の数だけ集めて初めて復元できます。

代表が Shamir の秘密分散で、秘密 s を定数項に持つ次数 k-1 の多項式 f(x) を作り、f(1), f(2), … を各人のシェアとします。k 個未満の点からは次数 k-1 の多項式が一意に定まらず秘密は完全に隠れ、k 個集めればラグランジュ補間で f(0) = s を復元できます。これが (k, n) 閾値方式です。より単純な加法的秘密分散では、s = s_1 + s_2 + … + s_n（mod 大きな素数）となるようランダムに分割し、全シェアを足さない限り何も分からない形にします。

加法的秘密分散（3者の例）:
  秘密 s を s = s1 + s2 + s3 (mod p) に分割
  各サーバーは s_i だけを持つ → 単独では s が全く分からない

  加算: 各自が自分のシェアを足すだけでよい（通信不要）
    a = a1+a2+a3, b = b1+b2+b3 のとき
    各 i が (a_i + b_i) を持てば、合計は a+b のシェアになる
  乗算: シェアの単純な積では次数が合わず、参加者間の通信
        （Beaver triple などの事前計算）が必要

ここが秘密分散ベース MPC の本質です。加算はローカルで完結する（通信不要）が、乗算には参加者間の対話が要る。この非対称性のため、計算（回路）の乗算段数がそのまま通信コストを決めます。BGW プロトコルは Shamir 分散の上で任意の算術回路を評価し、不正者が一定数（semi-honest なら n の過半数が正直、すなわち t < n/2）以下なら安全に計算できます（悪意ある攻撃者に耐える場合は t < n/3 とさらに厳しくなる）。GMW はブール回路版にあたります。

Garbled Circuit：2 者間の秘匿計算

二つ目の系統が Garbled Circuit（ガーブル回路、Yao のプロトコル）で、主に2 者間の秘匿計算に使われます。発想は「論理回路の真理値表を暗号化して相手に渡す」ことです。

一方（Garbler）が計算したい関数をブール回路に変換し、各ワイヤの 0 / 1 に**ランダムなラベル（鍵）**を割り当てます。各ゲートの真理値表は、入力ラベルを鍵として出力ラベルを暗号化した形に「ガーブル（撹乱）」され、行はシャッフルされます。相手（Evaluator）は自分の入力に対応するラベルだけを受け取り、暗号化された表を一段ずつ復号して回路全体を評価しますが、ラベルがどちらの真理値か分からないため中間値を一切知りません。

Garbler:   回路の各ワイヤに 0/1 ラベルを割当て、各ゲートを
           ラベルで暗号化した「ガーブル真理値表」を作成 → 送付
Evaluator: 自分の入力ラベルだけ受け取り、表を復号しながら評価
           最後の出力ラベルだけ意味（0/1）に変換 → 結果を得る

ここで核心的に必要なのが **Oblivious Transfer（OT, 紛失通信）**です。Evaluator は自分の入力ビットに対応するラベルを Garbler から受け取らねばなりませんが、Garbler には Evaluator の入力ビットを知られたくないし、Evaluator は要求していないほうのラベルを得てはならない。OT はまさにこの「2 つのうち欲しい片方だけを、どちらを選んだか相手に知られず受け取る」プリミティブで、Garbled Circuit の安全性の土台になります。OT 自体は Diffie-Hellman のような公開鍵プリミティブから構成できます。

HE と MPC の使い分けと実用化

両者は競合ではなく前提が違うため、適材適所で使い分けます。

• 準同型暗号（HE/FHE）：データ提供者は 1 人、計算は信頼できない単一サーバーに委ねたい場合。暗号化して送れば、以後の通信は不要（非対話）で、サーバーが結果暗号文を返すだけ。代償は計算オーバーヘッドの大きさ。
• MPC：複数の当事者が各自の秘密入力を持ち寄り、誰にも生データを渡したくない場合。計算は軽い（平文計算に近い演算もある）が、参加者間で何ラウンドも通信する必要があり、ネットワーク遅延がコストを支配します。

実用化が進んでいる代表領域を挙げます。プライバシー保護機械学習では、暗号化したまま推論する秘匿推論（CKKS ベースの FHE）や、複数組織がデータを集約せずモデルを学習する協調学習が研究・実装されています。**秘匿照合（Private Set Intersection, PSI）**は、2 者が持つ集合の共通要素だけを、それ以外の要素を明かさず求める技術で、連絡先マッチングや不正検知で使われます。閾値署名・分散鍵管理は前述のとおり暗号資産で広く実用化されています。

まとめ

準同型暗号と MPC は、平文を一切露出させずに計算結果だけを得るという同じ目的を、異なる前提で達成します。準同型暗号は暗号文のまま演算でき、加算か乗算の一方だけの部分準同型、回数制限付きのやや準同型、任意回数の**完全準同型（FHE）**に分かれます。FHE は格子（LWE）暗号文のノイズが演算で増えていく問題を、bootstrapping で暗号文の中で復号を行いノイズを除去することで解決しますが、計算オーバーヘッドが実用化の壁として残ります。

MPC は複数者が秘密入力を持ち寄って関数値だけを計算する枠組みで、秘密分散ベース（加算はローカル・乗算は対話が必要）と Garbled Circuit（Oblivious Transfer に依存する 2 者間方式）の二系統があります。HE は単一サーバーへの非対話な計算委託に、MPC は多者間の対話的協調に向き、秘匿推論・秘匿照合・閾値署名などで実用が進んでいます。土台となる公開鍵の基礎は 暗号の基礎、根拠を見せずに正しさを示す関連技術は ゼロ知識証明、FHE が依拠する格子問題は ポスト量子暗号 と併せて押さえると、プライバシー保護計算の全体像がつかめます。