Secure Conformance Checking using Token-based Replay and Homomorphic Encryption

以下は、論文「Secure Conformance Checking using Token-based Replay and Homomorphic Encryption（トークンベースのリプレイと準同型暗号を用いた安全な適合性チェック）」の詳細な技術的サマリーです。

1. 問題定義

適合性チェック（Conformance checking）は、プロセスマイニングの中核的な操作であり、イベントログ（実際の行動）をプロセスモデル（期待される行動）と比較して逸脱を特定するものです。従来、この作業には、モデル所有者とログ所有者の両方が、ビジネスアナリストに対してデータを平文で共有する必要がありました。

しかし、カスタム製造や組織間コラボレーションなどのシナリオでは、当事者は機密情報を保護したいと望むことがよくあります。

• モデル所有者は、独自のプロセスロジック（例：生産ワークフロー）を秘密にしたいと考えるかもしれません。
• ログ所有者は、機密実行データ（例：顧客注文の詳細）をモデル所有者から保護したいと考えるかもしれません。

課題は、他の当事者に underlying なプロセスモデルやイベントログを明かさずに、暗号化されたデータ上で（特にトークンベースのリプレイを用いて）適合性チェックを実行し、かつ適合度指標（逸脱）を計算する能力を維持することです。

2. 手法

著者は、**準同型暗号（HE）**を使用し、線形代数（行列およびベクトル演算）を用いてトークンベースのリプレイアルゴリズムを再定式化した、安全なフレームワークを提案しています。

中核概念

• トークンベースのリプレイ: ペトリネット上でイベントログのトレースを「リプレイ」するアルゴリズムです。消費されたトークン、生成されたトークン、遷移を可能にするために不足していたトークン、および終了時に残存したトークンを追跡します。
• 準同型暗号（HE）: 具体的には、著者は暗号化された整数の復号なしに算術演算（加算、減算、乗算）および比較（最小/最大）をサポートする**Zama の Concrete（TFHE ベース）**を利用しています。
• クライアント - サーバーアーキテクチャ:
  • クライアント（ログ所有者）: イベントログを保持します。現在のマーキングと発火させる次のイベント（遷移）を暗号化し、サーバーに送信します。
  • サーバー（モデル所有者）: ペトリネットモデルを保持します。事前に計算された行列を使用して暗号化されたデータ上でリプレイステップを実行し、新しい暗号化されたマーキングとローカルカウンターを返します。
  • プライバシー: サーバーは平文のログを一度も見ることはなく、クライアントはリプレイから推測される範囲を超えて平文のモデル構造を見ることはありません。

アルゴリズムの再定式化

トークンベースのリプレイを HE と互換性のあるものにするため、著者は条件分岐や分岐に依存する従来の「トークンゲーム」を行列乗算とベクトル演算に置き換えました。

1. 事前計算（サーバー側）:

   • ペトリネットは**結合行列（Incidence Matrix, $N$）**に変換されます。
   • 可能なすべての「有効化（enablements）」（現在のマーキングと遷移の組み合わせ）を表す**ダイナミクス行列（Dynamics Matrix, $E$）**が構築されます。
   • 有効な発火シーケンスの Parikh ベクトル（遷移数）を格納する**発火シーケンス行列（Firing Sequences Matrix, $S$）**が用意されます。
   • 各遷移の入力場所を格納する**プレセット行列（Preset Matrix, $P$）**が用意されます。

2. リプレイステップ（安全な実行）:

   • 有効化チェック: クライアントは暗号化された現在のマーキング（$M$）と暗号化された次のイベント（$t$）を送信します。サーバーは行列乗算を用いて**セレクターベクトル（$sel$）**を計算します：$E \cdot [M, t]^T$。これにより、遷移が直接有効化されるか、サイレント遷移（$\tau$）を必要とするかが決定されます。
   • 不足トークンの処理: 遷移が有効化されていない場合、アルゴリズムはプレセット行列 $P$ から必要な「不足トークン（$\pi$）」を計算します。
   • 統合されたマーキング更新: HE において情報漏洩を招く条件付き if/else 文を避けるため、著者は「適合する」と「適合しない」のロジックを単一の式に統合しました。
     $$M' = (M + N \cdot \sigma^T) \cdot \text{sum}(sel) + (M + \pi^T + N \cdot t^T) \cdot (1 - \text{sum}(sel))$$
     ここで、$\text{sum}(sel)$ はバイナリスイッチとして機能します（有効化された場合は 1、そうでない場合は 0）。
   • カウンター計算: アルゴリズムは、ベクトル差と条件付きマスク（スイッチに基づいて 0 または 1 を乗算）を用いて、不足（$m$）、消費（$c$）、生成（$p$）、および残存（$r$）トークンを計算します。

3. 適合度計算:

   • トレース内のすべてのイベントを処理した後、クライアントは最終カウンターを復号し、標準的な式を用いて適合度スコアを計算します。
     $$f = \frac{1}{2}\left(1 - \frac{m}{c}\right) + \frac{1}{2}\left(1 - \frac{r}{p}\right)$$

3. 主要な貢献

1. 初の安全なトークンベースのリプレイ: 準同型暗号を特定のトークンベースのリプレイ適合性チェックアルゴリズムに適用した最初の研究です。
2. 行列ベースの再定式化: 著者は、非線形で状態に依存するトークンゲームを、分岐ロジックを不要にする準同型暗号に適した線形代数的定式化へと成功裏に変換しました。
3. プライバシー保護アーキテクチャ: モデル所有者がトレース内容を学習することなく暗号化されたトレースを処理し、ログ所有者がリプレイ結果を超えてモデル構造について何ら学習しないクライアント - サーバープロトコルです。
4. 実装と評価: Zama の Concrete フレームワークを使用して Python で実装された動作プロトタイプにより、このアプローチの実現可能性を実証しました。

4. 結果

著者は、合成イベントログと『Process Mining』の書籍および PM4Py チュートリアルからのペトリネットモデルを使用してプロトタイプを評価しました。

• パフォーマンス（平文 vs 暗号化）:
  • 平文データ（CLR）: 実行時間はミリ秒単位でした。
  • 暗号化データ（SEC）: トークンカウンター計算なしのトレースの場合、実行時間は7.8 秒から 15.8 秒の範囲でした。
  • カウンター付き暗号化（SEC+）: 実行時間は19.3 秒から 37.4 秒の範囲でした。
• 最適化の洞察:
  • サーバー側関数内でカウンター（$p, c, m, r$）を計算する初期バージョンは、35 分から 84 分を要しました。
  • 著者は、この遅延が、HE コンパイラ（Concrete）が戻り値にデフォルトで 16 ビット整数を使用することによる過大なオーバーヘッドに起因することを特定しました。カウンター集計をクライアント側（中間結果の復号）へ移動させることで、時間を 40 秒未満に削減しました。
• スケーラビリティ: この手法は、長さの異なるトレース（4 から 13 のイベント）および適合するトレースと適合しないトレースの両方を正常に処理しました。

5. 意義と今後の課題

• 意義: この論文は、安全な適合性チェックが実用的に可能であることを証明しています。これにより、組織は機密情報や患者のプライバシーを犠牲にすることなく、サプライチェーンや医療分野などでプロセスコンプライアンスを検証できます。分岐ロジックから行列演算への転換は、プロセスマイニングへの HE 適用にとって重要な理論的貢献です。
• 限界:
  • パフォーマンス: 1 分未満であるものの、暗号化された実行は平文に比べて著しく遅く（桁違いに）、時間がかかります。
  • トークン洪水: 現在の実装は、暗号化ドメインにおける「トークン洪水」（場所が 1 つ以上のトークンを蓄積する問題）を完全に解決していません。
  • 精度: HE フレームワークにおける整数精度への依存が、演算の複雑さを制限します。
• 今後の方向性:
  • 実世界のイベントログでのテスト。
  • 暗号化ドメインにおけるトークン洪水への対応。
  • 精度とパフォーマンスのトレードオフを最適化するための他の HE プラットフォームの探索。
  • コスト分析のために完全なクライアント - サーバーネットワークバージョンの実装。

結論として、この論文は安全なプロセスマイニングのための堅牢な概念実証を提供し、代数的再定式化を通じて、準同型暗号がトークンベースのリプレイのような複雑なアルゴリズムタスクに効果的に適応可能であることを実証しています。