Secure Conformance Checking using Token-based Replay and Homomorphic Encryption

Luis-Armando Rodríguez-Flores, Luciano García-Bañuelos, Abel Armas-Cervantes, Astrid-Monserrat Rivera-Partida · 2026

Read Secure Conformance Checking using Token-based Replay and Homomorphic Encryption by Luis-Armando Rodríguez-Flores, Luciano García-Bañuelos, Abel Armas-Cervantes, Astrid-Monserrat Rivera-Partida (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25190.txt.

Introduction

Rodríguez-Flores and three colleagues propose a secure approach to conformance checking, the process-mining task of finding discrepancies between a process model and an event log. Normally both model and log sit open to the analyst. But a log owner may wish to protect sensitive entries while still checking conformance against another party's model. Their method combines the well-known token-based replay algorithm with homomorphic encryption, so checking proceeds without exposing protected log contents. An evaluation on a synthetic log shows the technique is practical.

Catalog record

CREATORLuis-Armando Rodríguez-Flores, Luciano García-Bañuelos, Abel Armas-Cervantes, Astrid-Monserrat Rivera-Partida
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48666
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.25190

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Secure Conformance Checking using Token-based Replay and Homomorphic Encryption Luis-Armando Rodríguez-Flores, Luciano García-Bañuelos, Abel Armas-Cervantes, Astrid-Monserrat Rivera-Partida Abstract Conformance checking, one of the main process mining operations, aims to identify discrepancies between a process model and an event log. The model represents the expected behaviour, whereas the event log represents the actual process behaviour as captured in information systems’ records. Traditionally, the process model and the event log are both accessible to the business analyst performing the conformance checking. However, in some contexts the log’s owner may want to protect critical or sensitive information in the log and still check its conformance with respect to a model belonging to another party. In this paper, we propose a secure approach to conformance checking based on the well-known token-based replay algorithm and homomorphic encryption. An evaluation is performed using a synthetic log, showing the practicality of the proposed technique. oken-based replay, Petri nets, Process mining, Conformance checking, Homomorphic encryption. 1 Introduction and related work Conformance checking [ 4 ] is one of the main operations in process mining. This operation contrasts the observed and expected process behavior to identify undesirable deviations. The expected behavior is given as a process model and the observed behavior is captured as an event log recorded by information systems. Event logs are collections of process executions, which are sequences of activity instances ( a.k.a. events ) commonly referred to as traces . Conformance checking approaches can be classified into three families: rule-based, alignment-based and token-based replay. The work reported here belongs to the last family. Token-based replay was introduced in the seminal work [ 14 ] . Later, with the appearance of alignment-based techniques [ 1 ] , token-based replay became less used due to its scalability issues. The scalability issues were caused by the original version requiring exhaustive explorations of the reachability graph, resulting in high overhead. Later, Berti et al. [ 2 ] revisited token-based replay to address the scalability problems and reignite the interest in this approach. In essence, token-based replay consists of firing traces captured in an event log to determine if they are accurately described by a process model. Specifically in the context of a process described as a Petri net model, a trace is accurately described if, from an initial marking, the trace can be replayed on the Petri net and a desired final marking is reached. If deviations occur, then tokens would remain after the trace has been replayed, or artificial tokens would be artificially added to the Petri net to make it possible for an event in a trace to be fired. Traditionally, conformance checking is performed “in clear” such that the model and the event log are known to the end-user performing the operation. However, in some scenarios, the process model and event log must be kept private. For instance, in custom manufacturing, manufacturers strive to keep their production details secret, especially those related to the production of custom pieces made for customers developing new high tech products. Still customers would be willing to check the progress on the production of their pieces. The latter calls for a conformance checking technique over encrypted data. Some studies have proposed solutions to safeguard confidentiality of event logs using encryption techniques. For instance, [ 3 ] presents a framework that enables outsourcing process mining analyses while hiding sensitive information in event logs through the use of symmetric and homomorphic encryption. Since the structure of the event log is preserved, it is possible to apply most process mining tools to the encrypted datasets. However, solely encrypting event logs may leave them vulnerable to de-anonymization techniques. To mitigate this risk, the work in [ 12 ] proposes a confidentiality framework that integrates encryption with abstraction methods (directly follows matrices of activities and resources) to discover process models and social networks from event logs. The challenge of ensuring privacy in cross-organizational contexts was introduced in [ 10 ] . The approach requires all involved parties sharing public fragments of their process models with a trusted third party, which then merges these fragments into a cross-organizational model. Then, each organization retrieves the fragments relevant to its operations and combines them with its private models. Similarly, [ 7 ] proposes a method that allows multiple parties to perform basic process mining operations – such as process discovery and performance analysis queries – over encrypted sub-logs belonging to the different parties in such a way that they do not share confidential information with each other. Strategies such as vectorization of event logs and a divide-and-conquer scheme to process sub-logs in parallel were used to address scalability issues. Despite these advancements, at the time of this work, we are not aware of any other work applying homomorphic encryption in a conformance checking setting. This paper presents an implementation of the token-based replay approach for conformance checking using homomorphic encryption. In order to do so, it is necessary to re-formulate the approach using matrix multiplication operations. Specifically, this paper presents a new token-based replay formulation using the marking equation. To show the practicality of this new formulation, it is evaluated using a synthetic event log. The remainder of the paper is organized as follows. Section 2 introduces relevant concepts, and definitions used in the rest of the paper. The approach is presented in Section 3 and is evaluated in Section 4 . The evaluation is used a synthetic event log. Finally, Section 5 presents the conclusions and some directions for future work. 2 Background An important concept used in the rest of the paper is that of multiset, which is a generalization of the notion of set. In a multiset, there are multiple instances of an element. The formal definition is presented next. Definition 1 (Multiset) Let X be a set. B\in\mathcal{B}(X)=X\rightarrow\mathbb{N} is a multiset over X where each element x\in X appears B(x) times. A relevant operation defined between multisets B_{1},B_{2}\in\mathcal{B}(X) is that of difference: • (difference) B^{\prime}=B_{1}\backslash B_{2}\Longleftrightarrow B^{\prime}(x)=max(B_{1}(x)-B_{2}(x),0)~\forall x\in X . We can also say, in the same setting, that B^{\prime}=B_{1}-B_{2} . 2.1 Petri nets In the remainder of the paper, \mathcal{A} represents the universe of activity names, and A\subseteq\mathcal{A} is a set of activity names. We also consider the symbol \tau\notin\mathcal{A} , which represents internal actions that remain hidden to any system observer. With abuse of notation, we define A^{\tau}=A\cup\{\tau\} . Definition 2 ((Labeled) Petri Net, Accepting Petri Net) A labeled Petri net , or simply a net , is a tuple N=(P,T,F,\lambda) , where P is a finite set of places, T is a finite set of transitions, with P\cap T=\emptyset , F\subseteq(P\times T)\cup(T\times P) is a set of arcs called flow relations, and \lambda:T\rightarrow A^{\tau} is a labeling function assigning an activity name to a transition or \tau if the transition is silent. A marking M:P\rightarrow\mathbb{N}_{0} is a function associating a place p\in P with a (natural) number of tokens in p . An accepting Petri net \mathcal{N}=(N,M_{0},M_{f}) is a Petri net N=(P,T,F,\lambda) with a fixed initial marking M_{0} and a final marking M_{f} . Places and transitions are conjointly referred to as nodes . We write \bullet{y}=\{x\in P\cup T\ |\ (x,y)\in F\} and {y}\bullet=\{z\in P\cup T\ |\ (y,z)\in F\} to denote the

Read the complete text