# Post-quantum hash functions using $\mathrm{SL}_{n}(\mathbb{F}_{p})$

Corentin Le Coz Supported by the Israel Science Foundation (grant no. 2919/19)
Faculty of Mathematics, Technion, Israel<EMAIL_ADDRESS>
Department of Computer Science, University of York, UK<EMAIL_ADDRESS>
Department of Geometry and Topology, University of Seville, Spain,
<EMAIL_ADDRESS>
Department of Mathematics, University of Virginia<EMAIL_ADDRESS>
Computer Science and Mathematics Departments, Queens College CUNY, Department
of Computer Science, University of York, UK<EMAIL_ADDRESS>Christopher Battarbee  Faculty of Mathematics, Technion, Israel,
<EMAIL_ADDRESS>
Department of Computer Science, University of York, UK<EMAIL_ADDRESS>
Department of Geometry and Topology, University of Seville, Spain,
<EMAIL_ADDRESS>
Department of Mathematics, University of Virginia<EMAIL_ADDRESS>
Computer Science and Mathematics Departments, Queens College CUNY, Department
of Computer Science, University of York, UK<EMAIL_ADDRESS>Ramón
Flores Partially supported by grant PID2020-117971GB-C21 of the Spanish
Ministry of Science and Innovation, and grant FQM-213 of the Junta de
Andalucía. Faculty of Mathematics, Technion, Israel<EMAIL_ADDRESS>
Department of Computer Science, University of York, UK<EMAIL_ADDRESS>
Department of Geometry and Topology, University of Seville, Spain,
<EMAIL_ADDRESS>
Department of Mathematics, University of Virginia<EMAIL_ADDRESS>
Computer Science and Mathematics Departments, Queens College CUNY, Department
of Computer Science, University of York, UK<EMAIL_ADDRESS>
Thomas Koberda Partially supported by NSF grant DMS-2002596 Faculty of
Mathematics, Technion, Israel<EMAIL_ADDRESS>
Department of Computer Science, University of York, UK<EMAIL_ADDRESS>
Department of Geometry and Topology, University of Seville, Spain,
<EMAIL_ADDRESS>
Department of Mathematics, University of Virginia<EMAIL_ADDRESS>
Computer Science and Mathematics Departments, Queens College CUNY, Department
of Computer Science, University of York, UK<EMAIL_ADDRESS>and
Delaram Kahrobaei Partially supported by a Canada’s New Frontiers in Research
Fund, under the Exploration grant entitled “Algebraic Techniques for Quantum
Security” as well as a grant from CUNY. Faculty of Mathematics, Technion,
Israel<EMAIL_ADDRESS>
Department of Computer Science, University of York, UK<EMAIL_ADDRESS>
Department of Geometry and Topology, University of Seville, Spain,
<EMAIL_ADDRESS>
Department of Mathematics, University of Virginia<EMAIL_ADDRESS>
Computer Science and Mathematics Departments, Queens College CUNY, Department
of Computer Science, University of York, UK<EMAIL_ADDRESS>
###### Abstract

We define new families of Tillich-Zémor hash functions, using higher
dimensional special linear groups over finite fields as platforms. The Cayley
graphs of these groups combine fast mixing properties and high girth, which
together give rise to good preimage and collision resistance of the
corresponding hash functions. We justify the claim that the resulting hash
functions are post-quantum secure.

##  1 Introduction

Hash functions obtained from families of expander graphs were introduced by
Charles-Lauter-Goren in [CLG08], where they were in turn inspired by a scheme
of Tillich-Zémor [TZ94a]. Charles-Lauter-Goren considered specific families of
expander graphs discovered by Lubotzky-Phillips-Sarnak [LPS88] and Pizer
[Piz90]. The Charles-Lauter-Goren construction is quite general, and can be
applied to any expander family in which finding cycles is hard, and thereby
furnishes collision resistant hash functions. Similar schemes have been
proposed by several authors; see [SS16, BSV17, GM18], and [Sos18] for a survey
on this topic.

Interest in hash functions based on novel platforms fits into the context of
recent efforts to modernize existing hash functions, and to adapt them to the
design and security of hash-based consensus mechanisms, most notably with
respect to blockchains [Bor20], and especially in light of the recently proved
practicality of finding collisions in the SHA-1 hashing algorithm [SBK+17].

The general idea behind Tillich-Zémor hash functions is the following. Fixing
a base vertex, the input of the hash function is interpreted as a sequence of
instructions, resulting in a non-backtracking path in a $d$-regular graph. The
output of the hash function is the endpoint vertex of the path. More
precisely, the input is a string of numbers in

$[d-1]\vcentcolon=\\{1,2,\ldots,d-1\\}$

of arbitrary length, and the output is the vertex obtained by performing a
simple walk starting at a base vertex, using the elements of $[d-1]$ as
transition data for subsequent steps in the walk. See Definition 2.3 below for
details.

A well-constructed hash function is an efficiently computable function which
enjoys two main features. The first is _preimage resistance_ , which means
that given a point in the hash value, it is computationally hard to find an
input that maps to that hash value. The second, is _collision resistance_ ,
which requires the problem of finding distinct inputs with the same output to
be computationally difficult.

The main goal of this paper is to propose a new Goren-Lauter-Charles–type
scheme, where the hash functions use Cayley graphs of the special linear
groups $\operatorname{SL}_{n}(\mathbb{F}_{p})$ as platforms, where here $p$ is
prime and $n\geq 3$. A crucial observation is that, in schemes using these
groups as a platform, the problem of finding a preimage or a collision
corresponds to finding factorizations of the identity matrix with prescribed
factors. With this observation in hand, and by taking into account recent work
of Arzhantseva-Biswas [AB22] concerning the expanding properties of the Cayley
graphs of these groups, we offer a detailed study of the security of our
protocol. In particular, we have the following:

  * •

_Preimage resistance_. In Proposition 2.5, we collect the expansion properties
the family of Cayley graphs $\\{G_{n,p}\\}_{p}$ of the groups
$\operatorname{SL}_{n}(\mathbb{F}_{p})$, where $n\geq 3$ is fixed and where
$p$ tends to infinity. Expansion in this family of graphs guarantees good
mixing properties, because under these conditions the random walk gives a good
approximation to the uniform distribution after $O(\log p)$ steps. In
particular, the likelihood of success of an indistinguishability attack is
strictly bounded, and tends to $1/2$ as the order of the group tends to
infinity; see Proposition 3.3.

  * •

_Collision resistance_. The strength of our hash function with respect to
collision resistance is mainly based on the absence of small cycles in the
Cayley graphs of the underlying groups. In fact, Proposition 3.1 provides a
lower bound on the girth of the graphs $\\{G_{n,p}\\}_{p}$ on the order of
$\log p$. It follows that a factorization of the identity, which is easily
seen to be equivalent to finding a collision for the hash function, is in turn
equivalent to solving over the a system of $n^{2}$ equations in a number of
variables that is $O(\log p)$, over the field $\mathbb{F}_{p}$. In full
generality, solving such systems of equations is NP-hard.

Replacing the problem of factoring the identity with the problem of factoring
an arbitrary group element yields a similar system of equations, lending
further evidence of resistance of the hash function to finding preimages; see
Section 3.2.

For $n=2$, certain Cayley graphs of the groups
$\operatorname{PSL}_{2}(\mathbb{F}_{p})$ give rise to the celebrated
Lubotzky–Phillips–Sarnak expander graphs [LPS88], which were then used to
build hash functions in [CLG08]. A successful collision attack (i.e. an
efficient computation of a collision) was found in [TZ08], by taking
coefficients in $\mathbb{Z}[i]$ and then reducing to a system of equations of
degree two. The essentially different nature of higher dimensional special
linear groups gives evidence of additional security, and makes it likely that
these attacks are far more difficult to execute for the hash functions
proposed here.

Considering symmetric generating sets enables us to employ results from the
theory of simple random walks in simplicial graphs. Nevertheless, the fact
that we restrict ourselves to non backtracking random walks precludes the use
of multiplicativity of the has function, and thus complicates parallel
computation. We discuss these issues in Section 3.4.

##### Structure of the paper:

In Section 2 we give the relevant group theoretic background, define the hash
functions, prove the expansion property of the Cayley graphs, and exhibit
concrete examples. In Section 3, we describe the various properties of our
scheme: namely, we relate free generation with a lower bound on the girth; we
then describe the role of polynomial equations in preimage finding and in
collision resistance, as well as the role of mixing in indistinguishability
attacks. Finally, we discuss multiplicativity and parallel computing, showing
that the collision attack from Grassl et. al. [GIMS11] using palindromes does
not break the scheme presented here. Section 4 concludes the paper.

##### Acknowledgments:

The authors would like to thank Ludovic Perret, Hadi Salmasian, Vladimir
Shpilrain, and Bianca Sosnovski for helpful comments and discussions.

##  2 Definition of the hash functions

This section defines our hash functions and exhibits concrete instances. We
start by recalling some relevant background material which will be essential
in our construction and in the sequel.

###  2.1 Background about special linear groups

For general results about special linear groups over finite fields, we refer
the reader to Hall’s book [Hal15]. In this section we concentrate on a number
of properties established by Arzhantseva-Biswas in their article [AB22]. We
summarize their results in the following theorem:

######  Theorem 2.1 (Arzhantseva-Biswas [AB22]).

Let $n\geq 2$ and let $p$ a prime. Write
$\pi_{p}:\operatorname{SL}_{n}(\mathbb{Z})\to\operatorname{SL}_{n}(\mathbb{F}_{p})$
for the canonical projection given by reduction modulo $p$. There exist
matrices $\tilde{A},\tilde{B}\in\operatorname{SL}_{n}(\mathbb{Z})$ such that:

  1. (i)

There exists a prime $p_{0}$ such that for all $p\geq p_{0}$, the matrices
$\tilde{A}_{p}\vcentcolon=\pi_{p}(\tilde{A})$ and
$\tilde{B}_{p}\vcentcolon=\pi_{p}(\tilde{B})$ generate
$\operatorname{SL}_{n}(\mathbb{F}_{p})$.

  2. (ii)

If $\langle\tilde{A},\tilde{B}\rangle$ is the subgroup generated by
$\tilde{A}$ and $\tilde{B}$ inside of $\operatorname{SL}_{n}(\mathbb{Z})$,
then $\langle\tilde{A},\tilde{B}\rangle$ is isomorphic to $F_{2}$, the free
group of rank two.

  3. (iii)

The diameter of the Cayley graph $G_{n,p}$ of
$\operatorname{SL}_{n}(\mathbb{F}_{p})$ with respect to $\\{\tilde{A}_{p}^{\pm
1},\tilde{B}_{p}^{\pm 1}\\}$ is $O(\log p)$.

Observe that for $n\geq 3$, items (i) and (ii) reflect the fact that the
subgroup of $\operatorname{SL}_{n}(\mathbb{Z})$ generated by $\tilde{A}$ and
$\tilde{B}$ is usually a thin subgroup of $\operatorname{SL}_{n}(\mathbb{R})$.
The fact that $\tilde{A}_{p}$ and $\tilde{B}_{p}$ generated the corresponding
finite quotients for all but finitely many values of $p$ is a reflection of
strong/superstrong approximation. In turn, item (iii) implies that the girth
of $G_{n,p}$ is optimal, because the graphs $\\{G_{n,p}\\}_{p}$ form a family
of expander graphs (see Proposition 2.5 below).

######  Remark 2.2.

When using the Cayley graphs $G_{n,p}$ as a platform, we think of $n$ as being
fixed and $p$ as modulating the level of security, with the trade-off being
that the hash functions functions become more expensive to compute for large
$p$.

Possible choices for $\tilde{A}$ and $\tilde{B}$ are given by:

$\tilde{A}=\begin{pmatrix}1&a&0&0&\ldots&0\\\ 0&1&a&0&\ldots&0\\\
0&0&1&a&\ldots&0\\\ \vdots&&&&&\vdots\\\ &&&&\ldots&a\\\ 0&0&0&0&\ldots&1\\\
\end{pmatrix},\,\tilde{B}=\begin{pmatrix}1&0&0&\ldots&&0\\\ b&1&0&\ldots&&0\\\
0&b&1&\ldots&&0\\\ 0&0&b&\ldots&&0\\\ \vdots&&&&\vdots&\vdots\\\
0&0&0&\ldots&{b}&1\\\ \end{pmatrix}\in\operatorname{SL}_{n}(\mathbb{F}_{p}),$

with $a,b\geq 2$. These matrices will be crucial in the description of our
hash function.

###  2.2 The general construction

We now use matrices given in [AB22] to define an explicit family of hash
functions.

######  Definition 2.3 (Special linear group based hash functions).

Let $n\geq 3$ and let $p$ be a prime number. Let $a,b,\ell\geq 2$ that
satisfy:

  * •

If $n=3$, $a\equiv 1(\bmod\,3)$, $b\equiv-1(\bmod\,3)$ and $\ell=4^{k}$ for
some positive integer $k$.

  * •

If $n\geq 4$, there exists a prime $q$ such that $n\equiv a\equiv b\equiv
1(\bmod\,q)$ and $\ell$ is at least $3(n-1)$ and is of the form $q^{k+1}+1$
for some integer $k$.

Consider the matrices $\tilde{A}$ and $\tilde{B}$ from the previous section.
In the following we will denote $A\equiv\tilde{A}^{\ell}$ and
$B\equiv\tilde{B}^{\ell}$.

We use the notation $[k]$ to denote the set of integers in $[k]$, and
$[k]^{*}$ to denote the set of finite strings of integers in $[k]$. We now
define the hash function
$\varphi:[3]^{*}\to\operatorname{SL}_{n}(\mathbb{F}_{p})$. We start by
choosing bijections

$s:[4]\to\\{A^{\pm 1},B^{\pm 1}\\},\quad s_{\lambda}:[3]\to\\{A^{\pm 1},B^{\pm
1}\\}\setminus s(\lambda)$

for each $\lambda\in[4]$.

Then, given

$x=(x_{i})_{1\leq i\leq k}\in[3]^{k},$

we have the following inductive definition:

  * •

$B_{1}=s(x_{1})$,

  * •

$B_{i}=s_{\lambda}(x_{i})$ with $\lambda=s^{-1}(B_{i-1}^{-1})$, for $2\leq
i\leq k$.

Finally, we set $\varphi(x)\vcentcolon=B_{1}\cdots
B_{k}\in\operatorname{SL}_{n}(\mathbb{F}_{p})$.

######  Remark 2.4.

Note that $G_{n,p}$ is $4$–regular, so that after the first bit $x_{1}$ of the
input $x$, there are exactly three non-backtracking edges in the graph by
which to proceed. The input $x$ can thus be viewed as encoding a reduced word
in the free group $F_{2}$. The lack of backtracking in the resulting walk on
$G_{n,p}$ is crucial for the avoidance of collisions, as well as for the
reduction of mixing time.

As stated in [AB22], the elements $\\{A^{\pm 1},B^{\pm 1}\\}$ generate a free
subgroup of $\operatorname{SL}_{n}(\mathbb{Z})$ and generate
$\operatorname{SL}_{n}(\mathbb{F}_{p})$ for all but finitely many values of
$p$, and these facts give rise to strong preimage and collision resistance of
the resulting hash functions.

###  2.3 Expansion

For us to implement the Charles-Lauter-Goren approach, we must take advantage
of the good mixing properties of the expander graphs.

######  Proposition 2.5.

For $n\geq 3$ fixed and $p\rightarrow\infty$, the sequence $\\{G_{n,p}\\}_{p}$
is a family of expander graphs.

###### Sketch of proof.

By item (i) of Theorem2.1, there exists a prime $p_{0}$ such that for all
$p\geq p_{0}$, the matrices $\tilde{A}_{p}\vcentcolon=\pi_{p}(\tilde{A})$ and
$\tilde{B}_{p}\vcentcolon=\pi_{p}(\tilde{B})$ generate
$\operatorname{SL}_{n}(\mathbb{F}_{p})$. Now, since
$\operatorname{SL}_{n}(\mathbb{Z})$ has property (T) for $n\geq 3$ [BdlHV08],
and $\operatorname{SL}_{2}(\mathbb{Z})$ has property $(\tau)$ with respect to
the family of congruence subgroups[Lub05], the proposition follows. ∎

An immediate consequence of this proposition is that the random walk
approximates the uniform distribution after $O(\log p)$ steps in the
corresponding graph $G_{n,p}$. As we will elaborate in Section 3.3, this
result is relevant for the purpose of analyzing preimage resistance to
indistinguishability attacks; see Proposition 3.3, in particular. We note that
in [BSV17], random walks are conducted on Cayley graphs with respect to non-
symmetric generating sets, and thus their asymptotic behavior is less clear.
Similar issues arise in [TNS20], since then hash values could be restricted to
a proper subgroup. As stated in [AB22], we note that one can effectively
compute the bound lower $p_{0}$. No explicit bound on $p_{0}$ has been given,
though by combining existing results one can probably prove that $p$ need not
be very large, likely on the order of magnitude of $n$; see for instance
[GV12, Appendix] and [Gur99, Theorem D]. Note that the larger the value of the
prime $p$, the more secure the hash function.

###  2.4 A concrete example

We finish this section by describing a family of concrete examples of hash
functions, which are constructed for the specific values $a=4$, $b=2$ and
$\ell=4$. We do not know what minimal value of $n$ would ensure security.

######  Definition 2.6.

Let $p$ be a prime, and let

$A=\begin{pmatrix}1&4&0&0&\ldots&0\\\ 0&1&4&0&\ldots&0\\\ 0&0&1&4&\ldots&0\\\
\vdots&&&&&\vdots\\\ &&&&\ldots&4\\\ 0&0&0&0&\ldots&1\\\
\end{pmatrix}^{4},\,B=\begin{pmatrix}1&0&0&\ldots&&0\\\ 2&1&0&\ldots&&0\\\
0&2&1&\ldots&&0\\\ 0&0&2&\ldots&&0\\\ \vdots&&&&\vdots&\vdots\\\
0&0&0&\ldots&{2}&1\\\
\end{pmatrix}^{4}\in\operatorname{SL}_{n}(\mathbb{F}_{p}),$

Let $s(1)=A$, $s(2)=B$, $s(3)=A^{-1}$, $s(4)=B^{-1}$. We define the functions
$\\{s_{\lambda}\\}_{\lambda\in[4]}$ as follows:

  * •

$s_{1}(1)=B$, $s_{1}(2)=A^{-1}$, $s_{1}(3)=B^{-1}$,

  * •

$s_{2}(1)=A$, $s_{2}(2)=A^{-1}$, $s_{2}(3)=B^{-1}$,

  * •

$s_{3}(1)=A$, $s_{3}(2)=B^{-1}$, $s_{3}(3)=B$,

  * •

$s_{4}(1)=A$, $s_{4}(2)=A^{-1}$, $s_{4}(3)=B$,

Given an input sequence $x=\\{x_{i}\\}_{i\in[1,k]}\in[3]^{k}$, we inductively
define:

  * •

$B_{1}=s_{1}(x_{1})$

  * •

$B_{i}=s_{\lambda}(x_{i})$, with $\lambda=s^{-1}(B_{i-1}^{-1})$, for each
$k\in[2,k]$.

Then, the sequence $x$ is hashed to the matrix:

$\varphi(x)=B_{1}\cdots B_{k}.$

Thus, we obtain a hash function for every $n\geq 3$.

##  3 Properties of the constructed hash functions

In this section we use graph and group-theoretic machinery to describe the
security of the hash functions defined above. We center our analysis on
resistance to preimage and collision breaking. The exposition is divided into
three parts: first, we establish a lower bound in the girth of the Cayley
graphs of the group $\operatorname{SL}_{n}(\mathbb{F}_{p})$ with respect to
the generating system $\\{A_{p}^{\pm 1},B_{p}^{\pm 1}\\}$; second, we describe
the consequences of girth bounds for collision resistance; third, we
investigate resistance of the protocol against an indistinguishability attack.

###  3.1 Free groups and girth

The following proposition is in the spirit of [BSV17].

######  Proposition 3.1.

Let $A,B\in\operatorname{SL}_{n}(\mathbb{Z})$ such that the entries of $A^{\pm
1}$ and $B^{\pm 1}$ are bounded in absolute value by a positive constant $c$.
If $A$ and $B$ generate a free subgroup of
$\operatorname{SL}_{n}(\mathbb{Z})$, then the girth of the Cayley graph of
$\langle A_{p},B_{p}\rangle\leq\operatorname{SL}_{n}(\mathbb{F}_{p})$, with
respect to $\\{A_{p}^{\pm 1},B_{p}^{\pm 1}\\}$ is at least

$\left\lfloor\frac{\log(p-1)}{\log nc}\right\rfloor.$

###### Proof.

For any reduced word $w$ in $A^{\pm 1}$ and $B^{\pm 1}$, we write
$w_{\mathbb{Z}}$ (resp. $w_{\mathbb{F}_{p}})$) for the projection of $w$ to
$\operatorname{SL}_{n}(\mathbb{Z})$ (resp.
$\operatorname{SL}_{n}(\mathbb{F}_{p})$). It follows by a straightforward
induction on $k$ that, if $w$ has length $k$, then the entries of
$w_{\mathbb{Z}}$ cannot exceed $(nc)^{k}$ in absolute value. Now, let $\ell$
be the girth of the corresponding Cayley graph. Then, there exists a non
trivial reduced word $w$ of length $\ell$ such that $w_{\mathbb{F}_{p}}=1$. It
follows that $w_{\mathbb{Z}}$ is of the form $1+pM$, where $M$ is an integer
matrix. Since $w$ is non trivial and since $\\{A,B\\}$ generate a rank two
free subgroup of $\operatorname{SL}_{n}(\mathbb{Z})$, the matrix $M$ is
nonzero. We conclude that $w_{\mathbb{Z}}$ has an entry of absolute value at
least $p-1$. Since the entries of $w_{\mathbb{Z}}$ cannot exceed $(nc)^{k}$ in
absolute value, we have that the length $\ell$ of $w$ is bounded below by
$\lfloor\frac{\log(p-1)}{\log nc}\rfloor$, the desired conclusion. ∎

###  3.2 Preimage and collision resistance, and post-quantum heuristics

We now analyze the resistance of our model to finding preimages and to
collisions. Observe that finding a preimage of a particular hash value (resp.
finding a collision of hash values) is equivalent to finding a factorization
of a given group element (resp. of the identity) in
$\operatorname{SL}_{n}(\mathbb{F}_{p})$ with respect to the generating set.

The matrices $A_{p},B_{p}$ involved have order $p$, so a factorization can be
seen as a family of equations $\\{\eqref{equation: Em}\\}_{m\geq 0}$ with
variables

$k_{1},\ldots,k_{m},\ell_{1},\ldots,\ell_{m}\in\mathbb{F}_{p}$

satisfying:

$A^{k_{1}}B^{\ell_{1}}\ldots A^{k_{m}}B^{\ell_{m}}=M,$

for a given challenge $M\in\operatorname{SL}_{n}(\mathbb{F}_{p})$. Note that
there are trivial solutions to preimage and collision breaking of the hash
function, since $A_{p}^{p}$ is the identity. Since the girth of $G_{n,p}$ is
$O(\log p)$, we consider nontrivial solutions to preimage or collision
breaking to be ones where

$C_{1}\log p\leq\sum_{i=1}^{m}(k_{i}+\ell_{i})\leq C_{2}\log p,$

where $C_{1}$ and $C_{2}$ are positive constants depending on $n$ but not on
$p$. Note that estimates for $C_{1}$ and $C_{2}$ can be produced, and that
Proposition 3.1 furnishes an estimate for $C_{1}$, for instance. Sharp values
for $C_{1}$ and $C_{2}$ are of relatively minor consequence for us.

Each entry of the left-hand side matrix in equation $\eqref{equation: Em}$ is
polynomial in $k_{1},\ldots,k_{m},\ell_{1},\ldots,\ell_{m}$. Thus, the
equation $\eqref{equation: Em}$ corresponds to a system of $n^{2}$
multivariate polynomial equations over $\mathbb{F}_{p}$.

Solving multivariate polynomial equations over a finite field is known to be
NP-hard [GJ79], which suggests a good level of security. Moreover, the
reduction to solving multivariate polynomials, a class of hardness problems
considered for standardization by NIST, provides a certain degree of
confidence that the hash function is post-quantum. We contrast this approach
with schemes based on isogeny graphs, which reduce to a more well-defined
problem, albeit one not know to be NP-hard.

NP-hardness of a class of problems is a worst case complexity property, and
for certain NP-hard classes of problems, relatively simple and efficient
algorithms can find solutions in the vast majority of cases. Thus, NP-hardness
of the underlying problem is not a guarantee of post-quantum behavior of the
hash function.

A more compelling case for the hash function to be post-quantum arises from
empirical difficulty of factoring in special linear groups over finite fields.
For instance, in [FPPR11], subexponential factorization algorithms were found
for $\operatorname{SL}_{2}(\mathbb{F}_{2^{k}})$, and these were only found in
2011. These algorithms rely essentially on the fact that the matrices are
$2\times 2$, and on the fact that the underlying field has characteristic two.
Thus, the methods do not generalize in any straightforward way to larger
dimensional special linear groups nor to fields with odd characteristic. In
practice, factoring matrices over finite fields is quite difficult, and
implemented algorithms are inefficient. Hardness appears to be optimized when
the system of equations resulting from $\eqref{equation: Em}$ is neither
underdetermined nor overdetermined, i.e. when the number of equations and
variables is comparable. Thus, the larger the value of $p$ the more secure the
hash function, at the expense of computational time and space, and the balance
of degrees of freedom and constraints occurs when $n^{2}\sim\log p$, or in
other words when $n$ is approximately the square root of the logarithm of $p$.
We may then expect the factorization problem to take exponential time in the
number of variables in this case, and by resistant to the speedup resulting
from quantum attacks.

###  3.3 The mixing property and indistinguishability attacks

In this section we study how to formalize the relationship between mixing
properties and indistinguishability, and how expansion weakens
indistinguishability attacks and thus gives heuristic confidence in pre-image
breaking resistance.

####  3.3.1 The mixing property

By the mixing property, we mean that the output vertex of a random input — in
our case a random walk — approaches the uniform distribution on the hash
space. When the random walk approaches the uniform distribution quickly,
mixing is observed even when the input messages have relatively small length,
say polynomial in $\log p$. More precisely, we have the following corollary of
result of Alon-Benjamini-Lubetzky-Sodin [ABLS07], which characterizes the rate
at which a random walk on a graph converges to the uniform distribution in
terms of the spectral properties of its adjacency matrix:

######  Theorem 3.2.

[ABLS07, Theorem 1.1, cf. proof of Theorem 1.3] Suppose $d>2$. Let
$X_{0},X_{1},\ldots,X_{\ell}$ be a non backtracking random walk on a
$d$–regular connected graph $G$ with $N$ vertices. There is a constant $C>0$
such that whenever $\ell\geq C\cdot\log N$ we have

$\left|\operatorname{Pr}(X_{\ell}=v)-1/N\right|\leq 1/N^{2},$

for every vertex $v$ of $G$.

Examining the proof given in [ABLS07], one finds that the rate of mixing
depends not so much on the graph $G$, as much as on eigenvalues of the
adjacency matrix of $G$. Thus, if $G$ is a member of a sequence
$\\{G_{i}\\}_{i\in\mathbb{N}}$ of expander graphs, we may take the constant
$C$ in Theorem 3.2 to depend only on the expansion constant of the family.

It is well-known that mixing properties are desirable in Tillich-Zémor hashing
schemes; see [CLG08, TZ08]. As explained in [TZ08], mixing is particularly
relevant when the hash functions are used in protocols whose security relies
on the random oracle model; see [BR93] for example of such protocols. The
relevance of this approach depends on the distribution of possible messages
and in particular on how they are encoded, a question we do not address in the
present paper.

Surprisingly few mathematical statements addressing the relationship between
mixing and attacks are present in the literature; an example can be found in
[Ste21, Theorem 3], in the context of commitment schemes. The following
proposition, which is the main goal of this section, fits in this context. We
will give precise definitions of all the terms involved below.

######  Proposition 3.3.

Let $\varphi:[3]^{k}\to\operatorname{SL}_{n}(\mathbb{F}_{p})$ the hash
function of Definition 2.3, and let
$N=|\operatorname{SL}_{n}(\mathbb{F}_{p})|$. There is a positive constant $C$
such that if $k\geq C\cdot\log N$, then a generic indistinguishability attack
wins with probability at most $1/2+1/N$.

In particular we have the following immediate consequence. Note that
probability $1/2$ is the best we can hope for if an adversary is asked to
distinguish between two situations, because such an adversary can always
choose at random with success probability $1/2$.

######  Corollary 3.4.

In the previous notation, when $p$ tends to infinity, the probability of
winning for a generic indistinguishability attack tends to $1/2$.

The complexity of the so-called generic indistinguishability attack mentioned
here is linear in the number of vertices of the graph involved. Thus, in the
specific case of Proposition 3.3 it has exponential complexity, since the size
of $\operatorname{SL}_{n}(\mathbb{F}_{p})$ is polynomial in $p$, and our
reference is $\log p$. Thus, we obtain a more general notion of
indistinguishability than in [KL21, §6.8], restricted to polynomial-time
algorithms.

The proof of Proposition 3.3 will be obtained as a corollary of the more
general Proposition 3.5, and of the mixing properties of the random walk on
$\operatorname{SL}_{3}(\mathbb{F}_{p})$. We elaborate on these ideas
presently.

####  3.3.2 Generic attack of indistinguishability challenge

The goal of this subsection is to define indistinguishability challenges,
investigate possible attacks, and to justify to what extent the hash functions
defined in this paper are resistant to these attacks.

##### Indistinguishability challenge.

Let $H$ be a finite set. The challenger $\mathcal{C}$ has access to two public
probability distributions $\mu_{X}$ and $\mu_{Y}$, which take values in $H$.
These distributions are a priori distinct, and we think of them as being
“close”. $\mathcal{C}$ picks $X\in H$ (resp. $Y\in H$) at random, according to
the distribution $\mu_{X}$ (resp. $\mu_{Y}$). $\mathcal{C}$ then flips a
balanced coin $P\in\\{0,1\\}$ and sends to their adversary $\mathcal{A}$ the
element $Z\in H$, which satisfies:

  * •

$Z=X$ if $P=0$,

  * •

$Z=Y$ if $P=1$.

Given $Z$, the goal of $\mathcal{A}$ is to guess $P$. In other words,
$\mathcal{A}$ needs to decide if $\mathcal{C}$ sent an element of $H$
according to the distribution of $\mu_{X}$ or of $\mu_{Y}$.

##### Generic indistinguishability attack.

The adversary $\mathcal{A}$ knows the public distributions $\mu_{X}$ and
$\mu_{Y}$. For each binary relation

$*\in\\{<,=,>\\},$

we denote by $H_{*}$ the set of $h\in H$ such that
$\operatorname{Pr}(Y=h)*\operatorname{Pr}(X=h)$. The best strategy available
to $\mathcal{A}$ is the following:

  * •

If $Z\in H_{>}$, then $\mathcal{A}$ guesses $P=1$,

  * •

If $Z\in H_{=}$, then $\mathcal{A}$ guesses a random $P\in\\{0,1\\}$,

  * •

If $Z\in H_{<}$, then $\mathcal{A}$ guesses $P=0$.

In the following proposition, we relate the $\ell^{\infty}$-distance between
the distributions $\mu_{X}$ and $\mu_{Y}$ on one hand, and the chances of
success of $\mathcal{A}$ following the strategy above on the other hand.

######  Proposition 3.5.

Let $\varepsilon>0$ be such that

$|\operatorname{Pr}(X=h)-\operatorname{Pr}(Y=h)|\leq\varepsilon,$

for every $h\in H$. Then, $\mathcal{A}$ guesses the correct $P$ with
probability at most

$\frac{1}{2}+\varepsilon\frac{\\#H}{4}.$

######  Remark 3.6.

The probability that $\mathcal{A}$ guesses correctly is $1/2$ when the
strategy is to guess a random $P\in\\{0,1\\}$, so Proposition 3.5 above
essentially says that $\mathcal{A}$ cannot do much better, provided the
distributions are sufficiently close.

###### Proof of Proposition 3.5.

Let $P_{\mathcal{A}}\vcentcolon=\operatorname{Pr}(\mathcal{A}\text{ is
right})$. We have

$P_{\mathcal{A}}=\sum_{h\in H}\operatorname{Pr}(\mathcal{A}\text{ is
right}\mid Z=h)\operatorname{Pr}(Z=h)$

For each binary relation $*\in\\{<,=,>\\}$ let

$P_{*}=\sum_{h\in H_{*}}\operatorname{Pr}(\mathcal{A}\text{ is right}\mid
Z=h)\operatorname{Pr}(Z=h).$

Then, we have $P_{\mathcal{A}}=P_{<}+P_{=}+P_{>}$. We analyze each of these
terms independently.

  * •

If $Z\in H_{=}$, then $\mathcal{A}$ guesses a random $P\in\\{0,1\\}$. Thus,

$\displaystyle P_{=}$ $\displaystyle=\sum_{h\in
H_{=}}\frac{\operatorname{Pr}(Z=h)}{2}$
$\displaystyle=\frac{\operatorname{Pr}(X=h)+\operatorname{Pr}(Y=h)}{4}.$

  * •

If $Z\in H_{<}$, then $\mathcal{A}$ guesses $P=0$. Thus,

$\displaystyle P_{<}$ $\displaystyle=\sum_{h\in
H_{<}}\operatorname{Pr}(P=0\mid Z=h)\operatorname{Pr}(Z=h)$
$\displaystyle=\sum_{h\in H_{<}}\operatorname{Pr}(Z=h\mid
P=0)\operatorname{Pr}(P=0)$ $\displaystyle=\sum_{h\in
H_{<}}\frac{\operatorname{Pr}(X=h)}{2}.$

  * •

If $Z\in H_{>}$, then $\mathcal{A}$ guesses $P=1$. Thus,

$\displaystyle P_{>}$ $\displaystyle=\sum_{h\in
H_{>}}\operatorname{Pr}(P=1\mid Z=h)\operatorname{Pr}(Z=h)$
$\displaystyle=\sum_{h\in H_{>}}\operatorname{Pr}(Z=h\mid
P=1)\operatorname{Pr}(P=1)$ $\displaystyle=\sum_{h\in
H_{>}}\frac{\operatorname{Pr}(Y=h)}{2}.$

So, we obtain

$P_{\mathcal{A}}=\frac{1}{2}\sum_{h\in
H}\max\\{\operatorname{Pr}(X=h),\operatorname{Pr}(Y=h)\\}.$

We can now give an upper bound on $P_{\mathcal{A}}$. We can assume without any
loss of generality that $\\#H_{<}\leq\frac{\\#H}{2}$. Then,

$\displaystyle P_{\mathcal{A}}$ $\displaystyle=\frac{1}{2}\sum_{h\notin
H_{<}}\operatorname{Pr}(Y=h)+\frac{1}{2}\sum_{h\in
H_{<}}\operatorname{Pr}(X=h)$ $\displaystyle\leq\frac{1}{2}\sum_{h\notin
H_{<}}\operatorname{Pr}(Y=h)+\frac{1}{2}\sum_{h\in
H_{<}}\left(\operatorname{Pr}(Y=h)+\varepsilon\right)$
$\displaystyle\leq\frac{1}{2}\sum_{h\in
H}\operatorname{Pr}(Y=h)+\varepsilon\frac{\\#H_{<}}{2}$
$\displaystyle\leq\frac{1}{2}+\varepsilon\frac{\\#H}{4}.\qed$

##### Generic indistinguishability attack in our framework.

In the framework of hash functions, we consider a function $\varphi:S\to H$,
where $S$ and $H$ are finite sets. The challenger $\mathcal{C}$ has two
variables in hand, namely $X^{\prime}\in S$ and $Y\in H$, both chosen
uniformly at random. The indistinguishablility challenge is now adapted to the
two variables $X\vcentcolon=\varphi(X^{\prime})$ and $Y$. We can now prove
Proposition 3.3.

###### Proof of Proposition 3.3.

From Theorem 3.2, there are constants $C,C^{\prime}>0$ such that after $C\log
N=C^{\prime}\log p$ steps, the non backtracking random walk on
$\operatorname{SL}_{n}(\mathbb{F}_{p})$ is at $\ell^{\infty}$-distance at most
$1/N^{2}$ from the uniform distribution. From Proposition 3.5, the generic
indistinguishability attack wins with probability at most $1/2+1/4N$. ∎

###  3.4 Multiplicativity and parallel computing

The hash functions considered in this article take as input a string of
integers in $[3]$, converting each integer into a matrix of the form
$\\{A^{\pm 1},B^{\pm 1}\\}$, and finally outputs the product of these
matrices.

The fact that we require the underlying walk to be non-backtracking implies
that this attribution is not locally determined: a given bit in the string is
mapped to a matrix that depends on the previous bits. This dependency can be
dramatic: for example, according to Definition 2.6 a sequence of the form
$133\cdots 3$ will be mapped to the product $B\cdot B\cdot B\cdots B$, while a
sequence of the form $333\ldots 3$ will be mapped to the product $B^{-1}\cdot
B^{-1}\cdot B^{-1}\cdots B^{-1}$. In particular, the last bit $3$ of these two
strings can be mapped to different matrices, depending on the first bit in the
string. The endpoints of the corresponding walk in in the Cayley graph may be
arbitrarily far away from each other.

As a consequence, the function $\varphi$ need not be multiplicative under
concatenation of strings. This lack of multiplicativity makes it difficult to
perform parallel computations with the given hash functions, as we now
investigate in more detail.

####  3.4.1 Good and bad tails

Recall that for a finite set $X$, the notation $X^{*}$ is used for the set of
finite length strings of elements of $X$. As before, the notation $[3]$
denotes the set $\\{1,2,3\\}$.

######  Definition 3.7.

Let $G$ be a finite group, generated by two elements $A$ and $B$. Let
$\tilde{\varphi}:[3]^{*}\to\\{A^{\pm 1},B^{\pm 1}\\}^{*}$.

A string $s\in[3]^{*}$ is called a _good tail_ with respect to
$\tilde{\varphi}$ if there exists $S\in\\{A^{\pm 1},B^{\pm 1}\\}$ such that
for every $s^{\prime}\in[3]^{*}$, the last letter of
$\tilde{\varphi}(s^{\prime}s)$ is $S$, where here $s^{\prime}s$ is the string
obtained from the concatenation of $s^{\prime}$ and $s$. A string which is not
a good tail is called a _bad tail_.

Local constraints in Definition 2.6, can be obtained by the following fact:

######  Fact 3.8.

The function

$\tilde{\varphi}:\\{x_{i}\\}\in[3]^{*}\mapsto\\{B_{i}\\}\in\\{A^{\pm 1},B^{\pm
1}\\}^{*}$

constructed in Definition 2.6 has the following good tails: 11, 31, 22, 32, 13
and 23.

###### Proof.

It is straightforward to check that:

  * •

any string ending in 11 or 31 outputs a string ending in $A$;

  * •

any string ending in 22 or 32 outputs a string ending in $A^{-1}$;

  * •

any string ending in 13 outputs a string ending in $B$;

  * •

any string ending in 23 outputs a string ending in $B^{-1}$. ∎

The following proposition shows that the attribution above is optimal.

######  Proposition 3.9.

Special linear group based hash functions (Definition 2.3) admit at most six
good tails of length two.

The bound in Proposition 3.9 is sharp, as shown via the attributions of
Definition 2.6. The proof of Proposition 3.9 will follow from the following
lemma:

######  Lemma 3.10.

Let

$\tilde{\varphi}:\\{x_{i}\\}\in[3]^{*}\mapsto\\{B_{i}\\}\in\\{A^{\pm 1},B^{\pm
1}\\}^{*}$

be a special linear group based hash function (Definition 2.3), and let
$b\in[3]$. There exists $b^{\prime}\in[3]$ such that $b^{\prime}b$ is a bad
tail with respect to $\tilde{\varphi}$.

###### Proof.

The only freedom that we have in the construction of Definition 2.3 is how we
define the maps $s_{i}$. We call elements of $\\{A^{\pm 1},B^{\pm 1}\\}$ _step
matrices_. Using $\tilde{\varphi}$, we say that the elements of $[3]$ are
_encoded_ by step matrices. We summarize the definitions of the maps $s_{i}$
in a table, with one row for each step matrix, and one column for each element
of $[3]$. Each cell from this tabular contains a step matrix.

To use this table, start from a string $\\{x_{i}\\}\in[3]^{*}$. Say that for
some $i>1$, we want to find the step matrix associated with $x_{i}$. Let $S$
be the step matrix encoding $x_{i-1}$. Then, the step matrix encoding $x_{i}$
is the step matrix in the cell located in the row labelled by $S$ and in the
column labelled by $x_{i}$.

It follows from the definition of the maps $s_{i}$ that for each step matrix
$S$, the row labelled by $S$ contains exactly the three matrices in the set
$\\{A^{\pm 1},B^{\pm 1}\\}\setminus S^{-1}$. The attributions of Definition
2.6 can be described as in Figure 1.

Figure 1: Description of the maps $s_{i}$ in Definition 2.6 last step matrix | 1 | 2 | 3
---|---|---|---
| $A^{-1}$ | $B$ | $A^{-1}$ | $B^{-1}$
| $B^{-1}$ | $A$ | $A^{-1}$ | $B^{-1}$
| $A$ | $A$ | $B^{-1}$ | $B$
| $B$ | $A$ | $A^{-1}$ | $B$

Moreover, since each matrix can actually be the last step matrix used, every
cell of the table can potentially be used. Fix an element $b\in[3]$, and
assume for a contradiction that every integer $b^{\prime}\in[3]$ has the
property that $b^{\prime}b$ is a good tail. The column corresponding to each
$b^{\prime}$ has to contain at least two different step matrices. This implies
that, in the row labelled by $b$, at least two cells contain the same step
matrix. Since this is true for each $b^{\prime}\in[3]$, this implies in
particular that there is a step matrix $S$ that is contained three times in
the column labelled by $b$. The fourth cell of this column cannot be part of
the row labelled by $S$ since this would give rise to another $S$ in a
different column. This implies that the label $S^{\prime}$ of this row appears
in a cell of another column. Additionally, this column contains a cell with
step matrix not equal to $S^{\prime}$. Then, the label $b^{\prime}\in[3]$ of
this column gives us an integer having the property that inputs ending by
$b^{\prime}b$ can have either $S$ or another matrix as a final matrix. This is
a contradiction and concludes the proof of the lemma. ∎

###### Proof of Proposition 3.9.

From Lemma 3.10, to each integer of $[3]$ corresponds at least on bad tail,
giving three different bad tails. ∎

As remarked previously, Definition 2.6 shows that the estimate in Proposition
3.9 is sharp, and so that in some sense, we have found an optimal way of
defining the maps $s_{i}$.

####  3.4.2 Multiplicativity

It follows from the discussion of good and bad tails above that
multiplicativity of the hash function can be obtained by restricting to
sequences whose product ends with the matrix $s(1)$.

######  Fact 3.11.

In Definition 2.6, we have
$\varphi(s_{1}*s_{2})=\varphi(s_{1})\cdot\varphi(s_{2})$, provided $s_{1}$
ends with $11$ or $31$.

####  3.4.3 Parallel computing

Multiplicativity of the hash function under suitable conditions can be
leveraged to compute its values by parallel computation. First, look for good
tail substrings, namely: 11, 31, 22, 32, 13 or 23. For generic messages, one
would expect such substrings to be quite common. Next, split the input
immediately following one of these strings, and apply a slightly modified hash
function (i.e. using the relevant $s_{i}$ instead of $s_{1}$ in the first
matrix attribution). Finally, compute the product of the hash outputs.

######  Example 3.12.

Say we want to hash the string $1321321323$. Observe that:
$132\mathbf{13}21323$. We thus compute: $M_{1}=\varphi(13213)$ and
$M_{2}=\varphi^{\prime}(21323)$, where $\varphi^{\prime}$ is defined
analogously to $\varphi$ in Definition 2.6, apart from the fact that $B_{1}$
is set to be $s_{4}(x_{1})$ instead of $s_{1}(x_{1})$, since $\varphi(13213)$
is a product ending by $B$. Finally, $\varphi(1321221323)=M_{1}\cdot M_{2}$.

###  3.5 Palindromic attacks

One of several proposals of hashing by walks on Cayley graphs can be found in
[TZ94b], wherein the Cayley graph is that of $SL_{2}(\mathbb{F}_{2^{n}})$. A
method for finding collisions for this hash function is presented in [GIMS11]
(cf. [FPPR11]); we argue that the attack does not apply in our case, though
our evidence for this claim is primarily empirical.

The idea of [GIMS11] is to find collisions on palindromes; that is, bit-string
entries that are invariant under reversing the order. To begin, one conjugates
generators of $SL_{2}(\mathbb{F}_{2^{n}})$ to obtain new generators which give
rise to an isomorphic graph, but which are symmetric matrices. That is, if the
original generators are $\\{A^{\pm 1},B^{\pm 1}\\}$, one finds a matrix $C$
such that $\hat{A}=CAC^{-1}$ and $\hat{B}=CBC^{-1}$ are both symmetric
matrices.

We first note that in our case, finding $C$ is not easy; for $SL_{3}(5)$ and
$SL_{3}(7)$, about $0.02\%$ of the elements satisfy this criterion. Moreover,
there is no obvious way to compute $C$; attempts to calculate the entries of
such a matrix directly have proved resistant to equation solving methods in
standard computer algebra systems - indeed, this approach is actually less
efficient than just checking all possible matrices. Therefore, we do not have
much data for larger primes, since the naive method used to find a suitable
matrix $C$ quickly becomes computationally infeasible.

Provided one can find a matrix $C$, it follows that collisions in the hash
function with respect to $\hat{A},\hat{B}$ as generators are exactly the
collisions with $A,B$ as generators; one can therefore rename the matrices
$\hat{A},\hat{B}$ as $A,B$. One then proceeds according [GIMS11, Lemma 1]:
upon input of a palindromic string $v$, the output of the product of
conjugated generators in $SL_{2}(\mathbb{F}_{2^{n}})$ will always be a
symmetric matrix.

Since our hash function requires avoidance of backtracking in the walk, we are
not guaranteed a palindromic matrix product from a palindromic input string;
however, since one could reverse-engineer the necessary input to obtain a
palindromic matrix product, we proceed to discuss palindromic matrix products
without reference to hash function.

It turns out, as one may check easily by induction, that a palindromic product
in symmetric generators will itself be symmetric. The ultimate goal of
[GIMS11] is to use this fact to demonstrate that the function

$\rho:M\mapsto AMA+BMB,$

where $M$ is a palindromic product, outputs a matrix populated with either
zeroes or the square of a field element appearing as an entry in $M$. One then
employs number theoretic tricks to force the nonzero elements to $0$ in $M$
and thus to obtain $\rho(M)=0$. One thus builds distinct but equal palindromic
matrix products.

Consider the generators from Definition 2.6 over
$\operatorname{SL}_{3}(\mathbb{F}_{11})$. Transforming these generators with
respect to the matrix

$C=\begin{pmatrix}2&6&10\\\ 5&3&10\\\ 2&3&3\end{pmatrix},$

one checks that the palindrome $M=ABABA$ is such that

$M=\begin{pmatrix}7&4&2\\\ 4&0&6\\\
2&6&6\end{pmatrix},\quad\rho(M)=\begin{pmatrix}2&1&5\\\ 1&1&7\\\
5&7&7\end{pmatrix}.$

In particular, for each $i\in[10]$, the matrix $\rho(M)$ contains an entry
that is not the $i^{th}$ power of any entry of $M$. This furnishes evidence
that for $p=11$, there is little hope of extending [GIMS11, Corollary 1] to
our context; we argue that the lack of closed form of transformed generators
in general, the difficulty of finding them for larger parameters, and this
example with a small value of $p$, conspire to provide strong evidence that
the approach will fail in general.

##  4 Conclusions

We have presented new Tillich-Zémor hash functions, with platforms Cayley
graphs of $\operatorname{SL}_{n}(\mathbb{F}_{p})$ for $n\geq 3$. We show that
choosing appropriate generating matrices produces graphs without small cycles,
and having a quick mixing property, both of which are highly desirable for
preimage and collision resistance. Moreover, flexibility of choice of
generating matrices and of the dimension $n$ gives the option of increasing
the complexity of attacks. Future work includes the exact computation of the
spectral gap and the prime $p_{0}$ (cf. item (i) of Theorem 2.1). Moreover,
simulations should be carried out in order to compare with other existing
schemes and determine the optimal values of $p$ and $n$ to be taken in
implementations.

## References

  * [AB22] Goulnara Arzhantseva and Arindam Biswas.  Logarithmic girth expander graphs of $\mathrm{SL}_{n}({\mathbb{F}}_{p})$.  Journal of Algebraic Combinatorics, 2022.
  * [ABLS07] Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin.  Non-backtracking random walks mix faster.  Commun. Contemp. Math., 9(4):585–603, 2007.
  * [BdlHV08] Bachir Bekka, Pierre de la Harpe, and Alain Valette.  Kazhdan’s Property (T).  New Mathematical Monographs. Cambridge University Press, 2008.
  * [Bor20] Tom Borthwick.  Applications of homomorphic cryptographic primitives in blockchain and the internet of things, Undergraduate Thesis, University of York, 2020.
  * [BR93] Mihir Bellare and Phillip Rogaway.  Random oracles are practical: A paradigm for designing efficient protocols.  In Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS ’93, page 62–73, New York, NY, USA, 1993. Association for Computing Machinery.
  * [BSV17] Lisa Bromberg, Vladimir Shpilrain, and Alina Vdovina.  Navigating in the Cayley graph of $SL_{2}(\mathbb{F}_{p})$ and applications to hashing.  Semigroup Forum, 94(2):314–324, 2017.
  * [CLG08] Denis Charles, Kristin Lauter, and Eyal Goren.  Cryptographic hash functions from expander graphs.  Journal of Cryptology, 22:93–113, 12 2008.
  * [FPPR11] Jean-Charles Faugère, Ludovic Perret, Christophe Petit, and Guénaël Renault.  New subexponential algorithms for factoring in $\mathrm{SL}_{2}({\mathbb{f}_{2^{n}}})$.  IACR Cryptol. ePrint Arch., page 598, 2011.
  * [GIMS11] Markus Grassl, Ivana Ilić, Spyros Magliveras, and Rainer Steinwandt.  Cryptanalysis of the tillich–zémor hash function.  Journal of cryptology, 24(1):148–156, 2011.
  * [GJ79] Michael R. Garey and David S. Johnson.  Computers and intractability.  A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, Calif., 1979.  A guide to the theory of NP-completeness.
  * [GM18] Mohammad Hossein Ghaffari and Zohreh Mostaghim.  More secure version of a Cayley hash function.  Groups Complex. Cryptol., 10(1):29–32, 2018.
  * [Gur99] Robert M. Guralnick.  Small representations are completely reducible.  J. Algebra, 220(2):531–541, 1999.
  * [GV12] A. Salehi Golsefidy and Péter P. Varjú.  Expansion in perfect groups.  Geom. Funct. Anal., 22(6):1832–1891, 2012.
  * [Hal15] Brian Hall.  Lie groups, Lie algebras, and representations, volume 222 of Graduate Texts in Mathematics.  Springer, Cham, second edition, 2015.  An elementary introduction.
  * [KL21] Jonathan Katz and Yehuda Lindell.  Introduction to modern cryptography.  Chapman & Hall/CRC Cryptography and Network Security. CRC Press, Boca Raton, FL, 2021.  Third edition [of 2371431].
  * [LPS88] A. Lubotzky, R. Phillips, and P. Sarnak.  Ramanujan graphs.  Combinatorica, 8(3):261–277, 1988.
  * [Lub05] Alex Lubotzky.  What is$\dots$property $(\tau)$?  Notices Amer. Math. Soc., 52(6):626–627, 2005.
  * [Piz90] Arnold K. Pizer.  Ramanujan graphs and Hecke operators.  Bull. Amer. Math. Soc. (N.S.), 23(1):127–137, 1990.
  * [SBK+17] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov.  The first collision for full SHA-1.  In Advances in cryptology—CRYPTO 2017. Part I, volume 10401 of Lecture Notes in Comput. Sci., pages 570–596. Springer, Cham, 2017\.
  * [Sos18] Bianca Sosnovski.  Recent developments in Cayley hash functions.  In Mathematical software—ICMS 2018, volume 10931 of Lecture Notes in Comput. Sci., pages 438–447. Springer, Cham, 2018.
  * [SS16] Vladimir Shpilrain and Bianca Sosnovski.  Compositions of linear functions and applications to hashing.  Groups Complex. Cryptol., 8(2):155–161, 2016.
  * [Ste21] Bruno Sterner.  Commitment schemes from supersingular elliptic curve isogeny graphs.  Cryptology ePrint Archive, Report 2021/1031, 2021.  https://ia.cr/2021/1031.
  * [TNS20] Hayley Tomkins, Monica Nevins, and Hadi Salmasian.  New Zémor-Tillich type hash functions over ${\rm GL}_{2}(\mathbb{F}_{p^{n}})$.  J. Math. Cryptol., 14(1):236–253, 2020.
  * [TZ94a] Jean-Pierre Tillich and Gilles Zémor.  Group-theoretic hash functions.  In Algebraic coding (Paris, 1993), volume 781 of Lecture Notes in Comput. Sci., pages 90–110. Springer, Berlin, 1994.
  * [TZ94b] Jean-Pierre Tillich and Gilles Zémor.  Hashing with sl 2.  In Annual International Cryptology Conference, pages 40–49. Springer, 1994.
  * [TZ08] Jean-Pierre Tillich and Gilles Zémor.  Collisions for the LPS expander graph hash function.  In Proceedings of the Theory and Applications of Cryptographic Techniques 27th Annual International Conference on Advances in Cryptology, EUROCRYPT’08, page 254–269, Berlin, Heidelberg, 2008. Springer-Verlag.


# FairLay-ML: Intuitive Debugging of Fairness in Data-Driven Social-Critical
Software

Normen Yu
Gang Tan Department of Computer Science
Pennsylvania State University
<EMAIL_ADDRESS>
Department of Computer Science
Pennsylvania State University
<EMAIL_ADDRESS>
Luciana Carreon
Saeid Tizpaz-Niari Department of Computer Science
University of Texas at El Paso
<EMAIL_ADDRESS>
Department of Computer Science
University of Texas at El Paso
<EMAIL_ADDRESS>

###### Abstract

Data-driven software solutions have significantly been used in critical
domains with significant socio-economic, legal, and ethical implications. The
rapid adoptions of data-driven solutions, however, pose major threats to the
trustworthiness of automated decision-support software. A diminished
understanding of the solution by the developer and historical/current biases
in the data sets are primary challenges.

To aid data-driven software developers and end-users, we present FairLay-ML, a
debugging tool to test and explain the fairness implications of data-driven
solutions. FairLay-ML visualizes the logic of datasets, trained models, and
decisions for a given data point. In addition, it trains various models with
varying fairness-accuracy trade-offs. Crucially, FairLay-ML incorporates
counterfactual fairness testing that finds bugs beyond the development
datasets. We conducted two studies through FairLay-ML that allowed us to
measure false positives/negatives in prevalent counterfactual testing and
understand the human perception of counterfactual test cases in a class
survey. FairLay-ML and its benchmarks are publicly available at
https://github.com/Pennswood/FairLay-ML. The live version of the tool is
available at https://fairlayml-v2.streamlit.app/. We provide a video demo of
the tool at https://youtu.be/wNI9UWkywVU?t=127.

##  I Introduction

Addressing systemic bias and unfairness has been a fundamental societal
problem, and nothing is more ”systemic” in the 21st century than life-altering
decisions made by automated algorithms that often learn their logic from
historical data. These automated decision-making algorithms act as gatekeepers
for many social decisions: should a person remain in jail [1], is a person
qualified for a job [2], and will a loan receiver become a default [3]. This
is especially concerning when many of these algorithms are becoming less
human-driven and human-understandable [4, 5]. The problem of human
understandability and explainability particularly exacerbate discrimination in
the data-driven automated algorithms since different stakeholders (e.g.,
software developers, domain experts, end users, etc.) increasingly find it
more difficult to debug unfairness—the process of detecting, localizing, and
fixing fairness bugs. This paper presents FairLay-ML, an intuitive debugging
tool that aids data-driven software developers and end users to understand the
fairness implications of their solutions.

There are plenty of software tools in the literature to improve fairness [6,
7, 8, 9, 10]. IBM AIF360 [8] and Fairlearn [9] provide metrics and algorithms
to measure unfairness and mitigate it via various pre-processing (e.g.,
modifying training datasets), in-processing (e.g., modifying the loss
objective), and post-processing (e.g., calibration of scores) mechanisms.
Google What-if toolkit [11] is the closest to FairLay-ML. In particular, both
tools focus on individual fairness rather than group fairness, that is to
ensure similar individuals receive similar outcomes. Google What-if toolkit
allows to find a discriminatory instance by comparing a data point to its
similar counterfactual who has a different protected attribute. FairLay-ML, on
the other hand, goes beyond the training and development set and adapts
individual fairness testing methods [12, 13, 14] to explore the arbitrary
input space to find discriminatory instances. In addition, FairLay-ML allows
users to modify test cases and define counterfactuals based on their
intuitions (e.g., characteristics that make two individuals from different
groups to be similar).

We posit that significant user interactions in training and validating data-
driven solutions against fairness requirements are critical design goals of
the fairness toolkit. Hence, FairLay-ML integrates automation with human
feedback, e.g., we adapt automated test-case generations, but also allow users
to issue their own manual test cases based on their background and
experiences. Throughout all the activities, we provide intuitive explanations
and visualizations that guide users to make informed decisions.

FairLay-ML is a GUI app that integrates multiple research ideas into the
unified toolkit. The initial version is developed as a part of UG Thesis [15].
FairLay-ML takes a dataset of a target application (income, loan, credit,
recidivism, etc.) as input and (i) visualizes the interactions between
different features (e.g., distribution of job titles for male vs. female) via
plotly and streamlit, (ii) runs a multi-objective evolutionary algorithm based
on Parfait-ML [14] to train multiple models of varying accuracy vs. fairness
based on a given threshold, (iii) explains the model logic based on the
importance of different features on the outcome, (iv) conducts counterfactual
study to generate test cases that may lead to individual discrimination, (v)
explains how the model make a decision for a given test case, and (vi) allows
users to create and modify a counterfactual for a given test case.

After providing the background, we describe the core design and implementation
of FairLay-ML. Then, we overview the tool usage and showcase its usefulness
for two empirical evaluations. In particular, we experiment to measure
precision and recall of existing fairness testing techniques, thanks to the
flexibility of FairLay-ML in finding and manipulating test cases. We also
leverage FairLay-ML to conduct a class survey on the perception of
counterfactuals by students. We discuss the limitations and conclude by
describing future work.

##  II Background

In the rapidly evolving field of Machine Learning (ML) [4, 5], fairness has
become a main concern, specifically as ML software is being deployed or
assisting in making high-stakes decisions such as hiring decisions [2], parole
decisions [16], and financial lending [17]. These models often utilize large
datasets that may contain historical or systematic biases to make decisions
impacting people’s health, socio-economic, etc. Such biases in training data
can lead the model to maintain or even amplify the existing disparities. This
characteristic of ML systems may result in unfair outcomes based on legally
protected attributes such as gender and race. For example, the recidivism risk
assessment tool in criminal justice, COMPAS, has been under criticism for its
biased predictions that disadvantage African Americans [16]. Amazon had to
deactivate a hiring algorithm that excluded female applicants [2].

Fairness Notions. There are two broad fairness definitions: group fairness and
individual fairness.

Group Fairness. It ensures that statistics of outcomes remain similar between
two or more protected groups. The prevalent metric includes equal opportunity
difference (EOD) which measures the differences between true positive rates
between two groups and average odds difference (AOD) which measures the
difference between two groups in the average of true positive and false
positive rates [8, 18, 19]. Parfait-ML [14] used EDO and AOD to explore the
hyperparameter space of ML algorithms (e.g., the depth of decision trees, the
number of layers in DNNs, etc.) and find Pareto-optimal configurations that
maximize fairness within a given acceptable accuracy range [14].

Individual Fairness. Fairness through awareness ($FTA$) [20] requires two
individuals who are deemed to be similar (based on their non-protected
attributes) are treated similarly (regardless of their protected attributes).
However, defining the notion of similarity between individuals is difficult.
Counterfactual fairness [21] uses a causal dependency diagram between
variables and requires that the ML outcome is causally independent of
protected attributes. In this paper, we focus on a simpler notion,
counterfactual discrimination as proposed by Galhotra et al. [12] that
requires the ML outcome to remain similar between an individual and their
counterfactual who has only a different protected value. This notion is the
primary oracle of fairness testing [12, 22, 23, 13].

##  III FairLay-ML

We present FairLay-ML, a GUI MLOps pipeline that allows users to upload their
data and/or machine learning models to our toolkit for fairness debugging.
FairLay-ML identifies, explains, and suggests remedies to improve the model
fairness. We intend for FairLay-ML to be able to implement the remedies,
retrain the model on the given dataset, and allow the user to re-evaluate the
remedies for accuracy and fairness, as well as save the upgraded dataset and
model, all within our pipeline. The key focus of FairLay-ML is counterfactual
testing that measures the unfairness of data-driven software by computing the
differences between an original test case and its counterfactual with
different protected attributes. In doing so, FairLay-ML provides various data
visualizations on how different attributes interact, training algorithms, and
the logic of decision-making for a given data. The goal is to support users to
investigate generated counterfactual test cases and manipulate counterfactuals
based on their views.

###  III-A Feature Interactions

The data visualization tools provide an overview of how features correlate to
the sensitive feature. This tool helps users explore the distribution of
classifications for each feature, as well as understand how the features in a
dataset are interconnected in the context of bias in machine learning.
FairLay-ML ’s data visualization tool identifies key features that we should
pay attention to in our analysis of bias. For example, zip code has been found
in many contexts to accidentally be used by ML algorithms as a proxy for race
[24], as can more obvious bugs in the pipeline such as “husband” and “wife”
being used as a proxy for gender.

Our tool then seamlessly provides a user interface to dive deeper into the
correlations for each feature. By clicking on the correlation graph directly,
users are provided with a histogram of how likely a data point in each
possible value of a specific feature is in a protected class of the sensitive
feature. In doing so, users gain better context on whether specific values of
a feature could be used when they modify an input to generate a counterfactual
with a different protected attribute.

###  III-B Model Visualization and Explanation

Under the hood, FairLay-ML calls Parfait-ML to train different models of the
same algorithm, varying accuracy vs. fairness. Then, FairLay-ML displays a
model’s logic to gain (global) insights into how the model uses different
features to make decisions. Currently, FairLay-ML supports displaying decision
tree and random forest models by plotting each tree structure (or tree
structure of all the trees in the random forest) directly, as well as logistic
regression and support vector machine by graphing the weights of each feature
or the slope of the hyperplane with respect to each feature respectively.
Finally, FairLay-ML explains how a model classifies specific data points using
local interpretable model-agnostic explanations called LIME [25]. LIME shows
how each feature value of a data point impacts the model’s decision. This
enables users to understand what features and what values may change the
outcomes (e.g., from a favorable to an unfavorable one). In addition, these
methods of visualization combine with feature interactions to provide
explanations of the form “This model places a high weight on feature category
X, and X is strongly correlated with the sensitive feature, causing
unfairness.”

###  III-C Counterfactual Test Case Generation

Given a model and a set of test data points for the model, FairLay-ML can also
scatterplot the data points for their predicted probability and highlight
counterfactual points. This is useful during testing to see which individuals
are specifically impacted by unfairness. For example, some models may only
generate counterfactuals on the decision boundary (when the predicted
probability is close to 0.5). Some models may have a bigger spread of
counterfactuals, indicating a wider systemic gender bias within the model.

To dive deeper into a specific data point, users can filter by
counterfactuals, and even if the counterfactual generated a more accurate or
less accurate prediction. Users can also filter by false positive, false
negative, true positive, or true negative. FairLay-ML then takes advantage of
the previously mentioned explanation techniques such as LIME and model
visualization to generate a common story for the user.

##  IV Tool Usage

Figure 1: FairLay-ML Usage.

Figure 1 shows the end-to-end usage of FairLay-ML. A user begins by uploading
their tabular data (both in the original form with labeled categories and
features, as well as its numerically encoded) and a training algorithm (e.g.,
decision trees, logistic regressions, etc.). The user then specifies the
sensitive attribute and categories within the sensitive attribute that the
user wishes to study. From the data set, we first create an 80/20 train-test-
split to have training and validation data sets. FairLay-ML also provides
histograms and correlation metrics between each column and the sensitive
attribute on the training data (feature interactions). FairLay-ML uses
Parfait-ML [14] to generate various models with varying fairness/accuracy
trade-offs. The visualization allows users to investigate different models
where FairLay-ML plots the logic of models (e.g., normalized weights of
contributions from different features). FairLay-ML also highlights Pareto-
optimal models with red dots—those that achieve an ideal accuracy vs. fairness
trade-off. Once the user picks one model, as the decision-making model, then
FairLay-ML performs counterfactual testing based on the counterfactual
discrimination notion using Themis [12]. The tool plots the generated test
cases and highlights four types of data points: i) the original and
counterfactual data points agree on a positive outcome; ii) the original and
counterfactual data points agree on a negative outcome; iii) the original data
point classified as positive, while the counterfactual one is classified as
negative; and iv) the original data point classified as negative, while the
counterfactual one classified as positive. The user can then investigate
different data points. Once they click on one data point, FairLay-ML shows the
local explanations on how the model outcomes a particular decision using LIME
[25]. FairLay-ML also provides a dashboard to the users who can manipulate the
data point to see how different changes contribute to the outcome. This
enables users to investigate counterfactual test cases as well. They can use
the LIME plot and identify which features/values might lead to a realistic
counterfactual test case with significant discrimination.

##  V EMPIRICAL EVALUATION

We performed a preliminary evaluation of FairLay-ML for debugging
counterfactual test cases based on the following research questions (RQs):

  * •

RQ1. What is the false positive and false negative rates of prevalent
counterfactual testing?

  * •

RQ2. How accurate are humans in generating counterfactual test cases?

Currently, FairLay-ML supports four datasets: Adult Census Income [26], Credit
Bank [27], Loan Default [28], and COMPAS [29] over three protected attributes
(sex, race, age). Since Adult Census Income is the most intuitive and simple
applications (i.e., predicting whether incomes are above $50k based on
personal characteristics like the job, hours-per-week, sex, race, etc.), we
will focus on this dataset to answer the research questions.

Figure 2: Visualization of Counterfactual Test Case Generations.

RQ1. False Positives/Negatives of Counterfactual Testing. FairLay-ML
implements a counterfactual testing method based on Themis [12]. The approach
is to find individual discrimination (ID) instances—two inputs that share the
same relevant inputs, but they receive two different outcomes due to their
differences in the protected attributes—in a given amounts of time. Figure 2
shows 8,000 test cases visualized by FairLay-ML. The application is the Adult
Census Income and sex is the protected attribute. The red points show ID
instances where diamonds and square show whether the original instance or
counterfactual one received a favorable outcome (an income above $50k).
However, simply perturbing protected attributes from $A$ to $B$ can lead to
false positives or negatives. For example, an ID instance generated by
changing the protected attribute from Male to Female may be false without
adjusting the relationships (e.g., Husband to Wife). Similarly, a benign test
case may be buggy once all the relevant features are adjusted for it. We study
the false positive and negative rates of prevalent counterfactual testing. The
key feature of FairLay-ML is that it allows to pick a test case and adjust any
relevant features to generate a valid and proximal counterfactual. Thus, we
use FairLay-ML to evaluate false positive and false negative rates of Themis
approach. We pick 100 test cases uniformly at random from the set of test
cases. The selected test cases are reported in [30]. We observe that the rate
of false positives, false negatives, true positives, and true negatives are
21%, 16%, 37%, and 26%. An example of false positive is <sex="Male",
race="Black", occupation="Handles-Cleaner", relationship="Husband",
hours_per_week=80, native_country="Unknown"> where changing the sex attribute
to ”Female” flips the outcomes from favorable (more than $50k) to unfavorable
(less than $50k); but once the relationship is adjusted for (”Husband” $\to$
”Wife”), then both original and counterfactual outcomes are favorable.

Figure 3: Steps in Generating Counterfactuals (CF) with Human Intuition

RQ2. Validity and Proximity of Human Generated Counterfactuals. We perform a
class survey with $17$ participants (UG and graduate students from the UT El
Paso) using FairLay-ML. The details of survey can be found at [31] (permitted
by the IRB). Figure 3 shows the steps to complete the survey where students
can change up to 7 features of the target test cases (after changing the sex
attribute from male to female) and report a combination that flips the ML
decision from a favorable outcome (for the male individual) to an unfavorable
one (for the female individual). In doing so, the students need to ensure that
they preserve the validity and proximity of counterfactuals. The survey asked
each student to evaluate the CFs reported by one or two other students in
terms of its proximity to the target test case (with Id=25) and validity w.r.t
real-world constraints. The results showed that 9 students out of 17 were able
to find a combination that changes the ML outcome with a different sex and
relationship. The number of changes vary between 2 and 7. The nine valid
responses received 12 feedback on the validity and proximity. All the
responses said ”yes” to the validity of CFs, implying that the counterfactual
adheres to the real-world constraints. However, 6 of those evaluation feedback
said that the CFs are not proximal to the original target test case (e.g., one
counterfactual changed the education level). Most students tried to change
race to black and believed that such changes may have significant impacts on
the outcome, while being valid/proximal. We also observed that counterfactuals
vary between participants significantly. For example, some participants said a
separated individual may still have wife/husband relationship. Others believed
that changing the country of origin does not preserve the proximity of CFs.

##  VI Limitations

Our solution, FairLay-ML, currently supports tabular data in the form of a CSV
and binary classification algorithms from sci-kit learn. Decision Trees,
Support Vector Machines, Random Forest, and Logistic Regression models are
tested. We plan to extend the tool to support datasets beyond tabular ones as
well as training algorithms provided by TensorFlow and PyTorch.

##  VII Related Work

Seldonian [7] presented a mitigation technique that allows users to directly
specify (arbitrary) undesirable behaviors. The key innovation of Seldonian is
to enforce safety requirements during training in the offline contextual
bandits setting with probabilistic guarantees. FairLay-ML, on the other hand,
focuses on helping users detect and understand discrimination. IBM AIF360 [8]
and Fairlearn [9] implement various measures of fairness and algorithms to
mitigate unfairness in three stages pre-processing, in-processing, and post-
processing. However, they focus on group fairness and evaluate unfairness over
a pre-fixed development set. Google What-if toolkit [11] is the closest to
FairLay-ML, and we discussed it in detail in the introduction section.
eXplainable AI (e.g., LIME [25], SHAP [32], etc.) are also relevant, and
FairLay-ML significantly adapted XAI and visualization tools to enable users
to debug their data-driven software for fairness. However, those tools try to
explain how ML models globally (for all data points) and locally (for a
specific data point) make decisions. FairLay-ML focuses specifically on
fairness and allows users to identify significant test cases and compare
multiple data points simultaneously.

##  VIII Conclusion

We presented FairLay-ML, an intuitive debugging tool that aids data-driven
users to analyze and understand fairness implications of their solutions.
FairLay-ML integrates visualization, testing, and human annotations to help
developers navigate the complexity of data-driven solutions. One exciting
future direction is to support mitigating unfairness. One idea that is
partially implemented in the current tool is to mask features which are highly
correlating with protected attributes. We plan to enable users to perform
targeted data masking. For example, in the relationship feature in the Census
data set, there are 5 categories: husband, wife, not married, married with
children, and spouse in military; it may make sense to only mask husband and
wife, as proxies for gender, without masking the other categories.

## References

  * [1] “Northpointe suite risk needs assessments,” https://www.equivant.com/northpointe-risk-need-assessments/, 2021, online.
  * [2] “Amazon scraps secret ai recruiting tool that showed bias against women,” https://www.bbc.com/news/technology-45809919, 2018.
  * [3] “When an algorithm decides on the loan,” 2023. [Online]. Available: https://tinyurl.com/2kjr7fdz
  * [4] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [5] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” _nature_ , vol. 521, no. 7553, pp. 436–444, 2015.
  * [6] P. Saleiro, B. Kuester, L. Hinkson, J. London, A. Stevens, A. Anisfeld, K. T. Rodolfa, and R. Ghani, “Aequitas: A bias and fairness audit toolkit,” _arXiv preprint arXiv:1811.05577_ , 2018.
  * [7] A. Hoag, J. E. Kostas, B. Castro da Silva, P. S. Thomas, and Y. Brun, “Seldonian toolkit: Building software with safe and fair machine learning,” _ICSE (Demo Track)_ , 2023.
  * [8] R. K. Bellamy, K. Dey, M. Hind, S. C. Hoffman, S. Houde, K. Kannan, P. Lohia, J. Martino, S. Mehta, A. Mojsilović _et al._ , “Ai fairness 360: An extensible toolkit for detecting and mitigating algorithmic bias,” _IBM Journal of Research and Development_ , vol. 63, no. 4/5, pp. 4–1, 2019.
  * [9] S. Bird, M. Dudík, R. Edgar, B. Horn, R. Lutz, V. Milan, M. Sameki, H. Wallach, and K. Walker, “Fairlearn: A toolkit for assessing and improving fairness in AI,” Microsoft, Tech. Rep. MSR-TR-2020-32, May 2020. [Online]. Available: https://www.microsoft.com/en-us/research/publication/fairlearn-a-toolkit-for-assessing-and-improving-fairness-in-ai/
  * [10] M. S. A. Lee and J. Singh, “The landscape and gaps in open source fairness toolkits,” in _Proceedings of the 2021 CHI conference on human factors in computing systems_ , 2021, pp. 1–13.
  * [11] J. Wexler, M. Pushkarna, T. Bolukbasi, M. Wattenberg, F. Viégas, and J. Wilson, “The what-if tool: Interactive probing of machine learning models,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 26, no. 1, pp. 56–65, 2020. [Online]. Available: https://pair-code.github.io/what-if-tool/
  * [12] S. Galhotra, Y. Brun, and A. Meliou, “Fairness testing: testing software for discrimination,” in _FSE_ , 2017, pp. 498–510.
  * [13] V. Monjezi, A. Trivedi, G. Tan, and S. Tizpaz-Niari, “Information-theoretic testing and debugging of fairness defects in deep neural networks,” in _2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE)_ , 2023, pp. 1571–1582.
  * [14] S. Tizpaz-Niari, A. Kumar, G. Tan, and A. Trivedi, “Fairness-aware configuration of machine learning libraries,” in _44th International Conference on Software Engineering (ICSE 2022)_ , 2022.
  * [15] N. Yu, G. Tan, and S. Tizpaz-Niari, “Fairlay-ml: Intuitive remedies for unfairness in data-driven social-critical algorithms,” 2023, B.S. Thesis (Penn State). [Online]. Available: https://arxiv.org/abs/2307.05029
  * [16] S. M. Julia Angwin, Jeff Larson and L. Kirchne, “Machine bias,” https://www.propublica.org/article/machine-bias-risk-assessments-in-criminal-sentencing, 2021, online.
  * [17] H. C. Group, “Home credit default risk,” https://www.kaggle.com/competitions/home-credit-default-risk/overview, 2018\.
  * [18] J. Chakraborty, S. Majumder, Z. Yu, and T. Menzies, “Fairway: a way to build fair ml software,” in _Proceedings of ESEC/FSE_ , 2020, pp. 654–665.
  * [19] J. M. Zhang and M. Harman, “”ignorance and prejudice” in software fairness,” in _2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_. IEEE, 2021, pp. 1436–1447.
  * [20] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel, “Fairness through awareness,” in _Proceedings of the 3rd innovations in theoretical computer science conference_ , 2012, pp. 214–226.
  * [21] M. Kusner, J. Loftus, C. Russell, and R. Silva, “Counterfactual fairness,” _Advances in Neural Information Processing Systems 30 (NIPS 2017) pre-proceedings_ , vol. 30, 2017.
  * [22] S. Udeshi, P. Arora, and S. Chattopadhyay, “Automated directed fairness testing,” in _Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering_ , 2018, pp. 98–108.
  * [23] P. Zhang, J. Wang, J. Sun, G. Dong, X. Wang, X. Wang, J. S. Dong, and T. Dai, “White-box fairness testing through adversarial sampling,” in _Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering_ , 2020, pp. 949–960.
  * [24] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan, “A survey on bias and fairness in machine learning,” _ACM Comput. Surv._ , vol. 54, no. 6, jul 2021. [Online]. Available: https://doi.org/10.1145/3457607
  * [25] M. T. Ribeiro, S. Singh, and C. Guestrin, “”why should I trust you?”: Explaining the predictions of any classifier,” in _ACM SIGKDD_ , 2016, pp. 1135–1144.
  * [26] D. Dua and C. Graff, “UCI machine learning repository,” 2017. [Online]. Available: https://archive.ics.uci.edu/ml/datasets/census+income
  * [27] “UCI:statlog (german credit data) data set,” 2000. [Online]. Available: https://archive.ics.uci.edu/ml/datasets/statlog+(german+credit+data)
  * [28] “UCI:default of credit card clients data set,” 2009. [Online]. Available: https://archive.ics.uci.edu/ml/datasets/default+of+credit+card+clients
  * [29] ProPublica, “Compas software ananlysis,” https://github.com/propublica/compas-analysis, 2021, online.
  * [30] “Counterfactual test-case study,” 2024. [Online]. Available: https://tinyurl.com/y5sujcb5
  * [31] “Fairgame: Generating valid counterfactual via gamification,” 2024. [Online]. Available: https://tinyurl.com/48eaf2aj
  * [32] S. M. Lundberg and S.-I. Lee, “A unified approach to interpreting model predictions,” _Advances in neural information processing systems_ , vol. 30, 2017.