秘密計算の内部構造：技術者向け解説 – 準同型暗号とマルチパーティ計算

先の記事では、秘密計算のコンセプトを「データを隠したまま計算する技術」として紹介しました。本記事では、その「隠したまま計算する」とは具体的にどのような技術によって実現されているのか、技術者向けにもう少し深く掘り下げて解説します。

秘密計算を実現する主要な技術的アプローチは、大きく**準同型暗号（Homomorphic Encryption, HE）とマルチパーティ計算（Secure Multi-Party Computation, MPC または SMPC）**の2つに分類できます。

1. 準同型暗号 (Homomorphic Encryption, HE)

準同型暗号は、平文（元のデータ）を暗号化した状態（暗号文）のまま、特定の演算を行えるという性質を持つ暗号方式です。

数式で表現すると、Enc() を暗号化関数としたとき、例えば加法について準同型性を持つ暗号であれば、

Enc(m1) op_add Enc(m2) = Enc(m1 + m2)

が成り立ちます。（op_add は暗号文同士に対する特定の加算演算） 同様に乗法について準同型性を持つ場合は、

Enc(m1) op_mul Enc(m2) = Enc(m1 * m2)

が成り立ちます。（op_mul は暗号文同士に対する特定の乗算演算）

種類と特徴:

• 部分準同型暗号 (Partially Homomorphic Encryption, PHE): 加算または乗算のどちらか一方の演算のみ、暗号文のまま実行可能です。
  • 例: Paillier暗号（加法準同型）、素のRSA暗号（乗法準同型）
• やや準同型暗号 (Somewhat Homomorphic Encryption, SHE) / レベル付き準同型暗号 (Leveled HE): 加算と乗算の両方を、限られた回数だけ実行可能です。演算回数が増えるとノイズが増大し、復号できなくなるため、回路の深さ（演算回数）に制限があります。
• 完全準同型暗号 (Fully Homomorphic Encryption, FHE): 加算と乗算の両方を、理論上任意の回数実行可能です。ノイズが増大した場合に、それをリセットするブートストラッピング (Bootstrapping) という技術を用いて、演算回数を無限にすることができます。
  • 例: BGV方式, BFV方式, CKKS方式など。

主なユースケース:

• クライアントがデータを暗号化してクラウドに送り、クラウド側はデータを復号せずに（中身を見ずに）計算処理を行い、結果の暗号文をクライアントに返す、といった計算委託シナリオ。

課題:

• 計算コスト: PHEに比べ、SHE/FHEは暗号化・復号・準同型演算のいずれも計算コストが非常に高い。特にブートストラッピングは重い処理です。
• 暗号文サイズ: 一般的に平文に比べて暗号文のサイズが大きくなります（Ciphertext Expansion）。
• ノイズ管理: SHE/FHEでは、演算に伴うノイズの管理が重要かつ複雑になります。

2. マルチパーティ計算 (Secure Multi-Party Computation, MPC/SMPC)

MPCは、複数の参加者（パーティ）が、それぞれの秘密の入力値を誰にも明かすことなく、全員で協力してある関数（計算処理）の結果だけを得るためのプロトコル群です。

n 人のパーティ P1, ..., Pn がそれぞれ秘密の入力 x1, ..., xn を持っているとき、f(x1, ..., xn) の計算結果 (y1, ..., yn) を、途中の計算過程や他者の入力 xi を知ることなく得ることを目指します。

主要な技術要素:

• 秘密分散法 (Secret Sharing, SS):
  • データを複数の「シェア（分け前）」に分割し、各パーティに配布します。各シェア単体では元の情報に関する知識を得られませんが、一定数（閾値）のシェアを集めることで元の情報を復元できます。
  • 代表例: Shamirの秘密分散法（多項式評価に基づく）、加法的秘密分散（各シェアの和が元の値になる）。
  • シェアの状態で加算や乗算（より複雑な通信が必要）を行うことで、元の値を復元せずに計算を進めることができます。算術回路（加算と乗算で構成される回路）の計算に適しています。
• Garbled Circuit (GC):
  • 主に2者間計算（2PC）で用いられます。計算したい関数をブール回路（AND, OR, XORゲート等）で表現します。
  • 一方のパーティ（Garbler）が回路を「Garble化（暗号化・難読化）」し、各ワイヤに対応するランダムなラベル（Garbled Value）を生成します。
  • もう一方のパーティ（Evaluator）は、自身の入力に対応するラベルを Oblivious Transfer (OT) を用いてGarblerから受け取り、Garbled Circuitを（回路の意味を知ることなく）評価して出力ラベルを得ます。
  • 最後にGarblerが出力ラベルと実際の値の対応表を提供することで、Evaluatorは計算結果を知ることができます。
• Oblivious Transfer (OT):
  • MPC、特にGCにおいて重要な基礎技術です。
  • 送信者 (Sender) が持つ複数の情報のうち、受信者 (Receiver) が選択した1つの情報だけを受信者に渡し、送信者は受信者がどれを選択したかを知らず、受信者は選択しなかった他の情報については何も知ることができない、というプロトコルです。
  • 最も基本的な形式は 1-out-of-2 OT です。

代表的なプロトコルファミリー:

• Yao’s Protocol (GCベース、主に2PC向け)
• GMW Protocol (GC+OT または SS+OT ベース)
• BGW Protocol (Shamir秘密分散ベース)
• SPDZ プロトコルファミリー (加法的秘密分散 + HE + MACなどを利用、Malicious Security向け)

主なユースケース:

• 複数組織間での秘匿統計分析（例：複数銀行間での不正検知）
• Private Set Intersection (PSI): 互いのリストを明かさずに共通要素を見つける
• プライベートな情報に基づいたオークション
• 閾値署名・閾値暗号

課題:

• 通信オーバーヘッド: パーティ間で多くの通信が必要となる場合が多く、特にパーティ数や入力サイズが増えると通信量がボトルネックになりやすい。
• 同期: プロトコルはラウンドごとに進行することが多く、パーティ間の同期が必要になる場合があります。
• セキュリティモデル:
  • Semi-honest (Honest-but-Curious): プロトコルには従うが、途中で得た情報から他者の秘密を推測しようとするモデル。
  • Malicious (Active): プロトコルから逸脱して妨害や不正を行おうとする能動的な攻撃者を想定したモデル。Malicious Securityの達成はより困難で高コストになります。

HE vs. MPC

特徴	準同型暗号 (HE)	マルチパーティ計算 (MPC)
主体	データ所有者、計算実行者（例：クラウド）	複数の協調するパーティ
インタラクション	計算フェーズは非対話的（計算委託モデル）	プロトコル実行中、パーティ間の対話が必須
主なコスト	計算コスト（特にFHE）	通信コスト（ラウンド数、通信量）
得意な計算	回路が深い計算（FHE）、特定の演算（PHE）	多様な関数、特にパーティ間の協調が必要な計算
セキュリティ	暗号強度に依存	プロトコルの安全性、セキュリティモデルに依存

近年では、HEとMPCの要素を組み合わせたハイブリッドなアプローチも研究・開発されています。

実装と今後の展望

秘密計算技術は、理論的な研究だけでなく、実用化に向けたライブラリやフレームワークの開発も進んでいます。（例: Microsoft SEAL, HElib, PALISADE, TF Encrypted, MP-SPDZ など）

しかし、依然としてパフォーマンス（計算速度、通信量）が実アプリケーションの要求を満たすには課題があるケースも多く、アルゴリズムの改善、ハードウェアアクセラレーションなど、様々な方向からの研究開発が活発に行われています。

秘密計算は、プライバシー保護とデータ利活用の両立を可能にするキーテクノロジーとして、今後ますます重要性が増していくと考えられます。本記事が、その技術的背景の理解の一助となれば幸いです。

---