Plausible Deniability in Fully Homomorphic Computation

技術要約：完全準同型計算における否認可能性を備えた計算（PD-FHC）

1. 問題提起

信頼できないクラウドプロバイダーへの計算アウトソーシングは、既存の技術では同時に解決できない2つの異なる脅威にユーザーをさらすことになる：

1. 計算のプライバシー（Computational Privacy）： 正直だが好奇心旺盛な（honest-but-curious）プロバイダーからデータを保護すること（完全準同型暗号（FHE）および信頼実行環境（TEE）によって対処される）。
2. 否認可能な否認可能性（Plausible Deniability）： 強力な敵対者による強制を受けた際に、計算の「存在」や「意図」を信憑性を持って否定できる能力。

現在のソリューションには決定的なギャップが存在する：

• FHE: データ値は隠蔽するが、暗号文の送信自体が目立つ。強制的な敵対者は復号鍵を要求でき、FHEの使用自体がプライベートな計算が行われていることを確定させてしまう。
• TEE: 実効の証明となるアテステーションログを生成する。さらに、サイドチャネル攻撃による漏洩に対して脆弱である。
• 秘密計算（MPC）: 単一のパーティションのシェアの開示に対しては堅牢であるが、参加者が計算が行われたこと自体を否定したり、別の計算に置き換えたりすることを可能にするものではない。
• 否認可能な暗号化／ストレージ: 静的なデータ（メッセージやファイル）には対処しているが、動的な計算の意図までは拡張されていない。

本論文は、ユーザーがブール計算をアウトソーシングしつつ、「何を」計算したかを否定でき、かつ外部の観測者に対しては「計算が行われたこと自体」を否定できる必要があるというギャップを特定している。

2. 手法

著者らは、Fredkinゲートと最下位ビット（LSB）ステガノグラフィを用いて、ブール計算をカバー媒体（具体的にはRGB画像）の中に埋め込むフレームワークであるPD-FHCを提案している。

コアメカニズム:

• 共有配線、可変セマンティクス: このフレームワークは、ユニバーサルなFredkinゲートの単一かつ固定された配線を利用する。Fredkinゲートは、制御ビットが2つのデータビットを入れ替えるかどうかを決定する、可逆的な3入力/3出力ゲートである。
  • 制御ビットが0の場合、ゲートはパススルーとして機能する。
  • 制御ビットが1の場合、ゲートはデータビットを入れ替える。
  • 埋め込まれたデータによって制御ビットを設定することで、同一の物理的配線を用いて、異なる場所で異なる論理関数（例：AND、OR、NOT、または複雑な回路）を実装できる。
• マルチロケーション埋め込み: ユーザー（Alice）は、1つの「真の」回路と、$L-1$個の「デコイ（おとり）」回路を画像のLSBに埋め込む。
  • 真の回路: 秘密のポジション集合 $\Lambda_{j^*}$ に埋め込まれる。
  • デコイ回路: 他の互いに素なポジション集合 $\Lambda_j$ に埋め込まれる。
  • フィルビット: 残りのすべてのLSB位置は、特定の分布 $\pi$ から抽出されたビットで満たされる。
• 一様処理: クラウドプロバイダー（Carol）は画像と配線仕様（$C_{obf}$）を受け取る。彼女は、すべてのピクセル位置に対して並列にFredkinゲートを一様に適用する。彼女は、どの位置に真のデータ、デコイデータ、またはフィルノイズが含まれているかを判別できない。
• 強制への応答: 強制された場合、Aliceはポジション集合、入力、およびデコイ回路の出力を開示する。配線は同一であり、デコイ回路がクラウドの出力と一致する検証可能な結果を生成するため、敵対者はデコイと真の計算を区別することができない。

理論的基礎:

• 否認可能な計算媒体（DCM）: アドレス指定可能なビット位置、読み取り/書き込み機能、および一様に適用されるゲートファミリーを持つ媒体を定義する抽象的なフレームワーク。
• 一致した周辺条件（Matched-Marginal Condition）: 情報理論的なセキュリティのため、真のポジション、デコイのポジション、およびフィルポジションのビットは、すべて同じポジションごとの確率法則 $\pi$ から抽出されていなければならない。この条件下では、LSB平面は「交換可能（exchangeable）」であり、つまり画像の統計的分布は位置の置換に対して不変である。

3. 主な貢献

1. 抽象フレームワーク: 特定のカバー媒体（例：画像、音声、パケット）からセキュリティモデルを分離した、**否認可能な計算媒体（DCM）および否認可能な計算スキーム（DCS）**の定義。
2. 脅威モデルの定式化: 以下の2段階のモデルを区別する：
   • 正直だが好奇心旺盛な（HBC）クラウド: 計算のプライバシー（データの隠蔽）に関心がある。
   • 強制的な敵対者: 否認可能性（存在と意図の隠蔽）に関心がある。
     著者らは、「存在の識別（敵対者が隠された回路の存在を証明できるか？）」および「回路の発見（敵対者が開示されたデコイの中から真の回路を特定できるか？）」を測定する、新しいマルチラウンド強制ゲームを定義した。
3. 画像ベースの実装: RGB画像とFredkinゲートを用いた具体的な実装。
   • 位置プライバシーの証明: 一致した周辺条件の下で、クラウドプロバイダーは、分布 $\pi$ に関わらず、真の回路の位置を特定する上で（情報理論的に）ゼロの優位性しか得られないことを証明している。
   • 部分的回路の隠蔽: 配線は可視であるが、ゲートのセマンティクスは隠されている。制御ビットがなければ、配線はどのような関数が計算されているかについて何も明らかにしないことを本論文は証明している。
4. 実装とベンチマーク: Pythonによる実装を行い、回路サイズ（5〜302ゲート）および画像次元（$128^2$ 〜 $512^2$）にわたってベンチマークを実施した。

4. 結果

• セキュリティ保証:
  • 計算のプライバシー: ゲートファミリーが非秘密位置の統計分布を保持する（Fredkinゲートがビット置換を通じて満たす特性）限り、クラウドは秘密のデータ値や計算されている特定の関数について何も学習しない。
  • 存在の隠蔽: 一致した周辺条件の下では、存在の優位性は正確にゼロである。敵対者は、フィルビットのみを含む画像と、隠された回路を含む画像とを区別できない。
  • 回路の発見: デコイの意味的な妥当性（semantic plausibility）とサイドチャネル漏洩によって、デコイの中から真の回路を特定する優位性は制限される。位置と配線のベクトルは、敵対者の優位性に寄与しない。
• パフォーマンス: 実装は、ブール回路に対してTFHE（主要なFHEライブラリ）と同等の競争力のある性能を示しながら、FHEが提供できない否認性を提供している。
• 視覚的な不可知性: LSBの変更はチャンネルあたり最大 $\pm 1$ のシフトをもたらし、PSNR > 50 dBを実現しており、変化は視覚的に判別不能である。

5. 意義と主張

本論文は、計算のプライバシー、存在の隠蔽（外部の観測者に対して）、および部分的回路の隠蔽（クラウドプロバイダーに対して）を同時に満たす最初のフレームワークであると主張している。

控えめな主張と限界:

• カバーの妥当性の範囲: 著者らは、PD-FHCは任意の画像（例：休暇ののスナップショット）には適さないことを明示している。カバーサービスは、高エントロピーのLSB入力（ディザリング、ノイズ注入、または暗号ドメイン処理など）を正当に期待できるものである必要がある。もし宣言されたサービスが自然な画像を期待する場合、要求される一様なLSB平面は検知可能となる。
• 実入力の制約: 情報理論的なゼロ優位性の保証は、ユーザーの真の入力ビットがデコイおよびフィルビットと同じ分布 $\pi$ を従う場合にのみ正確に成立する。構造化された実入力の場合、優位性は実入力分布と $\pi$ の間の統計的距離（$\Delta$）によって制限される。
• 意味的な妥当性: 回路の発見に対するセキュリティは、デコイ回路の$\epsilon$-妥当性に依存する。本論文は、デコイ（例：明るさのチェック vs 暗号ハッシュ）を意味的に信憑性のあるものとして構築することは、手動かつドメイン固有のタスクであり、まだ自動化されていないことを認めている。
• 能動的攻撃: 本フレームワークは、正直だが好奇心旺盛なクラウドと受動的な外部観測者を想定している。画像を改ざんしたり、計算を拒否したりする能動的な攻撃者からは保護されない。
• 暗号学的難読化の欠如: 本論文は、暗号学的な回路難読化（実現不可能性の対象となる）を主張することを明示的に避けている。「難読化」は純粋にステガノグラフィ的なものであり、制御ビットによってゲートのセマンティクスを変化させることに依存している。

要約すると、PD-FHCは、カバー媒体の統計的条件が満たされる限り、ユーザーが強制を受けた際に検証可能な代替関数を提示することで、特定の計算の意図を信憑性を持って否定できる、計算アウトソーシングへの新しいアプローチを提供している。