aainstitutetext: Department of Physics, Shanxi Datong University, Datong
037009, Chinabbinstitutetext: Institute of Theoretical Physics, Shanxi Datong
University, Datong 037009, China

# Fractional phase transitions of RN-AdS black hole at Davies points

Li-Hua Wang a Yun He a,b Meng-Sen Ma***Corresponding author.
E-mail address<EMAIL_ADDRESS>
###### Abstract

We perform a study of phase transitions of RN-AdS black hole at its Davies
points according to a generalized Ehrenfest classification of phase transition
established on the basis of fractional derivatives. Davies points label the
positions where heat capacity diverges. According to the usual Ehrenfest
classification, second-order phase transitions occur there. For RN-AdS black
hole, the Davies points can be classified into two types. The first type
corresponds to the extreme values of temperature and the second type
corresponds to the infection point(namely the critical point) of temperature.
Employing the generalized Ehrenfest classification, we find that the orders of
phase transition at the two types of Davies points are different. It is
$3/2$-order for the first type and $4/3$-order for the second type. Thus this
finer-grained classification can discriminate phase transitions that are
supposed to be in the same category, which may provide some new insights
toward a better understanding of black hole thermodynamics.

##  1 Introduction

The works of Hawking and Bekenstein laid a firm foundation for the study of
black hole thermodynamics. Phase transition and critical phenomena are
important characteristics of usual thermodynamic systems. Therefore one may
naturally consider the corresponding properties of black holes. Davies found
that heat capacities of some black holes will diverge at certain points,
according to the Ehrenfest classification which is a feature associated with a
second-order phase transitionHut.379389.1977 ; Davies.13131355.1978 ;
Sokolowski.11131120.1980 . These divergent points of heat capacities are
called Davies points now.

In general, the heat capacities of black holes can be expressed in the
following form

$C_{X}=\left.T\frac{\partial S}{\partial T}\right|_{X}=\left.T\frac{\partial
S/\partial r_{h}}{\partial T/\partial r_{h}}\right|_{X},$ (1.1)

where $X$ represents a certain thermodynamic quantity and $r_{h}$ is the
radius of the event horizon. Therefore, divergent heat capacity is equivalent
to $\partial T/\partial r_{h}=0$. In fact, according to this result, Davies
points can be further classified into two types. For the first type, the
Davies points correspond to extreme points of temperature, where temperatures
may have maximal or minimal values. While for the second type, the Davies
point lies at the infection point of temperature, which is also the critical
points of black holes.

Properties of various black holes near critical points have been studied
extensively. On the basis of AdS/CFT, phase structures of the charged AdS
black holes were studied inChamblin.064018.1999 ; Chamblin.104026.1999 .
Thermodynamic stability and phase transition of some charged black holes were
analyzed by putting them in finite box Peca.124007.1999 ; Carlip.38273837.2003
; Lu.133.2011 . By means of thermodynamic geometry, thermodynamic curvature
can be calculated, from which one can ascertain the phase transition of black
holes near the critical pointsLiu.054.2010 ; Banerjee.064024.2011 ;
Cao.064015.2011 ; Wang.401404.2011 ; Niu.024017.2012 ; Wei.044014.2013 .
Inspired by the idea in Dolan.235017.2011  of treating the cosmological
constant as pressure and its conjugate quantity as the thermodynamic volume,
one can construct an extended phase space. In analogy to liquid-gas system,
$P-V$ criticality and phase structures of many AdS black holes have been
analyzedKubiznak.033.2012 ; Cai.005.2013 ; Hendi.084045.2013 ;
Chen.060401.2013 ; Mo.056.2013 ; Liu.179.2014 ; Ma.095001.2014 ; Xu.3074.2014
; Ma.035024.2015 ; Xu.124033.2015 ; Wei.084015.2016 ; Ma.024052.2017 ;
Miao.084051.2018 ; Xu.104022.2021 . In all these works, it concludes that the
phase transition occurring at the critical point is of the second order.

Hilfer proposed a kind of generalized Ehrenfest classification, which
classifies phase transition according to the continuity of the fractional
derivatives of free energyHilfer.1992 ; Hilfer.2000 . Inspired by Hilfer’s
work, we reanalyzed the phase transition of RN-AdS black hole using this
generalized Ehrenfest classification and found that the order of phase
transition at the critical point should be of $4/3$, but not $2$
Ma.490495.2019 . At present, this generalized Ehrenfest classification is
mainly used to deal with the phase transition at the critical(Davies) points,
so they do not affect the original phase structure of black holes. Chabab and
Iraoui further studied AdS black holes in higher dimensions and without
spherical symmetry and found that the order of fractional phase transition can
be dependent on the geometry of spacetimeChabab.620430.2021 ; Chabab.2022 .

The two types of Davies points both correspond to divergent heat capacity. In
other words, we cannot discriminate Davies points of the two types by means of
heat capacity. Employing fractional derivatives, one can generalize the
Ehrenfest classification to include phase transitions of fractional order.
This finer-grained classification may reflect more richer phase structures of
thermodynamic systems. We take the RN-AdS black hole as an example to analyze
the phase structure at its Davies points. Considering that the temperatures of
RN-AdS black hole have different behaviors at the two types of Davies points,
we expect that there should be different phase structures. Therefore, it is
our concern in this letter whether phase structures at the two types of Davies
points can be distinguished by means of this generalized Ehrenfest
classification. The second motivation is that we want to know whether the
order of phase transition at the critical point is the same in extended phase
space and the non-extended phase space.

The paper is arranged as follows. We first simply review RN-AdS black hole and
give some thermodynamic quantities in section 1. In section 2 we analyze the
phase structures at the first type of Davies point. It refers to two Davies
points on the left-hand side and the right-hand side. In section 3 we discuss
phase structures of the RN-AdS black hole at the critical point. At last, we
summarize our results and discuss the possible future study.

##  2 The RN-AdS black hole

RN-AdS black hole is a static spherically symmetric spacetime, the line
element of which is

$ds^{2}=-f(r)dt^{2}+f^{-1}(r)dr^{2}+r^{2}d\Omega^{2}.$ (2.1)

The metric function is

$f(r)=1-\frac{\displaystyle 2M}{\displaystyle r}+\frac{\displaystyle
Q^{2}}{\displaystyle r^{2}}-\frac{\displaystyle\Lambda r^{2}}{\displaystyle
3},$ (2.2)

where the parameters $M$,$Q$, and $\Lambda=-3/L^{2}$ are the black hole mass,
electric charge and the cosmological constant, respectively.

According to $f(r_{h})=0$, we can find the position of the event horizon. We
do not consider the extended phase space in this paper. There is no
thermodynamic volume and pressure in the first law of thermodynamics, which is

$dM=TdS+\phi dQ.$ (2.3)

In this case, $M$ is understood as the internal energy. Through Legendre
transformation, we can obtain the Helmholtz free energy $F=M-TS$, which
satisfies the differential relation

$dF=-SdT+\phi dQ.$ (2.4)

Thus, $F=F(T,Q)$ is a thermodynamic characteristic function, from which we can
derive all other thermodynamic quantities. We will consider the canonical
ensemble and take $(T,Q)$ as the thermodynamic variables.

The temperature of RN-AdS black hole is

$T=\frac{L^{2}r_{h}^{2}+3r_{h}^{4}-L^{2}Q^{2}}{4\pi L^{2}r_{h}^{3}}.$ (2.5)

The entropy satisfies the area law, $S=A/4=\pi r_{h}^{2}$. And the electric
potential at the horizon measured at infinity is $\phi=Q/r_{h}$.

Figure 1: The temperature and heat capacity of RN-AdS black hole as the
function of the horizon radius. We choose $L=1$. The blue and the red dashed
curve correspond to $Q=1/8$ and $Q=1/6$, respectively.

The heat capacity at constant charge is defined as

$C_{Q}=\left.\frac{\displaystyle\partial M}{\displaystyle\partial
T}\right|_{Q}=T\left.\frac{\displaystyle\partial S}{\displaystyle\partial
T}\right|_{Q}=T\left.\frac{\displaystyle\partial S/\partial
r_{h}}{\displaystyle\partial T/\partial r_{h}}\right|_{Q}=\frac{2\pi
r_{h}^{2}\left(L^{2}r_{h}^{2}+3r_{h}^{4}-L^{2}Q^{2}\right)}{-L^{2}r_{h}^{2}+3r_{h}^{4}+3L^{2}Q^{2}}.$
(2.6)

According to the denominator, we can derive the position of Davies points,

$r_{h}=\sqrt{\frac{L^{2}}{6}\pm\frac{1}{6}\sqrt{L^{4}-36L^{2}Q^{2}}}.$ (2.7)

When $L>6Q$, there are two different roots, which correspond to the first type
of Davies point. While for $L=6Q$, the two roots coincide, which is the
critical point and belongs to the second type of Davies point.

As is shown in Fig.1, in the blue curve there are two first types of Davies
points. Each Davies point separates the temperature into two branches. The
heat capacity has opposite signs on the two branches. As the two Davies points
coincide in the red curve, it becomes a critical point. We also depict the
heat capacity in this figure. At the two types of Davies point, heat
capacities both diverge. According to the standard Ehrenfest classification,
the phase transitions are both of second order. In the following, we will try
to distinguish these phase structures using our generalized Ehrenfest
classification.

##  3 Phase transitions at the first type of Davies points

According to Eq.(2.5), for smaller $r_{h}$ the temperature of RN-AdS black
hole is dominated by the electric charge $Q$ rather $L$, while for larger
$r_{h}$ the temperature is dominated by $L$. Therefore, the behaviors of the
temperature near the left Davies point are different from that near the right
Davies point. We should analyze the phase structures at the two Davies points,
respectively.

For simplicity, we set $L=1$ in this section.

The left Davies point lies at

$T_{c}=-\frac{\sqrt{\frac{3}{2}}\left(12Q^{2}+\sqrt{1-36Q^{2}}-1\right)}{\pi\left(1-\sqrt{1-36Q^{2}}\right)^{3/2}},\quad
r_{c}=\frac{\sqrt{1-\sqrt{1-36Q^{2}}}}{\sqrt{6}}.$ (3.1)

We define some dimensionless quantities

$T=T_{c}(1+t),\quad r_{h}=r_{c}(1+\rho).$ (3.2)

Now the Davies point lies at $t=\rho=0$. In this way, we can do a series
expansion near the Davies point. Because this left Davies point corresponds to
the maximal value of temperature, there is always $t\leq 0$.

After setting $Q=1/8$, we can obtain a dimensionless equation of state from
Eq.(2.5),

$0.057\rho^{4}-\rho^{3}(0.302t+0.0729)-\rho^{2}(0.906t+0.224)-0.906\rho
t-0.302t=0.$ (3.3)

Near the Davies point, we solve Eq.(3.3) to obtain a series solution of $\rho$
as functions of $t$,

$\displaystyle\rho$ $\displaystyle=$
$\displaystyle-1.162(-t)^{1/2}-1.804t-3.270(-t)^{3/2}+6.633t^{2}-14.616(-t)^{5/2}+O(t^{3}),$
$\displaystyle\rho$ $\displaystyle=$
$\displaystyle-1.162(-t)^{1/2}-1.804t+3.270(-t)^{3/2}+6.633t^{2}+14.616(-t)^{5/2}+O(t^{3}).$
(3.4)

The two series solutions correspond to the two branches on both sides of the
Davies point. The most notable feature of this result is that it contains
terms with fractional exponents.

According to the definition above, we can obtain free energy,

$F=\frac{(\rho+1)^{2}\left(\rho^{2}+2\rho-2\right)\left(\sqrt{1-36Q^{2}}-1\right)+18\left(\rho^{4}+4\rho^{3}+6\rho^{2}+4\rho+4\right)Q^{2}}{12(\rho+1)\sqrt{6-6\sqrt{1-36Q^{2}}}},$
(3.5)

where $\rho=\rho(t)$ is given by Eq.(3).

Substituting the results in Eq.(3) into the free energy, we have

$\displaystyle F$ $\displaystyle=$ $\displaystyle
0.105-0.053t-0.082(-t)^{3/2}+0.13t^{2}-0.227(-t)^{5/2}+O(t^{3}),$ (3.6)
$\displaystyle F$ $\displaystyle=$ $\displaystyle
0.105-0.053t+0.082(-t)^{3/2}+0.13t^{2}+0.227(-t)^{5/2}+O(t^{3}).$ (3.7)

One should note that there are also terms with fractional exponents.
Especially, the coefficients before the term $(-t)^{3/2}$ have opposite signs.

Now it is time to calculate the derivatives of the free energy. We will use
Caputo’s definition of fractional derivativesCaputo.1967 ; Kilbas.1993 ;
Gorenflo.1997 . The main formulae we may need are

$D^{\alpha}_{x}x^{n}=0,~{}~{}~{}\text{with $n$ integer and $\alpha>n$};\quad
D^{\alpha}_{x}x^{a}\propto x^{a-\alpha},~{}~{}~{}\text{with $a$ real}.$ (3.8)

For more properties of fractional derivatives one can refer to the appendix
ofMa.490495.2019 .

The $\alpha$-order fractional derivative of the free energy with $1<\alpha\leq
2$ have the form of

$D_{t}^{\alpha}F(t)=(-t)^{1-\alpha}\left[A(-t)^{1/2}\pm Bt+C(-t)^{3/2}\pm
Dt^{2}+\cdots\right],$ (3.9)

where $A,B,C,D$ are some constant coefficients. The ”+” sign corresponds to
the case of approaching the Davies point from the left-hand side and the ”-”
sign corresponds to the other side.

Due to $t\leq 0$, the $D_{t}^{\alpha}F-t$ curves all turn up on the left hand-
side of $t=0$ axis. One can also express $D_{t}^{\alpha}F$ as functions of
$\rho$. In this case, $D_{t}^{\alpha}F$ can occur on both sides of $\rho=0$
axis.

Figure 2: The behaviors of $D_{t}^{\alpha}F(t)$ near the left Davies point for
RN-AdS black hole. The left panel depicts the $D_{t}^{\alpha}F-t$ curves. The
black arrows indicate the direction of increasing $r_{h}$. The right panel
displays the $D_{t}^{\alpha}F-\rho$ curves.

Substituting concrete values of $\alpha$ into Eq.(3.9) and taking the
$t\rightarrow 0^{-}$ limit, we can obtain

$\lim_{t\rightarrow
0^{-}}D_{t}^{\alpha}F(t)=\left\\{\begin{array}[]{lr}0{}{}&\text{for}~{}~{}\alpha<3/2,\\\
\pm 0.291{}{}&\text{for}~{}~{}\alpha=3/2,\\\
\pm\infty{}{}&\text{for}~{}~{}\alpha>3/2.\end{array}\right.$ (3.10)

A look at the behaviors of $D_{t}^{\alpha}F(t)$ in Fig.2 shows that when
$\alpha<3/2$ the $D_{t}^{\alpha}F(t)$ is continuous at the Davies point, when
$\alpha=3/2$ the $D_{t}^{\alpha}F(t)$ has a finite jump and when $\alpha>3/2$
the $D_{t}^{\alpha}F(t)$ is divergent. According to the generalized
classification, a $3/2$-order phase transition occurs at this Davies point.

Next, we analyze the phase structure of the RN-AdS black hole at the right
Davies point. The procedure is similar. In this case, Davies point turns up at

$T_{c}=\frac{\sqrt{\frac{3}{2}}\left(1-12Q^{2}+\sqrt{1-36Q^{2}}\right)}{\pi\left(1+\sqrt{1-36Q^{2}}\right)^{3/2}},\quad
r_{c}=\frac{\sqrt{1+\sqrt{1-36Q^{2}}}}{\sqrt{6}}.$ (3.11)

With the dimensionless quantities, the equation of state is reduced to

$1.380\rho^{4}+(2.573-2.948t)\rho^{3}+(1.099-8.844t)\rho^{2}-8.844\rho
t-2.948t=0.$ (3.12)

It should be noted that the right Davies point of RN-AdS black hole
corresponds to the minimal value of temperature, thus we always have $t\geq
0$.

In the same way, we solve Eq.(3.12) to obtain $\rho=\rho(t)$ in series form
and substitute them into the free energy. At last, we can derive the free
energy in the following form

$\displaystyle F$ $\displaystyle=$ $\displaystyle
0.117-0.233t-0.510t^{3/2}-0.519t^{2}-0.397t^{5/2}+O(t^{3}),$ (3.13)
$\displaystyle F$ $\displaystyle=$ $\displaystyle
0.117-0.233t+0.510t^{3/2}-0.519t^{2}+0.397t^{5/2}+O(t^{3}).$ (3.14)

Except for the values of the coefficients and $t\geq 0$, these free energies
have similar forms to those near the left Davies point. Therefore, their
fractional derivatives are also analogous. We do not write out them here. In
Fig.3, we directly depict the behaviors of the fractional derivatives of free
energy as functions of $t$ or $\rho$. The $t\rightarrow 0^{+}$limit values of
the fractional derivatives are

$\lim_{t\rightarrow
0^{+}}D_{t}^{\alpha}F(t)=\left\\{\begin{array}[]{lr}0{}{}&\text{for}~{}~{}\alpha<3/2,\\\
\pm 0.678{}{}&\text{for}~{}~{}\alpha=3/2,\\\
\pm\infty{}{}&\text{for}~{}~{}\alpha>3/2.\end{array}\right.$ (3.15)

Figure 3: The behaviors of $D_{t}^{\alpha}F(t)$ near the right Davies point
for RN-AdS black hole. The left panel depicts the $D_{t}^{\alpha}F(t)-t$
curves. The black arrows indicate the direction of increasing $r_{h}$. The
right panel displays the $D_{t}^{\alpha}F(t)-\rho$ curves.

In summary, although the temperatures have different behaviors at the left and
right Davies points, the phase structures at the two points are similar.
However, phase transitions at these points are both $3/2$-order, but not
second-order as people thought before. To our knowledge, in usual
thermodynamic systems temperatures are generally monotonic and have no
analogues of the first type of Davies point.

##  4 Phase transitions at the second type of Davies point

Now we consider the second type of Davies point, namely the critical point,
where

$dT/dr_{h}=0,\quad d^{2}T/dr_{h}^{2}=0.$ (4.1)

The critical point lies at

$r_{c}=L/\sqrt{6},\quad Q_{c}=L/6,\quad T_{c}=\sqrt{\frac{\displaystyle
2}{\displaystyle 3}}\frac{\displaystyle 1}{\displaystyle\pi L}.$ (4.2)

We also use the dimensionless quantities defined above. Because the critical
point is an infection point, now the dimensionless temperature $t$ can be
greater or smaller than zero.

On the basis of the definition of Eq.(3.2), we also define $Q=Q_{c}(1+q)$. The
equation of state is simplified to

$2q+q^{2}+8t+24t\rho+24t\rho^{2}+(8t-4)\rho^{3}-3\rho^{4}=0.$ (4.3)

It is a quartic equation about $\rho$. In principle, we can analytically solve
it. But the exact solutions are too lengthy and unnecessary.

Near the critical point, the free energy has the form

$F=\frac{L\left(-\rho^{4}-4\rho^{3}+3q^{2}+8\rho+6q+8\right)}{24\sqrt{6}(\rho+1)}.$
(4.4)

For simplicity, we introduce a reduced free energy

$\tilde{F}=\frac{\displaystyle 24\sqrt{6}}{\displaystyle
L}F=\frac{-\rho^{4}-4\rho^{3}+3q^{2}+8\rho+6q+8}{\rho+1}.$ (4.5)

Next, we may have two approaches for further calculations. The first one is to
take the same procedure as the former section, first solve the equation of
state to obtain $\rho=\rho(t,q)$ and then substitute it into Eq.(4.5) to
obtain the free energy as functions of $(t,q)$. But here we choose another
method used by HilferHilfer.2000 . In the $(t,q)$ plane, there are infinitely
many possible ways of approaching the critical point. We can reparametrize the
dimensionless quantities,

$t=x\cos\theta,\quad q=x\sin\theta,$ (4.6)

where $\theta$ controls the direction of approaching the critical point, and
$x\rightarrow 0$ leads to $t\rightarrow 0$ and $q\rightarrow 0$.

Correspondingly, in this new coordinate $(x,\theta)$, we have

$\tilde{F}=\tilde{F}(t,q)=\hat{F}(x,\theta).$ (4.7)

In this way, we can solve Eq.(4.3) to obtain

$\displaystyle\rho$ $\displaystyle=$
$\displaystyle\rho(x,\theta)=\frac{x^{1/3}(\sin\theta+4\cos\theta)^{1/3}}{2^{1/3}}+\frac{x}{32}(3\sin\theta+28\cos\theta)+\frac{x^{2/3}(12\cos\theta-\sin\theta)}{4\times
2^{2/3}(\sin\theta+4\cos\theta)^{1/3}}$ (4.8) $\displaystyle+$
$\displaystyle\frac{x^{4/3}\left(29\sin^{3}\theta+2368\cos^{3}\theta+1136\sin\theta\cos^{2}\theta-4\sin^{2}\theta\cos\theta\right)}{384\times
2^{1/3}(\sin\theta+4\cos\theta)^{5/3}}+O(x^{5/3}).$

But it should be noted that this series solution is valid for
$\sin\theta+4\cos\theta\neq 0$, namely $q+4t\neq 0$. Substituting Eq.(4.6) and
Eq.(4.8) into Eq.(4.5), we obtain

$\displaystyle\hat{F}(x,\theta)$ $\displaystyle=$ $\displaystyle
8+(4\sin\theta-8\cos\theta)x-\frac{3(\sin\theta+4\cos\theta)^{4/3}x^{4/3}}{2^{1/3}}$
(4.9) $\displaystyle+$
$\displaystyle\frac{3(\sin\theta-4\cos\theta)(\sin\theta+4\cos\theta)^{2/3}x^{5/3}}{2^{2/3}}+\frac{[8\sin(2\theta)-309\cos(2\theta)-299]x^{2}}{32}$
$\displaystyle+$ $\displaystyle O(x^{7/3}).$

Now we can calculate the fractional derivatives of the free energy and take
the $x\rightarrow 0^{+}$ limit. The results are as follows,

$\lim_{x\rightarrow
0^{+}}D_{x}^{\alpha}\hat{F}(x,\theta)=\left\\{\begin{array}[]{lr}0{}{}&\text{for}~{}~{}\alpha<4/3,\\\
-\frac{4\times
2^{2/3}\pi(\sin\theta+4\cos\theta)^{4/3}}{3\sqrt{3}\Gamma\left(\frac{2}{3}\right)}{}{}&\text{for}~{}~{}\alpha=4/3,\\\
\pm\infty{}{}&\text{for}~{}~{}\alpha>4/3,\end{array}\right.$ (4.10)

Except for those values of $\theta$ satisfying $\sin\theta+4\cos\theta=0$, the
$4/3$-order derivative of the free energy is discontinuous, which is a
signature of $4/3$-order phase transition. For clarity, we can choose a
concrete direction to depict the fractional derivative. We take $\theta=0$ and
$\theta=\pi$, which correspond to the $t$-axis, thus $q=0$. Substituting them
into Eq.(4.9), we can obtain

$\tilde{F}(t)=\left\\{\begin{array}[]{lr}8-8t-12\times 2^{1/3}t^{4/3}-12\times
2^{2/3}t^{5/3}-19t^{2}+O(t^{7/3}),{}{}&~{}~{}t>0,\\\ 8-8t-12\times
2^{1/3}(-t)^{4/3}+12\times
2^{2/3}(-t)^{5/3}-19t^{2}+O(t^{7/3}),{}{}&~{}~{}t<0.\end{array}\right.$ (4.11)

Due to the $(\pm t)^{4/3}$ terms, there is indeed a finite jump for
$\alpha=4/3$,

$\lim_{t\rightarrow 0^{-}}\frac{\displaystyle
d^{\alpha}\tilde{F}}{\displaystyle
dt^{\alpha}}=\frac{32\sqrt[3]{2}\pi}{3\sqrt{3}\Gamma(2/3)}\neq\lim_{t\rightarrow
0^{+}}\frac{\displaystyle d^{\alpha}\tilde{F}}{\displaystyle
dt^{\alpha}}=-\frac{32\sqrt[3]{2}\pi}{3\sqrt{3}\Gamma(2/3)}.$ (4.12)

According to the generalized classification, the phase transition at the
critical point is of $4/3$ order. The result is exhibited in Fig.4.

Figure 4: The behaviors of $D_{t}^{\alpha}\tilde{F}(t)$ near the critical
point for RN-AdS black hole.

Now we need to deal with the exceptional case, $t+4q=0$, which selects a
special direction in the $(t,q)$ plane. We need to approach the critical point
along this direction from both sides.

In this case, the equation of state becomes

$-3\rho^{4}+\rho^{3}(8t-4)+24\rho^{2}t+24\rho t+16t^{2}=0.$ (4.13)

Its series solution is

$\rho(t)=-\frac{2t}{3}-\frac{40t^{2}}{81}-\frac{470t^{3}}{729}+O(t^{4}).$
(4.14)

One can see that in this special case there are no terms with fractional
exponents. It naturally leads to a free energy without fractional exponents

$\tilde{F}(t)=8-24t+32t^{2}+\frac{32t^{3}}{3}+O(t^{4}).$ (4.15)

Clearly, in the $t\rightarrow 0$ limit, the arbitrary fractional order
derivatives of this free energy is zero and integral order derivatives are
constants, thus the free energy is always continuous. This exceptional
direction is called phase boundary at the critical pointHilfer.2000 , but
where it is a second-order phase transition along this phase boundary.

##  5 Discussions and Conclusions

Based on the generalized Ehrenfest classification of phase transition, we
analyzed the phase structure of RN-AdS black hole at the Davies points. There
should be two types of Davies points, corresponding to the extreme points and
infection points of the temperature, respectively. According to standard
Ehrenfest classification, it is second-order phase transitions occurring at
these points. However, by means of fractional derivatives we found that at the
first type of Davies points, the phase transition is of $3/2$ order. At the
second types of Davies point, it is a $4/3$-order phase transition, which is
the same as the result we obtained in extended phase spaceMa.490495.2019 .
Therefore, this generalized classification can indeed reflect more details on
the critical behaviors of black holes.

RN black hole and Schwarzschild-AdS(SAdS) black hole can be taken as the
$\Lambda\rightarrow 0$ and $Q\rightarrow 0$ limits of RN-AdS black hole,
respectively. The two black holes both have the first type of Davies point. We
also studied the fractional phase transition of these black holes and found
that they are both of $3/2$ order. Indeed, if we divide the temperature curve
of the RN-AdS black hole into two parts, the left part has similar behaviors
to that of the RN black hole and the right part is similar to the temperature
of the SAdS. So it is not surprising that they have the same order of phase
transition.

We used to think that the equations of state determine the order of fractional
phase transition. But, according to Chabab.620430.2021  it seems that what
influences the order of phase transition is the symmetry of black hole
spacetimes. In the present work, one can see that the equations of state near
the first and second type of Davies points are both quartic equations. To
clarify this problem, we need to further consider other black holes. Although
for RN-AdS black hole it is a $3/2$-order phase transition at the first type
of Davies point, we do not know whether the order is the same for other black
holes with the first type of Davies point. Until now, the generalized
Ehrenfest classification is only used to deal with phase transitions at Davies
points of black holes. It should also be available for reanalyzing the
original first-order phase transition. The orders of phase transitions at
critical points are related to critical exponents. In real physical system,
these exponents can be explored in laboratory. The critical exponents
corresponding to the fractional order phase transitions of black holes should
also be examined. These interesting problems should be considered in future
works.

###### Acknowledgements.

We are grateful to the reviewers for their suggestions that helped to improve
the content of the paper. This work is supported in part by Shanxi Provincial
Natural Science Foundation of China (Grant No. 201701D121002), by Scientific
and Technological Innovation Programs of Higher Education Institutions in
Shanxi (Grant No. 2021L386) and by Datong City Key Project of Research and
Development of Industry of China (Grant No. 2018021).

## References

  * (1) P. Hut, _Charged black holes and phase transitions_ , _Monthly Notices of the Royal Astronomical Society_ 180 (1977) 379–389.
  * (2) P. C. W. Davies, _Thermodynamics of black holes_ , _Reports on Progress in Physics_ 41 (1978) 1313–1355.
  * (3) L. M. Sokolowski and P. Mazur, _Second-order phase transitions in black-hole thermodynamics_ , _Journal of Physics A: Mathematical and General_ 13 (1980) 1113–1120.
  * (4) A. Chamblin, R. Emparan, C. V. Johnson and R. C. Myers, _Charged ads black holes and catastrophic holography_ , _Physical Review D_ 60 (1999) 064018.
  * (5) A. Chamblin, R. Emparan, C. V. Johnson and R. C. Myers, _Holography, thermodynamics, and fluctuations of charged ads black holes_ , _Physical Review D_ 60 (1999) 104026.
  * (6) C. S. Peça and J. P. S. Lemos, _Thermodynamics of reissner–nordström–anti-de sitter black holes in the grand canonical ensemble_ , _Physical Review D_ 59 (1999) 124007.
  * (7) S. Carlip and S. Vaidya, _Phase transitions and critical behaviour for charged black holes_ , _Classical and Quantum Gravity_ 20 (2003) 3827–3837.
  * (8) J. X. Lu, S. Roy and Z. Xiao, _Phase transitions and critical behavior of black branes in canonical ensemble_ , _Journal of High Energy Physics_ 2011 (2011) 133.
  * (9) H. Liu, H. Lü, M. Luo and K.-N. Shao, _Thermodynamical metrics and black hole phase transitions_ , _Journal of High Energy Physics_ 2010 (2010) 054.
  * (10) R. Banerjee, S. K. Modak and S. Samanta, _Second order phase transition and thermodynamic geometry in kerr-ads black holes_ , _Physical Review D_ 84 (2011) 064024.
  * (11) Q.-J. Cao, Y.-X. Chen and K.-N. Shao, _Black hole phase transitions in hořava-lifshitz gravity_ , _Physical Review D_ 83 (2011) 064015.
  * (12) M. Wang, S. Chen and J. Jing, _Second-order phase transition of kehagias–sfetsos black hole in deformed hořava–lifshitz gravity_ , _Physics Letters B_ 695 (2011) 401–404.
  * (13) C. Niu, Y. Tian and X.-N. Wu, _Critical phenomena and thermodynamic geometry of reissner-nordström-anti-de sitter black holes_ , _Physical Review D_ 85 (2012) 024017.
  * (14) S.-W. Wei and Y.-X. Liu, _Critical phenomena and thermodynamic geometry of charged gauss-bonnet ads black holes_ , _Physical Review D_ 87 (2013) 044014.
  * (15) B. P. Dolan, _Pressure and volume in the first law of black hole thermodynamics_ , _Classical and Quantum Gravity_ 28 (2011) 235017.
  * (16) D. Kubizňák and R. B. Mann, _P $-$ v criticality of charged ads black holes_, _Journal of High Energy Physics_ 2012 (2012) 033.
  * (17) R.-G. Cai, L.-M. Cao, L. Li and R.-Q. Yang, _P-v criticality in the extended phase space of gauss-bonnet black holes in ads space_ , _Journal of High Energy Physics_ 2013 (2013) 005.
  * (18) S. H. Hendi and M. H. Vahidinia, _Extended phase space thermodynamics and p $-$v criticality of black holes with a nonlinear source_, _Physical Review D_ 88 (2013) 084045.
  * (19) S.-B. Chen, X.-F. Liu and C.-Q. Liu, _P—v criticality of an ads black hole in f ( r ) gravity_ , _Chinese Physics Letters_ 30 (2013) 060401.
  * (20) J.-X. Mo, X.-X. Zeng, G.-Q. Li, X. Jiang and W.-B. Liu, _A unified phase transition picture of the charged topological black hole in hořava-lifshitz gravity_ , _Journal of High Energy Physics_ 2013 (2013) 056.
  * (21) Y. Liu, D.-C. Zou and B. Wang, _Signature of the van der waals like small-large charged ads black hole phase transition in quasinormal modes_ , _Journal of High Energy Physics_ 2014 (2014) 179.
  * (22) M.-S. Ma, F. Liu and R. Zhao, _Continuous phase transition and critical behaviors of 3d black hole with torsion_ , _Classical and Quantum Gravity_ 31 (2014) 095001.
  * (23) H. Xu, W. Xu and L. Zhao, _Extended phase space thermodynamics for third-order lovelock black holes in diverse dimensions_ , _The European Physical Journal C_ 74 (2014) 3074.
  * (24) M.-S. Ma and Y.-Q. Ma, _Critical behaviors of a black hole in an asymptotically safe gravity with cosmological constant_ , _Classical and Quantum Gravity_ 32 (2015) 035024.
  * (25) J. Xu, L.-M. Cao and Y.-P. Hu, _P $-$v criticality in the extended phase space of black holes in massive gravity_, _Physical Review D_ 91 (2015) 124033.
  * (26) S.-W. Wei, P. Cheng and Y.-X. Liu, _Analytical and exact critical phenomena of d -dimensional singly spinning kerr-ads black holes_ , _Physical Review D_ 93 (2016) 084015.
  * (27) M.-S. Ma and R.-H. Wang, _Peculiar p $-$v criticality of topological hořava-lifshitz black holes_, _Physical Review D_ 96 (2017) 024052.
  * (28) Y.-G. Miao and Z.-M. Xu, _Parametric phase transition for a gauss-bonnet ads black hole_ , _Phys. Rev. D_ 98 (Oct, 2018) 084051.
  * (29) Z.-M. Xu, _Fokker-planck equation for black holes in thermal potential_ , _Physical Review D_ 104 (2021) 104022.
  * (30) R. Hilfer, _Multiscaling and classification of continuous phase transitions_ , _Phys. Rev. Lett._ 68 (1992) 190.
  * (31) R. Hilfer, _Applications of fractional calculus in physics_.  World scientific, 2000.
  * (32) M.-S. Ma, _Fractional-order phase transition of charged ads black holes_ , _Physics Letters B_ 795 (2019) 490–495.
  * (33) M. Chabab and S. Iraoui, _Fingerprinting the fractional order phase transitions in ads black holes_ , _Frontiers in Physics_ 8 (2021) 620430.
  * (34) M. Chabab and S. Iraoui, _Demystifying the fractional order phase transitions in ads black holes_ , 2022.  arXiv.2205.14674.
  * (35) M. Caputo, _Linear models of dissipation whose q is almost frequency independent—ii_ , _Geophysical Journal International_ 13 (1967) 529–539.
  * (36) A. A. Kilbas, O. Marichev and S. Samko, _Fractional integrals and derivatives (theory and applications)_.  Gordon and Breach, Switzerland, 1993.
  * (37) R. Gorenflo and F. Mainardi, _Fractional calculus_ , in _Fractals and fractional calculus in continuum mechanics_ , pp. 223–276.  Springer, 1997.


# A Comprehensive Analysis on the Leakage of Fuzzy Matchers

DURBET Axel  LIMOS, Université Clermont-Auvergne,
CNRS, Mines Saint-Étienne,
Aubière, France
<EMAIL_ADDRESS>GROLLEMUND Paul-Marie  LMBP, Université Clermont Auvergne,
CNRS, UMR 6620,
Aubière, France
<EMAIL_ADDRESS>THIRY-ATIGHEHCHI Kevin  LIMOS, Université
Clermont-Auvergne,
CNRS, Mines Saint-Étienne,
Aubière, France
<EMAIL_ADDRESS>
###### Abstract

This paper provides a comprehensive analysis of information leakage during
distance evaluation, with an emphasis on threshold-based obfuscated distance
(i.e., Fuzzy Matcher). Leakage can occur due to a malware infection or the use
of a weakly privacy-preserving matcher, exemplified by side channel attacks or
partially obfuscated designs. We provide an exhaustive catalog of information
leakage scenarios as well as their impacts on the security concerning data
privacy. Each of the scenarios leads to generic attacks whose impacts are
expressed in terms of computational costs, hence allowing the establishment of
upper bounds on the security level.

###### Index Terms:

Obfuscated Distance, Fuzzy Matcher, Hamming Distance, $L_{1}$ Distance, Attack
Complexity, Information Leakage, Biometrics, Coupon Collector Problem

##  I Introduction

In cryptology, the investigation of obfuscated distance functions is still
limited, and articles discussing this topic are relatively recent and scarce.
An obfuscated distance function facilitates the computation of the distance
between two hidden inputs by multiple parties, wherein each party gains
knowledge solely of the distance while preserving the privacy of the actual
inputs. These functions can be iteratively applied with various features, and
one of their fundamental properties is the preservation of input privacy.

A first approach to design an obfuscated distance function involves employing
homomorphic cryptography [1, 2, 3], which enables computations to be directly
applied on encrypted data without requiring decryption, thereby ensuring the
confidentiality of sensitive information; Garbled circuit [2, 4, 5] is a
cryptographic primitive based on symmetric encryption and oblivious transfer
which is used to privately evaluate a function on encrypted inputs without
revealing the inputs or the function’s logic to the evaluator. Functional
Encryption [6, 7, 8, 9, 10] enables the implementation of specific functions
on encrypted data, providing privacy and enhanced security across a wide range
of applications such as the distance evaluation; Oblivious transfer [11, 12,
13] enables secure multiparty computation while ensuring input privacy by
allowing data exchange without revealing the content; or others mathematical
methods based on computational assumptions [14, 15, 16, 17]. The obfuscated
distance is also employed for biometric applications, aiming at protecting the
client’s privacy while maintaining the effectiveness of the biometric
identification process. These cryptographic primitives can also be designed by
relying on a threshold-based obfuscated distance, related to error-correcting
codes [18], which are designed to detect and correct errors that may arise
during digital data transmission or storage, thereby ensuring reliable and
precise data retrieval; Secure sketches and fuzzy extractors [19, 20, 21, 22,
23] are cryptographic schemes able of extracting a consistent and reusable
cryptographic key from noisy or biometric data, facilitating secure
authentication while accommodating minor variations in the input data; Fuzzy
vaults [24] are cryptographic designs that securely store and retrieve secret
information by utilizing error-correcting codes and a noisy input (e.g.
biometric data), ensuring strong protection against unauthorized access and
maintaining data integrity.

All the previous functions and primitives are either founded on or encompass
Fuzzy Matcher, which belongs to a subclass of evasive functions. Evasive
functions [14, 25] are related to a class of functions that represent
significant computational challenges for any efficient algorithm attempting to
compute their output with high probability on most inputs. While many authors
focus on fuzzy matching for the Hamming distance, this paper directly tackles
the case of vectors in $\mathbb{Z}_{q}^{n}$ for the $L_{1}$ distance.
Furthermore, notice that our findings can be extended to the Hamming distance
as well. The theoretical security of each considered function and primitive is
extensively investigated and well-documented in their respective papers,
including the evaluation of the difficulty for an attacker to retrieve the
initially hidden input. However, the growing prevalence of side-channel
attacks [26, 27], implementation errors, or construction flaws [28] has raised
uncertainties about the provided security bounds. One possible concern is the
partial leakage of distance calculation information, which could lead to
unintended information disclosure during the execution of the function. Such
inadvertent disclosures involve significant security and privacy risks,
especially in sensitive applications like cryptographic protocols or data
privacy frameworks (e.g., biometric systems).

Understanding the implications of information leakage is a milestone in this
scientific literature. Hence, this paper focuses on assessing the impact of
such information leakage and on the complexity of retrieving hidden data. By
investigating this issue, we aim at enhancing knowledge of the impact on the
security of obfuscated distance designs and to improve the overall
understanding of information leakage risks in cryptographic systems.

Taking the examples of biometric authentication (that requires testing a
predicate about a distance) or password authentication (that requires testing
a predicate of equality), attacks of interest can be divided into two
categories:

  * •

Offline exhaustive search attacks correspond to attacks where a leaked but
protected database is given to the attacker, but the cryptographic obfuscation
mechanism used for the verification of a protected fresh vector (biometric
template), or the verification of a protected (hashed) password, is not
supposed to leak any information beyond its admissibility.

  * •

Online exhaustive search attacks correspond to attacks where an attacker is
enforced to interact with the authentication server to deduce information
about the target vector. Such attacks may require malware infection on the
server, in order for the attacker to retrieve additional leakage from the
matcher, i.e., beyond the minimal information leakage (‘yes’ or ‘no’).

#### Related Works

Pagnin et al. [29] demonstrated that in the context of a Fuzzy Matcher, the
result of the matcher can be exploited to retrieve the hidden vector. Their
work takes place in the minimal leakage, wherein only the matcher’s binary
output is given to the attacker. They explained the execution of this attack
and assessed its complexity. Our work shares a similar focus, as similar tools
are also examined. However, we extend the analysis by taking into account the
possibility of multiple additional information leaks thanks to the matching
operation. Similar to the aforementioned work, the proposed attacks aim at
recovering the original data, which, in the context of biometrics, corresponds
to compromising the privacy of the biometric data. This type of attack is
considered the most devastating for such systems, as evidenced by Simoens et
al. [30]. To the best of our knowledge, this is the sole paper that
comprehensively investigates this subject.

#### Contributions

We present a deep analysis of potential information leakage in distance
evaluation, with a specific focus on threshold-based obfuscated distance. The
paper thoroughly describes various scenarios where information leakage may
occur and examines their implications for security. To achieve this, we
systematically outline generic attacks corresponding to each scenario and
assess their complexities. Our contribution is to provide insights into the
finer points of information leakage in threshold-based obfuscated distance,
thus advancing the field of information security. The discussed scenarios give
rise to new attacks as well as a range of attacks that complete the work of
Pagnin et al.:

  1. 1.

Accumulation attacks that capture potential attacks from an honest-but-curious
server when a client authenticates to it. These attacks assume the use of
privacy-preserving cryptographic primitives for evaluating the distance
between two hidden vectors. Specifically, as an example, we assume the use of
a cryptographic obfuscator of the distance function.

  2. 2.

Attacks launched by malicious clients exploiting various information leakage
from the matcher in the context of a leaked (but obfuscated) database, or by
interacting with the server during an online exhaustive search attack. As a
summary of our main contributions, the complexity type of our attacks is
summarized in Table I along with the scenarios considered.

Complexity type | Threshold related | Leakage | Need genuine client | Theorem
---|---|---|---|---
Exp. | Above | Position | $\times$ | Theorem 3
Below | Distance | $\times$ | Theorem 6
Position | $\times$ | Theorem 7
Distance and positions | $\times$ | Theorem 8
Below | Distance, positions and values | $\times$ | Theorem 9
Both | Positions | $\times$ | Theorem 12
Minimal | $\times$ | Theorem 10
Lin. | Above | Distance | $\times$ | Theorem 2
Distance and position | $\times$ | Theorem 4
Below | Positions and values (accumulation) | $\checkmark$ | Theorem 1
Both | Distance | $\times$ | Theorem 11
Distance and positions | $\times$ | Theorem 13
Const. | Above | Distance, position, and values | $\times$ | Theorem 5
Both | Distance, positions and values | $\times$ | Theorem 14
Table I:  Summary of the different leakages and their corresponding exploit
complexities.

#### Outline

Section II initially presents the fundamental definitions required to read the
paper, with a particular emphasis on the matcher. We also introduce certain
notations and terminologies, and provide a classification of leakages. This
comprehensive description of all leakage scenarios allows for an analysis of
potential information leaks. The key contributions of the paper are
highlighted in Section III, where Table II offers a succinct overview of the
scenarios. In the subsection III-B, we describe a novel attack paradigm that
encompasses the accumulation attack, along with a complete analysis of its
complexity. In contrast, the subsections III-D, III-C, III-E deepen detailing
various attacks corresponding to the identified scenarios, alongside an
assessment of their complexities. A succinct summary of these complexities is
provided in Table III.

##  II Preliminaries

In this section, the (Obfuscated) Matcher is introduced as a function utilized
for verifying the proximity of two hidden inputs. Secondly, the notations used
throughout the analysis are presented. Then, a list of all the considered
information leakage scenarios is presented.

###  II-A (Obfuscated) Matcher

Let $\mathbb{Z}_{q}^{n}$ be a metric space equipped with the distance $d$ and
$\epsilon\in\mathbb{R}_{\geq 0}$ a threshold. A private matching scheme $\Xi$
is a pair of an algorithm Hide and a Match which respectively allow hiding a
data $x\in\mathbb{Z}_{q}^{n}$ and check if a newly provided data
$y\in\mathbb{Z}_{q}^{n}$ is such that $d(x,y)\leq\epsilon$.

######  Definition 1 (Hide)

Let $\Xi$ be a matching scheme, $\mathbb{Z}_{q}^{n}$ be a metric space
equipped with the distance $d$, a space $\mathbb{K}$ and
$\epsilon\in\mathbb{R}_{\geq 0}$ a threshold. Given $x\in\mathbb{Z}_{q}^{n}$,

$\displaystyle\Xi.\texttt{Hide}:$ $\displaystyle\mathbb{Z}_{q}^{n}$
$\displaystyle\xrightarrow{}\mathbb{K}$ $\displaystyle x$
$\displaystyle\xrightarrow{}X$

Such that $\Xi.\texttt{Hide}$ can be computed by a polynomial time algorithm
(PPT), but any polynomial time randomized algorithm $\mathcal{A}$ that
attempts to compute a pseudo-inverse for $\Xi.\texttt{Hide}$ succeeds with
negligible probability.

Once $x$ has been hidden by the function $\Xi.\texttt{Hide}$, it is possible
to check if a vector $y$ is close to $x$ with respect to $\epsilon$. In other
words, $\Xi.\texttt{Match}$ indicates if $y\in B_{\epsilon}(x)$, where
$B_{\epsilon}(x)=\\{y\in\mathbb{Z}_{q}^{n}\,|d(x,y)\leq\epsilon\\}$ is the
ball of radius $\epsilon$ and centered in $x$.

######  Definition 2 (Match)

Let $\Xi$ be a matching scheme, $\mathbb{Z}_{q}^{n}$ be a metric space
equipped with the distance $d$, $x\in\mathbb{Z}_{q}^{n}$, $\mathbb{K}$ be
$\Xi.\texttt{Match}(\mathbb{Z}_{q}^{n})$ and $\epsilon\in\mathbb{R}_{\geq 0}$
a threshold. Given $Y\in\mathbb{K}$ the output of $\Xi.\texttt{Hide}(y)$ and
$X$ the output of $\Xi.\texttt{Hide}(x)$,

$\displaystyle\Xi.\texttt{Match}:$ $\displaystyle\mathbb{K}\times\mathbb{K}$
$\displaystyle\xrightarrow{}\\{0,1\\}$ $\displaystyle Y,X$
$\displaystyle\xrightarrow{}\begin{cases}0&\text{ if }d(x,y)\leq\epsilon,\\\
1&\text{ otherwise},\\\ \end{cases}$

such that $\Xi.\texttt{Match}$ is a deterministic polynomial time algorithm
that succeeds with probability $1$.

###### Remark II-A.1

Both $\Xi.\texttt{Match}$ inputs are hidden by the function
$\Xi.\texttt{Hide}$.

To simplify, we assume that a vector $y\in\mathbb{Z}_{q}^{n}$ can be directly
used with $\Xi.\texttt{Match}$, i.e., pre-transformation
$\Xi.\texttt{Hide}(y)$ is omitted when it is not necessary. The
$\Xi.\texttt{Match}$ function has the possibility to disclose certain
information, and its possible leakage scenarios are described in the following
sections.

###  II-B Notations and Attacker Models

In the following, we consider the metric space $\mathbb{Z}_{q}^{n}$ (the set
of vectors of size $n$ with value in $\llbracket 0,q-1\rrbracket$) equipped
with the distance $d$. Let us define the oracle $\sigma_{x,\epsilon}$ that
models the role of $\Xi.\texttt{Match}$, to which the attacker is given
access. For the sake of simplicity, the threshold $\epsilon$ and the hidden
vector $x$ are omitted when the context is explicit.

In this framework, the goal of the attacker is to retrieve the hidden data
$x\in\mathbb{Z}_{q}^{n}$ from the transformation $\Xi.\texttt{Hide}(x)$. To do
so, she is performing queries to the oracle $\sigma_{x,\epsilon}$ as well as
the function $\Xi.\texttt{Hide}$. Moreover, as regards the accumulation attack
scenario, the attacker has access to the oracle $\mathcal{O}_{x,\epsilon}$
which returns $\Xi.\texttt{Hide}(y)$ with $d(x,y)\leq\varepsilon$. Hence,
$\mathcal{O}$ returns a new hidden vector from the genuine client during its
authentication in the system. A matching scheme $\Xi$, as defined in Section
II-A, can leak some information and we consider that $\Xi.\texttt{Match}$
leaks extra information beyond its binary output ($0$ or $1$). The section
comprises two subsections. The first one enumerates the types of information
leaks related to a matching scheme and defines the associated scenarios. The
second subsection focuses on the various attacks employed to exploit the
leaked information. By examining these aspects, we aim at enhancing the
understanding of the real security of a matching scheme under different
leakage scenarios.

###  II-C Typology of Information Leakage

There are three main categories of leakage:

  1. 1.

Information leakage below the threshold.

  2. 2.

Information leakage above the threshold.

  3. 3.

Information leakage both below and above the threshold.

Among these scenarios, several sub-settings can be identified. The first sub-
setting corresponds to the absence of any leakage, resulting in
$\Xi.\texttt{Match}$ yielding only binary outcomes ($0$ or $1$). Then, the
following sub-settings are examined:

  1. 1.

Knowledge of the distance $d$.

  2. 2.

Knowledge of the positions of the errors only.

  3. 3.

Knowledge of both the distance $d$ and the positions of the errors.

  4. 4.

Knowledge of both the distance and the positions and their corresponding
values.

All these scenarios and sub-settings are summarized in Table III.

Threshold | Extra Information
---|---
Above | No extra leakage
Distance
Position
Distance and position
Distance, position, and value
Below | No extra leakage
Distance
Position
Distance and, position
Distance, position, and value
Above and Below | No extra leakage
Distance
Position
Distance and position
Distance, position, and value
Table II:  Summary of distance leakages.

##  III Attacks exploiting Leaking Distance

###  III-A Leakage Exploit Attacks

Several attacks are related to the different types of aforementioned leakage
scenarios. The first attack is the exhaustive search, which tests all possible
vectors until the right one is found.

######  Definition 3 (Exhaustive Search or Brute-Force Search)

This attack is a very general problem-solving technique that consists in
testing all possibilities until the problem statement is verified. The
complexity of this attack is $O(q^{n})$ queries to $\sigma$.

Then, by considering some extra information, it is possible to perform a hill-
climbing attack [31]. The aim is to find the solution by iteratively improving
a potential solution.

######  Definition 4 (Hill-climbing attack)

The hill-climbing attack is based on a mathematical optimization technique. It
begins with an arbitrary solution, then it attempts to improve the solution by
applying some slight variations. If the modified solution improves the score
obtained with the target function, the previous process is repeated with the
new solution until the attack succeeds. The complexity of this attack is in
$O(nq)$.

By employing the oracles $\sigma$ and $\mathcal{O}$ under specific conditions,
the attacker recovers the complete information of $x$ by accumulating some
knowledge about $x$ at each query. However, the accumulation attack only
applies to special cases, which are examined in more detail in Section III-B.

######  Definition 5 (Accumulation Attack)

The accumulation attack is a passive attack where the attacker recovers a
certain amount of information at each interaction. By accumulating this
information, the entropy of the target is getting smaller until its entropy
goes to zero. In the end, the attacker has a complete knowledge of the target.

In [29], the authors show that from any closed vector $y$ of $x$, i.e.,
$d(x,y)\leq\varepsilon$, it is possible to retrieve the center $x$ of the ball
using $\sigma$.

######  Definition 6 (Center Search Attack [29, 30])

This attack aims at finding $x$ the center of the acceptance ball
$B_{\epsilon}(x)$. The starting point of the attack is to find a point
$b^{\prime}$ on the edge of the ball, and then converge to its center. The
complexity of this attack is $O(nm)$ where $m=\mathrm{min}(\lfloor
2\epsilon\rfloor,2\ln q)$.

We refer the reader to the work of Pagnin et al. [29] for more details.

###  III-B Accumulation Attack

To model this attack, we consider that $\sigma$ leaks information on the
positions and values of errors. Assume that the errors in $y$ given by
$\mathcal{O}$ are uniformly distributed.

###### Theorem 1

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the positions of the errors
and their values below the threshold, an attacker can retrieve $x$ in
$O\left(\sum_{j=1}^{n}(-1)^{j-1}\binom{n}{j}\left(1-\frac{n-j}{n}\right)^{-1}\right)$
queries to to both $\mathcal{O}_{x,\varepsilon}$ and $\sigma_{x,\varepsilon}$.

The complexity of this attack relies on the coupon collector’s problem. This
problem is a well-known problem of probability theory, where one seeks to
determine the expected number of trials needed to collect a complete set of
distinct items from a large pool with replacement. This problem has received
considerable attention in the literature, with notable studies conducted by
Ferrante et al. [32, 33] and Flajolet et al. [34].

In order to support Definition 5 and gives the ideas for the proof of Theorem
1, the subsequent example serves to illustrate the design of an Accumulation
Attack.

###### Example III-B.1

Assume a setting with a metric space $\mathbb{Z}_{2}^{n}$ equipped with the
Hamming distance. A client seeks to authenticate to an honest-but-curious
server that uses a scheme leaking $d_{H}(x,y)$ and the corresponding errors if
$d_{H}(x,y)\leq\epsilon$. As the client is legitimate, i.e.,
$d_{H}(x,y)\leq\epsilon$, the server recovers the value of at most $\epsilon$
erroneous bits. If the server is lucky, in $n/\epsilon$ steps, the data of the
client is compromised. The server needs to collect all the bits of the client,
turning this problem into a Coupon Collector problem. According to Ferrante et
al. [32, 33] and assuming that errors uniformly occur in vector coordinates,
the server retrieves the biometric data after an expected number of $N$
authentications with

$\displaystyle\sum\limits_{j=1}^{n}(-1)^{j-1}\binom{n}{j}\left(1-\frac{n-j}{n}\right)^{-1}$
$\displaystyle\geq N$
$\displaystyle\sum\limits_{j=1}^{n}(-1)^{j-1}\binom{n}{j}\left(1-\frac{\binom{n-j}{\epsilon}}{\binom{n}{\epsilon}}\right)^{-1}$
$\displaystyle\leq N.$

For example, let assume $x=(0,0,1,1,0,1,0)$, $\varepsilon=3$. The server set
$z=(?,?,?,?,?,?,?)$. Session 1: The client authenticates with
$y=(1,1,0,1,0,1,0)$. In this case, $d_{H}(x,y)=3\leq\varepsilon$. The server
gets the value of the erroneous bits of the client and updates
$z=(0,0,1,?,?,?,?)$. Session 2: the client authenticates with
$y=(0,0,0,0,1,1,0)$. In this case, $d_{H}(x,y)=3\leq\varepsilon$, and the
server gets the value of the erroneous bits of the client and updates
$z=(0,0,1,1,0,?,?)$. Finally, the server has a vector inside the ball. Hence,
she is able to perform an impersonation attack because the entropy of $z$ is
smaller than the threshold, or she can perform the Center Search Attack 6.
Moreover, by trying some extra steps, she will retrieve the very last bits.

###### Proof 1

Using the same argument as in the example, the vector $x$ is recovered in
$O\left(\sum_{j=1}^{n}(-1)^{j-1}\binom{n}{j}\left(1-\frac{n-j}{n}\right)^{-1}\right)$
queries to both $\mathcal{O}_{x,\varepsilon}$ and $\sigma_{x,\varepsilon}$.
$\blacksquare$

###  III-C Attacks complexities for a leakage above the threshold

In this section, the first scenario is considered, which involves leakage
above the threshold $\varepsilon$. In other words, when a hidden vector $x$ is
used, the submission of another vector $y$ such that $d(x,y)>\varepsilon$ to
the $\sigma_{x,\varepsilon}$ oracle may lead to the extra gain of knowledge.

#### The distance is leaked

The first case happens when the distance is provided to the attacker as the
extra gain of knowledge.

###### Theorem 2

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the distance above the
threshold, an attacker can retrieve $x$ in $O(n(q+m)-\varepsilon)$ queries to
$\sigma_{x,\varepsilon}$, where $m=\mathrm{min}(\lfloor 2\epsilon\rfloor,2\ln
q)$.

###### Proof 2

In this situation, a hill-climbing attack can be executed by the attacker
until a vector $y$ is obtained, precisely at a distance of $\varepsilon$ from
their target $x$. This stage of the attack can be completed within
$nq-\varepsilon$ steps. Subsequently, the hill-climbing attack cannot be
continued since it falls below the threshold, yielding no further extra
information. However, the attacker can now proceed with the center search
attack, which requires $nm$ steps, where $m=\mathrm{min}(\lfloor
2\epsilon\rfloor,2\ln q)$. As a result, the complexity of the attack aimed at
recovering $x$, in this case, is in $O(n(q+m)-\varepsilon)$.
$\blacksquare$

#### The positions are leaked

In this case, the error positions are the extra information provided to the
attacker, while the value of each error remains secret.

###### Theorem 3

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the error positions above
the threshold, an attacker can retrieve $x$ in average in
$O(q^{n(1-1/q)-\varepsilon}+nm)$ (resp. in the worst case in
$O(q^{n-\varepsilon}+nm)$) where $m=\mathrm{min}(\lfloor 2\epsilon\rfloor,2\ln
q)$ queries to $\sigma_{x,\epsilon}$.

###### Proof 3

An exhaustive search on the erroneous coordinates must be performed by the
attacker to down below the threshold. It is reasonable to assume that this
part can be accomplished in $q^{n(1-1/q)-\varepsilon}$ steps. Given two random
vectors $x$ and $y$ from $\mathbb{Z}_{q}^{n}$, the expected number of
coordinates that differ between them is approximately $n(1-1/q)$. This
approximation highlights the difference with the case of an exhaustive search.
Indeed, if we simply look at it asymptotically, there is no difference between
both. Subsequently, the attacker can perform the center search attack in $nm$
steps, where $m=\mathrm{min}(\lfloor 2\epsilon\rfloor,2\ln q)$. Hence, the
overall complexity of the attack in this scenario is in $O(q^{n(1-1/q)}+nm)$.
The worst case is equivalent to the case above.
$\blacksquare$

#### The distance and the position are leaked

In this case, when the attacker queries a vector above the threshold, she is
provided with both the distance and the error positions.

###### Theorem 4

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the distance and the
positions of the errors above the threshold, an attacker can retrieve $x$ in
average in $O(n(q+m-1)-\varepsilon)$ (resp. in the worst case in
$O(n(q+m)-\varepsilon)$) where $m=\mathrm{min}(\lfloor 2\epsilon\rfloor,2\ln
q)$ queries to $\sigma_{x,\epsilon}$.

###### Proof 4

Her hill-climbing attack must be executed on the erroneous coordinates. This
stage can be achieved average in $nq(1-1/q)-\varepsilon$ steps (resp. in the
worst case in $nq-\varepsilon$), using the same argument as the above section.
In the next stage, the attacker can run the center search attack in $nm$
steps, with $m=\mathrm{min}(\lfloor 2\epsilon\rfloor,2\ln q)$. The overall
complexity is in average $O(n(q+m-1)-\varepsilon)$ (resp. in the worst case
$O(n(q+m)-\varepsilon)$).
$\blacksquare$

#### The distance, the position, and the value are leaked

In this last case, the distance, the error positions and values are leaked.

###### Theorem 5

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the distance, the positions
of the errors, and their values above the threshold, an attacker can retrieve
$x$ in $O(1)$ queries to $\sigma_{x,\epsilon}$.

###### Proof 5

In this case, the query answer is an error-correcting code, hence yielding a
complexity of $O(1)$.
$\blacksquare$

###  III-D Attack Complexities for Leakage Below the Threshold

The second scenario is considered, involving leakage below the threshold.
Specifically, assuming the hidden target vector $x$, submitting another vector
$y$ such that $d(x,y)\leq\varepsilon$ to the $\sigma_{x,\varepsilon}$ oracle
may leak additional information. It is important to note that some systems,
such as error-correcting codes, purposely leak information below the threshold
and so this is the most likely scenario.

#### The distance is leaked

The first case occurs when the distance is given to the attacker as extra
information.

###### Theorem 6

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and a fuzzy
matcher $\Xi$ such that $\Xi.\texttt{Match}$ leaks the distance below the
threshold, an attacker can retrieve $x$ in $O(q^{n-\varepsilon}+qn)$ queries
to $\sigma_{x,\epsilon}$.

###### Proof 6

The first step involves obtaining a vector below the threshold, which requires
performing an exhaustive search attack in $q^{n-\varepsilon}$ steps. Then, a
hill-climbing attack can be executed in $qn$ steps. Therefore, the overall
complexity is in $O(q^{n-\varepsilon}+qn)$.
$\blacksquare$

#### The position are leaked

The position of the errors is the extra information given to the attacker,
while their values remain secret.

###### Theorem 7

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the position of the errors
below the threshold, an attacker can retrieve $x$ in
$O(q^{n-\varepsilon}+q^{\varepsilon})$ queries to $\sigma_{x,\epsilon}$.

###### Proof 7

The first step is to fall inside the ball, which requires the attacker to
perform an exhaustive search attack in $q^{n-\varepsilon}$ steps.
Subsequently, an exhaustive search on the erroneous positions must be
performed, which takes $q^{\varepsilon}$ steps. Hence, the complexity of the
attack to recover $x$, in this case, is in
$O(q^{n-\varepsilon}+q^{\varepsilon})$.
$\blacksquare$

Threshold related | Leakage | Complexity type | Worst case complexity in Big-$O$ | Average complexity in Big-$O$
---|---|---|---|---
Above | Distance | Lin. | $n(q+m)-\varepsilon$ | $-$
Position | Exp. | $q^{n-\varepsilon}+nm$ | $q^{n(1-1/q)-\varepsilon}+nm$
Distance and position | Lin. | $n(q+m)-\varepsilon$ | $n(q+m-1)-\varepsilon$
Distance, position, and values | Const. | $1$ | $-$
Below | Distance | Exp. | $q^{n-\varepsilon}+qn$ | $-$
Position | Exp. | $q^{n-\varepsilon}+q^{\varepsilon}$ | $-$
Distance and positions | Exp. | $q^{n-\varepsilon}+q\varepsilon$ | $-$
Positions and values (accumulation) | Lin. | $\infty$ | $\sum_{j=1}^{n}(-1)^{j-1}\binom{n}{j}\left(1-\frac{n-j}{n}\right)^{-1}$
Distance, positions and values | Exp. | $q^{n-\varepsilon}$ | $-$
Both | Minimal | Exp. | $q^{n-\varepsilon}+nm$ | $-$
Distance | Lin. | $nq$ | $-$
Positions | Exp. | $q^{n}$ | $q^{n(1-1/q)}$
Distance and positions | Lin. | $nq$ | $nq(1-1/q)$
Distance, positions and values | Const. | $1$ | $-$
Table III: Summary of all leakage exploits and their complexities, where
$m=\mathrm{min}(\lfloor 2\epsilon\rfloor,2\ln q)$. The dash in the second
column signifies that the worst-case complexity prevails. The average
complexity of the accumulation attack assumes uniformly distributed errors
across each authentication session.

#### The distance and the position are leaked

In this case, the distance and the positions of the errors are given to the
attacker when a vector below the threshold is queried.

###### Theorem 8

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the distance and the
positions of the errors below the threshold, an attacker can retrieve $x$ in
$O(q^{n-\varepsilon}+q\varepsilon)$ queries to $\sigma_{x,\epsilon}$.

###### Proof 8

An exhaustive search is performed by the attacker to fall below the threshold
in $q^{n-\varepsilon}$ steps. Subsequently, a hill-climbing attack is executed
on the faulty coordinates, which takes $q\varepsilon$ steps. Therefore, the
complexity of the attack to recover $x$ in this case is in
$O(q^{n-\varepsilon}+q\varepsilon)$.
$\blacksquare$

#### The distance, the positions, and the values are leaked

In this last case, the distance, the position of the errors, and the value of
each error are leaked.

###### Theorem 9

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the distance, the position
of the errors, and the value of each error below the threshold, an attacker
can retrieve $x$ in $O(q^{n-\varepsilon})$ queries to $\sigma_{x,\epsilon}$.

###### Proof 9

We are confronted with an error-correcting mechanism that allows the
correction below the threshold. The cost of this attack is equivalent to the
cost of an exhaustive search aiming at a vector below the threshold. As a
result, the complexity of the attack to recover $x$, in this case, is in
$O(q^{n-\varepsilon})$.
$\blacksquare$

###  III-E Leakage Below and Above the Threshold

The last scenario is considered, which involves a leakage independent of the
threshold. In other words, when a hidden vector $x$ is targeted, the queried
vector $y$ to the $\sigma_{x,\varepsilon}$ oracle may result in the leak of
additional information. Most of the reasoning comes from the previous cases.

#### Minimal Leakage (single bit of information leakage)

This case is the same for the three possible scenarios (above, below, and
both).

###### Theorem 10

Given $\varepsilon$ a threshold, $x$ a vector in $\mathbb{Z}_{q}^{n}$ and a
fuzzy matcher $\Xi$, an attacker can retrieve $x$ in $O(q^{n-\varepsilon}+nm)$
queries to $\sigma_{x,\epsilon}$, with $m=\mathrm{min}(\lfloor
2\epsilon\rfloor,2\ln q)$.

###### Proof 10

The best chance for the attacker is to find a vector in the ball of $x$. Then,
she performs the center search attack [29]. Hence, the complexity of the
attack to recover $x$ in this case is in $O(q^{n-\varepsilon}+nm)$ with
$m=\mathrm{min}(\lfloor 2\epsilon\rfloor,2\ln q)$.
$\blacksquare$

#### Leakage of Distance

When the distance is given to the attacker, she can perform a hill-climbing
attack in $O(nq)$. This is the classical setup for a hill-climbing attack
[31].

###### Theorem 11

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the distance, an attacker
can retrieve $x$ in $O(nq)$ queries to $\sigma_{x,\epsilon}$.

#### Leakage of Position(s)

In this case, the extra information given to the attacker is the positions of
the errors, but the corresponding values remain secret.

###### Theorem 12

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the positions of the
errors, an attacker can retrieve $x$ in an average number of $O(q^{n(1-1/q)})$
(resp. a worst-case number of $O(q^{n})$) queries to $\sigma_{x,\epsilon}$.

###### Proof 11

She has to perform an exhaustive search for the erroneous bits. Hence, the
average complexity of the attack to recover $x$, in this case, is
$O(q^{n(1-1/q)})$, while the worst case complexity is $O(q^{n})$.
$\blacksquare$

#### Leakage of Distance and Position(s)

In this case, the distance and the positions of the errors are given to the
attacker when she guesses a vector.

###### Theorem 13

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the distance and the
positions of the errors, an attacker can retrieve $x$ in an average number of
$O(qn(1-1/q))$ (resp. a worst-case number of $O(qn)$) queries to
$\sigma_{x,\epsilon}$.

###### Proof 12

She has to perform a hill-climbing attack on the erroneous values. Hence, the
average complexity of the attack to recover $x$ in this case is
$O(qn(1-1/q))$, while the worst-case complexity is $O(qn)$.
$\blacksquare$

#### Leakage of Distance, Position(s) and value(s)

In this last case, the distance, the positions of the errors and corresponding
values are leaked.

###### Theorem 14

Given a threshold $\varepsilon$, a vector $x\in\mathbb{Z}_{q}^{n}$ and $\Xi$ a
fuzzy matcher such that $\Xi.\texttt{Match}$ leaks the distance, the positions
of the errors and their values, an attacker can retrieve $x$ in $O(1)$ queries
to $\sigma_{x,\epsilon}$.

In this case, it is clear that the complexity is in $O(1)$.

Information leakage is related to the properties and the design of the
obfuscated distance. Attacks for each leakage are summarized in Table III.

##  IV Conclusion

Our investigation into the information leakage of a fuzzy matcher has shed
light on critical security vulnerabilities that arise under various scenarios.
By evaluating the impact of different types of leakage, including distance,
error position, and error value, we have gained insights into the potential
risks posed to data privacy and security in practical applications.

Our analysis encompasses all possible setups, both above and below the
threshold, allowing us to identify specific conditions under which information
leakage can have a substantial effect on the overall security of the system.
The simplicity and efficacy of the proposed attack for exploiting information
leakage underscore the importance of actively addressing potential
vulnerabilities for any fuzzy matcher in particular when the leaked
information is above the threshold or both above and below the threshold.
Furthermore, the attacks presented in this study, relying on exhaustive
search, have the potential for theoretical improvement by using techniques
such as set-covering and sampling without replacement, as shown by Pagnin et
al. [29]. However, it is noteworthy to mention that the feasibility of the
aforementioned approach is hindered by the NP-hard nature of the set-covering
problem, which renders the attack impractical. It is important to highlight
that the leakage below the threshold does not significantly hurt the security
of the fuzzy matcher while the leakage above significantly decreases the
security. Ultimately, our research emphasizes the critical importance of
exploring information leakage in cryptographic systems, highlighting the
ongoing necessity for the development of robust cryptographic primitives
capable of withstanding side-channel attacks and effectively mitigating
potential information leaks.

The accumulation attack we investigated is based on the assumption of errors
uniformly distributed throughout each authentication session. As far as we are
aware, no previous studies provide an analysis of how these errors are
distributed. In practical scenarios, some errors might manifest more
frequently. If the distribution of errors is skewed, this could substantially
increase the expected number of authentications required from the legitimate
user so that the server fully recovers the hidden vector.

## Acknowledgement

The authors acknowledge the support of the French Agence Nationale de la
Recherche (ANR), under grant ANR-20-CE39-0005 (project PRIVABIO).

## References

  * [1] Masaya Yasuda.  Secure hamming distance computation for biometrics using ideal-lattice and ring-lwe homomorphic encryption.  Information Security Journal: A Global Perspective, 26(2):85–103, 2017.
  * [2] Yan Huang, David Evans, Jonathan Katz, and Lior Malka.  Faster secure $\\{$Two-Party$\\}$ computation using garbled circuits.  In 20th USENIX Security Symposium (USENIX Security 11), 2011.
  * [3] Shantanu Rane and Wei Sun.  Privacy preserving string comparisons based on levenshtein distance.  In 2010 IEEE international workshop on information forensics and security, pages 1–6. IEEE, 2010.
  * [4] Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway.  Foundations of garbled circuits.  In Proceedings of the 2012 ACM conference on Computer and communications security, pages 784–796, 2012.
  * [5] Andrew Chi-Chih Yao.  How to generate and exchange secrets.  In 27th annual symposium on foundations of computer science (Sfcs 1986), pages 162–167. IEEE, 1986.
  * [6] Shweta Agrawal, Xavier Boyen, Vinod Vaikuntanathan, Panagiotis Voulgaris, and Hoeteck Wee.  Functional encryption for threshold functions (or fuzzy ibe) from lattices.  In Public Key Cryptography–PKC 2012: 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012. Proceedings 15, pages 280–297. Springer, 2012.
  * [7] Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval.  Better security for functional encryption for inner product evaluations.  Cryptology ePrint Archive, 2016.
  * [8] Tatsuaki Okamoto and Katsuyuki Takashima.  Adaptively attribute-hiding (hierarchical) inner product encryption.  In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, pages 591–608, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
  * [9] Pratish Datta, Ratna Dutta, and Sourav Mukhopadhyay.  Strongly full-hiding inner product encryption.  Theoretical Computer Science, 667:16–50, 2017.
  * [10] Junichi TOMIDA, Masayuki ABE, and Tatsuaki OKAMOTO.  Efficient inner product functional encryption with full-hiding security.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E103.A(1):33–40, 2020.
  * [11] Mehmet Sabir Kiraz, Ziya Alper Genç, and Suleyman Kardas.  Security and efficiency analysis of the hamming distance computation protocol based on oblivious transfer.  Security and Communication Networks, 8(18):4123–4135, 2015.
  * [12] Julien Bringer, Hervé Chabanne, and Alain Patey.  Shade: Secure hamming distance computation from oblivious transfer.  In International Conference on Financial Cryptography and Data Security, pages 164–176. Springer, 2013.
  * [13] Julien Bringer, Herve Chabanne, Melanie Favre, Alain Patey, Thomas Schneider, and Michael Zohner.  Gshade: Faster privacy-preserving distance computation and biometric identification.  In Proceedings of the 2nd ACM workshop on Information hiding and multimedia security, pages 187–198, 2014.
  * [14] Steven D. Galbraith and Lukas Zobernig.  Obfuscated fuzzy hamming distance and conjunctions from subset product problems.  In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography, pages 81–110, Cham, 2019. Springer International Publishing.
  * [15] Koray Karabina and Onur Canpolat.  A new cryptographic primitive for noise tolerant template security.  Pattern Recognition Letters, 80:70–75, 2016.
  * [16] Nils Fleischhacker and Mark Simkin.  Robust property-preserving hash functions for hamming distance and more.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 311–337. Springer, 2021.
  * [17] Nils Fleischhacker, Kasper Green Larsen, and Mark Simkin.  Property-preserving hash functions for hamming distance from standard assumptions.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 764–781. Springer, 2022.
  * [18] W Cary Huffman and Vera Pless.  Fundamentals of error-correcting codes.  Cambridge university press, 2010.
  * [19] Benjamin Fuller, Xianrui Meng, and Leonid Reyzin.  Computational fuzzy extractors.  Information and Computation, 275:104602, 2020.
  * [20] Yevgeniy Dodis, Leonid Reyzin, and Adam Smith.  Fuzzy extractors.  Security with Noisy Data: On Private Biometrics, Secure Key Storage and Anti-Counterfeiting, pages 79–99, 2007.
  * [21] Yunhua Wen and Shengli Liu.  Robustly reusable fuzzy extractor from standard assumptions.  In Advances in Cryptology–ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part III 24, pages 459–489. Springer, 2018.
  * [22] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith.  Fuzzy extractors: How to generate strong keys from biometrics and other noisy data.  SIAM journal on computing, 38(1):97–139, 2008.
  * [23] Jung Hee Cheon, Jinhyuck Jeong, Dongwoo Kim, and Jongchan Lee.  A reusable fuzzy extractor with practical storage size: Modifying canetti et al.’s construction.  In Information Security and Privacy: 23rd Australasian Conference, ACISP 2018, Wollongong, NSW, Australia, July 11-13, 2018, Proceedings 23, pages 28–44. Springer, 2018.
  * [24] Ari Juels and Madhu Sudan.  A fuzzy vault scheme.  Designs, Codes and Cryptography, 38:237–257, 2006.
  * [25] Boaz Barak, Nir Bitansky, Ran Canetti, Yael Tauman Kalai, Omer Paneth, and Amit Sahai.  Obfuscation for evasive functions.  In Theory of Cryptography Conference, pages 26–51. Springer, 2014\.
  * [26] Furkan Aydin and Aydin Aysu.  Leaking secrets in homomorphic encryption with side-channel attacks.  Cryptology ePrint Archive, Paper 2023/1128, 2023.  https://eprint.iacr.org/2023/1128.
  * [27] Mohammad Hashemi, Domenic Forte, and Fatemeh Ganji.  Time is money, friend! timing side-channel attack against garbled circuit constructions.  Cryptology ePrint Archive, 2023.
  * [28] Sergiu Carpov, Caroline Fontaine, Damien Ligier, and Renaud Sirdey.  Illuminating the dark or how to recover what should not be seen in fe-based classifiers.  Cryptology ePrint Archive, Paper 2018/1001, 2018.  https://eprint.iacr.org/2018/1001.
  * [29] Elena Pagnin, Christos Dimitrakakis, Aysajan Abidin, and Aikaterini Mitrokotsa.  On the leakage of information in biometric authentication.  In International Conference on Cryptology in India, pages 265–280. Springer, 2014.
  * [30] Koen Simoens, Julien Bringer, Hervé Chabanne, and Stefaan Seys.  A framework for analyzing template security and privacy in biometric authentication systems.  IEEE Transactions on Information Forensics and Security, 7:833–841, 2012.
  * [31] George Lasry.  A methodology for the cryptanalysis of classical ciphers with search metaheuristics.  kassel university press GmbH, 2018.
  * [32] Marco Ferrante and Nadia Frigo.  A note on the coupon - collector’s problem with multiple arrivals and the random sampling, 2012.
  * [33] Marco Ferrante and Monica Saltalamacchia.  The coupon collector’s problem.  MATerials MATemàtics, 2014:35, 05 2014.
  * [34] Philippe Flajolet, Daniele Gardy, and Loÿs Thimonier.  Birthday paradox, coupon collectors, caching algorithms and self-organizing search.  Discrete Applied Mathematics, 39(3):207–229, 1992.