VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization⋆,⋆⋆ Miit Dagaa (Researcher), Swarna Priya Ramua,∗ (Corresponding Author)
arXiv:2604.12431v1 [cs.CR] 14 Apr 2026
a School of Computer Science Engineering and Information Systems, Vellore Institute of Technology, Vellore, 632014, Tamil Nadu, India
ARTICLE INFO
ABSTRACT
Keywords: k-anonymity verifiable computation intelligent auditing explainable AI Merkle trees SHAP
Organisations increasingly outsource privacy-sensitive data transformations to cloud providers, yet no practical mechanism lets the data owner verify that the contracted algorithm was faithfully executed. VeriX-Anon is a multi-layered verification framework for outsourced Target-Driven k-anonymization combining three orthogonal mechanisms: deterministic verification via Merkle-style hashing of an Authenticated Decision Tree, probabilistic verification via Boundary Sentinels near the Random Forest decision boundary and exact-duplicate Twins with cryptographic identifiers, and utility-based verification via Explainable AI fingerprinting that compares SHAP value distributions before and after anonymization using the Wasserstein distance. Evaluated on three cross-domain datasets against Lazy (drops 5% of records), Dumb (random splitting, fake hash), and Approximate (random splitting, valid hash) adversaries, VeriX-Anon correctly detected deviations in 11 of 12 scenarios. No single layer achieved this alone. The XAI layer was the only mechanism that caught the Approximate adversary, succeeding on Adult and Bank but failing on the severely imbalanced Diabetes dataset where class imbalance suppresses the SHAP signal, confirming the need for adaptive thresholding. An 11-point k-sweep showed Target-Driven anonymization preserves significantly more utility than Blind anonymization (Wilcoxon 𝑝 = 0.000977, Cohen’s 𝑑 = 1.96, mean F1 gap +0.1574). Clientside verification completes under one second at one million rows. The threat model covers three empirically evaluated profiles and one theoretical profile (Informed Attacker) aware of trap embedding but unable to defeat the cryptographic salt. Sentinel evasion probability ranges from near-zero for balanced datasets to 0.52 for imbalanced ones, a limitation the twin layer compensates for in every tested scenario.
1. Introduction The global data centre outsourcing market was valued at USD 127.8 billion in 2024 and is projected to reach USD 157.1 billion by 2030 (Research and Markets (2025)). Organisations across healthcare, finance, and government routinely transfer sensitive datasets to cloud providers for processing, analytics, and anonymization. The economic logic is clear: outsourcing avoids the capital cost of onpremise infrastructure and gives access to elastic compute that small data owners cannot replicate internally. But outsourcing creates a trust problem. The data owner hands over records containing personally identifiable information (PII) and expects the cloud to apply a specific privacy algorithm, for example, 𝑘-anonymity via Target-Driven decision tree partitioning. The cloud returns an anonymized dataset, a tree structure, and (at best) a hash. The data owner has no mechanism to verify that the cloud actually ran the contracted algorithm rather than a cheaper shortcut. Yet the data owner, not the cloud, bears the regulatory and reputational cost if the anonymization was performed incorrectly or not at all. This is not a hypothetical risk. The 2024 IBM Cost of a Data Breach Report puts the average breach cost at USD 4.88 million, a 10% year-over-year increase and the highest ever recorded (IBM Security (2024)). Healthcare ∗ Corresponding author: Swarna Priya Ramu
[email protected] (M. Daga); [email protected] (S.P. Ramu) ORCID (s): 0009-0005-4629-458X (M. Daga); 0000-0002-8287-9690 (S.P.
breaches average USD 9.77 million. GDPR fines have exceeded EUR 5.88 billion in aggregate since 2018 (DLA Piper (2025)), and a single outsourcing firm (Capita plc) was fined GBP 14 million in 2025 after a ransomware breach exposed 6.6 million records, affecting 325 of the over 600 pension fund clients it served (Information Commissioner’s Office (2025)). A cloud provider that drops records to save compute or substitutes a faster but utility-destroying algorithm exposes the data owner to penalties of this magnitude. The need for 𝑘-anonymity itself is well-established. Sweeney (Sweeney (2002)) demonstrated in 1997 that 87% of the U.S. population can be uniquely identified from just three quasi-identifiers (ZIP code, birth date, sex), and used a $20 voter registration list to re-identify the Massachusetts governor’s medical records. Two decades of follow-up work confirmed the fragility of naive anonymization: Narayanan and Shmatikov (Narayanan and Shmatikov (2008)) deanonymized Netflix users from movie ratings, and de Montjoye et al. (de Montjoye, Radaelli, Singh and Pentland (2015)) showed that 90% of individuals in a credit card dataset could be re-identified from just four transactions. 𝑘-Anonymity addresses this by grouping records so that every individual is indistinguishable from at least 𝑘 − 1 others on the quasi-identifier attributes. Target-Driven anonymization (Friedman, Schuster and Wolff (2006)) takes this further: instead of partitioning data blindly, it builds a decision tree that splits on the target variable, preserving predictive utility within each equivalence class. The result is an anonymized dataset that remains useful for downstream
Ramu)
:
Page 1 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
classification, not just a privacy-compliant but analytically useless table. The missing piece is verification. The entire literature on 𝑘-anonymity focuses on how to perform anonymization correctly. Almost nothing addresses what happens after the data owner outsources the task and receives the result. No existing framework simultaneously verifies (a) that the correct algorithm was used (structural correctness), (b) that all records were processed (data completeness), and (c) that predictive utility was preserved (algorithmic integrity). Three bodies of prior work are relevant, and none fills this gap on its own. General-purpose verifiable computation frameworks ( Gennaro, Gentry and Parno (2010), Parno, Howell, Gentry and Raykova (2016)) are theoretically sound but impractical for large anonymization trees: the proof generation overhead makes them orders of magnitude more expensive than the original computation for tree-structured tasks with tens of thousands of nodes. Trap-based verification (canary records in database auditing) provides datalevel checks but no structural or utility verification; as we show in Section 6.2, trap-only methods miss an entire class of adversary that substitutes random splitting while processing all records. Explainable AI tools like SHAP (Lundberg and Lee (2017)) have been used for model debugging and data drift detection, but SHAP has not been used as a verification mechanism for outsourced data transformations. The connection between SHAP value distributions and the algorithmic integrity of an anonymization process is, to our knowledge, new. VeriX-Anon can therefore be understood as an intelligent auditing system: it combines machine learning (Random Forest boundary detection), Explainable AI (SHAP-based utility fingerprinting), and cryptographic hashing into a single automated verification pipeline that replaces manual or re-execution-based auditing. We note that using SHAP or similar feature attribution methods for detecting data drift or model drift is an active area of research (e.g., Chaudhury, Sadhukhan and Sengupta (2024)). Our contribution is not the observation that SHAP distributions shift under data perturbation, which is well established, but the specific application of this shift as a verification signal within a cryptographic auditing pipeline for outsourced anonymization. The integration of these three mechanisms is not merely additive. As we demonstrate empirically in Section 6.2 (Table 6), no individual layer group achieves complete detection when used in isolation: hash-only verification (Layer 1) correctly identifies 6 of 12 scenarios (all honest and all Dumb, but misses all Lazy and all Approximate), traponly verification (Layers 2a+2b) correctly identifies 6 of 12 (all honest and all Lazy, but misses all Dumb and all Approximate), and XAI-only verification (Layer 3) correctly identifies 8 of 12 (all honest, both real-data Dumb attacks, Bank Lazy, and two of three Approximate attacks, but misses Adult Lazy, Diabetes Lazy, Diabetes Dumb, and Diabetes Approximate). The layers are complementary by design: each one covers a failure mode that the others cannot detect. This complementarity is the core contribution, and it cannot :
be achieved by any single known technique regardless of how it is configured. This paper presents VeriX-Anon, a multi-layered verification framework that allows a data owner to mathematically audit whether a cloud provider correctly performed TargetDriven 𝑘-anonymization on outsourced data. The specific contributions are: 1. A tri-layer intelligent verification architecture combining deterministic verification (Merkle-style SHA256 hashing of the authenticated decision tree), probabilistic verification (Boundary Sentinels targeting the Random Forest decision boundary at 𝑃 ∈ [0.45, 0.55], plus exact-duplicate Twins), and AI-driven utility verification (Explainable AI fingerprinting via the Wasserstein distance of SHAP value distributions), forming an integrated expert auditing system. 2. A Boundary Sentinel generation technique that exploits the uncertainty region of a Random Forest classifier to produce synthetic records maximally sensitive to changes in the splitting logic. Unlike generic canary records, these sentinels are placed where algorithm substitution causes the largest displacement. 3. A formal probability analysis of sentinel evasion under data-dropping attacks (Equation 13), with empirical validation showing evasion probabilities ranging from near-zero (Adult Income, 160 sentinels) to 0.52 (Bank Marketing, 13 sentinels under 88/12 class imbalance). 4. Empirical evaluation across three cross-domain datasets (societal, financial, medical) against three adversary profiles (Lazy Cloud: drops 5% of records; Dumb Cloud: substitutes random splitting with a fake hash; Approximate Cloud: substitutes random splitting with a valid hash), achieving correct detection in 11 of 12 scenarios. The single evasion occurs on the severely imbalanced Diabetes dataset, where the XAI signal is too weak to flag the Approximate adversary. No single verification layer achieves full coverage alone; the multi-layered design is necessary. 5. Statistical validation with Wilcoxon signed-rank test (𝑝 = 0.000977 for F1, 𝑝 = 0.006836 for Wasserstein distance), Cohen’s 𝑑 effect sizes of 1.96 (F1) and −1.02 (WD), and bootstrap 95% confidence intervals excluding zero for both metrics, all computed over an 11-point 𝑘-sweep. 6. Sub-second client verification overhead: 0.788 s at 𝑛 = 106 rows, with the 𝑂(𝑛∕𝑘) hash traversal dominated by a fixed 𝑂(1) XAI overhead of approximately 0.5 s. The remainder of this paper is organised as follows. Section 2 surveys related work on 𝑘-anonymity, verifiable computation, and XAI-based data quality assurance. Section 3 defines the technical building blocks that VeriX-Anon relies on. Section 4 defines the system model, adversary profiles, and security assumptions. Section 5 presents the VeriX-Anon methodology across its four phases. Section 6 reports experimental results, including detection accuracy, Page 2 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
scalability, and utility-privacy trade-offs with full statistical analysis. Section 7 discusses limitations, including XAI limitations under severe class imbalance, sentinel density, and epsilon sensitivity. Section 8 concludes with future directions.
classification tasks, it is to be understood that this is a classical approach without any involvement of cryptographic auditing structures, and in this case, utilizing it within a multi-controller outsourced environment fails to provide guarantees of structural correctness or completeness.
2. Related Work
2.2. Verifiable Computation and Authenticated Data Structures
Three bodies of prior work intersect with VeriX-Anon: anonymisation algorithms that perform 𝑘-anonymity (but do not verify it after outsourcing), verifiable computation frameworks that authenticate outsourced results (but were not designed for decision-tree-based anonymisation), and Explainable AI methods that measure data fidelity (but have not been integrated into a cryptographic auditing pipeline). This section reviews each area and identifies the gaps that VeriX-Anon fills.
2.1. k-Anonymity and Target-Driven Anonymization Kesarwani et al. (Kesarwani, Kaul, Braghin, Holohan and Antonatos (2021)) developed a methodology for secure k-anonymity over encrypted databases using a fully homomorphic encryption framework within a federated cloud architecture. Data partitioning was performed by applying a secure k-means clustering algorithm over encrypted data to group similar tuples prior to generalisation. Although the proposed model achieved data masking and differential privacy without decrypting the dataset, it is to be understood that this is a forward-execution approach without any involvement of post-hoc verification mechanisms, and in this case, the data owner cannot mathematically audit whether the service provider actually executed the correct anonymization algorithm. De Capitani di Vimercati et al. (De Capitani di Vimercati, Foresti, Ghirimoldi and Samarati (2024a)) developed a methodology for target-driven data anonymization using decision trees guided by classification targets. Data generalisation was performed by evaluating candidate splits in a top-down manner and independently anonymizing the resulting leaf nodes to minimize information loss. Although the constructed model partitioned the data to satisfy kanonymity and l-diversity while maintaining downstream analytic utility, it is to be understood that this is a local transformation approach without any involvement of verifiable outsourced computation, and in this case, delegating this process to an untrusted cloud environment leaves the framework vulnerable to lazy or malicious execution. Barezzani et al. (Barezzani, di Vimercati, Foresti, Ghirimoldi and Samarati (2025)) developed a methodology for target-aware data anonymization using a combination of decision tree partitioning and generalized clustering algorithms. The anonymization process was performed by grouping tuples that share similar predictive features and subsequently enforcing privacy constraints on each isolated cluster. Although the stacked anonymization pipeline preserved the predictive features necessary for downstream :
Gennaro et al. (Gennaro et al. (2010)) developed a methodology for non-interactive verifiable computing using Yao’s garbled circuits integrated with fully homomorphic encryption. The verification preparation was performed by allowing the client to execute a one-time preprocessing stage that creates a garbled circuit for the target function. Although the theoretical model enabled a computationally weak client to outsource arbitrary functions and verify the returned results, it is to be understood that this is a highly generalized approach without any involvement of specific optimizations for decision tree algorithms, and in this case, the immense proof generation overhead renders it impractical for largescale dataset anonymization. Parno et al. (Parno et al. (2016)) developed a methodology for nearly practical verifiable computation using quadratic arithmetic programs to compile C code into a verifiable cryptographic protocol. The cryptographic translation was performed by mapping arithmetic circuits into a set of polynomials that enable public verification via a short cryptographic proof. Although the Pinocchio system produced verification times of approximately 10 milliseconds, it is to be understood that this is an arithmetic circuit approach without any involvement of embedded probabilistic data traps, and in this case, the worker’s computational burden remains too heavy for evaluating massive multidimensional datasets. Mykletun et al. (Mykletun, Narasimha and Tsudik (2006)) developed a methodology for ensuring authentication and integrity in outsourced databases using signature aggregation techniques such as condensed-RSA. The integrity checking was performed by generating tuple-level digital signatures and mathematically aggregating them to provide a unified proof for database query replies. Although the digital signature approach mitigated querier computation and bandwidth overheads, it is to be understood that this is an exact-match verification approach without any involvement of algorithmic auditing, and in this case, it cannot verify complex structural transformations like k-anonymity partitioning. Etemad and Küpçü (Etemad and Küpçü (2020)) developed a methodology for dynamic data outsourcing using implicitly-ordered authenticated data structures coupled with homomorphic verifiable tags. The auditing setup was performed by integrating rank-based skip lists and Merkle trees to support rapid block updates and blockless verification at the cloud server. Although the framework supported dynamic updates and provided strong probabilistic data possession guarantees, it is to be understood that this is a raw data auditing approach without any involvement of Page 3 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization Table 1 To the best of our knowledge, no existing framework combines deterministic, probabilistic, and utility-based verification for outsourced data anonymization. VeriX-Anon is the first to integrate all three mechanisms within a single auditing pipeline. Reference Kesarwani et al. (Kesarwani et al. (2021)) De Capitani di Vimercati et al. De Capitani di Vimercati et al. (2024a) Mykletun et al. (Mykletun et al. (2006)) Etemad and Küpçü Etemad and Küpçü (2020) Liu et al. (AUDIO) (Liu, Wang, Monreale, Pedreschi, Giannotti and Guo (2012)) De Capitani di Vimercati et al. (De Capitani di Vimercati, Foresti and Samarati (2024b)) Zheng et al. (Zheng, Wang, Wang, Duan and Nepal (2022)) Chaudhury et al. (Chaudhury et al. (2024)) Gennaro et al. (Gennaro et al. (2010)) Parno et al. (Pinocchio) (Parno et al. (2016)) Naive Re-execution Baseline VeriX-Anon (Proposed)
explainable AI utility metrics, and in this case, it falls short of verifying the algorithmic correctness of data subjected to clustering or generalization. Liu et al. (Liu et al. (2012)) developed a methodology for integrity auditing of outlier-mining-as-a-service systems using the strategic insertion of artificial outlier and nonoutlier tuples. The data preparation was performed by randomly sampling the original dataset and constructing specific boundary cases to serve as hidden traps for the semihonest server. Although the AUDIO framework provided a strong probabilistic guarantee of completeness and correctness for the mining results, it is to be understood that this is a trap-based approach without any involvement of deterministic cryptographic tree structures, and in this case, applying it to target-driven anonymization fails to verify the structural integrity of the generated decision tree. De Capitani di Vimercati et al. (De Capitani di Vimercati et al. (2024b)) developed a methodology for query integrity in smart environments using a hybrid model that combines deterministic authenticated data structures with probabilistic controls like sentinels and twins. The verification process was performed by enriching relational datasets with duplicate records and artificial tuples prior to executing the required SQL operations. Although the combined scheme verified the completeness and correctness of outsourced relational queries, it is to be understood that this is a standard relational algebra approach without any involvement of explainable AI fingerprinting, and in this case, it cannot measure the utility preservation of complex machine learning transformations. Zheng et al. (Zheng et al. (2022)) developed a methodology for optimizing secure decision tree inference outsourcing using an advanced carry look-ahead adder within an additive secret sharing framework. The secure inference logic was performed by distributing bitwise threshold comparisons across non-colluding servers to eliminate the traditional linear delay of ripple carry adders. Although the system reduced the online inference latency and network communication rounds for cloud servers, it is to be understood that this is a secure inference approach without any involvement of large-scale dataset verification, and in this
:
Deterministic Verification × × ✓ ✓ Partial ✓ Partial × ✓(General) ✓(General) ✓ ✓
Probabilistic Traps × × × × ✓ ✓ × × × × × ✓
Utility Verification × × × × × × × Partial × × ✓(Trivially) ✓
Cross-Domain Evaluation × × × × × × × × × × × ✓
Practical Complexity ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ × × × ✓
case, it cannot be scaled to audit the complete construction of a k-anonymity decision tree.
2.3. Explainable AI for Data Quality Assurance Chaudhury et al. (Chaudhury et al. (2024)) developed a methodology for explainable artificial intelligence using the Wasserstein distance to quantify model explainability and feature importance. The diagnostic analysis was performed by measuring the optimal transport cost required to morph the probability distribution of key predictive features (such as duration, age, and balance (Moro, Laureano, Cortez et al. (2011))) from a validation set into the distribution of the training data. Although the mathematical formulation evaluated the fidelity of a model and highlighted critical decision boundaries, it is to be understood that this is a post-hoc interpretability approach without any involvement of cryptographic auditing tools, and in this case, it cannot function as a standalone mechanism to verify the execution integrity of an outsourced algorithm.
2.4. Positioning of VeriX-Anon In evaluating the landscape of outsourced computation, it is vital to consider a naive re-execution baseline where the client simply re-runs the full Target-Driven Anonymization locally to verify the correctness of the Cloud’s output. The re-execution process is performed by downloading the outsourced results and fully reconstructing the decision tree from the raw feature space (including variables such as duration, age, and balance (Moro et al. (2011))). Although this naive approach achieves perfect deterministic verification, it is to be understood that this requires 𝑂(𝑛 log 𝑛) computation to build the full decision tree, and in this case, it defeats the entire purpose of outsourcing the computation to the Cloud. Conversely, VeriX-Anon achieves comprehensive verification in 𝑂(𝑛∕𝑘) time for the hash traversal alongside an 𝑂(1) overhead for the Explainable AI XAI utility check. This renders our approach strictly cheaper and highly practical for resource-constrained clients. As summarized in Table 1, the existing literature addresses isolated facets of outsourced data security, model explainability, and database integrity. Cryptographic frameworks provide rigorous mathematical proofs but incur prohibitive computational costs. Data mining auditing systems Page 4 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
utilize artificial traps but lack structural verification and utility analysis. Furthermore, while the Wasserstein distance effectively measures data fidelity, it has not been integrated into a cryptographic auditing pipeline. VeriX-Anon bridges these critical research gaps by introducing a multilayered verification framework. By combining 𝑂(𝑛∕𝑘) authenticated decision tree traversal with probabilistic boundary sentinels and 𝑂(1) explainable AI fingerprinting, VeriXAnon provides a practical, cross-domain solution that avoids the 𝑂(𝑛 log 𝑛) bottleneck of naive client-side re-execution, ensuring that outsourced anonymization is both mathematically verifiable and utility-preserving.
3. Background and Fundamentals This section defines the technical building blocks that VeriX-Anon relies on. Readers familiar with 𝑘-anonymity, Merkle trees, and SHAP may skip ahead to Section 4.
3.1. 𝑘-Anonymity and Quasi-Identifier Generalisation Sweeney (Sweeney (2002)) showed that 87% of the U.S. population can be uniquely identified from just three attributes: ZIP code, date of birth, and sex. These attributes are called quasi-identifiers (QIs), and 𝑘-anonymity exists to neutralise them. A dataset satisfies 𝑘-anonymity if every record is indistinguishable from at least 𝑘−1 other records on the QI columns. The mechanism is generalisation: replace specific QI values with broader ranges until each distinct QI combination appears at least 𝑘 times. Records sharing the same generalised QI values form an equivalence class. Generalisation comes at a cost. If ages {25, 27, 63} are all mapped to [0, 100], the equivalence class is private but analytically worthless. Smaller, tighter classes preserve more information but risk violating the 𝑘 threshold. Every anonymisation algorithm navigates this tension differently.
3.2. Target-Driven Decision Tree Anonymisation Blind anonymisation algorithms (e.g., Mondrian partitioning) split the data on quasi-identifiers without considering what the data will be used for afterwards. Target-Driven anonymisation, introduced by Friedman et al. (Friedman et al. (2006)) and refined by De Capitani di Vimercati et al. (De Capitani di Vimercati et al. (2024a)), builds a binary decision tree that partitions records by maximising variance reduction on a binary label. Each split selects the QI feature and threshold that best separate the target classes. Each leaf node becomes an equivalence class, and the QI values within it are generalised to their observed [min, max] range. Why does this matter? Records within the same leaf tend to share the same target label, so a classifier trained on the anonymised output can still distinguish positive from negative cases. Blind splitting mixes target classes within leaves and destroys this signal. VeriX-Anon exists because this distinction is invisible in the output. A data owner who receives an anonymised dataset and a tree structure cannot tell, by inspection alone, :
whether the cloud used Target-Driven or blind splitting. The verification framework provides that answer.
3.3. Merkle Trees and Hash-Based Authentication A Merkle tree is a binary tree in which every node stores a cryptographic hash (Merkle (1989)). Leaf nodes hash their own data content. Internal nodes hash the concatenation of their children’s hashes. The root hash therefore commits to the entire structure: change any single leaf or internal node, and every hash on the path to the root changes with it. In VeriX-Anon, the decision tree is the Merkle tree. Leaf nodes hash their generalisation bounds, and internal nodes hash their split feature, split value, and children’s hashes. If the cloud substitutes a different splitting algorithm or modifies the tree after construction, the root hash will not match the client’s independent re-computation. One distinction from the standard Merkle use case is worth noting. Blockchain systems typically use Merkle trees for single-element inclusion proofs in 𝑂(log 𝑛) time: proving that one transaction exists in the tree without revealing the rest. VeriX-Anon performs full tree re-verification in 𝑂(𝑛∕𝑘) time, because the client needs to verify the entire tree, not just one record’s membership. Section 5.5 discusses this cost in detail.
3.4. SHAP Values and Feature Attribution VeriX-Anon uses SHAP values not for model interpretation (their usual purpose) but as a data fingerprint. The idea is straightforward: if the anonymisation preserves the predictive relationships in the data, then a model trained on the anonymised output should attribute importance to the same features, in the same proportions, as a model trained on the original data. If those attributions diverge, something changed in the data’s structure. SHAP (SHapley Additive exPlanations), introduced by Lundberg and Lee (Lundberg and Lee (2017)), assigns each input feature a contribution score for a given prediction. The method is rooted in cooperative game theory: the Shapley value of feature 𝑗 for input 𝑥 is its average marginal contribution across all possible subsets of features. For a model ∑ 𝑓 , the SHAP values satisfy 𝑗 𝜙𝑗 (𝑥) = 𝑓 (𝑥) − 𝔼[𝑓 (𝑋)], meaning they fully decompose the gap between a specific prediction and the model’s average output. For tree-based models, the TreeExplainer algorithm computes exact SHAP values in polynomial time by exploiting the tree structure directly.
3.5. Wasserstein Distance The magnitude of this divergence is measured by the 1-Wasserstein distance (also called the Earth Mover’s Distance). For two distributions 𝑃 and 𝑄 over ℝ: ∞
𝑊1 (𝑃 , 𝑄) =
∫−∞
|𝐹𝑃 (𝑥) − 𝐹𝑄 (𝑥)| 𝑑𝑥
(1)
where 𝐹𝑃 and 𝐹𝑄 are the cumulative distribution functions. Informally, 𝑊1 measures the minimum cost of reshaping Page 5 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
Figure 1: Threat coverage matrix. Left columns show each adversary’s actions (data dropping, algorithm substitution, hash fabrication). Right columns show which verification layer catches the deviation. No single layer achieves full coverage; the multilayered design is necessary for 11/12 correct detection across the three empirically evaluated adversary profiles (1 –3 ). The Approximate adversary (3 ) bypasses Layers 1, 2a, and 2b entirely; Layer 3 (XAI) is the only mechanism that detects this attack, succeeding on Adult and Bank but failing on Diabetes due to severe class imbalance. 4 (Informed) is a theoretical profile analysed in Section 4.2.5 and is excluded from the 11/12 count; Caught* assumes salt secrecy holds.
one distribution into the other, where cost is mass moved times distance travelled. Chaudhury et al. (Chaudhury et al. (2024)) applied it to compare SHAP distributions for model explainability; VeriX-Anon adapts the same metric to compare SHAP distributions before and after anonymisation. A small 𝑊1 indicates that feature importance was preserved. A large 𝑊1 indicates that the cloud’s processing altered the data’s predictive structure, which is evidence of algorithm substitution. The threshold 𝜀 separating acceptable from suspicious divergence is calibrated empirically and discussed in Sections V-C3 and VII-C.
4. System Model and Threat Model This section defines the three entities in the VeriX-Anon protocol, the adversary profiles against which the framework is evaluated, and the security assumptions that bound the analysis. Figure 1 summarises the adversary action space and per-layer detection coverage.
:
4.1. System architecture The protocol involves three logical entities. In practice, the client and verification oracle run on the same machine; we separate them for clarity.
4.1.1. Client (data owner) The client holds a dataset = {(𝑥𝑖 , 𝑦𝑖 )}𝑁 , where 𝑥𝑖 is 𝑖=1 a vector of Quasi-Identifier (QI) attributes and 𝑦𝑖 ∈ {0, 1} is a binary target variable. The client wants 𝑘-anonymity applied to via Target-Driven decision tree partitioning, but lacks the computational resources (or prefers not) to perform this operation locally. Before outsourcing, the client injects Boundary Sentinels and Twins into the dataset, assigns cryptographic TrackerIDs to every record, and transmits the augmented dataset ′ = ∪ ∪ to the cloud. 4.1.2. Cloud provider The cloud receives ′ and is contractually obligated to: 1. Build a Target-Driven decision tree that partitions records by maximising variance reduction on the target 𝑦. Page 6 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
2. Generalise QI values within each leaf to their [min, max] range, producing 𝑘-anonymous equivalence classes. 3. Compute a bottom-up Merkle-style SHA-256 hash over the tree structure. 4. Return three objects to the client: the anonymized dataset ∗ , a leaf assignment mapping ∶ TrackerID → leaf_id, and the Merkle root hash 𝐻root . The cloud has full access to the feature values and target column of ′ . It does not have access to the client’s trap manifest (the set of sentinel TrackerIDs, the twin pair map, or the client’s XAI baseline).
4.1.3. Verification oracle (client-side) After receiving (∗ , , 𝐻root ) from the cloud, the client executes a four-layer verification audit. This is a local computation: the client never sends verification queries back to the cloud, so the cloud cannot adapt its behaviour based on which checks are being run.
4.2. Adversary profiles We define one honest baseline and three adversary profiles, ordered by increasing deviation from the honest protocol. A fifth profile, the Informed Attacker (4 ), is analysed theoretically in Section 4.2.5.
4.2.1. Honest cloud (0 ) The honest cloud follows the protocol exactly. It processes all records in ′ , builds the Target-Driven tree with variance reduction splitting, generalises leaves, computes the correct Merkle hash, and returns the complete result. This profile is the baseline: VeriX-Anon should report VERIFIED for all honest executions. 4.2.2. Lazy cloud (1 ) The lazy cloud drops a fraction 𝛿 = 0.05 of records from ′ before processing. It then runs the correct TargetDriven algorithm on the reduced dataset ′red ⊂ ′ with |′red | = (1 − 𝛿) ⋅ |′ |. The returned hash is valid for the reduced tree. Motivation: processing fewer records saves compute. In a pay-per-use cloud model, a 5% reduction in data volume translates directly to reduced CPU time and memory. The lazy cloud bets that the client will not notice a small number of missing records in a large anonymized output. Because the tree over the reduced data is internally consistent, the Merkle hash is correct for that tree. Layer 1 (hash verification) will pass. The attack is detectable only through Layer 2 (missing sentinels or twins) or, in some cases, through Layer 3 (SHAP distribution shift if the dropped records alter the feature importance structure). 4.2.3. Dumb cloud (2 ) The dumb cloud replaces Target-Driven splitting with random-feature splitting (Mondrian-style blind partitioning). It processes all records in ′ but ignores the target variable 𝑦 entirely, splitting on randomly selected features
:
at the median value. After building the blind tree, it fabri′ cates a root hash 𝐻root ≠ 𝐻root to disguise the algorithm substitution. Motivation: random splitting is cheaper than TargetDriven splitting. Computing variance reduction requires evaluating every candidate feature at every node and reading the target column. Random splitting skips this entirely. The dumb cloud saves computation at the cost of destroying predictive utility in the anonymized output. Because all records are present and the tree is deterministic (random but consistent), Layer 2 (sentinels and twins) will pass: sentinels are not dropped, and identical twins follow the same random splits into the same leaf. The attack is detectable through Layer 1 (the fabricated hash does not match the client’s re-computation) and Layer 3 (SHAP distributions diverge because the blind tree does not preserve the target-feature relationships).
4.2.4. Approximate cloud (3 ) The approximate cloud takes the exact same utilitydestroying shortcut as the dumb cloud: it uses randomfeature splitting to save compute. But it does not fake the math. It processes every single record and computes a perfectly valid Merkle root hash for its substandard tree. Motivation: The cloud wants to save CPU cycles but knows the client verifies hashes and row counts. By doing the hashing correctly and keeping all data intact, the cloud effortlessly bypasses Layer 1 (structural checks) and Layer 2 (trap checks). The only way to catch this adversary is to measure the actual machine learning utility of the returned data. This profile exists specifically to test the necessity of Explainable AI fingerprinting. 4.2.5. Adversary limitations and the informed attacker (4 ) The four profiles above assume the adversary does not know sentinels and twins exist in the outsourced data. A stronger adversary, the Informed Attacker (4 ), knows the client embeds traps and tries to remove them before processing. Cryptographic TrackerIDs (SHA-256 with a secret salt) make sentinels and twins statistically indistinguishable from genuine records. The TrackerID is a deterministic hash of the salt, the record’s role, its index, and its feature vector. Without the salt, the cloud cannot map TrackerIDs to trap records. The IDs themselves are uniformly distributed 256bit strings. No statistical test on the ID values can separate traps from real data. Boundary Sentinels do have a structural tell. Because we place them near the decision boundary (𝑃 ∈ [0.45, 0.55]), they might cluster in specific regions of the feature space. An attacker with a clean copy of the original public dataset could run outlier detection to flag perturbed records in those dense boundary regions. If the adversary successfully drops the sentinels, Layer 2a becomes useless.
Page 7 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
This is exactly why VeriX-Anon uses multiple layers. If the informed attacker defeats Layer 2 completely by removing all sentinels and twins, Layer 1 (ADT Hash) and Layer 3 (XAI Fingerprint) still catch the deviation. Layer 1 flags structural changes to the tree. Layer 3 flags utility degradation. To beat the entire framework, the informed attacker has to identify and remove all traps, reproduce the exact Target-Driven tree structure to satisfy the hash check, and preserve SHAP distributions within 𝜀. If an attacker does all that compute, they have effectively run the honest protocol anyway. We leave formal analysis of an adaptive informed attacker (one that observes verification outcomes and tweaks its approach across multiple rounds) to future work.
4.3. Security assumptions The verification guarantees of VeriX-Anon rest on four assumptions: 1. Limited client compute. The client retains enough local resources to train a Random Forest on 10% of (for sentinel generation) and an XGBoost model on 2,000 rows (for XAI fingerprinting). Both operations complete in seconds on commodity hardware. The client does not need the resources to build the full anonymization tree, which is the point of outsourcing. 2. SHA-256 collision resistance. The Merkle authentication in Layer 1 relies on the assumption that SHA256 is collision-resistant. An adversary that can find two distinct tree structures producing the same root hash could defeat Layer 1. Under standard cryptographic assumptions, this requires 𝑂(2128 ) work, which is computationally infeasible. 3. Trap indistinguishability. The cloud cannot distinguish sentinel or twin records from genuine records without access to the client’s secret salt. TrackerIDs are deterministic SHA-256 hashes that appear uniformly random to any party without the salt. Featurelevel indistinguishability depends on the perturbation being small enough that sentinels fall within the natural variation of the dataset (enforced by the 0.05 ⋅ 𝜎𝑗 perturbation bound in Equation 2). 4. Secret trap manifest. The client’s trap manifest (sentinel IDs, twin pair map, XAI baseline distributions) is never transmitted to the cloud. In particular, the cryptographic salt used in TrackerID generation (Equation 4) remains client-side at all times; if the cloud were to obtain the salt, it could recompute TrackerIDs and identify which records are sentinels, twins, or genuine, defeating Layer 2 entirely. The cloud receives only ′ (the augmented dataset with TrackerIDs and target column). All verification is performed client-side after the cloud returns its output.
:
5. Proposed Methodology: The VeriX-Anon Framework VeriX-Anon operates in four sequential phases. The client first prepares the dataset by injecting cryptographically tracked traps (Phase 1). The cloud then performs authenticated Target-Driven anonymization and returns the result with a Merkle root hash (Phase 2). The client independently computes an XAI fingerprint on its local data before outsourcing (Phase 3). Finally, the client runs a fourlayer verification engine that cross-checks the cloud’s output against all three verification mechanisms (Phase 4). Figure 2 illustrates the end-to-end architecture. We use the term mathematically verifiable to describe a system in which every verification layer has a quantifiable guarantee: Layer 1 provides deterministic correctness (any structural tampering is detected with probability 1 under the collision-resistance assumption of SHA-256), Layer 2 provides probabilistic completeness (sentinel evasion probability is bounded by Equation 13 and twin consistency is deterministic), and Layer 3 provides empirically calibrated utility verification (violation detection above the threshold 𝜀 with sensitivity governed by the OR-rule in Equation 11). Each layer’s detection properties are formally characterised, even where the underlying mechanism is probabilistic or empirical rather than deterministic.
5.1. Phase 1: Client-Side Preparation Before outsourcing, the client embeds two types of verifiable structures into the dataset: Boundary Sentinels (probabilistic traps near the decision boundary) and Twins (deterministic duplicate pairs). Both are tagged with cryptographic TrackerIDs that the cloud cannot distinguish from genuine records.
5.1.1. Boundary Sentinel Generation The client trains a Random Forest classifier (𝐵 = 50 trees, max_depth = 5) on a 10% stratified subsample of the original dataset . For each record 𝑥𝑖 ∈ , the trained model produces a class-1 probability 𝑃 (𝑦 = 1 ∣ 𝑥𝑖 ). Records falling within the uncertainty band 𝑃 ∈ [0.45, 0.55] sit near the decision boundary, where they are most sensitive to changes in the splitting logic. From this boundary set, the client selects up to ⌈0.02⋅𝑁⌉ candidates and perturbs only their numerical columns: ( ) max 𝑥′𝑗 = clip 𝑥𝑗 + (0, 0.05 ⋅ 𝜎𝑗 ), 𝑥min 𝑗 , 𝑥𝑗
(2)
where 𝜎𝑗 is the population standard deviation of column 𝑗, and the clip operation ensures that values fall within the range of that column. Categorical columns are not modified. Integer-type columns are rounded at this stage. This generates synthetic data that is statistically valid but placed in a position where any variation from Target-Driven logic, such as random splitting, will move them to incorrect leaves. The number of sentinels depends on the class distribution within the dataset. Balanced datasets will have more Page 8 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
Figure 2: VeriX-Anon end-to-end architecture. The client prepares the dataset with embedded traps (Phase 1), outsources to the cloud for authenticated Target-Driven anonymization (Phase 2), and runs the four-layer verification engine (Phase 4) against a locally computed XAI baseline (Phase 3).
sentinels than imbalanced ones. In our experiments, Adult Income had 501 sentinels, 160 within the 2% limit, while Bank Marketing had only 13. The implications are given in Section 7.2.
5.1.2. Twin Generation The client selects 5% of genuine records uniformly at random and creates exact duplicates. Under a deterministic anonymization algorithm, two identical feature vectors must traverse the same tree path and land in the same leaf. If the cloud’s returned leaf assignments place any (original, twin) pair in different leaves, this constitutes proof that the cloud used a non-deterministic or randomized method. Formally, let 𝑥𝑖 be a genuine record and 𝑥′𝑖 = 𝑥𝑖 be its twin. Under deterministic tree : (𝑥𝑖 ) = (𝑥′𝑖 )
∀ (𝑥𝑖 , 𝑥′𝑖 ) ∈ TwinPairs
(3)
Any violation of Equation 3 is a sufficient condition for detecting non-deterministic processing. A potential concern is that exact duplicates could be detected by an adversary running standard deduplication on the outsourced data. In datasets with continuous numerical features, exact duplicates are statistically rare in natural data, and their presence could raise suspicion. Two mitigations exist. First, the twin injection rate (5%) is low enough that :
duplicates are plausible as natural repetition in large administrative datasets (e.g., repeated hospital visits or duplicate survey entries). Second, future versions could replace exact twins with near-duplicates, applying a small perturbation (e.g., ±1 in the least significant digit of numerical features) that preserves the same-leaf guarantee under deterministic tree splitting with quantised thresholds. Formal analysis of near-duplicate twins is left to future work.
5.1.3. Cryptographic Tracking IDs Each record (genuine, sentinel, or twin) receives a deterministic SHA-256 identifier: ( ) TID𝑖 = SHA-256 salt ‖ role𝑖 ‖ 𝑖 ‖ bytes(𝑥𝑖 )
(4)
where salt is a secret string known only to the client, role𝑖 ∈ {genuine, sentinel, twin}, and bytes(𝑥𝑖 ) is the bytelevel representation of the record’s feature vector. Because the hash is deterministic, the client can always recompute any TrackerID without storing random nonces. For twin pairs, the client maintains a local mapping twin_pair_map[TIDorig ] = TIDtwin that links each original record to its duplicate. This mapping, along with the set of sentinel TrackerIDs, forms the client’s trap manifest , which is never shared with the cloud.
Page 9 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
5.1.4. Dataset Assembly and Outsourcing The client concatenates genuine records, sentinels, and twins into a single outsourced dataset: ′ = ∪ ∪
(5)
The combined dataset is shuffled using a seeded pseudorandom permutation before transmission. Shuffling prevents the cloud from inferring trap positions based on row ordering. Each row carries its TrackerID and the binary target column; the cloud has no information about which rows are genuine, sentinels, or twins.
5.2. Phase 2: Authenticated Target-Driven Anonymization (ADT) The cloud receives ′ and is contracted to perform Target-Driven 𝑘-anonymization. This section describes the honest protocol; adversarial deviations are defined in Section 4.
5.2.1. Target-Driven Decision Tree Construction The cloud builds a binary decision tree that partitions records to maximize within-leaf target homogeneity. At each internal node, the cloud selects the feature 𝑓 ∗ and split value 𝑠∗ (the column median) that maximise variance reduction:1
2 − Δ𝜎 2 = 𝜎parent
2 𝑛𝐿 ⋅ 𝜎𝐿2 + 𝑛𝑅 ⋅ 𝜎𝑅
𝑛parent
(6)
2 are the target variances of the 2 where 𝜎parent , 𝜎𝐿2 , and 𝜎𝑅 parent, left child, and right child respectively, and 𝑛𝐿 , 𝑛𝑅 , 𝑛parent are the corresponding record counts. Tree construction terminates when any of the following conditions holds:
1. The number of records within the node is less than 2 × min_leaf, where min_leaf = 2𝑘 (i.e., the node contains fewer than 4𝑘 records). This ensures that any binary split produces children with at least 2𝑘 records each, satisfying the 𝑘-anonymity guarantee. 2. The node is pure, i.e., 𝜎 2 = 0, which means that all records within this node have the same target value. 3. The depth of the tree exceeds a safety limit of 50. This limit prevents unbounded recursion in pathological cases (e.g., features with many unique values producing long chains of binary splits). In practice, the deepest tree observed in our experiments had 11 levels (Diabetes, 8,000 rows, 𝑘 = 5). The limit of 50 is never reached during normal operation and serves only as a safeguard. 1 In the reference implementation, the parent node variance is computed
using the pandas Series.var() method (sample variance, ddof = 1), while child node variances are computed using NumPy array .var() (population variance, ddof = 0). This inconsistency has negligible effect on split selection because all candidate splits at a given node share the same parent variance as the reference value, and child nodes contain at least 2𝑘 = 10 records, where the difference between 𝑛 and 𝑛−1 denominators is under 10%. Standardising to a single convention would not change any split decision in the experiments reported here.
:
The choice of using the median ensures that we do not have any "degenerate" splits that could result in a leaf with too few records to satisfy the 𝑘-anonymity condition.
5.2.2. Leaf-Level Generalization Each leaf node generalises its Quasi-Identifier (QI) columns by replacing individual values with the observed [min, max] range within that leaf. All records assigned to the same leaf become indistinguishable on every QI attribute. Because each leaf contains at least 2𝑘 records (enforced by the stopping rule), the resulting partition satisfies 𝑘anonymity. For downstream compatibility (e.g., training a classifier on anonymized data), each generalised value can be reconstructed as the range midpoint:
𝑥(𝑗) = mid
𝑥(𝑗) + 𝑥(𝑗) max min 2
(7)
5.2.3. Merkle-Style Tree Authentication After building the tree and generalising leaves, the cloud computes a bottom-up SHA-256 hash over the entire tree structure. This produces a single root hash 𝐻root that cryptographically commits to every split decision and every leaf’s generalisation bounds. For leaf nodes: 𝐻𝓁 = SHA-256("LEAF|" ‖ |𝓁| ‖ "|" ‖ canonical_bounds(𝓁)) (8) where |𝓁| is the number of records in leaf 𝓁, and canonical_bounds(𝓁) is a deterministic string encoding of the leaf’s generalisation ranges, sorted alphabetically by feature name with values rounded to 6 decimal places and pipe-separated. 𝐻𝑣 = SHA-256("INTERNAL|" ‖ 𝑓𝑣 ‖ "|" ‖ 𝑠𝑣 ‖ "|" ‖ 𝐻𝐿
(9)
‖ "|" ‖ 𝐻𝑅 ) where 𝑓𝑣 is the split feature, 𝑠𝑣 is the split value (rounded to 6 decimal places), and 𝐻𝐿 , 𝐻𝑅 are the hashes of the left and right children. The canonical formatting (fixed decimal precision, alphabetical sorting) eliminates platform-dependent floating-point representation issues. The cloud returns three objects to the client: (1) the anonymized dataset ∗ , (2) a leaf assignment mapping ∶ TrackerID → leaf_id, and (3) the root hash 𝐻root .
5.3. Phase 3: XAI Fingerprinting Before outsourcing, the client computes an expected “fingerprint” of its data’s predictive structure. After receiving the cloud’s output, the client computes a second fingerprint on the anonymized data and measures the divergence. Large divergence indicates that the cloud’s processing destroyed the predictive logic encoded in the original data.
Page 10 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
5.3.1. Client Baseline Computation The client trains an XGBoost classifier (100 estimators, max depth 6, learning rate 0.1) on a 2,000-row subsample of the clean data . Using TreeExplainer (Lundberg and Lee (2017)), the client extracts SHAP value distributions for the top-3 features ranked by mean absolute SHAP value (mean|𝜙𝑓 |). These distributions form the client’s baseline ) fingerprint Φclient = {𝜙(𝑓 } . client 𝑓 ∈top-3 The 2,000-row subsample keeps SHAP computation tractable regardless of dataset size and makes the XAI layer 𝑂(1) with respect to 𝑛. The choice of 2,000 rows balances two competing concerns. A smaller subsample (e.g., 500 rows) risks unstable SHAP estimates, particularly for features with heavy-tailed distributions, because TreeExplainer’s output variance scales inversely with sample size. A larger subsample (e.g., 5,000 rows) increases computation time without proportionally improving fingerprint stability, since XGBoost with 100 estimators converges in its feature importance rankings well below 2,000 rows for the datasets tested. In our experiments, the top-3 feature rankings were consistent across 1,000-row and 2,000-row subsamples for both Adult Income and Bank Marketing. The 5,000-row Experiment 3 subsample produced a slightly different top-3 ranking (age, marital-status, relationship vs. age, relationship, education-num), which we attribute to subsample composition rather than instability. A formal sensitivity analysis across subsample sizes is a valuable direction for future work. 5.3.2. Cloud Output Evaluation Upon receiving the anonymized dataset ∗ , the client flattens generalised ranges to midpoint values using Equation 7, then trains an identical XGBoost model on a 2,000row subsample and extracts SHAP distributions for the same ) top-3 features: Φcloud = {𝜙(𝑓 } . cloud 𝑓 ∈top-3 5.3.3. Wasserstein Distance Comparison and Violation Rule For each top-3 feature 𝑓 , the client computes the 1Wasserstein distance (Earth Mover’s Distance) between the client and cloud SHAP distributions: ( ) ) (𝑓 ) 𝑊𝑓 = 𝑊1 𝜙(𝑓 , 𝜙 client cloud
(10)
The client applies an OR-rule: if any single feature’s Wasserstein distance exceeds the threshold 𝜀, the cloud is flagged for an algorithmic integrity violation: XAI_Violation = ∃ 𝑓 ∈ top-3 s.t. 𝑊𝑓 > 𝜀
5.4. Phase 4: Multi-Layered Client Verification Engine Upon receipt of the cloud’s output (∗ , , 𝐻root ), the client performs four independent verification procedures. The motivation behind this is the "Swiss Cheese" model, where each layer protects against a different type of deviation, with the combination protecting against deviations not covered by any single layer.
5.4.1. Layer 1: ADT Hash Verification The client reconstructs the Merkle hash tree from the returned anonymized data and tree structure using Equations 8 and 9. If the hash value at the root of the reconstructed tree matches the reported hash value from the cloud 𝐻root , it is certain that the tree structure is unchanged. Any difference between the two hash values indicates that the cloud either altered the tree structure or fabricated a hash value. This layer is deterministic; that is, there are no false positives or false negatives for structural tampering. The complexity of this layer is 𝑂(𝑛∕𝑘).
(11)
The OR-rule is strictly more sensitive than an averaging rule. If the cloud substitutes a utility-destroying algorithm (e.g., random splitting), it may damage one feature’s SHAP distribution severely while leaving others relatively intact. Averaging could mask this single-feature damage; the ORrule catches it. :
The value of 𝜀 is set to 0.45 after being empirically tuned for the default operating point 𝑘 = 5. At this 𝑘-value, the maximum honest per-feature Wasserstein distance is 0.4436 (relationship), sitting 0.0064 below 𝜀. The minimum adversarial per-feature distance that triggers the OR-rule in the Experiment 3 feature set is 0.4574 (relationship under the Blind adversary at 𝑘 = 5),giving a separation margin of 0.0138. We emphasise that 𝜀 must be calibrated per contracted 𝑘-value: at 𝑘 = 10, 12, and 15, the honest per-feature WD for marital-status exceeds 0.45 (reaching 0.5744 at 𝑘 = 12), which would produce false positives under the current global threshold. In a production deployment, the client would calibrate 𝜀 for the specific 𝑘-value contracted with the cloud, not across the full 𝑘-sweep. We emphasise that 𝜀 is not a learned model parameter and its calibration does not constitute data leakage in the machine learning sense. In a real deployment, the client would establish 𝜀 during a one-time calibration phase: the client runs the Target-Driven anonymisation locally on a small representative sample (e.g., 1,000 rows) at the contracted 𝑘-value, computes the honest SHAP Wasserstein distances, and sets 𝜀 above the observed honest maximum with a safety margin. This calibration requires the client to anonymise only a small sample locally (seconds of compute), not the full dataset. The adversarial distribution is not needed for calibration because any 𝜀 set above the honest baseline will flag deviations that exceed it. The 𝑘-sweep in Section 6.4 serves to validate this approach across a range of 𝑘-values; it is not used to fit 𝜀 to adversarial outputs.
5.4.2. Layer 2a: Sentinel Presence Check At this layer, the client checks if the sentinels from are present in ∗ . The absence of sentinels indicates that the cloud has discarded data during processing. ( ) Sentinel_Pass = ∀ TID𝑠 ∈ IDs ∶ TID𝑠 ∈ ∗ .TrackerIDs Page 11 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
(12) The probability that a data-dropping adversary (dropping fraction 𝛿) evades all |𝑆| sentinels is: ( 𝑃evade =
1−
|𝑆| |′ |
)|′ |⋅𝛿 (13)
When |𝑆| is large compared to |′ |, evasion probability falls quickly. Yet, when class imbalance results in a small number of boundary candidates (e.g., in the Bank Marketing problem, |𝑆| = 13 compared to |′ | = 8, 413), evasion probability can be substantial (Section 7.2). Equation 13 assumes uniform random dropping. If the adversary uses a non-uniform strategy (e.g., preferentially dropping records from the majority class to reduce compute while minimally affecting the tree), the evasion probability would differ. Majority-class-biased dropping would be less likely to hit sentinels that cluster near the decision boundary (which is class-balanced by construction), potentially reducing evasion probability relative to the uniform case. Complexity: 𝑂(|𝑆|), where |𝑆| ≤ 0.02𝑛.
5.4.3. Layer 2b: Twin Leaf Consistency Check For every (original, twin) pair in twin_pair_map, the client verifies that both TrackerIDs map to the same leaf in : ( Twin_Pass = ∀ (TID𝑜 , TID𝑡 ) ∈ twin_pair_map ∶ (14) ) [TID𝑜 ] = [TID𝑡 ] This check is independent of Layer 1. A Lazy adversary that drops 5% of records but runs the correct algorithm on the remainder will produce a valid hash for the reduced tree, passing Layer 1. However, dropped twins cause missing entries in , and any non-deterministic processing (even with all records present) causes leaf mismatches. Complexity: 𝑂(|𝑇 |), where |𝑇 | = 0.05𝑛.
5.4.4. Layer 3: XAI Fingerprint Verification The client evaluates the cloud’s anonymized output using the procedure described in Section 5.3.3. If any top-3 feature’s Wasserstein distance exceeds 𝜀, the layer flags a violation. This layer is completely orthogonal to Layers 1 and 2. A Dumb adversary fakes the root hash and gets caught by Layer 1. An Approximate adversary, however, computes a mathematically perfect hash for a utility-destroying tree. Because the hash is valid and no data is dropped, Layers 1 and 2 pass the output. Layer 3 is the only mechanism that catches this utility degradation. Conversely, a Lazy adversary that drops just 5% of records might produce Wasserstein distances within 𝜀, slipping past Layer 3 but getting caught by Layer 2. Complexity: 𝑂(1) relative to 𝑛, since SHAP computation uses a fixed 2,000-row subsample. :
Table 2 Client-side verification complexity by layer. Total cost is dominated by the 𝑂(𝑛∕𝑘) hash traversal. The XAI layer is constant with respect to 𝑛 because SHAP computation uses a fixed subsample of 2,000 rows. Layer Layer 1 (ADT Hash) Layer 2a (Sentinels) Layer 2b (Twins) Layer 3 (XAI) Total
Operation Full tree hash re-computation TrackerID presence lookup Leaf assignment comparison SHAP extraction + Wasserstein
Complexity 𝑂(𝑛∕𝑘) 𝑂(|𝑆|) ≈ 𝑂(0.02𝑛) 𝑂(|𝑇 |) ≈ 𝑂(0.05𝑛) 𝑂(1) 𝑂(𝑛∕𝑘)
5.4.5. Verdict Aggregation The final verdict is the conjunction of all four checks:
Verdict =
4 ⋀
( ) Layer𝑖 ∗ , , 𝐻root ,
(15)
𝑖=1
where is the client’s trap manifest (sentinel IDs, twin pair map, and XAI baseline). The system reports VERIFIED if and only if all layers pass. A failure in any single layer produces VIOLATION DETECTED, and the audit log records which specific layer(s) triggered.
5.5. Complexity Analysis Table 2 summarises the per-layer verification cost. The tree hash verification visits every node in the decision tree. Because each leaf contains at least 2𝑘 records, the number of leaves is at most 𝑛∕(2𝑘), and the total number of nodes (leaves plus internals) is 𝑂(𝑛∕𝑘). This is not 𝑂(log 𝑛): a standard single-element Merkle proof traverses a root-toleaf path of length 𝑂(log 𝑛), but VeriX-Anon performs full re-verification of the entire tree, which requires visiting every node. The distinction matters because 𝑛∕𝑘 can be substantially larger than log 𝑛 for large datasets with small 𝑘. The sentinel check and twin check are linear with respect to the number of injected traps, which is a constant proportion of 𝑛. The XAI layer trains a model on 2,000 rows exactly and uses Wasserstein distance over three feature distributions, which is constant with respect to 𝑛. In reality, for smaller values of 𝑛, the XAI cost is dominant at around 0.5s to train the model and compute SHAP. Conversely, for larger values of 𝑛, the hash traversal cost is dominant. Section 6.3 shows that verification time remains sub-second for 𝑛 = 106 .
6. Experimental Results and Evaluation This section reports three experiments. Experiment 1 evaluates detection accuracy across 3 datasets and 4 cloud profiles (3 honest + 9 adversarial = 12 scenarios total). Experiment 2 measures client-side verification time from 𝑛 = 10,000 to 𝑛 = 1,000,000. Experiment 3 quantifies the utility-privacy trade-off using an 11-point 𝑘-sweep with paired statistical tests. All code runs as a single reproducible Kaggle notebook, available from the corresponding author upon reasonable request. Page 12 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
6.1. Experimental Setup 6.1.1. Datasets Three cross-domain datasets were selected to test generalisability across societal, financial, and medical contexts. 1. Adult Income (OpenML id=1590): 48,842 rows, 14 quasi-identifiers. Binary target: annual income exceeding $50K. Class distribution: 76% negative, 24% positive. 2. Bank Marketing (OpenML id=1461, Moro et al. (2011)): 45,211 rows, 16 quasi-identifiers. Binary target: term deposit subscription. Class distribution: 88% negative, 12% positive. OpenML encodes column names as V1 through V16; we use the original UCI feature names (age, job, marital, education, default, balance, housing, loan, contact, day, month, duration, campaign, pdays, previous, poutcome) throughout this paper. The full mapping is provided in Appendix B. 3. Diabetes 130-US Hospitals (UCI Machine Learning Repository): 101,766 rows, 16 quasi-identifiers. Binary target: hospital readmission within 30 days. Class distribution: 89% negative, 11% positive. Missing values encoded as ? in the original CSV were imputed using column-wise mode for categorical features and median for numerical features.
6.1.2. Configuration All experiments use the parameters in Table 3. For Experiment 1, each dataset is subsampled to 8,000 rows. This size is chosen to balance two constraints: (a) the 12scenario evaluation (3 datasets × 4 cloud profiles) requires 12 full anonymisation runs plus 12 verification audits, each involving tree construction, SHAP extraction, and hash computation; and (b) the verification mechanisms (hash checking, sentinel presence, twin consistency, SHAP comparison) operate identically regardless of dataset size, since they depend on structural properties (tree topology, record presence, feature distributions) rather than raw row count. The scalability experiment (Section 6.3) separately confirms that verification time remains sub-second at 𝑛 = 106 . Experiment 3 uses 5,000 rows for the same reason: the 11-point 𝑘-sweep requires 22 anonymisation runs (11 × 2 methods), and larger subsamples would not change the relative F1 or WD comparisons between Target-Driven and Blind anonymisation. For Experiment 3, the Adult Income dataset is subsampled to 5,000 rows to allow the 11-point 𝑘-sweep to complete within reasonable time. 6.1.3. Trap Injection Summary The trap injection counts for each dataset at 𝑘 = 5 are given in Table 4. The number of sentinel yield depends on the class balance. For Adult Income, there are 501 boundary candidates, limited by the 160 sentinels imposed by the 2% limit. Bank Marketing, with an 88/12 imbalance, only has 13 boundary points, all of which are sentinels. This affects the sentinel-based detection power, as discussed in Section 7.2.
:
Table 3 Default experimental configuration. All parameters are fixed across datasets unless stated otherwise. Parameter 𝑘-anonymity parameter Wasserstein threshold 𝜀 SHAP subsample size Sentinel injection ratio Twin injection ratio Random Forest (sentinel gen.) XGBoost (XAI fingerprint) ADT max tree depth Bootstrap resamples Lazy adversary drop fraction 𝛿
Value 5 0.45 2,000 rows 2% of 𝑁 5% of 𝑁 50 trees, max depth 5 100 estimators, max depth 6 50 10,000 0.05
Table 4 Trap injection summary for each dataset at 𝑘 = 5. Boundary points are records with RF prediction probability 𝑃 ∈ [0.45, 0.55]. Trap ratio is the fraction of the outsourced dataset that consists of sentinels and twins. Metric Adult Income Bank Marketing Diabetes 130-US Boundary Pts. 501 13 4 Sentinels 160 13 4 Twins 400 400 400 Outsourced Size 8,560 8,413 8,404 Trap Ratio 6.5% 4.9% 4.8%
Table 5 Software environment for all experiments. Component Python NumPy pandas scikit-learn XGBoost SHAP SciPy Matplotlib hashlib
Platform
Version 3.12.12 2.0.2 2.3.3 1.6.1 3.2.0 0.50.0 1.16.3 3.10.0 Python stdlib Linux (Kaggle), Intel Xeon @ 2.20 GHz, CPU-only
6.1.4. Software Environment All experiments were run on Kaggle’s free-tier cloud notebook environment with a single Intel Xeon CPU at 2.20 GHz, without any GPU acceleration. The software stack we used is listed in Table 5. Our framework relies only on standard Python libraries, including hashlib for the SHA256 hashing algorithm, and widely used open-source tools. We do not rely on any proprietary or custom-compiled software or GPU-specific tools.
6.2. Multi-Layered Threat Detection Results VeriX-Anon correctly identified 11 of 12 scenarios: 3 honest clouds verified, 3 lazy clouds detected, 3 dumb clouds detected, and 2 approximate clouds detected. No single verification layer can achieve this result alone. Table 6 breaks down the exact numbers. Figure 3 maps this coverage visually to show exactly how the layers back each other up when one fails.
Page 13 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
Figure 3: Per-layer verification coverage across three domains and four cloud profiles. Green cells indicate correct behaviour (pass for honest, caught for malicious). Orange cells indicate missed attacks on that layer. The Diabetes Dumb cloud escapes Layer 3 (XAI) but is caught by Layer 1 (ADT Hash). The Diabetes Approximate cloud escapes all four layers, producing the single incorrect verdict (11/12 overall).
Table 6 Per-layer detection results across 3 datasets and 4 adversary profiles. ✓= layer correctly identifies the scenario (pass for honest, caught for malicious). × = layer misses the attack. The overall verdict is correct in 11 of 12 cases. Layer 3 (XAI) is the only layer capable of catching the Approximate adversary. Scenario Adult–Honest Adult–Lazy Adult–Dumb Bank–Honest Bank–Lazy Bank–Dumb Diabetes–Honest Diabetes–Lazy Diabetes–Dumb Adult–Approx Bank–Approx Diabetes–Approx
L1 L2a L2b L3 Overall ✓ ✓ ✓ ✓ ✓ × ✓ ✓ × ✓ ✓ × × ✓ ✓ ✓ ✓ ✓ ✓ ✓ × × ✓ ✓ ✓ ✓ × × ✓ ✓ ✓ ✓ ✓ ✓ ✓ × ✓ ✓ × ✓ ✓ × × × ✓ × × × ✓ ✓ × × × ✓ ✓ × × × × ×
6.2.1. Dumb Cloud analysis The Dumb adversary substitutes Target-Driven splitting with random feature Mondrian partitioning and generates a fake root hash. In Layer 1, all three datasets are caught because the fake hash does not match the client’s re-computed hash. In Layer 3, two out of three datasets are caught: Adult Income (with an average WD = 0.3293 and a age feature with WD = 0.5120 violating 𝜀 = 0.45) and Bank Marketing (with an average WD = 0.4945 and a duration feature with WD = 1.2618). The third dataset, Diabetes, completely evades Layer 3 (with an average WD = 0.1320), because the dataset’s severe class imbalance (89/11 split) produces weak feature-target SHAP structure that does not diverge significantly under algorithm substitution. Section 7.1 discusses this limitation. Layer 2 (both sentinels and twins) does not detect the Dumb adversary because the adversary processes all records :
(no dropping of data) and because, although Mondrian partitioning is utility-destroying, it is still deterministic: identical twin vectors have the same random splits to the same leaf.
6.2.2. Lazy Cloud analysis The Lazy adversary drops 5% of the data but uses the correct Target-Driven algorithm for the remaining records. Because of the internally consistent tree structure for the reduced data, Layer 1 succeeds: the cloud responds with a valid hash for the smaller tree. Layer 3 catches one of three datasets: Bank Marketing, whose Wasserstein distance for the duration feature is 0.6208, exceeding 𝜀 = 0.45. Layer 3 misses the remaining two datasets because dropping 5% of the data does not shift SHAP distributions enough to exceed 𝜀 on Adult Income (average WD = 0.2290, maximum WD = 0.2997 for age) or Diabetes (average WD = 0.1263, maximum WD = 0.1814 for number_diagnoses). Layer 2b (Twins) catches all three datasets. Dropped records include twins, producing missing entries in the leaf assignment mapping: Adult 365/400 consistent (35 missing), Bank 347/400 (53 missing), Diabetes 359/400 (41 missing). Layer 2a (Sentinels) catches Adult Income (157/160 present, 3 missing) and Diabetes (3/4 present, 1 missing). Bank Marketing sentinels all survive the 5% drop (13/13 present), as expected given the low sentinel count. For Bank Marketing, the sentinel evasion probability under 5% dropping is: ( 𝑃evade =
13 1− 8,413
)420 ≈ 0.52
(16)
A 52% chance of all 13 sentinels surviving a 420-record drop is not surprising. This result again verifies that sentinelbased detection is unreliable when class imbalance results in a limited number of boundary candidates. Furthermore, it verifies our multi-layered solution, where Layer 2b (Twins) corrects for failures of Layer 2a, and Layer 3 extends coverage for datasets with strong feature-target correlations. Page 14 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization Table 7 Per-feature SHAP Wasserstein distances for the top-3 features under each adversary profile. † denotes individual per-feature values exceeding 𝜀 = 0.45. Average rows are provided for reference only; the detection decision uses the OR-rule (Equation 11) on individual features. The Diabetes Dumb adversary produces no per-feature violations, escaping Layer 3 entirely (caught by Layer 1). Dataset Adult Adult Adult Adult
Feature age relationship education-num Average
Honest 0.1998 0.0883 0.1430 0.1437
Lazy 0.2997 0.1592 0.2280 0.2290
Dumb 0.5120† 0.2098 0.2660 0.3293
Bank Bank Bank Bank
duration age balance Average
0.4185 0.1906 0.1845 0.2645
0.6208† 0.2310 0.2859 0.3792
1.2618† 0.1723 0.0495 0.4945
Diabetes Diabetes Diabetes Diabetes
number_diagnoses num_lab_procedures num_medications Average
0.0868 0.0874 0.1223 0.0988
0.1814 0.1023 0.0953 0.1263
0.2419 0.0680 0.0860 0.1320
6.2.3. Approximate Cloud analysis To prove the necessity of the XAI layer, we designed a fourth adversary. The Approximate cloud takes utilitydestroying algorithmic shortcuts to save compute, but it mathematically fakes nothing. It computes a perfectly valid Merkle hash for its bad tree and processes every single row. As Table 6 shows, Layers 1 and 2 completely fail to detect this attack on all three datasets. Layer 3 is the only mechanism that catches the utility degradation, successfully blocking the attack on the Adult and Bank datasets. The attack only succeeds on the Diabetes dataset. This happens precisely because the severe 89/11 class imbalance compresses the SHAP distributions below our detection threshold. This perfectly isolates both the necessity of utility-based verification and its boundary condition. The Approximate and Dumb adversaries share the same blind splitting implementation and random seed (RandomState(99)), producing identical blind trees for a given dataset. The identical per-feature Wasserstein distances in Table 7 follow from this shared seed. Evaluating the Approximate adversary across multiple seeds to characterise the variability of Layer 3 detection is a natural extension of this work. 6.2.4. Per-feature Wasserstein distance analysis Table 7 reports per-feature Wasserstein distances for the top-3 SHAP features across all 12 scenarios. Note that the Approximate adversary produces identical SHAP distributions to the Dumb adversary because both use the same blindsplitting function and random seed, as discussed above. Values exceeding 𝜀 = 0.45 are marked with †. Two observations can be made. Firstly, Bank Marketing’s duration attribute is most affected because its WD value changes most significantly from 0.4185 (honest) to 1.2618 (dumb), i.e., by a factor of 3. This is in line with duration being the most important predictor for term deposit :
Table 8 Client-side verification time vs. dataset size. The 𝑂(1) XAI overhead (approximately 0.5 s) dominates at small 𝑛. The 𝑂(𝑛∕𝑘) hash component grows linearly but remains a minor fraction of total time even at 𝑛 = 106 . Dataset Size (𝑛) Verification Time (s) 10,000 0.503 50,000 0.515 100,000 0.528 250,000 0.590 500,000 0.644 1,000,000 0.788
subscription in the original data. Secondly, WD values for Diabetes are packed tightly between 0.07 and 0.24 across all adversaries, which reflects the weak predictive structure arising from the dataset’s 89/11 class imbalance.
6.3. Scalability and Client Overhead The verification time on the client side when the size of the data set varies from 10,000 to 1,000,000 is shown in Table 8 and Figure 4 plots this trajectory, showing how the flat XAI cost dominates early on before the linear hash check takes over. The XAI fingerprinting layer has a constant time cost of approximately 0.5 seconds to train the model on 2,000 rows and extract SHAP. The cost of the hash verification component varies linearly with 𝑛∕𝑘, taking 0.003 seconds when 𝑛 = 10,000 and rising to 0.288 seconds when 𝑛 = 1,000,000. The hash verification component of the scalability experiment was estimated by running SHA-256 operations proportional to the number of tree nodes (𝑛∕𝑘) at each dataset size, measured on a Kaggle notebook instance using CPU. The XAI overhead (approximately 0.5 s) was measured from actual SHAP computation on real data, not simulated. The hash component dominates only at 𝑛 > 500,000; below this, the measured XAI cost accounts for over 85% of total time. Because SHA-256 throughput is well-characterised and architecture-independent (approximately 106 operations per second on commodity hardware), extrapolating hash cost via a counting loop is a standard benchmarking practice in systems security literature. The primary source of uncertainty is not the hash throughput but the memory allocation and tree traversal overhead at scale, which we estimate adds at most 20% to the hash-only time based on the ratio observed in our 8,000-row end-to-end runs. An independent verification cost benchmark measuring all four components (SHA-256 hashing of canonical node strings, real XGBoost/SHAP extraction, sentinel presence lookup, and twin consistency lookup) confirmed these estimates: 0.754 s at 𝑛 = 106 , consistent with Table 8. This confirms that the verification cost is not 𝑂(log 𝑛) (which would be the case for a single Merkle proof). VeriXAnon performs full tree re-verification at 𝑂(𝑛∕𝑘), but even this linear cost is dominated by the constant XAI overhead for datasets up to 106 rows.
Page 15 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
Figure 4: Client verification time vs. dataset size. The 𝑂(1) XAI overhead dominates at small 𝑛; the 𝑂(𝑛∕𝑘) hash verification scales linearly but remains sub-second at 𝑛 = 106 .
The experiments above measure client-side verification cost only. The cloud-side overhead of VeriX-Anon (building the authenticated tree with Merkle hashing and canonical formatting) was not benchmarked separately. In our Kagglebased evaluation, the total cloud processing time for 8,000 rows at 𝑘 = 5 ranged from 0.3 to 0.9 seconds across datasets, including tree construction, generalisation, and hash computation. The Merkle hashing component (bottom-up SHA256 over all nodes) adds approximately 5–10% to the tree construction time, as each node requires a single hash operation on a short canonical string. For production deployments at scale, the cloud-side overhead of Merkle authentication is expected to remain a small fraction of the total anonymisation cost, since the dominant expense is the variancereduction computation at each split, not the hashing. A formal cloud-side scalability study is left to future work.
Communication overhead. The VeriX-Anon protocol requires the cloud to return three objects: the anonymised dataset ∗ , the leaf assignment mapping , and the root hash 𝐻root . The anonymised dataset is identical in size to the outsourced dataset (the client needs it regardless of verification). The leaf mapping adds one TrackerID-to-leafID pair per record: at 64 bytes per TrackerID and 4 bytes per leaf ID, this is 68 bytes × 𝑁 rows. For 𝑁 = 100,000, the mapping is approximately 6.8 MB; for 𝑁 = 1,000,000, approximately 68 MB. The root hash is a single 256-bit value (32 bytes). The tree structure (split features and values for all internal nodes) adds approximately 100 bytes per node
:
× 𝑛∕𝑘 nodes, yielding 20 MB at 𝑛 = 106 , 𝑘 = 5. In total, the verification-specific overhead (mapping + tree + hash) is approximately 88 MB for a million-row dataset, which transfers in under 10 seconds on a 100 Mbps connection. This is modest relative to the dataset itself, which at 16 features × 8 bytes × 106 rows is approximately 128 MB.
6.4. Utility Preservation and XAI Fingerprinting Experiment 3 evaluates the utility-privacy trade-off using an 11-point 𝑘-sweep (𝑘 ∈ {2, 3, 4, 5, 7, 10, 12, 15, 20, 25, 30}) on the Adult Income dataset. The top-3 SHAP features for the 5,000-row subsample used in this experiment are age, marital-status, and relationship. These differ from the 8,000-row Experiment 1 rankings (age, relationship, education-num) because SHAP feature importance is sensitive to subsample composition. Both rankings are internally consistent within their respective experiments. For each 𝑘, both Target-Driven (honest) and Blind (dumb) anonymization are applied to the same outsourced dataset. F1-scores are computed on a held-out 20% stratified test set (not on training data) to measure generalisation rather than memorisation. Because the 𝜀 threshold was calibrated on the Experiment 3 feature set (age, marital-status, relationship), its applicability to the Experiment 1 feature set (age, relationship, education-num) relies on the assumption that the honest WD range is similar across feature sets at the same 𝑘-value. The per-feature WDs in Table 7 confirm that the Experiment 1 features remain below 𝜀 at 𝑘 = 5, validating this assumption for the default operating point. The full results can be seen in Table 9. Figure 5 charts this trade-off. Target-Driven Page 16 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
Figure 5: Utility-privacy trade-off across 11 𝑘-values. Left axis: F1-score (80/20 test set). Right axis: SHAP Wasserstein Distance. Dashed grey line: 𝜀 = 0.45.
Table 9 Utility-privacy trade-off across 11 𝑘-values (Adult Income, 80/20 test set). TD = Target-Driven (honest cloud). Blind = random-feature splitting (dumb cloud). F1 Gap = TD F1 − Blind F1. WD Gap = Blind WD − TD WD. Target-Driven F1 exceeds Blind at all 11 values. 𝑘 2 3 4 5 7 10 12 15 20 25 30
TD F1 0.6383 0.6597 0.6263 0.6420 0.5978 0.5472 0.5407 0.5660 0.5914 0.6085 0.5982
Blind F1 0.5034 0.5092 0.5128 0.4929 0.5139 0.4297 0.4461 0.4044 0.4605 0.2370 0.3750
F1 Gap +0.1349 +0.1505 +0.1135 +0.1491 +0.0839 +0.1175 +0.0946 +0.1616 +0.1309 +0.3715 +0.2232
TD WD 0.1718 0.2221 0.2928 0.2962 0.2164 0.2784 0.4299 0.3453 0.2039 0.2347 0.2974
Blind WD 0.3444 0.2772 0.2699 0.3686 0.3670 0.3778 0.3707 0.4173 0.4827 0.5250 0.4151
WD Gap +0.1726 +0.0551 −0.0229 +0.0724 +0.1506 +0.0994 −0.0592 +0.0720 +0.2788 +0.2903 +0.1177
has a higher F1 than Blind at every value of 𝑘. The average increase in F1 is +0.1574. The largest increase occurs when 𝑘 = 25: Target-Driven has F1=0.6085, Blind has F1=0.2370. The relative improvement is 156.9%. The WD columns show that there is a subtle point to be noted regarding the calibration of 𝜀. When 𝑘 = 12, the honest Target-Driven WD achieves 0.4299, which is only 0.0201 below 𝜀 = 0.45. When 𝑘 = 4, however, the WD gap is negative at -0.0229, which means that the Blind cloud has achieved a smaller WD value than that achieved by the honest cloud at this value of 𝑘. This shows that the discriminative ability of the XAI layer is not guaranteed for
:
all values of 𝑘, as discussed above. Section VII-C addresses this issue. From a practical point of view, 𝑘 = 3 with an honest WD of 0.2221 and 𝑘 = 20 with an honest WD of 0.2039 provide the largest difference between honest and adversarial WD, making them the safest choices for 𝜀 = 0.45. The default 𝑘 = 5 with an average WD of 0.2962, while not as good as 𝑘 = 3, has a per-feature relationship WD of 0.4436, which is just 0.0064 below 𝜀.
6.5. Statistical Significance Analysis We perform paired statistical tests on the 11 (𝑘, F1) and 11 (𝑘, WD) data points in Table 9. Since we are working with a small sample size 𝑛 = 11 and we do not know whether the data are normally distributed, we use the Wilcoxon SignedRank test instead of a paired 𝑡-test.
6.5.1. Wilcoxon signed-rank tests For the F1 comparison (Target-Driven vs. Blind): 𝑊 = 0.0,
𝑝 = 0.000977
(17)
The test statistic 𝑊 = 0.0 indicates that Target-Driven F1 exceeded Blind F1 in every single paired comparison. The 𝑝-value of 0.000977 is the minimum achievable for 𝑛 = 11 with the Wilcoxon test, confirming the result is significant well beyond 𝛼 = 0.01. For the Wasserstein distance comparison (Target-Driven vs. Blind): Page 17 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization Table 10 Statistical significance summary for the 11-point 𝑘-sweep (Target-Driven vs. Blind anonymization, Adult Income dataset). Both metrics show significant differences with large effect sizes. Metric F1-Score Wasserstein Dist.
Wilcoxon 𝑊 0.0 4.0
𝑊 = 4.0,
𝑝-value 0.000977 0.006836
Cohen’s 𝑑 1.9618 (large) −1.0228 (large)
Mean Gap [95% CI] 0.1574 [0.1203, 0.2079] 0.1115 [0.0534, 0.1737]
𝑝 = 0.006836
(18)
The non-zero 𝑊 reflects the two 𝑘-values (𝑘 = 4 and 𝑘 = 12) where the WD gap was negative. The test remains significant at 𝛼 = 0.01.
6.5.2. Cohen’s d effect sizes 𝑑F1 = 1.9618
(large),
𝑑WD = −1.0228
(large) (19)
Both effect sizes exceed |𝑑| = 0.8, the conventional threshold for a large effect (Cohen, 1988). The F1 effect (𝑑 = 1.96) is nearly twice the large-effect threshold, indicating that the utility advantage of Target-Driven over Blind anonymization is not just statistically significant but practically substantial.
6.5.3. Bootstrap confidence intervals We compute 10,000-resample bootstrap 95% confidence intervals for the mean F1 gap and WD gap: Mean F1 gap = 0.1574,
95% CI [0.1203, 0.2079] (20)
Mean WD gap = 0.1115,
95% CI [0.0534, 0.1737] (21)
Both intervals exclude zero, confirming that the observed differences are not artefacts of sampling variation. The F1 confidence interval is relatively tight (width 0.0876). The WD interval is wider (width 0.1203) because Wasserstein distances vary more across 𝑘-values.
6.5.4. Summary Table 10 consolidates the results. The tests confirm that Target-Driven anonymization preserves significantly more predictive utility than blind splitting. Both metrics clear the Wilcoxon signed-rank test with 𝑝-values well under 0.01. Statistical significance only tells half the story, though. The effect sizes show the actual practical impact. Cohen’s 𝑑 reaches 1.96 for the F1 score and −1.02 for the Wasserstein distance. Since the standard threshold for a large effect is just 0.8, the utility advantage of the Target-Driven approach is substantial. The bootstrap confidence intervals also exclude zero, proving these utility gains hold steady across the entire 𝑘-sweep.
:
7. Discussion and Limitations The experimental results in Section 6 demonstrate correct detection in 11 of 12 scenarios, but the per-layer analysis reveals important failure modes, boundary conditions, and design trade-offs that merit transparent discussion. The single evasion, the Approximate adversary on the Diabetes dataset, isolates the XAI layer’s sensitivity to severe class imbalance and is discussed below. This section addresses six issues: the Diabetes XAI anomaly (now including the Approximate adversary), sentinel density under class imbalance, epsilon sensitivity, a complexity clarification, scope limitations, and the absence of a direct baseline comparison.
7.1. XAI Limitations Under Severe Class Imbalance The Diabetes 130-US dataset exhibits a 89/11 class split (readmitted within 30 days vs. not). This severe imbalance produces weak feature-target SHAP structure: the honest cloud produces an average Wasserstein distance of only 0.0988, while both the Dumb and Approximate adversaries produce 0.1320 (identical values, since both use the same blind splitting logic). All values fall well below 𝜀 = 0.45, so both adversaries escape Layer 3 entirely on this dataset. No individual per-feature WD exceeds 𝜀 either (the highest is number_diagnoses at 0.2419). Layer 1 (ADT Hash) catches the Dumb adversary on Diabetes regardless, because the fabricated root hash never matches the client’s re-computation. The multi-layered design works as intended in that case: Layer 3 fails, but Layer 1 compensates. The Approximate adversary on Diabetes is a different story. Because the Approximate cloud computes a valid hash and retains all records, Layers 1 and 2 pass. Layer 3 also passes because the WD values stay below 𝜀. This makes Diabetes + Approximate the single scenario in which VeriX-Anon fails to detect a deviation, yielding 11/12 overall accuracy. The result demonstrates that XAI fingerprinting is most effective on datasets where the target variable has strong predictive relationships with the quasiidentifiers. When class imbalance compresses SHAP distributions into a narrow range, the Wasserstein distance between honest and adversarial processing becomes too small to exceed 𝜀. This is not a missing feature but a fundamental boundary condition of SHAP-based utility verification: when the target variable carries little predictive signal (because one class dominates), all models trained on the data produce near-uniform SHAP distributions regardless of whether the anonymization was honest or adversarial. No threshold-based method can separate two distributions that are both compressed into the same narrow range. Per-feature adaptive thresholding, as discussed in Section 7.3, is the most promising mitigation for production deployment.
7.2. Sentinel Density and Class Imbalance Boundary Sentinels are generated from records with RF prediction probability 𝑃 ∈ [0.45, 0.55]. The number of such records depends on the class distribution: balanced datasets produce more boundary candidates than imbalanced ones. Page 18 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
In our experiments, Adult Income (76/24 split) yielded 501 boundary candidates, Bank Marketing (88/12 split) yielded only 13, and Diabetes (89/11 split) yielded only 4. This asymmetry has a direct effect on detection power. When the Lazy adversary drops 5% of records from the Bank Marketing outsourced dataset (420 out of 8,413), the probability that all 13 sentinels survive is: )420 ( 13 ≈ 0.52 (22) 𝑃evade = 1 − 8,413 A 52% evasion probability is unacceptable for a standalone detection mechanism. In our experiments, sentinels caught Adult Income (157/160 present, 3 missing) and Diabetes (3/4 present, 1 missing). Bank Marketing sentinels all survived the drop (13/13 present). Layer 2b (Twins) compensated in every case: 400 twins per dataset produced clear detection signals (347/400 to 359/400 consistent, with 41 to 53 missing). This confirms the design rationale for including twins alongside sentinels, but it also exposes the sentinel layer as the weakest link when class imbalance is severe. Two mitigations are possible. First, adaptive injection: if the boundary region yields fewer than a minimum threshold of candidates (e.g., 50), the client could widen the probability band (e.g., 𝑃 ∈ [0.40, 0.60]) or oversample existing boundary points with stronger perturbation. Second, density-aware sentinel allocation: instead of a fixed 2% ratio, allocate sentinels proportionally to the boundary density so that every dataset reaches a target evasion probability (e.g., 𝑃evade < 0.01). Both strategies are left to future work.
7.3. Epsilon Sensitivity and Threshold Calibration The Wasserstein threshold 𝜀 = 0.45 was set using the calibration protocol described in Section 5.3.3: the client computes honest SHAP Wasserstein distances on a small local sample and sets 𝜀 above the observed maximum. The Dumb adversary’s average WD on Adult Income is 0.3293, which falls below 𝜀 = 0.45 but this does not represent an evasion. VeriX-Anon uses an OR-rule (Equation 11): the system flags a violation if any single top-3 feature exceeds 𝜀, not the average. The Dumb adversary was caught because the age feature spiked to WD = 0.5120 (well above 𝜀), even though relationship (0.2098) and education-num (0.2660) remained below. At the contracted 𝑘 = 5, the threshold 𝜀 = 0.45 sits between the maximum honest per-feature WD (0.4436 for relationship) and the minimum triggering adversarial perfeature WD (0.5120 for age under the Dumb adversary). This gap of 0.0684 is narrow. However, the 𝑘-sweep reveals that 𝜀 = 0.45 is not globally safe: at 𝑘 = 10, 12, and 15, the honest per-feature WD for marital-status exceeds 𝜀 (0.4958, 0.5744, and 0.5586 respectively), producing false positives under the OR-rule. This confirms that 𝜀 must be calibrated per 𝑘-value rather than set globally, and motivates the perfeature adaptive thresholding proposed below. Three further observations expose the sensitivity of this parameter: 1. At 𝑘 = 12, the honest Target-Driven average WD is 0.4299, but the per-feature WD for marital-status :
reaches 0.5744, which already exceeds 𝜀 = 0.45 and produces a false positive under the OR-rule. Similarly, 𝑘 = 10 (0.4958) and 𝑘 = 15 (0.5586) also exceed 𝜀 on this feature. A global 𝜀 is therefore insufficient; per-𝑘 calibration is necessary. 2. At 𝑘 = 4, the WD gap is negative (−0.0229): the Blind adversary produced a lower WD than the honest cloud. This occurs because random splitting can, by chance, preserve feature distributions at certain 𝑘-values. 3. At the default 𝑘 = 5, the per-feature relationship WD is 0.4436, sitting only 0.0064 below 𝜀 for the honest cloud. A single additional perturbation could push this into false-positive territory. It is important to clarify the role of Layer 3 within the framework. Unlike Layers 1 and 2, which provide deterministic or probabilistic guarantees rooted in cryptographic hash properties and combinatorial trap placement, Layer 3 operates as an empirically calibrated utility verification mechanism. The value of the XAI layer lies in catching adversaries that preserve structural correctness (passing Layer 1) and data completeness (passing Layer 2) while destroying predictive utility: a class of attack that the other two layers cannot detect by design. Deriving a dataset-agnostic threshold from the properties of the anonymisation algorithm (e.g., the expected variance reduction under honest splitting) is a promising direction for future work. These observations only apply to Layer 3. Layers 1 and 2, being threshold-free, do not depend on the value of the 𝜀calibration. The system’s detection rate (11/12) does not rely on Layer 3 being perfectly calibrated for most scenarios, as it has independent coverage from the other layers. The single exception is the Approximate adversary, which bypasses Layers 1 and 2 entirely and depends on Layer 3 alone for detection. For future work, we propose two approaches. Firstly, perfeature thresholding: rather than using a global value of 𝜀, feature-wise thresholds using the honest WD distribution across a 𝑘-sweep can be estimated. Features with high honest WD by design, such as duration in Bank Marketing, should have a higher threshold. Secondly, ROC-based thresholding can be carried out by running the 𝑘-sweep on the XAI layer under both honest and adversarial conditions and then selecting the threshold 𝜀 at which the point on the ROC curve maximizes the Youden index 𝐽 = sensitivity+specificity−1.
7.4. Computational Complexity Clarification Someone familiar with Merkle trees might assume that VeriX-Anon’s hash verification runs in 𝑂(log 𝑛), since a standard single-element Merkle inclusion proof traverses only a root-to-leaf path. This is not the case. VeriX-Anon performs full re-verification: the client recomputes the hash of every node in the tree (all leaves and all internal nodes) and compares the resulting root hash against the cloud’s reported value. The number of leaves is at most 𝑛∕(2𝑘), and the total number of nodes is 𝑂(𝑛∕𝑘). For 𝑛 = 1,000,000 and 𝑘 = 5, this means visiting up to 100,000 nodes, not log2 (1,000,000) ≈ 20. Page 19 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization
Full re-verification is necessary because VeriX-Anon verifies the entire tree structure, not just the membership of a single record. A single-element proof would confirm that one record is in the tree, but it would not detect structural changes elsewhere (e.g., a different splitting criterion applied to a subtree that does not contain the queried record). Despite the 𝑂(𝑛∕𝑘) cost, verification remains practical. At 𝑛 = 106 , the hash component takes 0.288 s, and total verification (including XAI) is 0.788 s. The linear cost is acceptable because the constant factor (one SHA-256 hash per node) is small.
7.5. Scope and Generalisability Limitations VeriX-Anon was designed and evaluated under a specific set of assumptions: 1. Binary classification only. The Target-Driven tree uses variance reduction on a binary target. Multiclass targets would require a different splitting criterion (e.g., Gini impurity) and would produce different SHAP distribution characteristics. The XAI layer’s threshold calibration would need to be re-validated for each target cardinality. 2. Static data only. The framework assumes the dataset is fixed at outsourcing time. Streaming or appendonly datasets would require incremental tree updates and incremental hash maintenance, neither of which is currently supported. 3. Decision tree partitioning only. The ADT authentication mechanism is specific to tree-based anonymization. Other anonymization strategies (e.g., clusteringbased approaches like MDAV, or graph-based methods for social network data) would require different authenticated data structures. 4. Three datasets, four cloud profiles (one honest baseline plus three adversary profiles). The experimental evaluation covers 12 scenarios (3 datasets × 4 cloud profiles, including the honest baseline). These span three domains (societal, financial, medical) and three attack strategies (data dropping, algorithm substitution with fake hash, and algorithm substitution with valid hash). The adversary space is still not exhaustive. Section 4.2.5 discusses the Informed Attacker (4 ) as a stronger adversary that is analysed theoretically but not yet evaluated empirically. In particular, an adversary that uses a target-aware but approximate algorithm (e.g., a shallower tree or a greedy split that skips expensive features) would produce a valid hash, retain all records, and potentially preserve SHAP distributions within 𝜀. Evaluating this class of adversary is a natural extension of the current work. 5. Subsample evaluation. Experiment 1 uses 8,000-row subsamples and Experiment 3 uses 5,000 rows, not the full dataset sizes. An end-to-end benchmark on synthetic datasets (Section 6.3) confirmed that clientside verification scales linearly to 𝑛 = 106 rows, but :
the detection accuracy experiments (Experiment 1) have not been repeated at full dataset scale. 6. Single-dataset utility analysis. Experiment 3 (the 11point 𝑘-sweep) was conducted only on Adult Income. Running the same analysis on Bank Marketing and Diabetes would strengthen the generalisability claim for the utility-privacy trade-off results and is planned for the extended version of this work.
7.6. Absence of Direct Baseline Comparison No existing published framework simultaneously performs deterministic, probabilistic, and utility-based verification of outsourced data anonymization. This makes a direct apples-to-apples comparison against a competing system impossible. The closest baselines are: 1. Trap-only verification (canary records in database auditing). These embed known records into the outsourced data and check whether they survive processing. This is analogous to VeriX-Anon’s Layer 2 in isolation. Trap-only methods lack structural verification (no authenticated tree, no hash comparison) and utility verification (no XAI fingerprinting). As demonstrated in Section 6.2, Layer 2 alone misses the Dumb adversary on all three datasets. 2. Full re-execution. The client re-runs the entire TargetDriven anonymization locally. This achieves perfect verification (every aspect of the output can be compared bit-for-bit) but requires 𝑂(𝑛 log 𝑛) computation to build the decision tree, defeating the purpose of outsourcing. The client must also possess the computational resources, memory, and software stack to execute the full anonymization algorithm. VeriXAnon’s verification cost is 𝑂(𝑛∕𝑘) for hash traversal plus 𝑂(1) for XAI, which is strictly cheaper and does not require the client to build a tree. Table 6 provides a stark quantitative comparison. A traponly approach (using Layers 2a and 2b in isolation) catches the Lazy adversary via twins. However, it completely misses the Dumb and Approximate adversaries because they retain all records. This yields a miserable 6/12 (50%) detection rate. A hash-only approach (Layer 1) catches the Dumb adversary but misses the Lazy attacker (valid hash on reduced data) and the Approximate attacker (valid hash on a bad tree). This also yields 6/12 (50%). A sampling-based audit that checks a random 10% of records detects structural changes probabilistically, but it cannot verify utility and forces the client to re-anonymise the sample locally. VeriX-Anon combines all three mechanisms to achieve 11/12 (91.6%) detection accuracy without forcing the client to build a single tree. Table 11 summarises these detection rates. VeriX-Anon occupies the space between these two extremes: it provides stronger guarantees than trap-only methods (adding deterministic hash verification and utility-based XAI checks) while remaining orders of magnitude cheaper than full re-execution. As the field of verifiable outsourced Page 20 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization Table 11 Detection accuracy of isolated verification approaches vs. VeriX-Anon across 12 scenarios (3 datasets × 4 cloud profiles). Approach Hash-only (Layer 1 alone) Trap-only (Layers 2a+2b alone) XAI-only (Layer 3 alone) Full re-execution VeriX-Anon (Proposed)
Correct 6/12 6/12 8/12 12/12 11/12
Accuracy 50.0% 50.0% 66.7% 100% 91.7%
breach (Capita plc) cost GBP 14 million (Information Commissioner’s Office (2025)), the verification overhead is negligible relative to the compliance risk it mitigates. In practice, VeriX-Anon could be integrated into existing Service Level Agreements as a contractual verification clause, where the cloud provider is required to return the tree structure and Merkle root hash alongside the anonymized data, and the client runs the four-layer audit before accepting delivery.
8. CONCLUSION anonymization matures, future work should benchmark VeriX-Anon against emerging systems that address the same verification problem.
7.7. Deployment Considerations Several practical considerations arise when deploying VeriX-Anon in a real cloud environment. First, the client must retain sufficient local resources to train a Random Forest on 10% of the data and an XGBoost model on 2,000 rows. On commodity hardware (e.g., a laptop with 8 GB RAM), both operations complete in under 5 seconds for the dataset sizes tested. For organisations with extremely limited compute (e.g., embedded devices), these operations could be offloaded to a trusted local server. Second, the protocol assumes the cloud returns the full anonymised dataset, the leaf assignment mapping, and the Merkle root hash. The verification-specific communication overhead is analysed in Section 6.3 and totals approximately 88 MB for a million-row dataset, modest relative to the dataset itself. Third, returning the tree structure (split features, split values, leaf bounds) to the client does not introduce a privacy risk beyond what the anonymised dataset already reveals. The tree encodes the generalisation logic applied to the data; the client, as the data owner, is entitled to this information and needs it to verify correctness. In a contractual cloud setting, the tree structure would be part of the Service Level Agreement (SLA) deliverables. Finally, integration with real cloud APIs (e.g., AWS Lambda, Azure Functions) would require packaging the ADT construction and Merkle hashing as a cloud-side module and the verification engine as a client-side library. The current Kaggle notebook implementation is a research prototype; production hardening (error handling, streaming hash computation, API wrappers) is engineering work rather than a research contribution and is left to future deployment. From a managerial perspective, VeriX-Anon changes the cost-benefit calculus of outsourced anonymization auditing. A Data Protection Officer at a hospital or financial institution currently has two options: trust the cloud provider’s output without verification, or re-execute the entire anonymization locally (defeating the purpose of outsourcing). VeriX-Anon introduces a third option: spend under one second of local compute to audit the cloud’s output across all three verification dimensions. Given that GDPR fines for inadequate anonymization have exceeded EUR 5.88 billion in aggregate since 2018 (DLA Piper (2025)) and that a single outsourcing :
VeriX-Anon demonstrates that outsourced k-anonymization can be verified without re-executing the anonymization algorithm, using an integrated intelligent auditing system that combines cryptographic, probabilistic, and AI-driven verification. The multi-layered design (Merkle hashing, probabilistic traps via Boundary Sentinels and Twins, SHAP fingerprinting) achieves what no single mechanism can: correct detection in 11 of 12 scenarios spanning three datasets and four cloud profiles (three adversary profiles plus the honest baseline). The Swiss Cheese principle holds in 11 cases; the single evasion (Approximate adversary on the severely imbalanced Diabetes dataset) isolates the XAI layer’s sensitivity to class imbalance rather than a systemic design flaw. The practical implications extend beyond the specific threat models tested here. Any organisation that outsources privacy-sensitive data transformations faces the same verification gap: the inability to confirm, after the fact, that the contracted algorithm was faithfully executed. VeriXAnon provides a concrete, sub-second audit mechanism that requires only a fraction of the computational resources needed for re-execution (𝑂(𝑛∕𝑘) + 𝑂(1) vs. 𝑂(𝑛 log 𝑛)). In other words, for a dataset of one million entries at 𝑘 = 5, this equates to 0.788 s of client-side computation versus rebuilding the decision tree from scratch. The limitations point to specific next steps. The XAI layer’s failure on the Diabetes 89/11 split, the one scenario VeriX-Anon missed entirely, makes the case for per-feature adaptive thresholds. The low sentinel counts on imbalanced datasets (4 for Diabetes, 13 for Bank Marketing, with evasion probability up to 0.52) call for boundary-aware injection strategies that widen the probability band when boundary candidates are scarce. Extending the framework to multiclass targets, regression tasks, and streaming data would make it more applicable to the full range of outsourced analytics tasks. Finally, testing the framework against a realworld cloud provider under contractually agreed upon SLA constraints is the ultimate validation.
A. CONFIGURATION PARAMETERS Table 12 lists all configuration parameters used throughout the experimental evaluation. These values are fixed across all datasets and adversary profiles unless stated otherwise in the main text.
Page 21 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization Table 12 Complete configuration parameters for VeriX-Anon. Parameter 𝑘-anonymity parameter Wasserstein threshold 𝜀 SHAP subsample size Sentinel injection ratio Twin injection ratio Sentinel boundary band Sentinel perturbation scale Random Forest (sentinel gen.) XGBoost (XAI fingerprint) ADT max tree depth ADT min leaf size Bootstrap resamples (CIs) Lazy adversary drop fraction 𝛿 𝑘-sweep values (Experiment 3) Random seed
Value 5 0.45 2,000 rows 2% of 𝑁 5% of 𝑁 𝑃 ∈ [0.45, 0.55] 0.05 ⋅ 𝜎𝑗 per column 50 trees, max depth 5 100 estimators, max depth 6, LR 0.1 50 2𝑘 (= 10 at 𝑘 = 5) 10,000 0.05 {2, 3, 4, 5, 7, 10, 12, 15, 20, 25, 30} 42
Table 13 Bank Marketing (OpenML id=1461) feature name mapping. Top-3 SHAP features marked with ⋆. OpenML Code V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V13 V14 V15 V16 Class
UCI Name age ⋆ job marital education default balance ⋆ housing loan contact day month duration ⋆ campaign pdays previous poutcome y (subscribed)
Type numeric categorical categorical categorical binary numeric binary binary categorical numeric categorical numeric numeric numeric numeric categorical binary target
B. BANK MARKETING COLUMN MAPPING OpenML dataset (ID 1461) encodes Bank Marketing features as V1–V16 instead of the original UCI names Moro et al. (2011). Table 13 shows the mapping used in this paper, with top-3 SHAP features highlighted.
C. REPRODUCIBILITY CHECKSUMS Table 14 reports the first 8 hex characters of the Merkle root hashes produced by the honest and dumb cloud for each dataset at 𝑘 = 5. These values are deterministic given the same input data, random seed, and configuration. They can be reproduced by running the Kaggle notebook, which is available from the corresponding author upon reasonable request.
:
Table 14 Merkle root hash prefixes (first 8 hex characters) for reproducibility verification. The Approximate cloud produces a valid hash distinct from both Honest and Dumb, confirming that Layer 1 cannot distinguish algorithm substitution when the hash is correctly computed. Dataset Honest Dumb Approx. Adult Income 4ede8cde d0592611 ff2b863d Bank Marketing 36ad5073 cd14b532 bb345a1a Diabetes 130-US 35b93103 0a6aa553 9eb529ab
Data Availability Statement The datasets analyzed during the current study are publicly available. The Adult Income dataset is available from OpenML (ID: 1590) at https://www.openml.org/d/1590. The Bank Marketing dataset is available from OpenML (ID: 1461) at https://www.openml.org/d/1461. The Diabetes 130-US Hospitals dataset is available from the UCI Machine Learning Repository at https://archive. ics.uci.edu/dataset/296/diabetes+130-us+hospitals+for+years+ 1999-2008.
The code used in this study is available from the corresponding author upon reasonable request.
CRediT authorship contribution statement Miit Daga: Conceptualization, Methodology, Software, Validation, Formal analysis, Investigation, Writing - Original Draft. Swarna Priya Ramu: Supervision, Writing Original Draft, Writing - Review & Editing, Project administration.
References Barezzani, S., di Vimercati, S.D.C., Foresti, S., Ghirimoldi, V., Samarati, P., 2025. Ta_da: Target-aware data anonymization. IEEE Transactions on Privacy 2, 15–26. Chaudhury, S.S., Sadhukhan, P., Sengupta, K., 2024. Explainable ai using the wasserstein distance. IEEE Access 12, 18087–18102. DLA Piper, 2025. DLA Piper GDPR fines and data breach survey: January 2025. URL: https://www.dlapiper.com/en-us/insights/publications/ 2025/01/dla-piper-gdpr-fines-and-data-breach-survey-january-2025. aggregate GDPR fines since 2018: EUR 5.88 billion; EUR 1.2 billion issued in 2024. Etemad, M., Küpçü, A., 2020. Generic dynamic data outsourcing framework for integrity verification. ACM Computing Surveys (CSUR) 53, 1–32. Friedman, A., Schuster, A., Wolff, R., 2006. k-anonymous decision tree induction, in: European Conference on Principles of Data Mining and Knowledge Discovery, Springer. pp. 151–162. Gennaro, R., Gentry, C., Parno, B., 2010. Non-interactive verifiable computing: Outsourcing computation to untrusted workers, in: Annual Cryptology Conference, Springer. pp. 465–482. IBM Security, 2024. Cost of a Data Breach Report 2024. Technical Report. IBM and Ponemon Institute. URL: https://www.ibm.com/ reports/data-breach. average breach cost USD 4.88M, 10% year-overyear increase; healthcare average USD 9.77M. Information Commissioner’s Office, 2025. ICO fines Capita GBP 14 million for security failings. URL: https://ico.org.uk/. ransomware
Page 22 of 23
VeriX-Anon: A Multi-Layered Framework for Mathematically Verifiable Outsourced Target-Driven Data Anonymization breach exposed 6.6 million records; 325 of over 600 pension fund clients affected. Kesarwani, M., Kaul, A., Braghin, S., Holohan, N., Antonatos, S., 2021. Secure k-anonymization over encrypted databases. arXiv preprint arXiv:2108.04780 . Liu, R., Wang, H., Monreale, A., Pedreschi, D., Giannotti, F., Guo, W., 2012. Audio: An integrity auditing framework of outlier-mining-as-aservice systems, in: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer. pp. 1–18. Lundberg, S.M., Lee, S.I., 2017. A unified approach to interpreting model predictions. Advances in neural information processing systems 30. Merkle, R.C., 1989. A certified digital signature, in: Conference on the Theory and Application of Cryptology, Springer. pp. 218–238. de Montjoye, Y.A., Radaelli, L., Singh, V.K., Pentland, A., 2015. Unique in the shopping mall: On the reidentifiability of credit card metadata. Science 347, 536–539. Moro, S., Laureano, R., Cortez, P., et al., 2011. Using data mining for bank direct marketing: An application of the crisp-dm methodology, in: Proceedings of the European Simulation and Modelling Conference (ESM), pp. 1–5. Mykletun, E., Narasimha, M., Tsudik, G., 2006. Authentication and integrity in outsourced databases. ACM Transactions on Storage (TOS) 2, 107–138. Narayanan, A., Shmatikov, V., 2008. Robust de-anonymization of large sparse datasets, in: 2008 IEEE Symposium on Security and Privacy (SP), IEEE. pp. 111–125. Parno, B., Howell, J., Gentry, C., Raykova, M., 2016. Pinocchio: Nearly practical verifiable computation. Communications of the ACM 59, 103– 112. Research and Markets, 2025. Data center outsourcing: Global strategic business report. URL: https://www.researchandmarkets.com/. global market estimated at USD 127.8 billion in 2024, projected to reach USD 157.1 billion by 2030 at CAGR 3.5%. Sweeney, L., 2002. 𝑘-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10, 557–570. De Capitani di Vimercati, S., Foresti, S., Ghirimoldi, V., Samarati, P., 2024a. Dt-anon: Decision tree target-driven anonymization, in: IFIP Annual Conference on Data and Applications Security and Privacy, Springer. pp. 111–130. De Capitani di Vimercati, S., Foresti, S., Samarati, P., 2024b. Query integrity in smart environments, in: Security and Privacy in Smart Environments. Springer, pp. 25–48. Zheng, Y., Wang, C., Wang, R., Duan, H., Nepal, S., 2022. Optimizing secure decision tree inference outsourcing. IEEE Transactions on Dependable and Secure Computing 20, 3079–3092.
:
Page 23 of 23