As the usage of Artificial Intelligence (AI) for sensitive purposes increases, there is a growing need for privacy-aware explainable AI (XAI) tools. In this paper, we present a privacy-preserving counterfactual explanation algorithm. Our starting point is a decision-support model that is able to operate on vertically partitioned datasets, meaning that each party holds a different subset of datapoint attributes. The goal of a counterfactual algorithm is to find, given an observation, a datapoint from the (virtual) dataset that is closest to the observation but has a different label. Our algorithm fully preserves the privacy of the n datapoints belonging to the different parties by combining the strengths of homomorphic encryption and secret sharing. Through a number of experiments, we demonstrate the added value of combining multiple datasets in a realistic scenario and show that the privacy-preserving solution does not affect the accuracy. We fully implement our solution and demonstrate that it scales as to thousands of datapoints. © 2026 by SCITEPRESS – Science and Technology Publications, Ltd.

Counterfactual explanations are a promising direction of explainable AI in many domains such as healthcare. These explanations produce a counterexample from the dataset that shows, for example, what should change about a patient to reduce their risk of developing diabetes type 2. However, this poses a clear privacy risk when the dataset contains information about people. Recent literature shows that this risk can be mitigated by using k-anonymity to generalise the explanation, such that it is not about a single person. In this paper, we investigate the trade-offs between privacy and explanation quality in the medical domain. Our results show that for around 40% of the explained cases, the real gain in privacy is limited as the generalisation increases while the explanations continue decreasing in quality. These findings suggest that this can be an unsuitable strategy in some situations, as its effectiveness depends on characteristics of the underlying dataset.