A Privacy-Preserving Approach to Conformance Checking
本論文は、ホモモルフィック暗号と文字列処理アルゴリズムを用いて、プロセスモデルとイベントログのいずれかを他者に開示することなく両者の不一致を安全に特定するプライバシーを保護する適合性チェック手法を提案するが、その代償として高い計算量とメモリ要件を伴う。
原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
この論文を、平易な言葉と日常的な比喩を用いて解説します。
全体像：材料を見ずにレシピを確認する
あなたが注文したカスタムケーキの顧客だと想像してください。あなたは、パン屋さんがあなたの特定のレシピ（プロセスモデル）に従っていること、そして厨房で実際に行われている手順があなたの注文と一致していることを確認したいと考えています。
通常、これを確認するには、パン屋さんが秘密のレシピ帳を見せ、あなたが秘密の注文書を見せる必要があります。しかし、パン屋さんがあなたのせいで秘密のレシピを盗まれるのを心配したり、あなたがパン屋さんに秘密の注文詳細を見られるのを心配したりする場合はどうでしょうか？
この論文は、どちらの当事者も相手の秘密情報を決して見ることなく、ケーキが正しく作られているかどうかを確認する方法を提案しています。
問題：プライバシー対確認
ビジネスソフトウェアの世界において、「適合性チェック（Conformance Checking）」とは、計画されたワークフロー（レシピのようなもの）と、実際に何が起こったかの記録（厨房のログのようなもの）を比較するプロセスです。
- モデル: 「期待される」経路（レシピ）。
- ログ: 「実際の」経路（シェフが実際に行ったこと）。
伝統的には、第三者（またはデータの所有者）が両方を見て誤りを発見します。しかし、ハイテク製造業のような機密性の高い業界では、企業は秘密の設計図を共有したくなく、クライアントはプライベートな注文詳細を共有したくありません。
解決策：「魔法の箱」と「検索エンジン」
著者たちは、このプライバシーの謎を解くために、主に 2 つのツールを使用したシステムを構築しました。
1. 魔法の箱（準同型暗号）
準同型暗号を特別な「魔法の箱」と考えてください。
- あなたは秘密の数字を箱の中に入れることができます。
- あなたは、箱を開けたり数字を見たりすることなく、誰かにその数字に 5 を足すよう依頼できます。
- 彼らは箱の中の「暗号化された」数字に対して計算を行い、結果を返します。
- あなたが箱を開けると、結果は正しい答え（元の数字 + 5）になっています。
この論文では、「クライアント（トレースを持つ人）」がデータをこの魔法の箱に入れます。「サーバー（モデルの所有者）」は、実際のデータを一度も見ることなく、箱の中で確認計算を行います。
2. 検索エンジン（FM インデックスと文字列処理）
手順が一致しているかを確認するために、システムはプロセスモデル全体を 1 つの巨大な文字列（レシピを長い文章に変えるようなもの）に変換します。そして、その文字列の上に超高速な検索エンジン（FM インデックスと呼ばれるもの）を構築します。
通常、検索エンジンでは単語を入力すると、即座にその文字列内の出現場所を見つけることができます。ここでは、システムはこの検索エンジンを用いて、クライアントのログにある「手順」が、モデルの文字列内の「手順」に含まれているかどうかを確認します。
仕組み：「後方検索」ゲーム
この論文では、一致を確認するためにクライアントとサーバーの間で行われる特定のゲームについて説明しています。
- 準備: サーバーは秘密のモデルを取り、それを長い文字列に変換し、その上に検索エンジン（FM インデックス）を構築します。これは秘密に保たれます。
- クエリ: クライアントは手順の秘密リスト（トレース）を持っています。これらの手順がモデルに適合するかどうかを知りたいのです。
- 秘密検索:
- クライアントは手順のリストを後ろから（最後の手順から最初の手順へ）見ます。
- 手順を直接送るのではなく、クライアントはサーバーに「ロックされた」リクエストを送信します。
- サーバーは検索エンジンを使って、モデル内でその手順を探します。
- 重要なのは: サーバーは「魔法の箱」の中でこの計算を行います。サーバーが見るのは実際のステップ名ではなく、かき混ぜられた数字だけです。
- サーバーは結果をクライアントに送り返します。
- クライアントは結果を解読して、手順が見つかったかどうかを確認します。
- 誤りの処理（ログムーブ）: クライアントのリストにある手順がモデルと一致しない場合、システムは「スキップ」（ログムーブと呼ばれる）を許可します。これは、「この手順はレシピにありませんでしたが、次の手順が合うか見てみましょう」と言っているようなものです。システムは誤りの前の位置を記憶しており、誤りをサーバーに明かすことなく再試行できます。
欠点：遅く、重たい
この論文は、これが素晴らしいプライバシー解決策である一方で、大きな代償を伴うことを認めています。速度とメモリです。
- 比喩: 紙に簡単な数学の問題を解くのは 1 秒で済みます。しかし、その紙を鉛で裏打ちされた金庫に入れ、友人に送り、厚いガラス窓を通して計算させ、送り返してもらう必要があると想像してください。それははるかに時間がかかります。
- 結果: 著者たちは実データと擬似データでこれをテストしました。その結果、プロセスのチェックにはトレースあたり約1.12 分を要することがわかりました。正確ではありますが、暗号化なしでチェックするよりもはるかに遅いです。「魔法の箱」（暗号化）には、多くの計算能力とメモリが必要です。
主張の要約
- 何をしたか: どちらの側も相手のデータを見ることなく、プロセスログがプロセスモデルに一致するかどうかを確認するシステムを構築しました。
- どのようにしたか: 高速なテキスト検索アルゴリズム（FM インデックス）と「魔法の箱」暗号化方式（準同型暗号）を組み合わせることで実現しました。
- 何が見つかったか: 機能します！安全に不一致を確認できます。
- 限界: 暗号化の計算が重いため、現在非常に遅く、多くのメモリを消費します。また、現時点では「ログムーブ（ログ内の手順をスキップ）」のみを処理でき、「モデルムーブ（モデル内の手順をスキップ）」は処理できません。
要約すると、この論文は、どちらの秘密も明かさずに秘密のレシピと秘密の注文を照合できることを証明していますが、現在、その計算を行うには長い時間がかかります。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。