💻 computer science

A Privacy-Preserving Approach to Conformance Checking

This paper proposes a privacy-preserving conformance checking approach using homomorphic encryption and string processing algorithms to securely identify discrepancies between a process model and an event log without revealing either to the other party, albeit at the cost of high computational and memory requirements.

Original authors: Luis Rodríguez-Flores, Luciano García-Bañuelos, Abel Armas-Cervantes, Astrid Rivera-Partida

Published 2026-05-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Luis Rodríguez-Flores, Luciano García-Bañuelos, Abel Armas-Cervantes, Astrid Rivera-Partida

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Checking a Recipe Without Seeing the Ingredients

Imagine you are a customer who ordered a custom cake. You want to make sure the baker is following your specific recipe (the Process Model) and that the steps they are actually taking in the kitchen match what you asked for (the Event Log).

Usually, to check this, the baker would have to show you their secret recipe book, and you would have to show them your secret order form. But what if the baker is worried you'll steal their secret recipe, or you are worried they'll see your secret order details?

This paper proposes a way to check if the cake is being made correctly without either party ever seeing the other's secret information.

The Problem: Privacy vs. Checking

In the world of business software, "Conformance Checking" is the process of comparing a planned workflow (like a recipe) against a record of what actually happened (like a kitchen log).

The Model: The "Expected" path (the recipe).
The Log: The "Actual" path (what the chef actually did).

Traditionally, a third party (or the owner of the data) looks at both to find mistakes. But in sensitive industries (like high-tech manufacturing), companies don't want to share their secret blueprints, and clients don't want to share their private order details.

The Solution: A "Magic Box" and a "Search Engine"

The authors created a system that uses two main tools to solve this privacy puzzle:

1. The Magic Box (Homomorphic Encryption)

Think of Homomorphic Encryption as a special "Magic Box."

You can put a secret number inside the box.
You can ask someone to add 5 to that number without them ever opening the box or seeing the number.
They perform the math on the "encrypted" number inside the box and hand it back.
When you open the box, the result is the correct answer (Original Number + 5).

In this paper, the "Client" (the person with the trace) puts their data into this Magic Box. The "Server" (the owner of the model) performs the checking math inside the box without ever seeing the actual data.

2. The Search Engine (FM-Index & String Processing)

To check if the steps match, the system turns the entire process model into one giant string of text (like turning a recipe into a long sentence). It then builds a super-fast Search Engine (called an FM-Index) on top of that text.

Normally, a search engine lets you type a word and instantly find where it appears in the text. Here, the system uses this search engine to see if the "steps" in the client's log exist within the "steps" of the model's text.

How It Works: The "Backward Search" Game

The paper describes a specific game played between the Client and the Server to check the match:

Preparation: The Server takes their secret model, turns it into a long string of text, and builds the Search Engine (FM-Index) on it. They keep this secret.
The Query: The Client has a secret list of steps (a trace). They want to know if these steps fit the model.
The Secret Search:
- The Client looks at their list of steps backwards (from the last step to the first).
- Instead of sending the step directly, the Client sends a "locked" request to the Server.
- The Server uses the Search Engine to look for that step in the model.
- Crucially: The Server does this math inside the "Magic Box." The Server sees only scrambled numbers, not the actual step names.
- The Server sends the result back to the Client.
- The Client unlocks the result to see if the step was found.
Handling Mistakes (Log Moves): If a step in the Client's list doesn't match the model, the system allows for a "skip" (called a Log Move). It's like saying, "Okay, this step wasn't in the recipe, but let's see if the next step fits." The system remembers where it was before the mistake so it can try again without revealing the mistake to the Server.

The Catch: It's Slow and Heavy

The paper admits that while this is a brilliant privacy solution, it comes with a heavy price tag: Speed and Memory.

The Analogy: Imagine doing a simple math problem on a piece of paper. It takes one second. Now imagine you have to put that paper in a lead-lined vault, send it to a friend, have them do the math through a thick glass window, and send it back. It takes much longer.
The Result: The authors tested this on real and fake data. They found that checking a process took about 1.12 minutes per trace. While accurate, it is much slower than checking without encryption. The "Magic Box" (encryption) requires a lot of computer power and memory.

Summary of Claims

What they did: They built a system to check if a process log matches a process model without either side seeing the other's data.
How they did it: By combining a fast text-search algorithm (FM-Index) with a "Magic Box" encryption method (Homomorphic Encryption).
What they found: It works! You can securely check for mismatches.
The Limitation: It is currently very slow and uses a lot of memory because the encryption math is heavy. It also only handles "Log Moves" (skipping steps in the log) and not "Model Moves" (skipping steps in the model) yet.

In short, the paper proves that you can check a secret recipe against a secret order without revealing either, but it currently takes a long time to do the math.

1. Problem Statement

Conformance checking is a core process mining operation that compares a process model (expected behavior) against an event log (observed behavior) to identify discrepancies. Traditionally, both the model and the log are accessible to the analyst. However, in sensitive contexts (e.g., custom manufacturing or proprietary production lines), the process model owner must protect their intellectual property, while the client (log owner) must protect their operational data.

The core problem addressed is: How to perform conformance checking between a process model and an event log without revealing the model to the log owner, or the log to the model owner?

2. Methodology

The authors propose a Secure Conformance Checking technique based on a Client-Server architecture, utilizing Fully Homomorphic Encryption (FHE) and string processing algorithms.

A. Core Concepts

Petri Nets & Unfolding: The process model is represented as a Petri net. To convert this into a format suitable for string searching, the authors use causally complete prefix unfolding. This transforms the potentially infinite behavior of a Petri net (due to loops) into a finite, acyclic structure containing all possible "runs" (complete executions).
String Representation: The runs from the unfolding are linearized and concatenated into a single text string, separated by special delimiters.
FM-Index & Backward Search: The concatenated string is indexed using the FM-Index (based on the Burrows-Wheeler Transform and Wavelet Matrix). This allows for efficient substring searching (finding if a trace exists within the model's runs) in $O(m)$ time.
Homomorphic Encryption (FHE): The system uses a public-key encryption scheme (specifically lifted ElGamal) that allows computations (addition and multiplication) to be performed directly on encrypted data.

B. The Secure Protocol

The approach maps the problem of finding optimal alignments (minimizing deviations) to approximate substring matching.

Server Side (Model Owner):
- Takes the process model, unfolds it, concatenates runs, and builds the FM-Index (BWT and Wavelet Matrix).
- Stores the index data structures (specifically 0-RANK and 1-SRANK vectors) in memory.
- Does not see the client's trace.
Client Side (Log Owner):
- Holds the event trace to be checked.
- Encrypts the trace data and the search state (indices) before sending queries to the server.
The Interaction (Secure Backward Search):
- The client iterates through the trace characters in reverse order.
- For each character, the client performs a Backward Search on the FM-Index. This involves traversing the Wavelet Matrix row by row (bitwise) to update the search interval $[f, g]$ .
- Privacy Mechanism:
  - The client sends encrypted vectors representing the current search indices.
  - The server performs homomorphic dot products and additions to update these indices based on the Wavelet Matrix rows.
  - To prevent the client from learning intermediate intervals (which could leak information about the model), the server adds a random offset to the results before returning them.
- Handling Mismatches (Log Moves):
  - If a character in the trace does not match the model (a "log move"), the client restores the previous search indices (stored before the iteration) and inserts a "skip" operation in the alignment.
  - This is done without the server knowing which character caused the mismatch, as the client controls the logic flow based on decrypted (but obfuscated) results.

3. Key Contributions

First Application of FHE to Conformance Checking: The paper claims to be the first work applying homomorphic encryption specifically to the conformance checking problem.
Secure Alignment via String Matching: It innovatively maps the complex problem of trace alignment to substring matching using the FM-Index, enabling the use of efficient string algorithms in an encrypted domain.
Client-Server Privacy Model: It establishes a protocol where the model owner never sees the trace, and the log owner never sees the model, yet an alignment score (and the alignment itself) can be computed.
Handling Log Moves: The algorithm specifically supports "log moves" (deviations where the log has an event not in the model) by allowing the client to revert search states securely.

4. Results and Evaluation

The method was implemented in C++ using the mcl library for homomorphic encryption and evaluated on a standard laptop workstation.

Datasets: Evaluated using one real-world event log and two synthetic logs (small to medium size with concurrency, choice, and loops).
Performance:
- Accuracy: The method successfully computed alignments for traces that fit the model and those with injected deviations.
- Overhead: The primary bottleneck is the computational cost of homomorphic operations.
- Complexity: The theoretical complexity is $O(C \cdot |q| \cdot |T|)$ , where $C$ is the large constant for encryption/decryption, $|q|$ is the trace length, and $|T|$ is the size of the indexed model runs.
- Execution Time: For a small model with 144 runs and 9 events per trace, the average alignment time was 1.12 minutes. The time per symbol was approximately 0.11 minutes.
- Scalability: The execution time showed a quasi-linear trend relative to the trace length, but the absolute times are currently too high for real-time, large-scale industrial applications due to the heavy cryptographic overhead.

5. Significance and Future Work

Significance: This work bridges the gap between Process Mining and Privacy-Preserving Data Mining. It demonstrates that sensitive business processes can be audited without exposing proprietary logic or operational data, a critical requirement for industries like custom manufacturing and healthcare.
Limitations:
- Currently supports only log moves (skipping events in the log). It does not yet support model moves (skipping events in the model), which would require more complex logic.
- High memory and processing requirements make it currently impractical for very large models or real-time systems.
Future Directions:
- Extending the approach to handle model moves.
- Improving the handling of loops (currently limited by the unfolding depth).
- Optimizing the cryptographic implementation to reduce the computational gap between plaintext and encrypted execution.

In conclusion, the paper presents a theoretically sound and technically feasible prototype for secure conformance checking, proving that privacy can be preserved at the cost of significant computational resources.