Confidential-PROFITT: Confidential PROof of FaIr Training of Trees
Authors: Ali Shahin Shamsabadi
Sierra Calanda Wyllie
Nicholas Franzese
Natalie Dullerud
Sébastien Gambs
Nicolas Papernot
Xiao Wang
Adrian Weller
Venue: ICLR 2023 notable top 5% (2023)
Keywords: Fairness
Audit
Confidentiality
Zero-Knowledge Proof

Abstract: Post hoc auditing of model fairness suffers from potential drawbacks: (1) auditing may be highly sensitive to the test samples chosen; (2) the model and/or its training data may need to be shared with an auditor thereby breaking confidentiality. We address these issues by instead providing a certificate that demonstrates that the learning algorithm itself is fair, and hence, as a consequence, so too is the trained model. We introduce a method to provide a confidential proof of fairness for training, in the context of widely used decision trees, which we term Confidential-PROFITT. We propose novel fair decision tree learning algorithms along with customized zero-knowledge proof protocols to obtain a proof of fairness that can be audited by a third party. Using zero-knowledge proofs enables us to guarantee confidentiality of both the model and its training data. We show empirically that bounding the information gain of each node with respect to the sensitive attributes reduces the unfairness of the final tree. In extensive experiments on the COMPAS, Communities and Crime, Default Credit, and Adult datasets, we demonstrate that a company can use Confidential-PROFITT to certify the fairness of their decision tree to an auditor in less than 2 minutes, thus indicating the applicability of our approach. This is true for both the demographic parity and equalized odds definitions of fairness. Finally, we extend Confidential-PROFITT to apply to ensembles of trees.

Published as a conference paper at ICLR 2023
CONFIENNIAA-PROFITT CONFIDENTIAL PROOF OF FAIR TRAINING OF TREES
Ali Shahin Shamsabadi', Sierra W Nicholas Franzese', Natalie Dullerud
Sébastien Gambs Nicolas
N Papernot "2,3 Xiao Wang"*, Adrian Weller
I The Alan Turing Institute, University of Toronto, 3 Vector Institute, Northwestem University,
5 Université du Québec à Montréal, University of Cambridge
ABSTRACT
Post hoc auditing of model fairness suffers from potential drawbacks: (1) auditing may be highly sensitive to the test samples chosen; (2) the model and/or its training data may need to be shared with an auditor thereby breaking confidentiality. We ad- dress these issues by instead providing a certificate that demonstrates that the learn- ing algorithm itself is fair, and hence, as a consequence, so too is the trained model. We introduce a method to provide a confidential proof of fairness for training, in the context of widely used decision trees, which we term Seffidential-RROFITI We propose novel fair decision tree learning algorithms along with customized zero-knowledge proof protocols obtain a proof of fairness that can be audited by a third party. Using zero-knowledd of both the model and its training data. We show empirically that bounding the information gain of each node with respect to the sensitive attributes reduces the unfairness the final tree. In extensive experiments on the COMPAS, Communi- ties and Crime. Default Credit, and Adult datasets, we demonstrate that a company can use Confidential-PROFITY to certify the fairness of their decision tree an auditor in less than 2 minutes, thus indicating the applicability of our approach. This is true for both the demographic parity and equalized odds definitions of fairness. Finally, we extend ConfidentialPROFIIT to apply to ensembles of trees.
proofs enables us to guarantee confidentiality
INTRODUCTION
The deployment of machine learning models in high-stake decision systems (Waddell 2016 Ben- jamens et al., 2020; Kleinberg et al., 2018) is associated with the risk of unfair decisions towards particular subgroups defined by sensitive attributes (Dwork et al.) (2022). A canonical approach for auditing such deployment to measure the fairness of trained model on reference dataset (Pentyala et al. 2022). In practice, this would be done by external party (i.e., an auditor). Such audits, however, can be difficult to organize and are sensitive to the choice of reference dataset (Fukuchi ct al. 2020). This may lead to form of unhelpful interaction between the company and the auditor, in which the company could deny a model unfair by claiming that the reference dataset does not belong the training distribution used, or the auditor forge reference dataset that could be used to blame the company for unfair predictions. One avenue to address this problem would be for the company to release its training data and the model the auditor who can then verify that fair training algorithm was used by e.g., locally rerunning the training process. However, this approach does not protect the confidentiality of the company's training data.
In this paper, we remediate these issues by introducing confidential proofs of fair training. We highlight that our method does not guarantee fairness. Rather, our approach employs a tunable parameter controlling the resulting degree of fairesss. The certificate we provide proves that our approach was employed, and also includes the specific parameter value used, and the resulting faireess metrics on the training data. We call this approach "faimess- training". or "fair training" for short. Concretely, we design a framework (i.e., Confidential-PROFITY that allows a company to directly prove to the auditor, through the execution of cryptographic protocol, that the learning algorithm used to train the model was fair by design. To achieve this without revealing the company's s
"Contributed Equally

---

Published as a conference paper at ICLR 2023
dataset or model to the auditor, we rely zero knowledge (ZK) proofs (Goldwasser et al. 1985 Goldreich et al.; 1991), which allow a party to prove statements about their private data without revealing it. Our framework is generic in the sense that it allows the company to prove to interested parties (e.g., users in addition to the auditor) the fairness of the model learning process- thus increasing public trust in the model.
We instantiate the confidential proof of fair training in the context of decision trees, which are widely used by companies in sensitive domains such as healthcare (Podgorelec et al., (002) and finance (Ghatasheh] 2014; Güntay et al. 2022), in part due to their performance, in their ability to be leveraged in ensemble methods (e.g.,, random forests), and also, occasionally, due their assumed interpretability (Molnar 2020). We propose a cryptographic protocol that can prove the fair training of decision trees with various common fairness definitions including demographic parity (Calders) et al. 2009) and equalized odds (Hardt et al.) 2016). Fair decision tree learning builds a decision tree iteratively by splitting its dataset according to a criterion capturing the information gain with respect to both the class and sensitive attributes. In particular, our criterion addresses issues of prior fair training algorithms by connecting information gain with respect to the sensitive attribute to demographic parity.
To render the verification more efficient, once it is implemented cryptographically, we propose a co-design involving concepts originating from both machine learning and cryptography. First, we design a K-ffiiendly fair decision tree learning algorithm based on the insight that verifying faimesss is sufficient because the accuracy is of no interest for the auditor. Prior works (Kamiran et al. 2010)) Raff et al. 2018) on fair decision tree learning consider only demographic parity and view the problem as as a joint optimization problem between accuracy and demographic parity. The optimal solution is obtained by searching exhaustively through an enumeration of all possible attributes and split points. However, in 2K, the whole exhaustive search would need to be proven using heavy cryptographic ma- chinery, which is computationally expensive in most settings of interest. To address this, we propose a generalized framework that formulates training as a constrained optimization problem, in which fairness is represented as a constraint and the accuracy is the objective of optimization. As a result, we only need to verify the satisfaction of the constraint in ZK without verifying the accuracy. Second, we propose an efficient ZK protocol that can perform the aforementioned fairness constraint verification efficiently using state-of-the-ee ZK protocols in the RAM model (Franzese et al. 202T). Instead of using a naīve verification approach that requires proving computation long as the training process, we design a fairness verification protocol with complexity sublinear to the training phase.
In summary, we propose novel way of auditing model fairness by proving directly that the training al algorithm itself is fair rather than inspecting the model and its predictions. As a consequence, we do not need reference dataset and both the training data and the model remain confidential, i.e., are not disclosed to the auditor. We highlight the following contributions:
We propose a new ZK-friendly fair decision tree learning algorithm such that its fairness can be verified efficiently without repeating the entire training process. We summarize existing fairness metrics and show that our approach is generally applicable to these metrics.
2. We design and implement a specialized ZK proof protocol to efficiently verify the fairness of the above training algorithm. While prior works exist in secure inference using ZK proofs, to the best of our knowledge are the first to propose secure training using ZK proofs.
3. We implement and evaluate our framework in terms of accuracy, fairness, running time, and scalability using decision trees and random forests trained on a variety of real-world datasets. For example on the Community and Crime dataset, Confidential-PRRC PPOFFTT can provide a certificate in less than 9 seconds that the company employed our fair training algorithm and obtained decision tree. In this example, our fair training algorithm can improve the equalized odds fairness, which is not supported by prior works (Kamiran al.) 2010 Raif et al. 2018), by 50% with negligible effects on the accuracy. In our implementation, Confidential PROFITT provides the same certificate for random forests in 70 seconds.
PROBLEM STATEMENT, BACKGROUND, AND RELATED WORK
Problem statement. Ignoring fairness in the training process may result in models that negatively affect users belonging to specific subgroups with respect to a sensitive attribute such as gender, race or disability (Kamiran & Calders 2009 Raff et al.) 2018). For example, Buolamwini & Gebru (2018) demonstrated that darker-skinned women are the most misclassified demographic group in
2

---

Published as a conference paper at ICLR 2023
commercially-usee facial recognition systems. Similarly, Amazon's 's automated recruiting system displayed a negative bias against hiring women"] Therefore, it is important for companies to demonstrate that their models have been trained with fairness constraints associated with minimizing negative biases. Our objective in this work is to provide a certificate proving that a company employs fair training algorithm with tunable parameter controlling the resulting degree of fairnes This is challenging for several reasons. First, the sharing of data, collected predominantly from users, with the third party might not be permitted due the associated privacy risks (Shokri & Shmatikov 2015). Second, confidentiality issues also arise as companies are usually not willing to disclose their models to protect their intellectual property (Zhang et al., 2018). Thus, the proof of fairness should ensure both the confidentiality of the training data as well as that of the model.
More formally, we consider two parties: prover (i.e., company, with a private training dataset D = (X, Y) in which X and Y denote respectively, the set of dataset attributes and ground-truth labels) and verifier (i.e., auditor). Both the prover and verifier must agree on the dimensions of (X, Y) and the sensitive attribute a, which is one of the columns of X, and fair decision tree training algorithm -(: (in practice the prover is likely to be the entity deciding these parameters as they are also responsible for training the model). For the sake of simplicity, we assume that Y and are binary and we use DT < A(X, Y) to denote the resulting decision tree. Our Confidential PROof of Fair enables the prover to prove the verifier that it has DT
Tree Training model, which is indeed correctly computed as A(X, Y). See Appendix A for a table of our notations.
Fairness. Many fairness metrics have been defined based on different philosophical and moral assumptions (Heidari al., 2019 Narayanan 2018). To show the generalizability of our framework, we consider four common notions of group fairness. Demographic Parity ignores the ground-truth label and ensures the equal probability of predicted positive label across subgroups. In comparison, Equalized Odds ensures that the predicted label is conditionally independent of the sensitive attribute and the ground truth label. Equality Opportunity and Predictive Equality enforce a partial form of equalized odds, suitable in domains in which being included (or not) in the positive class is viewed respectively as a desirable or poor outcome. Hereafter, we give the definitions for the first two metrics, with more details available in Appendix B
Definition 1 (Demographic Parity CCalders et al. 2009 ). A predictor Y satisfies Demographic Parity with respect to the sensitive attribute a if:
Pr 1/a = 0] = Pr = 1/a -]
10,
Definition 2 (Equalized Odds Hardt et al. 2016)). A predictor Y satisfies Equalized Odds with respect to the sensitive attribute a if:
Pr(f = 1 = y.a = 0] = Pr|f = 1|Y = y. a 1] Vy E 10, 13. v0,
Fairness and decision trees. Fair decision tree algorithms are usually either based on greedy optimizers (Kamiran et al. 2010 Loh| 2011) or Mixed-Integee Programming (MIP) solvers (Bennett Aghhees et 2019 Jo et al. (022). The former optimizes
splitting criterion for each node based on the data routed to it while the latter solves a mathematical optimization augmented with fairness constraint. In this paper, we focus greedy-based optimization methods as MIP-based methods are currently only applicable on datasets with at most thousands of inputs and with non-continuous features (Zantedeschi et al.) 202I). One such greedy approach from Kamiran cet al. (2010) defines a fair training algorithm by reformulating the information gain traditionally used for decision tree training to encourage demographic parity fairness. This work was extended to random forests by Raff et al. (2018). Both works manage the accuracy-fairnest trade-off via a novel gain term encouraging discrimination over the class label while discouraging discrimination with respect to the sensitive attribute, leading to both high performance and fairness.
Zero-knowledge proof. We design a Knowlenoee (ZK) proof protocol that lets the prover prove to the verifier that their model is trained using the fair training algorithm without revealing
ama zon 000 wwwp:thtattthhh--iibaaeee
women-
dUSKCN 0K00G
'See Practical considerations in Section 6 for a discussion of how the company can subsequently prove that
the fair-trained mode being deployed.
3

---

Published as a conference paper at ICLR 2023
their data or model, thus preserving confidentialiity Given agreed upon program P. ZK proof protocol II enables a prover to convince a verifier that they possess an input w such that P(w) 1, while revealing additional information about w (Goldwasser et al. 1985 Goldreich et al. 1991). Typically, a ZK proof protocol IT has the following properties:
Completeness - For any input w that P evaluates to 1 in the clear, an honest prover (who behaves correctly) can convince an honest verifier that P(w)
using II.
Soundness - Given an input w that P does not evaluate to 1 in the clear, no malicious prover (who can behave arbitrarily) can falsely convince an honest verifier that P(w) = using IT.
Zero Knowledge - If the prover and verifier execute IT to prove that P(w) = 1, even malicious verifier (who can behave arbitrarily) learns no information about w other than what can be inferred from the fact that P(w)= = 1.
In the context of this paper, we write fairness verification program that takes inputs a decision tree and a dataset and evaluates to if and only if the decision tree is trained using the fair training algorithm -(:-)) on the dataset. We instantiate this ZK proof protocol from a vector-oblivious linear evaluation (Weng et al. (021), with a recent extension to support ZK RAM accession (Franzese et al. 202T). Circuit-based models of computation incur relatively high overhead when the control flow of program depends on the input (Goldreich & Ostrovsky 1996). This limitation often becomes a bottle- neck when writing programs for decision trees (e.g.. when selecting a particular attribute of a sample to test against the threshold in each node). Utilizing a RAM model ZK bypasses much of this overhead, thereby allowing for a succinet and efficient implementation of our fairness verification program.
Cryptographic protocols and decision trees. Prior works (Hamada al. 2021 Abspoel et al. 2021 Adams et al. (021) designed protocols to allow multiple parties, each with a private dataset, to jointly train a decision tree. These protocols work a different setting compared to ours, where all private inputs come from the company proving the correctness of private computation. Other works (Zhang) et al. 2020a) developed ZK proofs for decision trees at inference but not at training time.
3
CONFIDENTIALPROFIIT
We propose Confidential-PROFTYY to confidentially certify the fair training of a decision tree. Confidential-PROO PROFITT consists of four main steps (see also the block diagram Appendix C
0. Local training:
The prover locally trains a decision tree on their private training data using our proposed fair decision tree learning algorithm. The algorithm is designed to be both i) crypto- friendly and efficient in ZK via a constraint optimization problem that maximizes the accuracy gain while the constraining the unfairness gain to some threshold; and ii) generic in supporting many fairness metrics (described in Section 2 by defining information gain with respect to each fairness metric.
1. Data and model commitment: The prover commits to the training data and the decision tree trained on this data. These commitments are binding and hiding, meaning that the prover cannot change the content being committed without the verifier's 's consent and that the commitment does not reveal anything about the underlying content (Katz& & Lindell| 2007).
2. Proving counter update in ZK: The prover locally computes and commits to the path each data point takes through the trained decision tree. The prover proves in ZK that the committed paths are correct by comparing the values of each data point to the splitting values in the tree. Then for each value of the sensitive attribute a, the prover counts the number of data points with value a that pass through each node, and proves that these counts are valid.
3. Prove fairness constraint in ZK: The prover computes fairness-related information gain of each node using their corresponding committed counters and proves to the verifier that this is below the desired threshold.
Next, we describe our fair decision tree learning algorithm and our ZK protocol in detail.
3.1 FAIR DECISION TREE LEARNING ALGORITHM
In this section, we propose a novel training algorithm to leam fair decision trees. The decision tree is learned by recursively partitioning the training dataset (Breiman et al., 2017) (see Appendix D for a detailed description of tree training). Splitting by the value, val, of the attribute, attr, partitions the
4

---

Published as a conference paper at ICLR 2023
Algorithm 1: Finding the best split for each node using our fair learning algorithm.
Input: Dutasel X jith node DT ij.. Sensitive altribule Threshold unlaimess based information gain Ginitstime (-). Output: Best split
Threshold_sttie aatrraatttttt_aaat
Initialize gains for each value each attribute b Make parent node
2: Parent = X
E Attributes
4: for E X do
val = selatrr]
Set split threshold value per datapoiat {a X|=[attr] 2 val]
Child; {a X [a/attrr] < val), Childa
Make ohl ldren
7:
Gain Guaaaa (Parent)
(hilsy
Ginissema (Child,)
Gain wrt label
8: Gaifuaaiine = Ginhedaamss (Parent) Ei
JChid,
[Pacn]] Giniiadamas (Childz)
Gain NeL sensitive attribute
if Gainustumzz S then
10: Threshold artribute gainsappendiattr, val, (Gainscanayy Gaimaatrraa }
P Record fair splits
1I:
return attrr, DT val, DT()) m8Xcaar/caaee Threshold_attriurr_ggee attribute__ainn
b Best split
dataset at the parent node into two children nodes, Parent {Child], Child2), such that:
Child: = [a E Parent]z[[attr] < val], Childz = {ar E Parent]x[attr] 2 val].
In general, the information gain of each split, Gain(Split), is the amount of information improved in the children nodes with respect to their parent node:
Childs] Gini(Childs),
Gain(Split) = Gini
PParent
in which Gini quantifies the impurity of each node. We introduce different variants of Gini: for accuracy-ber based information (GiniAccuraey) and for unfairness-basee information (Giniunfaimess) to capture the effect of each split both accuracy and fairness.
We define Giniaccuracy with respect to the class label (Breiman et al. Ginipe with respect the sensitive attribute a (Raff et al., 2018) as:
2017) and demographic parity
10!
X IXT
[u|
[x
[X]
GiniAccuracy (X)
Ginipp(X)
TCT
which X and X, are training points with ground-truth label e and sensitive attribute 8, respectively.
Definition (Equalized Odds-aware Information Gain). Given a prospective split over an attribute, we introduce the information gain with respect to the sensitive attribute conditioned on a class variable that we call equalized odds-aware information gain. The information gained over the split follows Equation 2 in which the equalized odds Gini index, Ginipoats (X), (X), is measured with respect to the sensitive atriibute conditioned on class:
X
| X
Ginignaee (X)
Gint Endi (X)
+
Gini gudts (X);
>
1x+1 X
|x-1
Gimi (X)
Gini (X)
X
a
Ginigodas (X) and Ginigodss(
(X) measure the impurity with respect to the sensitive attribute condi- tioned on the positive and negative class, respectively.
To find the best split among all possible splits, we propose constrained optimization problem that maximizes the accuracy-based information gain and upper-bounds talaimessshasee information gain:
max Gainnccurray! (Split) subject GainUnfarmess (Split) S т.
(5)
|Child
in which Gainpropemy (Split) Giniproponty (Parent)
Ginipropenty (Childy),
(6)
Paaent]
for Property E (Unfairness, Accuracy) } in which Unfairness denotes measure of unfairness such as demographic parity or equalized odds (see Definition B) Algorithm [ describes our fair tree training that supports different fairness metrics and can be verified efficiently.
5

---

Published as a conference paper at ICLR 2023
Algorithm 2: ZK proof of demographic parity fair tree training. For equalized odds fair tree training see Appendix
Input: Training set X, Trained decision tree DT. Threshold y over unfaimess-basse information gain.
Output: Commitmmnt trained decision tree parameters, ZK proof that parameters are fair.
Prover commits to the training data set and the trained decision tree, obtaining ] ([=I)ex and [DT].
Prover commits
counting trees [e*] and [e*] initialized to all zeros.
B Phase 1: 28 procfs of frequency
all Prover locally computes the path that takes through DT, acquires the comespanding node indices, and commits to them, namely [[/.].... [.x1).
4:
<-
[m/a]]]
Uaing Xx RAM sccess
6:
for a
[1, do
[b]
(I=(DT),, |tor|| |.all)
b=00 if goes left child, otherwise D. Prove that path is correct
8:
Prover proves 1- 214,1 [b])
Prover updates commitments [e' [+ll - le' (1,) + [o] and [c"(4]] - [6 [-A]
Phase 2:
28 proofs of fairness metric
10: for all (interior node indices) do
11:
Prover proves that:
[e] x | (Ie' [|] + [+D)
Le 24 + b10 x 12 +
Σ
le [2 bjD [c + 811 $ T/4
1e MI [e]
(0
3.2 EFFICIENT ZKP OF FAIR TRAINING
In this section, we describe our ZK protocol which efficiently checks the fair training of the model. Note that in this paper we do not invent new cryptographic protocols to prove arbitrary programs P (described in Section 2). Instead, our focus is to design a P that verifies that a decision tree was trained fairly, and can be executed efficiently by RAM model ZK protocol. To this end, in Section [31] we separated accuracy maximization and fairness requirements by modifying the split finding criterion. This means that one need only verify that the split point in the trained decision fairness requirement, as opposed to exhaustively trying all possible split points. As a result, our ZK verification of fair training has a computational complexity lower than the training itself.
satisfies the
Decision Tree and Commitment Representation. Each internal node n in a decision tree is represented as a tuple (attr, val), which respectively encode the attribute and threshold value by which n splits the data. The decision tree DT of height h is represented as an array of nodes, such that the two children of node DT[i] are [2 and 2 + 1]. To avoid leaking information about the topology of the tree, the array will always have space for full binary tree. Non-full trees can trivially be encoded using dummy threshold values to ensure that data never enters the missing nodes. We will use [x] to represent the cryptographic commitment of a value x known to the prover. This means the prover can prove facts about x without disclosing its value to the verifier.
Our ZKP protocol. Our efficient fairness verification is presented in Algorithm 2 It has two phases:
1. Phase 1:
ZK proofs of frequency counting. This step takes the trained decision and the training data and, for each node and each possible sensitive attribute value, obtains committed counters on the number of training data entries falling into that node.
2. Phase 2: ZK fairness metric verification. Based on the committed counters, prove in ZK that the calculated fairness metrics from the counters are below the required fairness threshold.
Below we formally state the security of our protocol. Intuitively, the protocol does not reveal anything about the training dataset the decision tree except to indicate that the fairness metric used for splitting is satisfied. Because a generic ZK protocol is used, the committed decision tree and the dataset can potentially be used to prove other statements. Below state our main theorem in the security of the protocol, which is formally proven in Appendix
Theorem 1. Algorithm 2 is secure ZK proof of fair training.
Extensions. In the above description, we show a ZK proof of fair training w.r.t. demographic parity. We note that is easily generalizable to other faimess metrics mentioned in Section 3.1 as we can

---

Published as a conference paper at ICLR 2023
COMPAS
Communities Crime
Default Credat
Adult
Bookss
Dem. Parily
Eodds
Dem. Parily
Eudds
Dem. Parily
Eodds
Dem. Parity
Konning time
12.74s
9.87s
8.318
7.37s
72.21s
50.80s
104.738
62.86s
Communication
28.7MB
21.1MB
23,9MB
16,9MB
107
67.7MB
145,2MB
89.1MB
Table I: Efficiency of Confidential-PROFII in terms of running time and communication costs on real-world datasets. Confidential-PROFII executes the confidential proof of fair tree training in a matter of seconds with low communication overhead. represent many group fairness metries with unified function such as:
o.. + FFF aTT," + BFF Demographic parity B = Equalized odds: {a 1,9 1,9 0} and (a = 0, 13.
00
For example, to support equalized odds, one must maintain four counter trees (rather than just cl and c², as in demographic parity) and verify the fairness metric accordingly. See our proposed ZK protocol for equalized odds in Appendix
4 EXPERIMENTAL EVALUATION
Our principal motivation for introducing Confidential-PROFITT is to prove to interested parties (e.g.. users or auditor) that the learning algorithm used to train a model is fair by design-while protecting the confidentiality of both the training data and model. Next, we empirically evaluate the novel aspects introduced by Confidential-PROFF
namely, (1) the ZK-friendly faimess-aware training algorithm along with (2) its customized ZK proof protocols. Therefore, validate empirically as follows: i) effectiveness in training a fair model:
the performance of Confidential-PRoFFe The unfairness of decision trees decreases (while keeping the accuracy high) as the bound the information gain w.r.t the sensitive attribute decreases; ii) efficiency in proving the use of fair algorithm: We implement our customized ZK protocol for verifying the algorithm and benchmark its runtime and communication costs. Our framework scales to real-world use cases (c.g., to large number of training samples and attributes as well as deep decision trees).
We assess the performance of Cinfidennial-PRFFFII benchmarking: COMPAS (Angwin et al.) 2016), Communities and Crime (Redmond] 2009). Adult Income (Adu 1996). and Default Credit (Def) 2016). Refer to Appendix G. for details on these datasets. Two distinet code bases are utilized. We use the E.M-ttollit (Wang et al. 2016) to efficiently implement our ZK protocol and JAVA and Python implementation to train and assess the accuracy and fairness of decision trees. Additional details about our implementations are in Appendix G.2
using four common datasets for fairess
Figure[sshowe the relationship between accuracy and fairness for decision trees with demographic parity and equalized odds fairness. These figures were constructed with a sweep of threshold values. We indicate the fairness and accuracy trees trained without the fairness constraint as "Original" in Figure I We also compare Confidential-PROFII a "Baseline" for the demographic parity fair training method in Kamiran et al.) (2010) and Raff et al. (2018). Note that this baseline is not applicable trees trained for equalized odds faimesss. Also note that the tree heights used for each dataset are described in Appendix G.T The figures indicate that Confidential-PROFTTI only marginal, or sometimes no, decreases in accuracy compared to trees trained without fairness or with the baseline demographic parity fairness from Kamiran al. (010)) and Raff al. (2018). Interestingly, for some datasets, the range of accuracy values achieved exceeds the performance of trees trained without the faimess constraint. The accuracy drops themselves are often less than 10%. For example, for the Communities and Crime dataset we increase the fairness by almost 50% with at most a 5% accuracy drop. Therefore, ConfidentialPRRFFTY" effectively improves the fairness.
Effectiveness of Confidential-PROFITYY
to
leads to increased fairness (shown by small fairness gap values) with
Efficiency of Confidential-PROFFT... Table shows the runtime and communication costs of our fair training ZKK protocols on Amazon EC2 machines in which the prover (i.e., the company) and the verifier (i.c., the auditor) are connected over a local area network (LAN). The runtime for all datasets is in the order of seconds. For example, it takes less than 10 seconds to prove the fair training in terms of demographic parity on COMPAS dataset. The communication overhead for both parties is at most 145 MB. For example, the total communication cost of running CanfidentialPRROEE equalized odds and demographic parity on the COMPAS dataset is 28 MB and 21 MB, respectively. Therefore, Confidential-P IinfidentialPRRFFTTY PROFITT efficiently proves the fair training of trees.
using
7

---

Published as a conference paper at ICLR 2023
Communitics and Crimes
COMPAS
Adult
Default Credit
1.0
Dengragie Patly
Devegagtio Purty Cap
Denogaehie Purty
Party
052
1.0
Epplinl Dukk Cup
Eqpalial Ocds Cop
Equalial Olds Oxy
PROFITT (Teaks)
PROVIT (Tees)
H Orginal (Toit)
H Original (Tesi)
Bandine (Duin)
+
Baseline (Ters)
Figure 1: Effectiveness of ConfidentialPRRFFITY in terms of demographic parity (first row) and decreases the unfairness of the decision tree while keeping the accuracy close to that of the original decision tree trained without any fairness constraints. Original indicates a decision tree trained without any fairness constraint.
equalized odds (second row) of trees. Confidential-PROFTII
Dassiag
100 2100 Figure 2: Scalability of Confidential-PROFII Confidential-PROFITY scales to large number of training samples, large number of attributes per sample, and large decision trees in practical running time (less than an hour). Default settings are: 10,000 for training samples, 10 for attributes and 10 for tree height.
20400 50003 40/00 8.00 X0M00
200
Feight
using demographic parity and equalized odds.
We further evaluate the scalability of Confidential-PROFITY by considering various numbers of training samples, number of attributes, and height of trees, which are [10 10%) [10, 10*] and [4, 10). respectively. Figure 2 shows the effect of the number of training samples, number of attributes and height of trees on the running time (see Appendix H for the communication cost) of SefiidentialPRRFFTT
when proving demographic parity and equalized odds. These results demonstrate that even for the maximum values of these parameters, the running time less than an hour. Therefore, Confidential-RRFFTY" is scalable. Next, we discuss the pattern of running time.
As expected, we observe linear scaling with the number of samples (left panel). The reason for this is that each sample is processed using a constant number of operations during the first phase of our protocol, and the number of operations the second phase is unchanged by the number of samples. The equalized odds protocol incurs higher running times, since it has to initialize and update four counting trees while the demographic parity version only needs to keep track of two. We also observe that the protocol scales linearly with the number of attributes (middle panel). This is because increasing the number of attributes increases the number of operations required to commit to the dataset. We note that the demographic parity and equalized odds protocols are roughly equivalent in run time for these experiments because committing to the dataset takes the same amount of work in both versions. Finally, we observe the beginning of exponential scaling as tree height increased (right panel). This is due to the exponentially increasing size of the trained decision tree and counting trees, as well as the fairness checking phase (which iterates through all interior nodes). Breakdown of computational costs between phases of the ZK protocol varied depending on parameters. For example, on the COMPAS dataset, the commitment, counting, and fairness checking phases took up approxi- mately 60%, 32%, and 0.2% of the runtime respectively whereas for the Default Credit dataset, those respective values became 24%, 72% and 2% (the remainder of the runtime is spent initializing the underlying ZK framework). This difference is caused by the size difference between the two datasets.
An analysis on fair splitting criterion versus fairness metrics. Figure 3 demonstrates a connec- tion between the fair learning algorithm and the fairness metrics investigated: the unfairness of demographic parity and equalized odds increases with the average unfairness gain values over all node splits for decision trees. This is intuitive given that similarly to the label-wise discrimination encouraged by Gain high values of Gainuatairess may bring the tree to discriminate across values of the sensitive attribute. By limiting this discrimination, we expect little change to the purity of successive nodes, eventually leading to leaves having a mixed population from each subgroup.
8

---

Published as a conference paper at ICLR 2023
Communities and Ctime (DP)
COMPAS (DP)
Communities and Chime (BOdks) COMPAS (EOdds)
Figure 3: Relationship between fair splitting criteria and unfaimess definitions. As the bound on the unfairness-based information gain decreases, the unfaireess of trained decision trees decreases.
Communities and Crime
COMPAS
Adult
Defullt Credit
Decngray Thuity Gip
Denceopah Darty Sapp
Deccopophál Purity (up
Deougriple Party Da)
1.00
Expatted Dlkk Cop
Regalbood Drdk Gap
Ko Dalk
Eigacbvol (4.6 Sky
PROFITT (Teais)
PROPITT (Tem)
(Texis)
Origmal (Teet)
Daseltn (Toin)
Baeelne (Teet)
Figure 4: Effectiveness of Confidential-PRFFIT in terms of demographic parity (first row) and equalized odds (second row) of random forests. Confidential-PRFFT
decreases the unfairness of the random forest while keeping the accuracy close that of the original random forest trained without fairness constraints. Original indicates random forest trained without any fairness constraint.
COMPAS
Communities and Crime
Default Credit
Adult
Parity
Fodds
Dem, Parity
Fedis
Dem. Parity
Fodds
Dem. Parity
108.73s
73.79
73.4%
51,88s
652.9%
372.55
908.63s
537.5%
Table 2: Confidential-PROFIITT executes the proof of fair random forests training in practical time.
5 CONFIDENTIAL PROOF OF FAIR TRAINING OF ENSEMBLES OF TREES
Ensembling decision trees into random forest can improve the performance of the resulting classifier (see Appendix | for these results). Therefore, we extend Confidential-PROFTTI to prove the fairness of random forests (Zhang et al. 2020b 2021 Raff et al., 2018). Concretely, we construct fair random forests from ensembles
fair decision trees with bagging and random feature selection (see Appendix G.2 for details of how to train random forests). By running secure coin- loin-flipiing protocol between the company and the auditor before training. the randomness used for subsampling data points and attributes during the ensemble process an efficient protocol for ZK proof of fairness for a random forest can be derived by performing ZK proofs of each decision tree and data consistency between different trees. See details in Appendix Figure and and Table 2 show accuracy-fairness relationships and running time of random forests. We achieves major fairness gains for random forests with marginal changes to the accuracy in a practical time.
be revealed to the auditor. Given this,
observe similar results: Confidential-PRores
CONCLUSION
In this paper, we proposed a framework that can be used to confidentially prove the fair training of a decision tree. Confidential-PROFFI can help companies avoid receiving fairness-related penalties as it certifies the fairness during training prior to making any decisions on clients' queries. Practical considerations. Across the whole data-based decision process, Maafidential-RROFFE can prove the fairness of the model-training phase. To provide an end-to-end faimess guarantee to the auditor, one could extend our framework by proving the fairness of the data source and by proving the inference-ting use of the model. The company can use faimess-aware data pre-processing to ensure a fair representation of the different subgroups (e.g., by swapping the ground- truut labels (Kamiran & Calders 2009 Luong et al., (201I) and prove the integrity of this process by providing a ZK proof to the auditor. To ensure the company uses the proven fair model in the deployment phase, one could use existing 7.K --a-seed verified inferences for trees (Zhang al. 2020al Singh et al.) 2021).

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We would like to acknowledge our sponsors, who support our research with financial and in-kind contributions: CIFAR through the Canada CIFAR Chair program and the Catalyst grant program, Microsoft, and NSERC through the Discovery Grant and COHESA Strategic Alliance. Resources used preparing this research were provided, part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. We would like to thank members of the CleverHans Lab for their feedback. Sébastien Gambs is supported by the Canada Research Chair program, Discovery Grant from NSERC well the NSERC-RDC DEEL project. Xiao Wang is supported by DARPA under Contract No. HR001 20C00887 NSF award #2016240, and research awards from Meta and Google. Adrian Weller acknowledges support from EPSRC grant EP/V056883/1, a Turing AI Fellowship under EP/VO25279/1, and the Leverhulme Trust via CFI.
ETHICS STATEMENT
The main objective behind ConfidentillPROFFIII to achieve provably fair training without the requirements of revealing the training data model to auditor. In particular, the combination of confidentiality and fairness alleviates companies' data and intellectual property concerns for auditing, which could increase fairness auditing and public trust in audited Al overall.
The main ethical issues this work are related to the definitions of fairness and benchmark datasets used. Indeed, algorithmic fairness is composed of multitudes of conflicting definitions. Our work focuses on group fairness, and specifically on demographic parity and equalized odds, both which popular and relevant metries. However by relying on these definitions, we acknowledge that this reinforces the political and philosophical worldviews and ideologies underlying them, and deprives other notions of fairness (e.g., individual fairness settings in which there given sensitive attribute) of due attention.
The datasets used to validate our methods are popular fairness benchmarks. Unfortunately, their popularity can be partially attributed to the blatant unfairness of the models they have produced and the harm these models may have done when deployed in practice. Our use of these benchmark datasets is merely to remain comparable with other approaches in the literature- we do not necessarily support the use of machine learning any these contexts, specifically recidivism prediction (COMPAS) community crime profiling (Communities and Crime).
To account for these risks, we advocate for more research at the intersection of privacy and fairness, particularly for other definitions of fairness. We also believe that it is important to foster more research on the development practical solutions in fairness and fairness auditing.
REPRODUCIBILITY STATEMENT
To support main contributions, have provided detailed report of algorithms and proofs in appendices. More precisely, we have detailed our datasets, hyperparameters and implementations Appendix G. and G.2 The code available at /tttps//ggitus. com/ cleverhans Ceb//oofiidentin 1al--POFITT This work is licensed under a Creative Commons Attribution- NonCommercial 4.0 International cccceeecsspp//r/eeeeeecoooooooo htw.://mmooooooo////eeeeeeeeeeee by-nc/4.07
REFERENCES
Adult. UCI Machine Learning Repository, 1996.
Default of Credit Card Clients. UCI Machine Learning Repository, 2016.
Mark Abspoel, Daniel Escudero, and Nikolaj Volgushev. Secure training of decision trees with
continuous attributes. Proceedings on Privacy Enhancing Technologies, (1):167-187, 2021. doi: 10.2 10.2478/popets- 22278//pppes-22221-0000,, 2021-0010. URI. https: / /oo.i erg/10 20110.24777
2021 -01000000000
Samuel Adams. Chaitali Choudhary, Martine De Cock, Rafael Dowsley, David Melanson, Ander- son CA Nascimento, Davis Railsback, and Jianwei Shen. ensembles over continuous data. arXiv preprint 10Xiv:2106.027770 2021.
training of tree
10

---

Published as a conference paper at ICLR 2023
Sina Aghaci, Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for condimscriminteive decision- maaiiiinmmmiing.... In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33. pp. 1418-1426, 2019.
Julia Angwin, Jeff Larson. Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, May 2016.
Retrieved January 15, 2022.
Stan Benjamens, Pranavsingh Dhunnoo, and Bertalan Meskó. The state of artificial intelligence- FDA-approved medical devices and algorithms: an online database. NPJ Digital Medicine, 3(1): 1-8, 2020.
Kristin P Bennett. Decision tree construction via linear programming. Technical report, University of Wisconsin-Madison Department Computer Sciences, 1992.
Dheeraj Bhaskaruni, Hui Hu, and Chao Lan. Improving prediction fairness via model ensemble. In 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), pp. 1810-1814. IEFF, 2019.
Sarah Bird, Miro Dudik, Richard Edgar, Brandon Horn, Roman Lutz, Vanessa Milan, Mchrnoosh Sameki, Hanna Wallach, and Kathleen Walker. Fairlcar:: A toolkit for as- sessing and improving fairness in AI. Technical Report MSR-TR-2020-32. Microsoft,
May 2020. /tA.///pps///w....oooooo.....oo.
//wp: www.:wwwww.ooo.ooommo com http:///wnn/eeeeerrrc//obbaaaaaa
Cairlearn-a-toolkeee asr-assssso--sssssnnns http:///ww...........o....ooooar
L. Breiman, Jerome H. Friedman, Richard A. Olshen, and C. Stone. Classification and regression trees. 1983.
Leo Breiman, Jerome H Friedman, Richard A. Olshen, and C. Stone. Classification and regression frees. Routledge, 2017.
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference on Fairness, Accountability and Transparency (ACM FAceT), pp. 77-91. PMLR, 2018
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops (ICDM), Miami, Florida, USA, December 2009.
Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143-202, January 2000. doi: 10.10077/0014459900000
Alexandra Chouldechova. Fair prediction with disparate impact: a study of bias in recidivism prediction instruments, 2016.
Sam Corbett-Davies Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq, Algorithmic decision making and the cost of faimess. In Proceedings of the 23rd International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD), Halifax, Canada, August 2017.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Faimness through awareness. Proceedings of the 3rd Innovations Theoretical Computer Science Conference (ITCS), pp. 214-226, 2012.
James Fantin. Fair-Forest, 2020. URL /tt.//tpps//ggghhh..om/////////a Forest
Michael Feffer, Martin Hirzel, Samuel C Hoffmann Kiran Kate, Parikshit Ram, and Avraham Shinnar. An empirical study of modular bias mitigators and ensembles. arXiv preprint arXiv:2202.0075), 2022.
Nicholas Franzese, Jonathan Katz, Steve Lu, Rafail Ostrovsky, Xiao Wang, and Chenkai Weng. Constant-overhead zero-knowlest for RAM programs. In Giovanni Vigna and Elaine Shi (eds.), ACM CCS 2021, pp. 178-191, Virtual Event, Republic of Korea, November 15-19, 2021. ACM Press. doi: 10.1 145/34601122 20.3484800
11

---

Published as a conference paper at ICLR 2023
Kazuto Fukuchi, Satoshi Hara, and Takanori Machara. Faking faimess via stealthily biased sampling. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 412 4199, 2020.
Nazech Ghatasheh. Business analyties using random forest trees for credit risk prediction: a comparison study. International Journal of Advanced Science and Technology, 72(2014):19-38) 2014.
Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs.
J. ACM, 43(3):33- may 1996. ISSN 0004-5411. doi: 00.1145/233551.233555 URL
https::/dbi.org//11 htt.://///....11///.... 11tp://0....1112351...22 2335533
Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM, 38(3))691-779, 1991.
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems (extended abstract). In 17th ACM STOC, pp. 291-304, Providence, RI, USA, May 6-8, 1985. ACM Press. doi: 10. 10.1145/22445.22175
Levent Güntay, Erdal Bozan, Umit Tiğrak, Tolga Durdu, and Gülçin Ece Özkahya. An explainable credit scoring framework: A use case of addressing challenges in applied machine learning. In 2022 IEEE Technology and Engineering Management Conference (TEMSCON EUROPE), pp. 222-227. IEEE, 2022.
Koki Hamada, Dai Ikarashi, Ryo Kikuchi, and Koji Chida. Efficient decision tree training with new data structure for secure multi-party computation. arXiv preprint arXiv:2112./2906 2021.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in Neural Information Processing Systems (NIPS), 29:3315-3323, 2016.
Hoda Heidari, Michele Loi, Krishna P. Gummadi, and Andreas Krause. moral framework for understanding of fair ML through economic models of equality of opportunity. In Proceedings of the 2019 Conference on Fairness, Accountability, and Transparency (ACM FAT*), Atlanta, Georgia, USA. January 2019.
Nathanael Jo, Sina Aghaei, Jack Benson, Andrés Gómez, and Phebe Vayanos. Learning optimal fair classification trees. arXiv preprint (Dt::2201.099322 2022.
Faisal Kamiran and Toon Calders. Classifying without discriminating. In 2009 2nd International Conference on Computer, Control and Communication, pp. 1-6. IEEE, 2009.
Faisal Kamiran, Toon Calders, and Mykola Pechenizkiy. Discrimination aware decision tree learning. In 2010 IEEE International Conference on Data Mining (ICDM), pp. 869-874, 2010. doi: 10. 10.1000000220000.500
Jonathan Katz and Yehuda Lindell. Introduction Modern Cryptography. Chapman and Hall/CRC Press, 2007. ISBN 978-1 778-1-58488-551-11
Jon Kleinberg, Himabindu Lakkaraju, Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. Human decisions and machine predictions. The Quarterly Journal of Economics, 133(1):237-293, 2018.
Wei- Yin Loh. Classification and regression trees. Wiley Interdisciplinary Reviews: Data mining and knowledge discovery, 1(1):14-33, 2011.
Binh Thanh Luong, Salvatore Ruggieri, and Franco Turini. k-nn an implementation of situation testing for discrimination discovery and prevention. In Proceedings of the 17th International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD), pp. 502-510, 2011.
Christoph Molnar. Interpretable machine learning. Lulu. com, 2020.
Arvind Narayanan. Tutorial: 21 faimess definitions and their politics, 2018. URL https
7/ www. www.wyoue www.tb..uuubbccccm com/ wwatt/aatt wwatchht=]IXXiximm
Sikha Pentyala, David Melanson, Martine De Cock, and Golnoosh Farnadi. Privfair: a library for privacy- preeec-pressrving fairness auditing. arXiv preprint 22Xx::2002.00088 2022.
12

---

Published as a conference paper at ICLR 2023
Vili Podgorelec, Peter Kokol, Bruno Stiglic, and Ivan Rozman. Decision trees: overview and their use in medicine. Journal of Medical Systems, 26(5):445 46355446366560 2002.
Edward Raff. Jsat: Java statistical analysis tool, library for machine learning. Journal of Machine Learning Research, 18(23):1-5, 2017. URL http:pppp//.m....or///p///tttt//
html
Edward Raff, Jared Sylvester, and Steven Mills. Fair forests: Regularized tree induction to minimize model bias. In Proceedings of the 2018 AAAI/ACM Conference on Al, Ethics, and Society (ATES), pp. 243-250, 2018.
Michael Redmond. Communities and Crime. UCI Machine Learning Repository, 2009.
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (ACM CCS), pp. 1310-1321, 2015.
Nitin Singh, Pankaj Dayama, and Vinayaka Pandit. Zero knowledge proofs towards verifiable decentralized AI pipelines. Cryptology ePrint Archive, 2021.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C. Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, R. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272 2020. doi: 10. 1991038/41992--199944
Kaveh Waddell. How algorithms can bring down minorities' credit scores. The Atlantic, 2, 2016.
Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. EMP-toolkit: Efficient MultiParty computation toolkit.
wttp://wwww..cc/emtoootaoooooo/a emp- toolkit 2016.
Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang. Wolverine: Fast, scalable, and communicationnefficeenn zero-knowledge proofs for boolean and arithmetic circuits. In 2021 IEEE Symposium on Security and Privacy, pp. 1074-1091, San Francisco, CA, USA, May 24-27, 2021. IEEE Computer Society Press. doi: 10. 10111109//400002000 202100000000022200000066
Valentina Zantedeschi, Matt Kusner, and Vlad Niculae. Learning binary decision trees by argmin differentiation. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 12298-12309. PMLR, 2021.
Jiaheng Zhang, Zhiyong Fang, Yupeng Zhang, and Dawn Song. Zero knowledge proofs for decision tree predictions and accuracy. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (ACM CCS), pp. 2039-2053, 2020a.
Jialong Zhang, Zhongshu Gu, Jiyong Jang, Hui Wu, Mare Ph Stoecklin, Heqing Huang, and Ian Molloy. Protecting intellectual property of deep neural networks with watermarking. In Proceedings of the 2018 Asia Conference on Computer and Communications Security (ACM ASIACCS), pp. 159-172, 2018
Jiang Zhang, Ivan Beschastnikh, Sergey Mechtaev, and Abhik Roychoudhury. Fairness-guided SMT-based rectification of decision trees and random forests. arXiv preprint arXiv:2011.11001, 2020b.
Wenbin Zhang, Albert Bifet, Xiangliang Zhang, Jeremy C Weiss, and Wolfgang Nejdl. Farf: A fair and adaptive random forests classifier. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), pp. 256. Springer, 2021.
13

---

Published as a conference paper at ICLR 2023
A
NOTATION
Table 3 shows the notation used throughout this paper.
Table 3: Notation table.
Notation
Meaning
Notation
Meaning
X
Dataset
Y
Set of binary ground-trune truth labels Sensitive attribute value
a
Binary sensitive attribute
s
X,
Dataset with sensitive attribute
X
Dataset with ground-truth label Decision tree height
DT
Decision tree
Threshold
A(.-)
Fairness-aware training algorithm
Y
Set of binary predicted labels
Gain (
Information gain
Gini O
Gini
[
Commitment of x
croooknowledge proof protocol
c
Counter
B FAIRNESS METRICS
In this section, we describe four common fairness metrics: Demographic Parity, Equalized Odds, Equal Opportunity, and Predictive Equality. We consider the former metries in this paper, though our work may be easily extended to these other metrics as equal opportunity and predictive equality are weaker versions of equalized odds.
Definition& 4 (Demographic parity (Calders et al. 2009)), predictor y satisfies Demographic Parity with respect to the sensitive attribute if:
Pr 1|5 = a) Pr(f = 1|5 =
Ya, E.
Satisfying demographic parity, statistical group parity, refers equal probability of predicted pos- itive label across subgroups partitioned by protected attribute S. In essence, enforeing demographic parity ensures that the predicted class under the model is independent of inclusion in particular subgroup. Such a fairness definition leads to situations and tasks in which the prediction intended be independent of subgroup inclusion. Additionally, demographic parity presents a fairmess metric that can, to some extent, overcome issues of bias in the true label associated with S, as demographic parity ignores the true label in its formulation. Although several tasks necessitate such properties in fairness metric. classification in domains in which target labels may be intrinsically related to subgroup values, such as healthcare, demographic parity fails to capture key relationships between target labels and subgroups that can lead to poorer fairness (in the societal sense of fairness). For example, prediction in breast cancer diagnosis needs to incorporate subgroup information about biological sex, due to higher rates in women.
Definition 5 (Equalized Odds (Hardt al. 2016 predictor Y satisfies Equalized Odds with respect to the sensitive attribute $ if:
Pr(r 1 = y. S a) Pr(r 1 S. b.] Vy (0.1),
The equalized odds metric a strict constraint on fairness that requires a predictor to jointly equalize the false positive rate (FPR) and true positive rate (TPR) across subgroups determined by S. In the equalized odds formulation, the fairness of model depends not only on the predicted label but on the true label distribution as well. Satisfying equalized odds ensures that the predicted class is conditionally independent of the protected attribute and the target class. Equalized odds was proposed to alleviate pitfalls of demographic parity, which cannot capture important relationships between the target class and the subgroup's 's information in its formulation of faimeess. Therefore, equalized odds better suited for tasks in which intrinsic information links subgroup inclusion and true class, but can propagate bias in cases where the "true" label encodes societal unfaimess. For equalized odds fairness, the prediction should be completely independent of the sensitive attribute. Note that equalizing both FPR and TPR implies searching for the intersection of per-subgroup
14

---

Published as a conference paper at ICLR 2023
area- receiver-operatorr
(AUROC), which may not be always satisfiable for non-trivial intersections. Similarly, such an intersection may lie in an undesirable region of the parameter space that significantly degrades the utility of the model overall. Thus, relaxation and calibration methods have spawned order to mitigate these issues with this fairesss metric (Hardt et al. 2016).
Definition 6 (Equal Opportunity (Hardt et al. 2016)). A predictor Y satisfies Equal Opportunity with respect to the sensitive attribute if:
Pr(y = 1|Y = 1,5 = Pr(y = 1|Y = Va,b E
Equal opportunity introduces weaker version of equalized odds, in which solely TPR is equalized across subgroups. Due to the relative difficulties associated with satisfying equalized odds, equality of opportunity relaxes the metric by permitting unequalized FPR, but continues to require TPR, and offers an advantage over demographic parity in certain settings by incorporating the target label into its formulation. Equality of opportunity largely works in domains in which the positive class could be viewed as "desirable" (thus the name opportunity) by enforcing equal inclusion in the positive class conditionally independent of S and true inclusion in the positive class.
Definition (Predictive Equality (Chouldechova 2016 Corbett- Davies et al. 2017 ). predictor Y satisfies Predictive Equality with respect to the sensitive attribute S if:
Pr[Y 1|Y S, = a] = Pr(y = 1|Y 0, =
Similar to equal opportunity, predictive equality enforces partial form of equalized odds requiring equalized FPR across subgroups with no constraints on TPR. Conversely to equal opportunity, predictive equality applies well in scenarios in which the inclusion in the positive class under the model can be considered poor outcome, and therefore causes considerable damage when the true label is negative.
Equality of opportunity and predictive equality both can be seen partial requirements for equalized odds:
aT. + 3 = aT, + B
Equalized odds {a = 1,3 = 0} and {a 0, =
(8)
Equal opportunity {a 1, 0}
Predictive equality: {a 0,8 1}.
Therefore, any predictor satisfying equalized odds will satisfy both predictive equality and equal opportunity.
C BLOCK DIAGRAM OF CONFIDENTTAA-
S overview of Confidential-PROFITT which consists of four main steps.
D DECISION TREE TRAINING
D.I DECISION TREE TRAINING WITHOUT FAIRNESS CONSTRAINTS
Decision trees used for classification are trained recursively from root leaf node by successively partitioning the input set, as shown in Algorithm 3 Ideally, data points in the leaf nodes are pure with respect to class and the leaves are used for prediction during inference. Partitioning is represented by nodes in a binary tree and enforced with Boolean condition that splits the data based on some attribute value into at most two disjoint child nodes. To find the optimal splitting criterion for node, the algorithm itcrates over every attribute and attribute value. These values are used as thresholds to split the data into child nodes. The algorithm measures the information gained (with respect to node class purity) between the parent and child nodes and chooses the splitting criterion that maximized this gain. The process finding the best split is detailed in Algorithm 4 Splitting continues until some maximum height is reached or until the node sizes have reached some minimum value. While there are many decision tree training algorithms, this paper uses the CART (Classification and Regression Tree) with information gain, Gini impurity, binary splitting, and binary classification for numerical and categorical datasets. The CART algorithm has been popular since its inception in 1983 (Breiman et al. 1983).
15

---

Published as a conference paper at ICLR 2023
0) Local training:
1) ConiidentalPRRFFIT - Commitment:
Prover localyy trains decision free DT
Prover commis to data and model without reveeling them changes commitments auditor's
Training dataset: (X,Y) Y), Training algorithm:
A faimess-aware training algorthim
[X,Y]
A(--)
Vanifior
Commitment
[X]]
[X] [T]]
DT
Prover
2) CROFFIT .. Prove counter upéate:
3) Confidential PROFITT - Prove faimess constraint
Confideriai-PROFITT
Prover locally computes path each training
Prover computes each spiit committed counters
proves path updates
counters
proves Gaintatnau <.
[a)], [s], M
le
[
+- (e [e]
=DT attr) < [DT vall
DTII
p + [T]
[Grower Gini((c [1]]) [<"[]])
DT
Suuie attr 2 (DTTI vall
DTRI
DTII
[Geuas]] Céni([e"[[] (+((a))
DT[A]]
DT|33]
[Gena Géni((c) [s],, [<"(s])
[e|12]]
[2)
je M (e [8] [+]
[a] + [=]
+
[
[ + ( [S]
Goinestatonal
[Grasas]
weighted average (eeuage((Graaavaaa
Figure Block diagram of the proposed Confidential Proof of Fairness, Confidential-PROFITI
Algorithm 3: Recursively building decision tree.
Input: Training dataset X. current decision tree height he, maximam decision tree height
Output: Trained decision tree DT
if DTehight > then null split FindBBet(plii(X)
split.leafs then
for leaf split do
return and link BuildTreerleff.... D'Thhigh+++ 1)
Algorithm 4: Finding the best (faimexs-oblivious) split for each node.
Input: Dutaset X jith node Íjl.
Output: Best split.
Accuracy Setiingannnss.
Initialise gains each each altribute & Make parent node
2: Parent = X
attr E Attributes
for E do val x mjattr] Child,
Set split threshold value per datapoint
{a X [xr[atrr] < val), Childy
{a X|s](ttr] 2 val)
Make ldren
7:
Gainassency Gini (Pareat) Σi=1
GinlAsemmy (Child.)
Gain wrt label
8: Accuracy, gainss.apend((atti val, Gainassmy)
val, return attr, DT val, DT[j] gains maXGaa Accancy Accurccyggain
b Beat aplit
D.2 DECISION TREE TRAINING WITH FAIRNESS CONSTRAINTS
Training decision tree with fairness while maintaining the root-to-leaf recursive training procedure only requires one additional step, detailed in Algorithm While iterating over the various splits, we measure both information gain with respect to class Gini impurity and fairness Gini impurity. We select the splits that produced fairness information gains below some threshold before choosing whichever had the highest class information gain. This leads high fairness and accuracy for the dataset.
16

---

Published as a conference paper at ICLR 2023
Functionality FZKDT
1. Prover and Verifier send T, abort if they do not match.
2. Prover sends dataset X, decision tree parameters DT Verifier receives 1 V interior node indices i, (4 I holds. Verifier receives otherwise.
Figure 6; Ideal functionality for verifying the fairness of decision tree in zero knowledge.
Functionality Fzk
Operations
Commitment to private inputs: receiving (Input, from P. store æ send [æ]] to each party. Commitment to (public) constants: On receiving (Const, x) from both parties, store x and send [>]] to cach party (if the two inputs do not match, both parties receive cheating).
Boolean circuit satisfiability: On receiving (Ciree C, [=o]..... [1] from both parties, in which the I's Boolean values and C' Boolean circuit, compute b C(zo, In-1) and send b to
V.
RAM Operations
Initialization: On receiving (Init, from and V. store N valuue arry A with values initialized
L. and set f := honest.
Write: On receiving (Write, [1] [d]]) from 1 and V. set A(i] == d and send fresh [d]] to each party.
Read: On receiving (Read, [1], d), from P. (Read, [+]] from V. send [d] to both parties. d & A|]
set f == cheating
Check: On receiving (Check) from send both parties.
Figure 7: Ideal functionality for Zero Knowledge Proofs with RAM access.
E PROOF OF SECURITY OF THEOREM
We prove the property of our protocol based the composition paradigm Canetti (2000), which the standard way for proving cryptographic protocols. We represent the ideal functionality for knowledge fairmess check FZKDT in Figure 6 To realize this functionality, the protocol a series of calls to a Zero- Knowledge Proof functionality with RAM capabilities Fzk, which is given in Figure This can be instantiated using existing works that construct RAM-based zero-knowledge proofs.
described in
Proof. A given execution of the protocol in Algorithm comes with a prescribed pattern of calls to FzK the low level details of this pattern are abstracted in the algorithm, but specified exactly in code that implements our protocol. Any deviation from this pattern of calls to Fzæ detected trivially (since the honest party sends a command to Fzk that goes unanswered), and results in abort of the protocol. Thus no adversary A is able to break security by deviating from this pattern. For those adversaries that follow the correct pattern of calls, construct simulators as follows.
Malicious Prover: Simulator S interacts with FZKDT with the following procedure, running malicious Prover A in the Fzk- model subroutine:
Simulating Fzk. S receives (Init, N) from A, in which N is the size of RAM required to represent the computation. Store flag f == honest. Initialize an array A in accordance with FZK. Next S receives sequence Input commands from A, followed by Const commands to obtain RAM indices, and Write commands to store the values in the RAM. Write the values into and interpret them as X and DT. Send back commitments [X] and [DT]]
2. Receive a sequence of (Const, 0) and (Const, RAM index) followed by Write commands to initialize et and c². Similarly the previous step, store these values in A and send back [ct]] and
[[a
For all I; X do:
4. Receive Input, Const, and Write commands to store (I,,...,hp Write the values
in A. and send back [[[]].-.. [[u]].
5. Receive (Read, [[idex of x||]]] s). if Alindex of a[a]] * s, set f cheating. Send back [s]
6. For all [1, H do:
17

---

Published as a conference paper at ICLR 2023
7. Receive bit b via Input command, followed by sequence of Reads trieve x a v and a Circ command to verify that = x: =[DT[[]]attz]] < DT[L,).val. Send back values obtained by executing Fzk faith- fully.
8. Receive commands verify [ 2[4,1 [b],
execute Fzk faithfully.
9. Receive commands to verify updates c² [4] + and [44 + -s and write the updates to the RAM. Execute Fzk faithfully.
10. For all i (interior node indices) do
Receive Read commands to retrieve c² [2]], c² (11, c 22 12, followed by Circ commands earry out the fairness check. Execute Fzk faithfully.
11. After protocol execution, execute Check command. If f cheatings send 1 to FZKDT and abort. Otherwise, send X and DT to FZKDT.
Clearly S constructs view for A that is indistinguishable from real world execution, since all interactions with A through FzK are performed faithfully. Input extraction follows trivially since A sends the values of X and DT to Fzk in the commitment phase. Further, view is consistent with the outputs generated by A's inputs, since the fairness checking phase directly computes (an algebraic rearrangement of) Gaininnaimess (i, X, DT) S for each interior node index i.
have that the generated
Malicious Verifier: Simulator S interacts with FZKDT with the following procedure, running malicious Verifier in the F2K- -hybbidd model subroutine:
Simulating Fzk, S receives (Init, N) from A, where N is the size of RAM required to represent the computation. Store flag f == honest. Initialize an array A in accordance with Fzk. Next, simulate series of Input commands by sending [O]] to A several times (with fresh randomness each time). Then receive a series of Const commands to obtain commitments to RAM indices simulate FzK by sending back commitments
the requested indices. Next receive Writ ee commands from A for storage of the dataset in the RAM. Store 0 at each requested index and send [O] to simulate responses to the Write commands. this way, A receives a list of commitments that stand in for [X] and [DT]]
2. Receive a sequence of (Const, 0) and (Const, RAM index) followed by Write commands initialize c and c², Give commitments to the requested Const values faithfully, store these values in A, and send back [c']] and [e_]-
3. For all x; X do:
4. To simulate commitment to {I,.... I send [[] for Input commands, and faithful commitments to RAM indices when Const commands are received from A. Simulate Write commands by storing at the requested indices in A, and send [O] to stand in for the commitments [[ [n]]].
5. Receive (Read, [index of r(al)), simulate honest execution of FzK by sending back [0] and keeping f = honest.
6. For all j E [1, H] do:
7. Send [b]] where b = 0. Receive Read commands to retrieve x =[DT[Z]]attrr) and x =[DT[[,].val simulate by sending [0] and keeping = honest. Next receive a Circ command to verify that b = =[D[[,,]aatr]] < DT[ send back indicat- ing that the equality holds.
8. Receive commands to verify [++1] = 2[1 + [b]. as in previous steps send [O] to simulate commitments for the Read commands (while keeping f honest) and send in response to Circ commands indicating that the desired equality holds.
9. Receive commands to verify updates ct (T,) + s and [T]T] + ms and write the updates to the RAM. Simulate the verification as in the previous two steps, and send [[] in response to the Write commands.
10. For all i finterior node indices} do
followed by Circ commands to carry out the fairness check. As before, send [0] to simulate commitments and send 1 to indicate that the fairness checks pass.
Receive Read commands to retrieve e¹ [t], [2i], [2i+1], c2i,],
11. After protocol execution, receive Check command, Simulate Fzx by sending honest. A.
18

---

Published as a conference paper at ICLR 2023
Algorithm 5: ZZer-knooleedee proof of equalized odds-aware tree training.
Input: Training set X, trained decision tree DT, Gainttttiiess threshold Oulput:
Praver commits to the training data set and the trained decision obtaining [X] ([=]>ex [DT].
2: Prover commits to four counting trees [c') [.Ic"].[e and [c'] initialized to all zeros.
Phase 1:
proofs of Erequency
for all E X do
Prover locally computes the path takes through DTT acquires the correponning indices, commits to them, namely [xx]]]
[[/i]......
[e] +- [=
Using 2X RAX access
[=
7:
[1] +- [v] A
[+]
u2l [yl 1
"3
10:
u4
19.
[
D counting ing tree updates b= if goes to left child, 1 otherwise Prove that path is correct
11:
for
do
12:
[6]
+ (I=[DIIL,]..tt < [Drl,,
13:
Prover proves [1++ 2[ + [6])
14.
Prover updates commiuments [e [4]]] + [c]]]]] + [me] fork 21,2,3,4).
Phase 2:
procIs of fairness metric
15: all 5 E finterior node indices) do
16:
Prover proves that:
[c 22 60
125 bl
Σ (c
[e + bl] $ r/4
(()))
[+]]]]
+
6]
17: Prover additionally proves that:
[+] x [+ ([ + [<D)) |*M++ +1+00
[ [d 22 + 4 x 12 b1
Σ
[e + b] + [c + T/4
pe(0.))
S constructs a view for A that is indistinguishable from real world execution, since all handles [O] given A are indistinguishable from those during real-world execution, and because in simulating Fzk. 8 can trivially indicate that the component circuits of the protocol are satisfied properly.
We would like to highlight that our approach relies on zero-knowledge proofs to formally guarantee the confidentiality of the learned model as well as of the data even against a malicious auditor (see the above mathematical proof). To be more precise, the confidentiality of the model and data ensured by the "zero- perro-knoweegge property of the underlying cryptographic protocol that can tolerate any malicious behavior (Goldwasser al. 1985 Goldreich et al., 1991). The security of these protocols are in turn based on standard hardness assumptions used to secure the Internet. We note that the kooollnwweedee proof protocol itself is not the focus of this paper; instead, we show how we can use existing vero-knowlle ledge proof protocols to prove fairnes--awan training in smart way for high efficiency. The confidentiality of our system can be ensured by any secure snowlknowedde proof system (which is what Appendix E proves), including the one used in this paper others systems.
F OUR EERO-KNOWLEDGR PROOF PROTOCOL FOR TREE TRAINING WITH EQUALIZED ODDS FAIRNESS
Algorithm 5 follows the same ideas as Algorithm 2. except it proves that Gain Bodde and Gain Bodds do exceed the threshold r, rather than Gain Dp. As Algorithm 2 these metrics are computed and proved by counting the number of samples of particular categories that pass through each node in the tree. However, to compute Gain godds and Gain Eodds we need to keep track of four categories of samples rather than just two: samples that are in the protected class with true positive label, samples in the unprotected class with true positive label, samples in the protected class with true negative label, and samples in the unprotected class with true negative label. To keep track of these quantities at each node, we use four counting trees, whose commitments are updated by adding Boolean values U1 through U4 indexing which category given sample falls into. In Phase 2 of the algorithm, the sample counts are used to show that in each interior node, the Gain Bodds and Gain Eodds exceed the threshold r.
Coaingodds
Eodds do not
19

---

Published as a conference paper at ICLR 2023
Dataset
#Samples
#Attr.
Sensitive attribute
Task
Tree height
COMPAS
6,151
Race (Binarized)
Yes/No recidivism
6
Crime
1,993
22
Race % Black .06
Crime rate .7
4
Default Credit
30,000
23
Age 2
Good/Bad credit
10
Adult
45,222
14
Gender (Binarized)
Income 50k
Table 4: Summary of datasets.
G DETAILS ON EXPERIMENTAL SETUP
G.1 DETAILS ON DATASETS
We consider four common datasets for faimess benchmarking (summarized in Table
1. COMPAS (Angwin et al. 2016 attempts to predict recidivism with recidivists comprising 53% of the dataset. For fairness, we consider just two the provided races (African- American and Caucasian) as sensitive attributes, in which African-Americans are the major- ity class at 60% of the dataset.
2. Communities and Crime (Redmond 2009
(Crime) is used for regression determine if a community will have a high violent crime rate. We adapt this task for classification by binarizing the target VioleniCrimesPeriii RacepctBlack 2 .06 in which the disadvantaged communities have higher Black populations and make up 52.1% % of the dataset.
to and for the fairness attribute binarize
3. Census Income (Adu 1996 5
(Adult) attempts to predict if an individuals income is 2 50, 000, in which 75% of the individuals have salary below 50K. We use gender (Male, Female) as the sensitive attribute, in which Males composed 68% the dataset.
4. Default Credit (Def 2016 0 (Credit) seeks to predict if an individual will default on an credit card payment. The default class composed 22% of the dataset, and the sensitive attribute used is the age with the minority group of young individual under 25 constituting 13% of the dataset.
G.2 DETAILS ON OUR IMPL EMPEENENTTOION
We two distinct code bases: for efficient 7K protocol implementation and the second for assessing the accuracy and fairness of our fair decision tree.
EMP-toolkit. We use EMP-toolkit (Wang et al., 2016) to implement our ZK protocol. EMP is written in C++ and offers efficient implementations of ZK protocols. This code base used for timing results (benchmarking the efficiency of our ZK protocol) and conducted using two Amazon EC2 c6a.2xlarge machines to represent the prover and verifier. We the Linux command to simulate LAN connection between the two machines with bandwidth of at most 1000Mbit/sec and latency of 2ms. We report the median runtime of 5 experiments at each parameter setting.
JSAT with Fair Trees and Forests. The Java Statistical Analysis Tool (JSAT) (Raff 2017). is an open source Java library which supports decision tree and random forest models. We built on the Fair-Forest extension of JSAT in Fantin (220)) and implemented splitting criteria to recreate the work of Kamiran et al. (2010) and Raff et al. (2018) as baseline for demographic parity fair trees. Additionally, we implement splitting criterion for Gaintufaines based on thresholds for both demographic parity and equalized odds faimess.
Retrieeed from
recidivi 8m-8mm---- www-risk-cooe ceisk-score-eo dat ysii
"Retrieved from
crime
Retrieved from http:///mm///ee.e.....oooaaaaaaa
'Retrieved ca card+clients
20

---

Published as a conference paper at ICLR 2023
To evaluate Confidential-PROFII
train decision trees and random forests for 250 values of with 10 random seeds each. For each dataset, we set the height of the tree by observing test and training set results in decision tree trained without faimess. We choose the smallest height that maintains accuracy without overfitring. These heights are reported for each dataset in Table
We evaluate fairness and accuracy using Fairlearn (Bird al. 2020 and SciPy (Virtanen al. 2020) over a testing set using a test-train split of 75% 25%. Experiments are run on Intel Xeon CPUs with Java (v. 14.0.2).
G.3 DETAILS ON OUR EVALUATION METRICS
Demographic parity unfairness. Demographic parity (DP) unfairness is often characterized by the absolute value of the gap between the positive prediction rate for each subgroup. DP unfairness has range of [0, in which value of 0 corresponds to perfect DP faimess. We measure this with Fairlearn's s
mmerrcc.demographiie cartiii__attttdyf_feeeeeee difference function (Bird et al. 2020).
DP unfairness =
Pr|y = 1|8 =a - Pr[y = 1|S- bll
ba be S.
Equalized odds unfairness. Equalized odds (Eodds) unfairness is characterized by the largest gap between subgroups' true positive and false positive rates. Eodds unfairness has a range of [0, 1], in which a value of corresponds to perfect Eodds fair. We measure this with Fairlearn's odds difference function (Bird et al. 2020).
cefflarn.metris..co
Bodds unfairness Pr[y 1|2 = 1,5 = a) Pr[L 1|Y = 1,5 bll
Ya, E S.
Unfairness gain of the trained decision tree. Unfairness gain (GaiMuufaiiess) is the information gain over parent and child nodes' Gini impurity (Ginitinfirmess) of sensitive attribute a. Ginivufaimess may be taken with respect to demographic parity or equalized odds unfairness.
Accuracy. The accuracy is computed from the ratio of the number of correct predictions to the total number of predictions. Here, we use SciPy's 's akleam..etrics..co.. metries.accuracy_.oo function (Virtanen et 2020).
H COMMUNICATION COSTS
In this section, we evaluate the communication costs of our framework.
Figure 8 evaaluates the communication costs of Confidential-PRont PROFITT as function of number of training samples, number of attributes, and height of trees using both demographic parity and equal- ized odds. The communication cost of Confidential-PROFTTY increases linearly as we increase the number of training samples or the number of attributes. The reason for this is that the communication cost of committing each sample is constant, and this cost increases the number of attributes increases. The increased steepness of the 10 sample benchmark likely a result of the batch amortization used by our underlying ZKP framework. In general, equalized odds incurs higher communication costs than demographic parity as proofs need to be performed over four counting trees in equalized odds, but only two in demographic parity.
I RANDOM FOREST CAN IMPROVE UPON THE PERFORMANCE OF A DECISION TREE
We show results for the model performances of both decision trees and random forests trained without fairness in Table 3 These results show that random forests improves upon the accuracy of decision trees across all datasets. However, random forests typically more unfair, supporting prior conclusions that standard ensemble strategies alone cannot improve faimess (Feffer et al. 2022 Bhaskaruni et al. 2019).
21

---

Published as a conference paper at ICLR 2023
Conmraiiaiion (MB)
Conammiccske (MIB)
Commanina iotioiiion (MBS)
8036
EXCH
750-
4303
200
750-
ricee wnim seen nоc00 Namber of loccing sumples
2000
3090
2000
1000
1000
10
Number of attributes
Height Time
Demographic parity
Equalized Odds
Figure 8: Communication costs of ConfidentialPROFII using demographic parity and equalized odds. Default settings are: 10, 000 for training samples, 10 for attributes and 10 for tree height.
Accuracy
Unfaimess (Demographic Parity)
Unfaimess (Eodds)
Dataset
DT
RF
DT
RF
DT
RF
Crime
.872 = .015
.891 + .015
.497 .088
.495 = .079
.432 + .129
.443 + 100
COMPAS
.601 .023
.652
.022
.121 .057
.178 .097
.135 + .055
.190 + .097
Adult
.759 = .016
.864
+ .002
.102 .088
.130 = .010
.076 - .014
.091 + .019
Credit
.980 + .003
.985 1 .002
.042 + .011
.034 - .010
.028 1 .014
.026 + .019
Table 5: Comparing accuracy and fairness of decision trees versus random forests.
Algorithm 6: 7K proof of fair training of a random forest.
Input: Training sot X. number of trees in ensemble N. number of attributes for each tree M, number of training samples for cach tree L, array N random integers ff,,:... ..... V. ar aray N L random integers [r Vv.zl (Known parties).
Output: Committmen to rundom forest parameters, ZK proof that parameters are fair.
Prover commits to row in the training set [X]
for all .N]
initialize emply sample array X,
attributes in [X] those indexed by rf, .... M.M--
for all
6: add [X][r?,, [ to X,
locally
decision DT with threshold unfaimess--asse information gain using training
8: Run Algurithm@wiit inguts X,, DT, and
Output concatenated ourputs of Algorithm
OUR ZERO-KNOWLER KNOWLEDGE PROOF PROTOCOL FOR RANDOM FOREST TRAINING WITH FAIRNESS
Our protocol for the fair training of decision trees is described in Algorithm 6 The parties use the input randomness (decided via secure coin- bii--fipping protocol) to index into a committed dataset, thus obtaining subsamples. Next, decision trees be trained on the subsamples to build the trees used in the random forest. Finally, the fairness of the trees can be verified individually using Algorithm 2 Note that the same heights for random forests for decision trees (as reported in Table We create random forests from collection of 10 decision trees in which each node considers random subset of attributes of size / H, in which H the total number of attributes.
K ADDITIONAL RESULTS ON THE RELATIONSHIPS BETWEEN UNFAIRNESS INFORMATION GAIN AND UNFAIRNESS DEFINITIONS
Figures and show the relationship between Gainttffiimess and the fairness gap for demographic parity and equalized odds, respectively. The Gainunaamess reported in these figures was computed from the average values for all nodes of ten trees trained from one of 250 threshold values. They show positive correlation between Gaimenta and the fairness gap, supporting our intuition that bounding Gaintniaimes leads to a smaller fairness gap.
22

---

Published as a conference paper at ICLR 2023
Communities and Crime
COMPAS
Adult
Default Credit
MECHEPTE Shatt Gep
U1/eroo Crerg
0.50
375
180
Figure 9: Relationship between unfairness information gain and the demographic parity gap. We
compute the average unfairness information gain over all node splits for decision trees created with sweep of threshold bounds on unfair information gain.
Communitics and Crime
COMPAS
Adult
Default Crodit
Sigal Lnd Oidb Cap
0.5
6.3
6.55
5.00
875
45
0.
Figure 10: Relationship between unfairness information gain and the equalized odds fairness gap.
We compute the average unfaimess information gain over all node splits for decision trees created with sweep of threshold bounds on unfair information gain.
23


Reviews:
[{"review_id": "yLI8HOKzyj", "reviewer": "Reviewer_hxRN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents two different ways of training a decision tree with fairness criteria and then providing a zero-knowledge proof certifying the fairness without revealing any further information.\n", "summary_of_the_review": "Interesting and well-executed application of zero-knowledge proofs\n", "strength_and_weaknesses": "I think this is in a great application of zero-knowledge proofs.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "qNEq6CIXB30", "reviewer": "Reviewer_C481", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a fair decision tree algorithm with confidential certification of fairness during training. This paper first provides a novel fair decision tree algorithm and then provides a zero-knowledge proof based verifier using frequency counting. This paper also perform extensive experiments to demonstrate the effectiveness of the fair training and also the auditing of fairness.  ", "summary_of_the_review": "This paper provides the first practical and efficient method for auditing fairness during training without revealing data or the model. This paper also provides extensive experiments to verify the accuracy, fairness, running time, and scalability.", "strength_and_weaknesses": "Strengths: 1. The proposed method is built upon standard protocols. It is efficient and secure. \n2. The proposed method can be easily extended to various fairness metrics.\nWeaknesses: 1. The data or the model are not revealed to the auditors. It would be better if the authors could discuss or demonstrate through experiments about the confidentiality from an adversary perspective.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EZTMhYCvMTe", "reviewer": "Reviewer_iYrA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers achieving the zero knowledge fair decision tree learning algorithms to guarantee confidentiality both the model and training data. An extension to ensembles of trees is also proposed. ", "summary_of_the_review": "The paper proposed a zero knowledge fair decision tree learning algorithm and verify the effectiveness and efficiency via benchmark datasets. Overall, I think the current paper is good.", "strength_and_weaknesses": "Strength:\n1. The idea of considering confidential proof of fairness for training is interesting. \n2. They design and implement the zero knowledge proof protocol for verifying the fairness and efficiency. \n3. They conduct experiments for verifying the effectiveness and efficiency of proposed methods. \nWeakness:\n1. The paper proposed a method for ZK proof of decision tree training process. Also the authors mention that \"Our objective in this work is to provide a company with an approach that can be used to prove to a third party the fairness of a machine learning model trained and deployed by that company\". It seems that the proposed method does not meet the proposed goal. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%