[a]Calum Milloy

# High-energy limit of $2\to 2$ scattering amplitudes at NNLL

Giulio Falcioni  Einan Gardi  Niamh Maher  Leonardo Vernazza

###### Abstract

The high-energy limit of $2\to 2$ scattering amplitudes offers an excellent
setting to explore the universal features of gauge theories. At Leading
Logarithmic (LL) accuracy the partonic amplitude is governed by Regge poles in
the complex angular momentum plane. Beyond LL, Regge cuts in this plane begin
to play an important role. Specifically, the real part of the amplitude at
Next-to-Next-to-Leading Logarithmic (NNLL) accuracy presents for the first
time both a Regge pole and a Regge cut. Analysing this tower of logarithms and
computing it explicitly through four loops we are able to systematically
separate between the Regge pole and the Regge cut. The former involves two
fundamental parameters, namely the gluon Regge trajectory and impact factors.
We explain how to consistently define the impact factors at two loops and the
Regge trajectory at three loops. We confirm that the singularities of the
trajectory are given by the cusp anomalous dimension. We also show that the
Regge-cut contribution at four loop is nonplanar.

##  1 Introduction to the high-energy limit of $2\to 2$ scattering amplitudes

The high-energy limit has long been an intersting laboratory to study gauge-
theory amplitudes, which simplify significantly in this regime. The
simplification in the limit means that multi-loop corrections are accessible,
and they may even be resummed to all orders (at a fixed logarithmic accuracy),
while still retaining a rich structure in both colour and kinematics.

Figure 1: A representation of the $2\to 2$ scattering of eq. (1).

We consider the $2\to 2$ scattering of massless partons in a generic gauge
theory

$\displaystyle i(p_{1},a_{1},\lambda_{1})+j(p_{2},a_{2},\lambda_{2})\to
j(p_{3},a_{3},\lambda_{3})+i(p_{4},a_{4},\lambda_{4}),$ (1)

where momenta, colour and helicity are labelled by $p_{i}$, $a_{i}$ and
$\lambda_{i}$ respectively. A pictorial representation is given in Figure 1.
The process is described in terms of the Mandelstam invariants,

$\displaystyle s=(p_{1}+p_{2})^{2}>0$ $\displaystyle t=(p_{1}-p_{4})^{2}<0$
$\displaystyle u=(p_{1}-p_{3})^{2}<0,$ (2)

where the signs dictate the physical scattering region. Momentum conservation
implies

$\displaystyle s+t+u=0.$ (3)

In $2\to 2$ scattering, the high-energy (Regge) limit is defined to be when
the centre-of-mass energy is much larger than the momentum transfer, i.e.
$s\gg-t$. At leading power the tree-level amplitude is

$\displaystyle\mathcal{M}_{ij\to ij}^{\text{tree}}$
$\displaystyle=4\pi\alpha_{s}\frac{2s}{t}(\mathbf{T}_{i}^{b})_{a_{1}a_{4}}(\mathbf{T}_{j}^{b})_{a_{2}a_{3}}\delta_{\lambda_{1}\lambda_{4}}\delta_{\lambda_{2}\lambda_{3}},$
(4)

where we observe that the helicity of each of the scattered partons is
conserved. We use colour operator notation to keep expressions general for any
representation. In the Regge limit it is convenient to define colour-flow
operators following the conventions of the Mandelstams [1, 2, 3],

$\displaystyle\mathbf{T}_{s}=\mathbf{T}_{1}+\mathbf{T}_{2},$
$\displaystyle\mathbf{T}_{t}=\mathbf{T}_{1}+\mathbf{T}_{4},$
$\displaystyle\mathbf{T}_{u}=\mathbf{T}_{1}+\mathbf{T}_{3}.$ (5)

The quantity $\mathbf{T}_{t}^{2}$ measures the colour charge of the
$t$-channel adjoint exchange,

$\displaystyle\mathbf{T}_{t}^{2}\mathcal{M}_{ij\to
ij}^{\text{tree}}=C_{A}\mathcal{M}_{ij\to ij}^{\text{tree}}.$ (6)

In the high-energy limit it can be shown that in the complex angular momentum
plane, the amplitude can be written as a sum over poles and cuts, dubbed
_Regge poles_ and _Regge cuts_. Regge cuts were shown by Mandelstam to arise
from only nonplanar diagrams [4]. Note that Mandelstam’s observation only
involved the _diagrams_ being nonplanar. In this work we connect this to gauge
theories, where planarity relates to colour and corresponds to the
large-$N_{c}$ limit.

Calculating the amplitude in the perturbative expansion in $\alpha_{s}$ we
would find that large logarithms will develop in the ratio $s/(-t)$. In the
Leading Logarithmic (LL) approximation, these can be resummed by the famous
Regge pole,

$\displaystyle\mathcal{M}_{ij\to
ij}^{\text{LL}}=\left(\frac{s}{-t}\right)^{C_{A}\alpha_{g}(t,\mu^{2})}\mathcal{M}_{ij\to
ij}^{\text{tree}},$ (7)

where $\alpha_{g}$ is called the Regge trajectory. This quantity admits a
perturbative expansion,

$\displaystyle\alpha_{g}(t,\mu^{2})=\sum_{n=1}^{\infty}\left(\frac{\alpha_{s}}{\pi}\right)^{n}\alpha_{g}^{(n)}(t,\mu^{2}),$
(8)

where the one-loop coefficient relevant at LL is

$\displaystyle\alpha_{g}^{(1)}(t,\mu^{2})=\frac{r_{\Gamma}}{2\epsilon}\left(\frac{\mu^{2}}{-t}\right)^{\epsilon},$
$\displaystyle
r_{\Gamma}=e^{\epsilon\gamma_{E}}\frac{\Gamma^{2}(1-\epsilon)\Gamma(1+\epsilon)}{\Gamma(1-2\epsilon)},$
(9)

with $\epsilon=(4-d)/2$ the dimensional regularisation parameter. We will set
the renormalisation scale $\mu^{2}=-t$ for simplicity. At this accuracy the
amplitude has the same colour structure as the tree-level, the octet exchange
in the $t$-channel.

Before moving on to Next-to-Leading Logarithms (NLL), we shall first introduce
the concept of signature under $s\leftrightarrow u$, where we notice that the
tree-level amplitude in eq. (4) is signature-odd. We define even and odd
amplitudes through

$\displaystyle\mathcal{M}^{(\pm)}(s,t)=\frac{1}{2}\left(\mathcal{M}(s,t)\pm\mathcal{M}(-s-t,t)\right).$
(10)

Upon defining the signature-even logarithm,

$\displaystyle
L\equiv\log\left(\frac{s}{-t}\right)-\frac{i\pi}{2}=\frac{1}{2}\left[\log\left(\frac{-s-i0}{-t}\right)+\log\left(\frac{-u-i0}{-t}\right)\right],$
(11)

and then expanding the amplitude in $L$, the coefficients of $L$ in the odd
(even) amplitudes are entirely real (imaginary) [5].

In this work, we focus solely on the odd amplitude $\mathcal{M}^{(-)}$, and we
will remove the superscript $(-)$ for convenience. For even amplitudes at NLL
see [6, 7, 8]. At NLL, the amplitudes obey Regge pole factorisation [9, 10,
11],

$\displaystyle\mathcal{M}_{ij\to
ij}^{\text{NLL}}=e^{C_{A}\alpha_{g}(t)L}C_{i}(t)C_{j}(t)\mathcal{M}_{ij\to
ij}^{\text{tree}},$ (12)

where $C_{i}(t)$ are energy-independent impact factors for each of the
scattered partons. They are expanded in powers of $\alpha_{s}$, similar to
$\alpha_{g}$ in eq. (8). The dependence on $s$ is entirely controlled by the
Regge trajectory. NLL accuracy is obtained by taking the Regge trajectory up
to two loops, and the impact factors at one loop.

It is worthwhile to compare Regge factorisation to infrared factorisation. It
is well-known that long-distance singularities factorise from the amplitude
[12, 13, 14, 15, 16, 17],

$\displaystyle\mathcal{M}_{ij\to
ij}=\mathbf{P}\exp\left\\{-\frac{1}{2}\int_{0}^{\mu^{2}}\frac{d\lambda^{2}}{\lambda^{2}}\mathbf{\Gamma}_{ij\to
ij}\right\\}\cdot\mathcal{H}$ (13)

where $\mathbf{\Gamma}_{ij\to ij}$ is dubbed the soft anomalous dimension. In
the high-energy limit it is given by [5]

$\displaystyle\mathbf{\Gamma}_{ij\to
ij}=\frac{1}{2}\gamma_{K}\left[L\mathbf{T}_{t}^{2}+i\pi\mathbf{T}_{s-u}^{2}\right]+\Gamma_{i}+\Gamma_{j}+\mathbf{\Delta}$
(14)

where at LL, divergences are captured by the lightlike cusp anomalous
dimension $\gamma_{K}$ and $\Gamma_{i}$ is the collinear anomalous dimension,
which collects collinear divergences associated to scattered parton $i$. The
operator $\mathbf{T}_{s-u}^{2}$ is defined as

$\displaystyle\mathbf{T}_{s-u}^{2}=\frac{1}{2}\left(\mathbf{T}_{s}^{2}-\mathbf{T}_{u}^{2}\right).$
(15)

The quantity $\mathbf{\Delta}$ starts at three loops [18] but only contributes
at NLL for even amplitudes from four loops [6] and NNLL for odd amplitudes
also from four loops [19]. Performing the integral over the $d$-dimensional
running coupling in eq. (13), reveals the explicit infrared poles of the
amplitude.

It is natural to compare the two exponentiations in eqs. (12) and (13). The
coefficient of the logarithm $L$ in the exponent gives

$\displaystyle\alpha_{g}(t)\stackrel{{\scriptstyle?}}{{=}}-\frac{1}{4}\int_{0}^{\mu^{2}}\frac{d\lambda^{2}}{\lambda^{2}}\gamma_{K}(\alpha_{s}(\lambda^{2}))+\mathcal{O}(\epsilon^{0}).$
(16)

The equivalency holds at two loops (i.e. NLL) [20]. We shall show that it also
holds at three loops through a proper definition of the trajectory and it
remains a conjecture that it holds beyond. The factor independent of the
logarithm suggests that the infrared divergences of the impact factors are
related to the collinear anomalous dimension $\Gamma_{i}$ [21, 22].

##  2 Distinguishing pole and cut contributions

At NNLL the factorisation in eq. (12) fails. The colour structure of the
amplitude is no longer given only by the exchange of an octet in the
$t$-channel, as for the tree-level amplitude, and new colour channels open up.
To describe also these contributions to the amplitudes, we generalise eq. (12)
by introducing a non-factorising term, which originates from Regge cuts [23,
24, 25, 22, 5, 26, 27, 28, 29, 19, 21]

$\displaystyle\mathcal{M}_{ij\to
ij}^{\text{NNLL}}=e^{C_{A}\alpha_{g}(t)L}C_{i}(t)C_{j}(t)\mathcal{M}_{ij\to
ij}^{\text{tree}}+\mathcal{M}_{ij\to ij}^{\text{NF}}.$ (17)

The high-energy behaviour of the amplitude will only be uncovered when the
perturbative series is resummed. As such, it is not clear how to properly
define the Regge pole and Regge cut in order-by-order computations. To see
this explicitly, we expand eq. (17) to two loops

$\displaystyle\mathcal{M}_{ij\to
ij}^{(2),\text{NNLL}}=\left(C_{i}^{(1)}C_{j}^{(1)}+C_{i}^{(2)}+C_{j}^{(2)}\right)\mathcal{M}_{ij\to
ij}^{\text{tree}}+\mathcal{M}_{ij\to ij}^{(2),\text{NF}}.$ (18)

In the expansion above, we are a priori free to move any term whose colour
factor is proportional to the tree-level from $\mathcal{M}_{ij\to
ij}^{(2),\text{NF}}$ into the two-loop impact factors $C_{i}^{(2)}$ (the one-
loop $C_{i}^{(1)}$ are fixed at NLL). There is an ambiguity in the definition
of the two-loop impact factors. Therefore, we need a prescription to
disentangle the two-loop impact factors from the contribution of Regge cuts.
How to properly distinguish the pole and cut contributions is the key result
in what follows [30].

We can access this non-factorising term by computing certain diagrams in the
high-energy limit. In this regime, the fundamental degrees of freedom are
Reggeized gluons, dubbed _Reggeons_ , see [6, 28] and references therein. At
tree-level, the diagram featuring the exchange of a single Reggeon in the
$t$-channel has the analytic structure of a Regge pole, i.e. the first term in
eq. (17).

We use the shockwave formalism of ref. [6] to compute diagrams with the
exchange of Multiple Reggeons (MR), which start at two loops111At one-loop, it
is possible to exchange only two Reggeons, but these contribute only to the
imaginary (even) part of the amplitude.. Example diagrams at two, three and
four loops are given in Figure 2. The two-loop diagram displayed in Figure
2(a) was computed in [5], giving

$\displaystyle\mathcal{M}_{ij\to
ij}^{(2),\text{MR}}=\pi^{2}\left(-\frac{1}{8\epsilon^{2}}+\frac{1}{8}\zeta_{2}+\frac{4}{3}\epsilon\zeta_{3}+\mathcal{O}(\epsilon^{2})\right)\left((\mathbf{T}_{s-u}^{2})^{2}-\frac{1}{12}C_{A}^{2}\right)\mathcal{M}_{ij\to
ij}^{\text{tree}}.$ (19)

A couple of comments are in order. The overall $\pi^{2}=-(i\pi)^{2}$ highly
suggests it originates from a cut. It has uniform transcendental weight as
this quantity is independent on the underlying gauge theory: the
$\mathcal{N}=4$ super Yang-Mills (SYM) result is the same as QCD.

(a) A two-loop MR diagram. The explicit result is given in eq. (19).

(b) A three-loop MR diagram.

(c) A four-loop MR diagram.

Figure 2: Example MR diagrams. The black lines represent the external
scattering partons and the double red lines are the Reggeon exchanges. There
is a symmetric sum over all possible orderings of the Reggeon attachments to
the external partons.

These features are maintained in the MR exchanges at three and four loops,
which are computed in [5] and [19], respectively. It is possible to identify
the entire contribution of MR diagrams with the Regge-cut term in eq. (17), as
done in [5]. This defines a scheme to extract the two-loop impact factors
$C_{i}^{(2)}$ and the three-loop Regge trajectory $\alpha_{g}^{(3)}$ by
matching eq. (17), where $\mathcal{M}_{ij\to ij}^{\text{NF}}$ is identified
with $\mathcal{M}_{ij\to ij}^{\text{MR}}$, with fixed-order calculations [31,
32, 33, 34, 35].

Here, we take a different point of view following refs. [21, 30]. Indeed,
according to the analysis of Mandelstam [4], the Regge cut contribution
$\mathcal{M}_{ij\to ij}^{\text{NF}}$ arises from nonplanar diagrams.
Therefore, its colour structure should be subleading in the limit of large
$N_{c}$. In contrast with this conclusion, the $\mathcal{M}_{ij\to
ij}^{\text{MR}}$ has non-vanishing contributions at two and three loops for
large $N_{c}$ [21, 19],

$\displaystyle\mathcal{M}_{ij\to ij}^{\text{MR}}\rvert_{\text{planar}}=$
$\displaystyle\frac{\pi^{2}r_{\Gamma}^{2}N_{c}^{2}}{6}\left(\frac{\alpha_{s}}{\pi}\right)^{2}\left\\{S^{(2)}(\epsilon)-\left(\frac{\alpha_{s}}{\pi}\right)r_{\Gamma}N_{c}L\left[S^{(3)}(\epsilon)-\frac{1}{2\epsilon}S^{(2)}(\epsilon)\right]+\mathcal{O}(\alpha_{s}^{3})\right\\}\mathcal{M}_{ij\to
ij}^{\text{tree}},$ (20) $\displaystyle S^{(2)}(\epsilon)=$
$\displaystyle-\frac{1}{8\epsilon^{2}}+\frac{3}{4}\epsilon\zeta_{3}+\frac{9}{8}\epsilon^{2}\zeta_{4}+{\cal{O}}(\epsilon^{3}),$
(21) $\displaystyle S^{(3)}(\epsilon)=$
$\displaystyle-\frac{1}{144\epsilon^{3}}+\frac{35}{72}\zeta_{3}+\frac{35}{48}\epsilon\zeta_{4}+{\cal{O}}(\epsilon^{3}).$
(22)

By looking at eq. (20), we notice that, for every scattering process, the
planar part of $\mathcal{M}_{ij\to ij}^{\text{MR}}$ is colour proportional to
the tree-level amplitude. Because of this property, by following the argument
below eq. (18), at two loops it is possible to absorb the planar part of
$\mathcal{M}_{ij\to ij}^{\text{MR}}$ in the definition of the impact factors
[21, 30]. At three loops, the planar terms in $\mathcal{M}_{ij\to
ij}^{\text{MR}}$ are again proportional to the tree-level amplitude and can be
absorbed in the definition of the three-loop gluon Regge trajectory. This
naturally gives a method to capture the true separation between the pole and
the cut, where we shift all the planar corrections into a new pole term with
new impact factors and a new Regge trajectory [30]

$\displaystyle\mathcal{M}_{ij\to
ij}^{\text{pole}}=\tilde{C}_{i}(t)\tilde{C}_{j}(t)e^{\tilde{\alpha}_{g}(t)C_{A}L}\mathcal{M}_{ij\to
ij}^{\text{tree}},$ (23)

where we have added a tilde on the parameters to dinstinguish between the old
and new pole terms. As the whole amplitude is a well-defined quantity, the
shifts in the two-loop impact factors and three-loop Regge trajectory can be
calculated

$\displaystyle\tilde{C}_{i/j}^{(2)}=$
$\displaystyle\,C_{i/j}^{(2)}+N_{c}^{2}\,(r_{\Gamma})^{2}\frac{\pi^{2}}{12}S^{(2)}(\epsilon),$
(24) $\displaystyle\tilde{\alpha}_{g}^{(3)}=$
$\displaystyle\,\alpha_{g}^{(3)}-N_{c}^{2}(r_{\Gamma})^{3}\frac{\pi^{2}}{6}S^{(3)}(\epsilon).$
(25)

This exhausts all possible parameters at NNLL to absorb planar contributions
into the pole term. This is consistent with the fact that at four loops the MR
term is entirely nonplanar [19, 21] and that it is conjectured to be so at all
higher loops [21, 30].

##  3 Applications

Having properly distinguished pole and cut contributions order-by-order in the
perturbation expansion, we can now extract Regge parameters. Using state-of-
the-art calculations for the relevant amplitudes, we first extract two-loop
impact factors and then the three-loop Regge trajectory. Lastly, as a by-
product of the four-loop computation of $\mathcal{M}_{ij\to
ij}^{(4),\text{MR}}$ we derive constraints on the infrared structure of four-
loop amplitudes.

###  3.1 Two-loop impact factors

Using eq. (24) we can extract the two-loop impact factors. To display results
it is more convenient to define the pole term as a symmetric sum of
exponentials, rather than a single exponentiated sum. In eq. (23) we make the
replacement

$\displaystyle\tilde{C}_{i}(t)\tilde{C}_{j}(t)e^{\tilde{\alpha}_{g}(t)C_{A}L}\to
Z_{i}(t)\bar{D}_{i}(t)\left[\left(\frac{s}{-t}\right)^{\tilde{\alpha}_{g}(t)}+\left(\frac{-s}{-t}\right)^{\tilde{\alpha}_{g}(t)}\right]Z_{j}(t)\bar{D}_{j}(t),$
(26)

where $Z_{i}(t)$ is the exponential of the integral over the collinear
anomalous dimension $\Gamma_{i}$

$\displaystyle Z_{i}(t)\equiv$
$\displaystyle\exp\left\\{-\frac{1}{2}\int_{0}^{\mu^{2}}\frac{d\lambda^{2}}{\lambda^{2}}\Gamma_{i}\right\\}.$
(27)

This replacement defines a finite collinear-subtracted impact factor
$\bar{D}_{i}(t)$, i.e. the poles of the impact factor are given by the
collinear anomalous dimension [22]. It is related to the $\tilde{C}_{i}(t)$ by

$\displaystyle\tilde{C}_{i}(t)=Z_{i}(t)\bar{D}_{i}(t)\sqrt{\cos{}\left(\frac{\pi
C_{A}\tilde{\alpha}_{g}(t)}{2}\right)}.$ (28)

Upon matching to amplitudes calculated in [31] we find the results

$\displaystyle\bar{D}_{g}^{(2)}=$
$\displaystyle\,C_{A}^{2}\Big{(}\frac{335}{288}\zeta_{2}+\frac{11}{18}\zeta_{3}-\frac{3}{32}\zeta_{4}-\frac{26675}{10368}\Big{)}+C_{A}n_{f}\Big{(}\frac{49}{108}-\frac{25}{144}\zeta_{2}+\frac{5}{36}\zeta_{3}\Big{)}$
$\displaystyle+C_{F}n_{f}\\!\Big{(}\frac{55}{192}-\frac{\zeta_{3}}{4}\Big{)}-\frac{25}{2592}n_{f}^{2}+{\cal
O}(\epsilon)\,,$ (29) $\displaystyle\bar{D}_{q}^{(2)}=$
$\displaystyle\,C_{A}^{2}\bigg{(}\frac{73\zeta_{2}}{32}-\frac{43\zeta_{3}}{48}-\frac{53\zeta_{4}}{64}+\frac{13195}{3456}\bigg{)}+C_{A}C_{F}\bigg{(}-\frac{5\zeta_{2}}{2}+\frac{475\zeta_{3}}{144}+\frac{65\zeta_{4}}{32}-\frac{78229}{10368}\bigg{)}$
$\displaystyle+C_{F}^{2}\bigg{(}\frac{21\zeta_{2}}{16}-\frac{15\zeta_{3}}{8}-\frac{83\zeta_{4}}{64}+\frac{255}{128}\bigg{)}+C_{A}n_{f}\bigg{(}-\frac{5\zeta_{2}}{16}-\frac{7\zeta_{3}}{24}-\frac{385}{432}\bigg{)},$
$\displaystyle+C_{F}n_{f}\bigg{(}\frac{\zeta_{2}}{8}+\frac{19\zeta_{3}}{72}+\frac{505}{648}\bigg{)}+\frac{25}{864}n_{f}^{2}+{\cal
O}(\epsilon)\,$ (30)

for gluons and quarks respectively. The values through to ${\cal
O}(\epsilon^{2})$ are given in ref. [30]. Upon taking the planar limit we find
that $\bar{D}_{g}^{(2)}$ agrees with the recent calculation of ref. [36]. Upon
extracting the terms of highest weight of eq. (29), we find the gluon impact
factor in planar $\mathcal{N}=4$ SYM [37, 38], which also coincides with the
impact factor in full colour [32, 5] when using the cut scheme.

###  3.2 Three-loop Regge trajectory

We can also extract the Regge trajectory. We use eq. (25) and the state-of-
the-art three-loop four quark amplitudes of ref. [33]. In doing so, we find
the poles are given by the cusp anomalous dimension, thus confirming eq. (16)
at three loops. If we had used the MR scheme, we would find that there are
infrared poles not described by $\gamma_{K}$ [5].

Upon defining the cusp-subtracted Regge trajectory $\hat{\tilde{\alpha}}_{g}$
through

$\displaystyle\hat{\tilde{\alpha}}_{g}\equiv\tilde{\alpha}_{g}+\frac{1}{4}\int_{0}^{\mu^{2}}\frac{d\lambda^{2}}{\lambda^{2}}\gamma_{K}(\alpha_{s}(\lambda^{2}))$
(31)

we find the finite result at three loops [30, 34]

$\displaystyle\hat{\tilde{\alpha}}_{g}^{(3)}=$
$\displaystyle\,C_{A}^{2}\bigg{(}\frac{297029}{93312}-\frac{799\zeta_{2}}{1296}-\frac{833\zeta_{3}}{216}-\frac{77\zeta_{4}}{192}+\frac{5}{24}\zeta_{2}\zeta_{3}+\frac{\zeta_{5}}{4}\bigg{)}$
$\displaystyle+C_{A}n_{f}\bigg{(}\frac{103\zeta_{2}}{1296}+\frac{139\zeta_{3}}{144}-\frac{5\zeta_{4}}{96}-\frac{31313}{46656}\bigg{)}+C_{F}n_{f}\bigg{(}\frac{19\zeta_{3}}{72}+\frac{\zeta_{4}}{8}-\frac{1711}{3456}\bigg{)}$
$\displaystyle+n_{f}^{2}\left(\frac{29}{1458}-\frac{2\zeta_{3}}{27}\right)+\mathcal{O}(\epsilon).$
(32)

Notice that when $n_{f}=0$ there are no $N_{c}$-subleading terms, in agreement
with the expectation that the Regge trajectory is maximally non-Abelian [20].
The result of eq. (3.2) agrees with the planar extraction given in [36].

###  3.3 Infrared Constraints

Another application of the calculation of the MR term is that we can find
constraints on the infrared structure of gauge-theory amplitudes. The
structure of infrared divergences for multi-leg massless scattering is known
at three loops in general kinematics [39]. In addition, in the high-energy
limit the entire NLL tower of corrections has been resummed [7, 18]. Given
that the four-loop computation of the Regge-cut term is known, we can match
the Regge decomposition in eq. (17) to the soft anomalous dimension in the
high-energy limit, eq. (14). It can be shown that only the Regge-cut term
contributes to $\mathbf{\Delta}$. Expanding $\mathbf{\Delta}$ as

$\displaystyle\mathbf{\Delta}=\sum_{m=3}^{\infty}\left(\frac{\alpha_{s}}{\pi}\right)^{m}\sum_{n=0}^{m-1}L^{n}\mathbf{\Delta}^{(m,n)},$
(33)

we have the four-loop results at NLL [6] and NNLL [19] respectively,

$\displaystyle\mathbf{\Delta}^{(4,3)}=$
$\displaystyle-i\pi\frac{\zeta_{3}}{24}\left[\mathbf{T}_{t}^{2},\left[\mathbf{T}_{t}^{2},\mathbf{T}_{s-u}^{2}\right]\right]\mathbf{T}_{t}^{2},$
(34) $\displaystyle\text{Re}\left[\mathbf{\Delta}^{(4,2)}\right]=$
$\displaystyle\,\zeta_{2}\zeta_{3},\left\\{\frac{1}{4}\mathbf{T}_{t}^{2}\left[\mathbf{T}_{t}^{2},(\mathbf{T}_{s-u})^{2}\right]+\frac{3}{4}\left[\mathbf{T}_{s-u}^{2},\mathbf{T}_{t}^{2}\right]\mathbf{T}_{t}^{2}\mathbf{T}_{s-u}^{2}+\frac{d_{AA}}{N_{A}}-\frac{C_{A}^{4}}{24}{}\right\\},$
(35)

where only the real part of $\mathbf{\Delta}^{(4,2)}$ is known as we only have
NNLL results for the odd amplitude. By matching the above to an ansatz for the
four-loop $\mathbf{\Delta}^{(4)}$ in general kinematics [40] we can find the
asymptotic limits of the functions [21].

The three-loop soft anomalous dimension was shown to be bootstrapable from
general considerations and matching to known collinear and high-energy limits
[41]. The above results gives useful constraints for a potential four-loop
bootstrap.

##  4 Conclusions

Beyond NLL, in the high-energy limit, amplitudes no longer factorise in terms
of a Regge pole, as given in eq. (12). A non-factorising term, originating
from Regge cuts, needs to be included as in eq. (17). This leads to an
ambiguity in how to properly define the pole term order-by-order in
perturbation theory. In this work, we have shown how to consistently do so
with the high-energy properties of Regge poles and Regge cuts in the complex
angular momentum plane. We remove all planar MR contributions from the non-
factorising term and define a new pole term with new NNLL parameters, namely
the two-loop impact factor $\tilde{C}_{i}^{(2)}$ and the three-loop Regge
trajectory $\tilde{\alpha}_{g}^{(3)}$.

As an application, we find $\mathcal{O}(\epsilon^{2})$ terms of the two-loop
impact factors of eqs. (29) and (30) using state-of-the-art amplitude
computations [31]. We also extract, for the first time, the three-loop Regge
trajectory, eq. (3.2), using the amplitudes of ref. [33]. The poles of the
Regge trajectory are given by the integrated cusp anomalous dimension when
using the cut scheme, eq. (31).

Furthermore, as a by-product of four-loop computations [6, 19], we can derive
constraints on the structure of infrared divergences in the high-energy limit
[21], see eqs. (34) and (35).

## References

  * [1] Yu.. Dokshitzer and G. Marchesini  “Soft gluons at large angles in hadron collisions”  In _JHEP_ 01, 2006, pp. 007  DOI: 10.1088/1126-6708/2006/01/007
  * [2] Vittorio Del Duca et al.  “An infrared approach to Reggeization”  In _Phys. Rev. D_ 85, 2012, pp. 071104  DOI: 10.1103/PhysRevD.85.071104
  * [3] Vittorio Del Duca et al.  “The Infrared structure of gauge theory amplitudes in the high-energy limit”  In _JHEP_ 12, 2011, pp. 021  DOI: 10.1007/JHEP12(2011)021
  * [4] S. Mandelstam  “Cuts in the Angular Momentum Plane. 2”  In _Nuovo Cim._ 30, 1963, pp. 1148–1162  DOI: 10.1007/BF02828822
  * [5] Simon Caron-Huot, Einan Gardi and Leonardo Vernazza  “Two-parton scattering in the high-energy limit”  In _JHEP_ 06, 2017, pp. 016  DOI: 10.1007/JHEP06(2017)016
  * [6] Simon Caron-Huot  “When does the gluon reggeize?”  In _JHEP_ 05, 2015, pp. 093  DOI: 10.1007/JHEP05(2015)093
  * [7] Simon Caron-Huot, Einan Gardi, Joscha Reichel and Leonardo Vernazza  “Infrared singularities of QCD scattering amplitudes in the Regge limit to all orders”  In _JHEP_ 03, 2018, pp. 098  DOI: 10.1007/JHEP03(2018)098
  * [8] Simon Caron-Huot, Einan Gardi, Joscha Reichel and Leonardo Vernazza  “Two-parton scattering amplitudes in the Regge limit to high loop orders”  In _JHEP_ 08, 2020, pp. 116  DOI: 10.1007/JHEP08(2020)116
  * [9] V.S. Fadin, R. Fiore, M.G. Kozlov and A.V. Reznichenko  “Proof of the multi-Regge form of QCD amplitudes with gluon exchanges in the NLA”  In _Phys. Lett. B_ 639, 2006, pp. 74–81  DOI: 10.1016/j.physletb.2006.03.031
  * [10] Boris Lazarevich Ioffe, Victor Sergeevich Fadin and Lev Nikolaevich Lipatov  “Quantum chromodynamics: Perturbative and nonperturbative aspects”  Cambridge Univ. Press, 2010  DOI: 10.1017/CBO9780511711817
  * [11] V.S. Fadin, M.G. Kozlov and A.V. Reznichenko  “Gluon Reggeization in Yang-Mills Theories”  In _Phys. Rev. D_ 92.8, 2015, pp. 085044  DOI: 10.1103/PhysRevD.92.085044
  * [12] Stefano Catani  “The Singular behavior of QCD amplitudes at two loop order”  In _Phys. Lett. B_ 427, 1998, pp. 161–171  DOI: 10.1016/S0370-2693(98)00332-3
  * [13] George F. Sterman and Maria E. Tejeda-Yeomans  “Multiloop amplitudes and resummation”  In _Phys. Lett. B_ 552, 2003, pp. 48–56  DOI: 10.1016/S0370-2693(02)03100-3
  * [14] S.Mert Aybat, Lance J. Dixon and George F. Sterman  “The Two-loop soft anomalous dimension matrix and resummation at next-to-next-to leading pole”  In _Phys. Rev. D_ 74, 2006, pp. 074004  DOI: 10.1103/PhysRevD.74.074004
  * [15] S.Mert Aybat, Lance J. Dixon and George F. Sterman  “The Two-loop anomalous dimension matrix for soft gluon exchange”  In _Phys. Rev. Lett._ 97, 2006, pp. 072001  DOI: 10.1103/PhysRevLett.97.072001
  * [16] Yao Ma  “A Forest Formula to Subtract Infrared Singularities in Amplitudes for Wide-angle Scattering”  In _JHEP_ 05, 2020, pp. 012  DOI: 10.1007/JHEP05(2020)012
  * [17] Ilya Feige and Matthew D. Schwartz  “Hard-Soft-Collinear Factorization to All Orders”  In _Phys. Rev. D_ 90.10, 2014, pp. 105020  DOI: 10.1103/PhysRevD.90.105020
  * [18] Einan Gardi, Simon Caron-Huot, Joscha Reichel and Leonardo Vernazza  “The High-Energy Limit of 2-to-2 Partonic Scattering Amplitudes”  In _PoS_ RADCOR2019, 2019, pp. 050  DOI: 10.22323/1.375.0050
  * [19] Giulio Falcioni, Einan Gardi, Calum Milloy and Leonardo Vernazza  “Climbing three-Reggeon ladders: four-loop amplitudes in the high-energy limit in full colour”  In _Phys. Rev. D_ 103, 2021, pp. L111501  DOI: 10.1103/PhysRevD.103.L111501
  * [20] I.. Korchemskaya and G.. Korchemsky  “Evolution equation for gluon Regge trajectory”  In _Phys. Lett._ B387, 1996, pp. 346–354  DOI: 10.1016/0370-2693(96)01016-7
  * [21] Giulio Falcioni et al.  “Scattering amplitudes in the Regge limit and the soft anomalous dimension through four loops”  In _JHEP_ 03, 2022, pp. 053  DOI: 10.1007/JHEP03(2022)053
  * [22] Vittorio Del Duca, Giulio Falcioni, Lorenzo Magnea and Leonardo Vernazza  “Analyzing high-energy factorization beyond next-to-leading logarithmic accuracy”  In _JHEP_ 02, 2015, pp. 029  DOI: 10.1007/JHEP02(2015)029
  * [23] Vittorio Del Duca and E.W.Nigel Glover  “The High-energy limit of QCD at two loops”  In _JHEP_ 10, 2001, pp. 035  DOI: 10.1088/1126-6708/2001/10/035
  * [24] Vittorio Del Duca, Giulio Falcioni, Lorenzo Magnea and Leonardo Vernazza  “High-energy QCD amplitudes at two loops and beyond”  In _Phys. Lett. B_ 732, 2014, pp. 233–240  DOI: 10.1016/j.physletb.2014.03.033
  * [25] Vittorio Del Duca, Giulio Falcioni, Lorenzo Magnea and Leonardo Vernazza  “Beyond Reggeization for two- and three-loop QCD amplitudes”  In _PoS_ RADCOR2013, 2013, pp. 046  DOI: 10.22323/1.197.0046
  * [26] V.S. Fadin  “Particularities of the NNLLA BFKL”  In _AIP Conf. Proc._ 1819.1, 2017, pp. 060003  DOI: 10.1063/1.4977159
  * [27] V.S. Fadin and L.N. Lipatov  “Reggeon cuts in QCD amplitudes with negative signature”  In _Eur. Phys. J. C_ 78.6, 2018, pp. 439  DOI: 10.1140/epjc/s10052-018-5910-1
  * [28] Victor Fadin  “BFKL – past and future”, 2020  arXiv:2012.11931 [hep-ph]
  * [29] V.. Fadin  “Three-Reggeon Cuts in QCD Amplitudes”  In _Phys. Atom. Nucl._ 84.1, 2021, pp. 100–104  DOI: 10.1134/S1063778820060149
  * [30] Giulio Falcioni et al.  “Disentangling the Regge Cut and Regge Pole in Perturbative QCD”  In _Phys. Rev. Lett._ 128.13, 2022, pp. 132001  DOI: 10.1103/PhysRevLett.128.132001
  * [31] Taushif Ahmed, Johannes Henn and Bernhard Mistlberger  “Four-particle scattering amplitudes in QCD at NNLO to higher orders in the dimensional regulator”  In _JHEP_ 12, 2019, pp. 177  DOI: 10.1007/JHEP12(2019)177
  * [32] Johannes M. Henn and Bernhard Mistlberger  “Four-Gluon Scattering at Three Loops, Infrared Structure, and the Regge Limit”  In _Phys. Rev. Lett._ 117.17, 2016, pp. 171601  DOI: 10.1103/PhysRevLett.117.171601
  * [33] Fabrizio Caola et al.  “Three-loop helicity amplitudes for four-quark scattering in massless QCD”, 2021  arXiv:2108.00055 [hep-ph]
  * [34] Fabrizio Caola et al.  “Three-Loop Gluon Scattering in QCD and the Gluon Regge Trajectory”  In _Phys. Rev. Lett._ 128.21, 2022, pp. 212001  DOI: 10.1103/PhysRevLett.128.212001
  * [35] Fabrizio Caola et al.  “Three-loop helicity amplitudes for quark-gluon scattering in QCD”, 2022  arXiv:2207.03503 [hep-ph]
  * [36] Vittorio Del Duca, Robin Marzucca and Bram Verbeek  “The gluon Regge trajectory at three loops from planar Yang-Mills theory”  In _JHEP_ 01, 2022, pp. 149  DOI: 10.1007/JHEP01(2022)149
  * [37] Vittorio Del Duca and E… Glover  “Testing high-energy factorization beyond the next-to-leading-logarithmic accuracy”  In _JHEP_ 05, 2008, pp. 056  DOI: 10.1088/1126-6708/2008/05/056
  * [38] V. Del Duca, C. Duhr and E… Glover  “Iterated amplitudes in the high-energy limit”  In _JHEP_ 12, 2008, pp. 097  DOI: 10.1088/1126-6708/2008/12/097
  * [39] Øyvind Almelid, Claude Duhr and Einan Gardi  “Three-loop corrections to the soft anomalous dimension in multileg scattering”  In _Phys. Rev. Lett._ 117.17, 2016, pp. 172002  DOI: 10.1103/PhysRevLett.117.172002
  * [40] Thomas Becher and Matthias Neubert  “Infrared singularities of scattering amplitudes and N3LL resummation for $n$-jet processes”  In _JHEP_ 01, 2020, pp. 025  DOI: 10.1007/JHEP01(2020)025
  * [41] Øyvind Almelid et al.  “Bootstrapping the QCD soft anomalous dimension”  In _JHEP_ 09, 2017, pp. 073  DOI: 10.1007/JHEP09(2017)073


# Feasibility of Privacy-Preserving Entity Resolution on Confidential
Healthcare Datasets Using Homomorphic Encryption

Yixiang Yao<EMAIL_ADDRESS>University of Southern CaliforniaLos
AngelesCaliforniaUSA ,  Joseph Cecil<EMAIL_ADDRESS>Information Sciences
InstituteWalthamMassachusettsUSA ,  Praveen Angyan<EMAIL_ADDRESS>Southern California Clinical and Translational Science InstituteLos
AngelesCaliforniaUSA ,  Neil Bahroos<EMAIL_ADDRESS>Southern
California Clinical and Translational Science InstituteLos
AngelesCaliforniaUSA and  Srivatsan Ravi<EMAIL_ADDRESS>University of
Southern CaliforniaLos AngelesCaliforniaUSA

(2024)

###### Abstract.

Patient datasets contain confidential information which is protected by laws
and regulations such as HIPAA and GDPR. Ensuring comprehensive patient
information necessitates privacy-preserving entity resolution (PPER), which
identifies identical patient entities across multiple databases from different
healthcare organizations while maintaining data privacy. Existing methods
often lack cryptographic security or are computationally impractical for real-
world datasets. We introduce a PPER pipeline based on AMPPERE, a secure
abstract computation model utilizing cryptographic tools like homomorphic
encryption. Our tailored approach incorporates extensive parallelization
techniques and optimal parameters specifically for patient datasets.
Experimental results demonstrate the proposed method’s effectiveness in terms
of accuracy and efficiency compared to various baselines.

entity resolution, data privacy, homomorphic encryption

††copyright: acmlicensed††journalyear: 2024††doi: XXXXXXX.XXXXXXX††conference:
Make sure to enter the correct conference title from your rights confirmation
email; October 03–05, 2024; Boise, ID††isbn: 978-1-4503-XXXX-X/18/06††ccs:
Information systems Entity resolution††ccs: Information systems
Deduplication††ccs: Security and privacy Privacy-preserving protocols

##  1\. Introduction

Patients visit different healthcare facilities to receive primary care,
specialized treatments such as obstetrics or dentistry, urgent or emergency
services, or to fill prescriptions. However, optimal and safe healthcare often
necessitates a unified medical history for each patient. Moreover, healthcare
research is frequently multidisciplinary, necessitating the merging of
datasets from various research teams. During health crises like pandemics, it
is crucial for organizations to share health datasets swiftly and securely. An
example is the National COVID Cohort Collaborative (N3C), which was
established to facilitate the sharing of secure and de-identified clinical
data across the US for COVID-19 research. Entity resolution (ER) is the task
of finding records that refer to the same entity across different data sources
(Papadakis et al., 2020). This technique aligns with the purpose of
identifying the same patients or research participants to consolidate data
about each individual in multidisciplinary and collaborative research.

When applied to patient datasets, ER faces significant challenges due to
privacy regulations such as the Health Insurance Portability and
Accountability Act (HIPAA) in the United States and the General Data
Protection Regulation (GDPR) in the European Union. The Privacy Rule provided
by the HIPAA (hip, 2024a) gives patients rights over their health information
and sets rules and limits on who can look at and receive their health
information. HIPAA specifies 18 elements in health data (hip, 2024b) that are
considered identifiers. Additionally, certain populations in healthcare are at
particularly high risk if their private information is exposed, such as
individuals with mental disabilities or mental health conditions, HIV, or
those experiencing homelessness. In healthcare and research, merging datasets
by sharing the full dataset is inherently risky. Even without explicit
identifiers, medical data containing rare conditions can be sufficient to
uniquely identify a patient.

Existing solutions to address these challenges include the use of privacy-
preserving entity resolution (PPER) techniques, which enable the matching of
records across datasets while keeping the data encoded and ensuring that
individual privacy is maintained (Vatsalan et al., 2013, 2017; Gkoulalas-
Divanis et al., 2021). These techniques encompass methods such as hashing,
masking, perturbation, and probabilistic approaches, as well as the use of
natural language models to encode records into multi-dimensional embedding
vectors. However, these methods are either susceptible to various attacks or
require a trade-off between data utility and privacy. As a solution, AMPPERE
(Yao et al., 2021), as an platform-agnostic PPER framework leveraging either
secure multi-party computation or fully homomorphic encryption, is proposed to
guarantee the cryptographic security of the data without sacrificing utility.
However, as a universal abstract model, AMPPERE encounters efficiency
challenges when scaling to large practical datasets, as it requires
compatibility with heterogeneous underlying secure multi-party computation
protocols or homomorphic encryption schemes.

In this work, we focus on resolving the real-world PPER challenge of
healthcare datasets, aiming to ensure HIPAA compliance and minimize the risk
of exposing private information. We develop our open-source solution using
AMPPERE as the foundation, ensuring precise computational accuracy and
provable privacy. We extensively parallelize the execution by employing
various techniques and optimize the parameters specifically for the datasets.
Subsequently, we conduct comprehensive experiments comparing our optimized
method with baselines, as well as ablation studies, to verify the
effectiveness of each optimized component.

color=red!20, inline]Yixiang: citations for medical related-stuff

Figure 1. The overview of the dataset and the pipeline. Arrows and boxes in
orange indicate the data is in cipher. Each record, after pre-processing and
tokenization, is encrypted into ciphertext. All records from both datasets are
then sent to the optimized AMPPERE pipeline, which homomorphically evaluates
the potential matches and produces record pairs with scores in encrypted form.
Finally, the data owners decrypt the results collectively, whereas the
adversary cannot gather any information.

##  2\. Patient Mortality Datasets

There are numerous PPER tasks in the healthcare domain. In this study, we
focus on one specific task related to patient mortality. Patients in a
healthcare organization are only marked as deceased if they pass away during
care. However, research into the causes of mortality necessitates up-to-date
information. Electronic Medical Records (EMR) systems are rarely updated with
the mortality statuses of former patients. Acquiring a patient’s current
mortality status requires matching against external datasets. Thus, the goal
is to develop an efficient and secure PPER pipeline for integrating external
mortality data with existing EMR systems to ensure accurate and comprehensive
mortality information for research purposes.

Datasets The patient mortality datasets consist of two sub-datasets. Dataset
$D_{1}$ contains cancer patients with deceased information and has the
identifiers shown in Figure 1. Dataset $D_{2}$ contains patients from the EMR
and has all of the identifiers as $D_{1}$. The basic statistics of these
datasets are summarized in Table 1. Note that both datasets contain additional
attributes, but only the identifiers share common information that are useful
to match entities.

Dataset | # records | SSN % | DOB % | FN % | LN %
---|---|---|---|---|---
$D_{1}$ | 19,274 | 80.2 | 100 | 100 | 99.99
$D_{2}$ | 859,725 | 95.3 | 99.95 | 99.99 | 99.99
Table 1. Basic statistics of patient mortality datasets.

Ground truth Ground truth is vital for developing PPER algorithms,
particularly for parameter tuning and performance evaluation. It consists of
sampled shared record pairs across two datasets. Typically, establishing such
a ground truth set requires labor-intensive annotation by human experts.
However, in patient mortality datasets, the presence of unique identifiers
allows for the straightforward formation of the ground truth set based on
these identifiers. MRNs serve as unique identifiers for patients within
healthcare systems, but they are only guaranteed to be unique within a single
organization. Hence, as a nationally unique identifier, the SSN is ideal for
bridging record pairs in constructing ground truth. Note we do not use SSN
directly for PPER because it is not generally available in other healthcare
datasets.

Output The output of PPER is required to be a list of matching record pairs
with match scores (0-100%). Additionally, some of the other identifiers are
selectively included for debugging purposes.

Pre-processing Medical record data vary in the exact representation of the
attributes; we therefore perform preprocessing to normalize the SSN and DOB
into standard forms across both datasets. Concretely, We normalize the SSNs to
the form XXX-XX-XXXX and transform the DOB representation into a normalized,
zero-padded MM/DD/YYYY representation. We additionally remove invalid SSNs and
perform deduplication on each dataset individually, reducing the size of
$D_{1}$ to 19,274 and $D_{2}$ to 859,714.

##  3\. Preliminaries and Related Work

###  3.1. Definitions

A formal problem of privacy-preserving entity resolution (PPER) can be framed
as a triple $T=(D,M,E)$, where $D=\\{D_{1}\ldots D_{n}\\}$ represents a
collection of $n$ distinct datasets comprising records $r$, each owned by a
different data owner $P=\\{P_{1}\ldots P_{n}\\}$. The encoding or encryption
algorithm $E$ is responsible for maintaining the confidentiality of records
from each dataset, such that $r$ from each $D$ is transformed into encoded or
ciphertext form, denoted as $\llbracket r\rrbracket\in E(D)$, where
$\llbracket r\rrbracket$ explicitly indicates that $r$ is in a privacy-
preserving representation (i.e., ciphertext in our setting). The match set $M$
contains pairs of records that match between any two datasets among the $n$
parties, that is, $M=\\{(\llbracket r_{i}\rrbracket,\llbracket
r_{j}\rrbracket)\,|\,r_{i}=r_{j};\llbracket r_{i}\rrbracket\in
E(D_{k}),\llbracket r_{j}\rrbracket\in E(D_{m})\\}$, where $r_{i}=r_{j}$
indicates that $r_{i}$ and $r_{j}$ refer to the same entity in the real world.

Conducting PPER naively requires so-called full comparison
$T=\\{(r_{i},r_{j})\,|\,r_{i}\in D_{k},r_{j}\in D_{m}\\}$ for all the possible
pairs between parties, resulting in a total number of comparisons equivalent
to the Cartesian product of the sizes of $D_{k}$ and $D_{m}$ (i.e.
$|T|=|D_{k}|\times|D_{m}|$). Since PPER can be computationally heavy, adopting
such a quadratic method is impractical. To eliminate unnecessary comparisons,
the blocking algorithm is employed to prune $T$ to $T^{\prime}$ by removing
pairs that are unlikely to be part of the solution $M$. Typically, each record
$r$ is represented by a set of blocking keys $\beta(r)=(k_{1},k_{2},\cdots)$,
where $\beta(\cdot)$ is the key generation function. Consequently, the
candidate pairs are the pairs that share at least one blocking key in common,
that is,
$T^{\prime}=\\{(r_{i},r_{j})\,|\,|\beta(r_{i})\cap\beta(r_{j})|>0,r_{i}\in
D_{1},r_{j}\in D_{2}\\}$.

###  3.2. Homomorphic Encryption and CKKS

Homomorphic encryption (HE) allows the computation to be performed over
encrypted data while preserving the input/output relationship of the function
between the plaintext and ciphertext data (Fontaine and Galand, 2007; Acar et
al., 2018). In general, an encryption scheme is said to be homomorphic if for
some operator $\odot$ over plaintext ($\odot_{\mathcal{M}}$) and ciphertext
($\odot_{\mathcal{C}}$), the encryption function $E$ satisfies: $\forall
m_{1},m_{2}\in\mathcal{M},\ E(m_{1}\odot_{\mathcal{M}}m_{2})\leftarrow
E(m_{1})\odot_{\mathcal{C}}E(m_{2})$, where $\mathcal{M}$ denotes the message
in plaintext and $\mathcal{C}$ denotes the message in ciphertext. $\leftarrow$
means the computation is direct without any decryption in the middle of the
process. Therefore, if we let $\odot$ to be $+$, a computation unit can
compute $m_{1}+m_{2}$ using the original message from the data owner in
encrypted form, that is, $E(m_{1})$ and $E(m_{2})$, and is able to compute the
addition of two encrypted messages without decrypting. Only the data owner
with the key can decrypt the message from ciphertext back to plaintext.

color=red!20, inline]Yixiang: rephrase the above text, copied from our KDD
paper

CKKS (Cheon-Kim-Kim-Song) (Jung Hee Cheon, 2017) is an encryption scheme that
falls under the umbrella of homomorphic encryption. It supports approximate
arithmetic operations on encrypted real or complex numbers, and can pack
multiple numbers into a single ciphertext for efficiency. CKKS, along with
other HE schemes, offers two primary advantages: First, it maintains the
accuracy of algorithms compared to their plaintext equivalents while ensuring
the confidentiality of the data. Second, it has been rigorously proved to be
both semantically (Sako, 2011) and IND-CPA (Bellare et al., 1997; Goldwasser
and Micali, 1984) secure. Therefore, our pipeline, based on AMPPERE, employs
the CKKS HE scheme to safeguard data privacy, ensuring that neither the data
owners learn about the data from other parties nor the third parties learn
about the individual data or the actual outcome of the computation.

###  3.3. Related Works

PPER Initial research has explored using secure one-way hashing and masking
algorithms to protect record content (Dusserre et al., 1995; Quantin et al.,
1998), but these methods are limited as they do not account for similar
variants of records. Some algorithms use probabilistic data structures, such
as Bloom filters (Schnell et al., 2009; Niedermeyer et al., 2014), but these
are vulnerable to frequency attacks and require a balance between data privacy
and utility. Other approaches modify string matching algorithms (Wang et al.,
2015; Zhu and Huang, 2017) yet their applicability remains restricted to
specific algorithms within particular application contexts. With advancements
in word/sentence embedding techniques, some methods (Scannapieco et al., 2007;
Bonomi et al., 2012; Li et al., 2021) transform original records into multi-
dimensional embedding vectors that preserve key semantics for similarity
comparison and clustering. However, these embeddings are not secure and are
susceptible to inversion attacks (Song and Raghunathan, 2020). Recently,
methods utilizing secure multi-party computation or homomorphic encryption-
based approaches have been explored (Lindell, 2005; Ghai et al., 2023; Yao et
al., 2021), offering strong privacy guarantees but are still computationally
and resource-intensive.

PPER in healthcare Despite the numerous proposed PPER methods, their
application in the healthcare domain remains limited due to concerns about
scalability, explainability, and stability. Datavant (dat, 2024) is a company
that provides commercial PPER services for healthcare datasets, selected by
the N3C collaborative. Specifically, their PPER solution (Bernstam et al.,
2022; Kiernan et al., 2022) generates tokens based on the structure of the
dataset to represent records and performs matching based on the number of
matches of these tokens. These tokens are secured through a two-step private
token generation process that first generates master tokens based on SHA-256
(Penard and van Werkhoven, 2008) and then encrypts the tokens to site-specific
tokens using AES-128 (Rijmen and Daemen, 2001). Even though this method
ensures the identifier is not directly reversible, it has several drawbacks.
For instance, because the tokens are hashed, the matching process can only
achieve exact matches, making the precision of the matching reliant on the
complexity of the token generation rules. Additionally, the same individual-
specific tokens are produced across different datasets, which is generally not
considered semantically secure.

##  4\. Pipeline Implementation and Optimization

Before diving into our PPER pipeline, we introduce certain baselines upon
which our work is built and subsequently compare them.

Naive HE adaptation This is the most basic version of the PPER pipeline using
HE. It simply wraps the ER operation with HE, that is, Private Set
Intersection (PSI) (Chen et al., 2017). Therefore, such a method finds pairs
using a full quadratic comparison over $T$.

Cleartext ER This is a plaintext version of the ER pipeline. This operates
almost in the same way as the privacy-preserving pipeline: It first computes
candidate pairs $T^{\prime}$ with blocking, then computes similarity scores
using ER within $T^{\prime}$.

AMPPERE As introduced before, AMPPERE is an abstract model that defines a
cryptographically secure PPER pipeline. Its underlying implementation can be
either secure multi-party computation or fully homomorphic encryption. The
timing diagram of AMPPERE’s execution is in Figure 2. The raw content of the
record is homomorphically encrypted in $P_{1}$ and $P_{2}$, with blocks
generated individually. These encrypted records and blocks are then
transmitted to $P_{3}$ for merging and deduplication using Private Matrix
Operation. After obfuscation, the entities are resolved using a
computationally efficient PSI method called Vector Rotation, according to all
interactively decrypted candidate pair IDs. The ultimate results are then
returned to $P_{1}$ and $P_{2}$, where they are collaboratively decrypted.

However, AMPPERE does not scale well to large datasets because of abstract
layers for generality. In this work, we chose CKKS for the specific
implementation of AMPPERE, primarily because of its efficiency in algorithmic
computation and the non-interactive flexibility it offers to the involved
parties. We use OpenFHE (Badawi et al., 2022) to implement this scheme. In the
subsequent subsections, we illustrate our methodology for constructing the
pipeline tailored specifically to medical datasets. We also explore
optimization strategies for achieving both maximum accuracy (because CKKS is
an approximate arithmetic) and swift execution times. Specifically, in Section
4.1, Section 4.2, and Section 4.3, we demonstrate the approach to
parallelizing the pipeline from the architecture level, programming level, and
algorithm level, respectively. In Section 4.4, we explore the integration of
state-of-the-art approximation operators for reduced interactivity. Finally,
in Section 4.5, we elaborate on the parameter tuning in the context of CKKS.

Figure 2. The timing diagram of AMPPERE

###  4.1. Chunking

Chunking is a common solution for handling large-scale data in ER by breaking
down the dataset into smaller “chunks” to process them more efficiently with
limited computation resources. In the modern ER pipeline, chunking serves an
important role in making the original data into manageable units so that they
can be consumed and orchestrated by distributed computation frameworks such as
MapReduce (Dean and Ghemawat, 2008). Typically, chunking is based on the
output of blocking (Efthymiou et al., 2017). As depicted in the left segment
of Figure 3, after the autonomous generation of blocks in $P_{1}$ and $P_{2}$,
they need to be shared so that these single-side blocks are merged according
to their blocking keys. Subsequently, the candidate pairs for ER are
formulated with an optional deduplication step, and these pairs are chunked
and distributed to computation units.

However, at least two issues persist for directly adopting the blocking-based
approach. 1) Sharing blocks for merging and deduplication exposes the
information of potential entity matches. 2) The overhead of encrypted records
and blocks is non-trivial in terms of the process of serialization,
deserialization, and data transmission. The blocking-based approach causes a
relatively arbitrary distribution, thereby lacking I/O efficiency.

color=red!20, inline]Yixiang: and the total size of the blocks is not
consistent

As a solution, we leverage the record-based approach, as delineated in the
right segment of the Figure 3. The record pairs are first-class citizens and
are assigned to chunks along with the associated blocks. In each chunk, blocks
are privately merged and deduplicated via AMPPERE’s private matrix operation.
Consequently, the process of blocking leaks no information and needs no
additional I/O-heavy data transmission or serialization/deserialization.

Figure 3. Chunking strategies. Data owners compute blocks independently. In
the case of the blocking-based method, these blocks are shared to form
candidate pairs, which are subsequently chunked. Whereas for the record-based
approach, chunking occurs directly on the records, and candidate pairs are
generated via private matrix manipulation within each chunk.

###  4.2. Parallel Programming

Modern computers are equipped with multiple CPU cores, and multi-
processing/multi-threading are the techniques in which multiple
processes/threads are executed concurrently by utilizing multiple CPU cores.
We adopt such techniques as programming-level parallelization to utilize the
available computation resources fully.

Concretely, decryption is performed in parallel to retrieve the obfuscated
pairs, while converting the candidate pair matrix into a candidate pair list
is also executed concurrently. Besides, in more sophisticated scenarios, we
orchestrate parallel programming with SIMD (Section 4.3). We encrypt and
evaluate records as vectors for ease of maintenance and representation
consistency, and the concurrent execution of multiple vectors leverages
parallel programming. In Algorithm 1, we eliminate duplicate candidate pairs
using a private matrix represented by $M$ encrypted $N$-dimensional vectors.
The privacy-preserving update of the matrix is distributed across multiple
threads. Moreover, in Algorithm 2, when comparing record similarity, the token
comparison using Vector Rotation (VR) over encrypted record pair is SIMD-
accelerated; meanwhile, multiple VR operations are executed concurrently.

1:$cand\\_pairs\leftarrow\left[\llbracket\operatorname{zeros}(N)\rrbracket;M\right]$

2:for $key\in row\\_index$ do

3: for $\llbracket row\\_id\rrbracket\in row\\_index[key]$ do

4: for $\llbracket col\\_id\rrbracket\in col\\_index[key]$ do

5: $cand\\_pairs[\llbracket row\\_id\rrbracket]\leftarrow update($

6: $\hskip 20.00003ptcand\\_pairs[\llbracket row\\_id\rrbracket],$

7: $\hskip 20.00003pt\llbracket packed\\_col\\_id\rrbracket,$

8: $\hskip 20.00003pt\llbracket all\\_col\\_ids\rrbracket)$
$\left.\rule{0.0pt}{62.39996pt}\right\\}\ \mbox{in parallel}$

9: end for

10: end for

11:end for

Algorithm 1 Algorithm for deduplicating using a matrix.

1:$overlaps\leftarrow[]$

2:for $(\llbracket r_{A}\rrbracket,\llbracket r_{B}\rrbracket)\in enc\\_pairs$
do

3: $overlaps.append(\operatorname{VR}(\llbracket r_{A}\rrbracket,\llbracket
r_{B}\rrbracket))$ $\left.\rule{0.0pt}{19.20007pt}\right\\}\ \mbox{in
parallel}$

4:end for

Algorithm 2 Algorithm for computing the overlaps between records.

###  4.3. SIMD

SIMD stands for Single Instruction Multiple Data, in which a single
instruction is applied to multiple data elements at the same time, rather than
processing each data element individually. This approach is particularly
efficient for tasks in homomorphic encryption evaluation that involve
performing the same operation on a large set of data. For example, adding
numerous integer pairs sequentially in a loop can be achieved through a single
addition operation between two vectors, where the original integer pairs are
packed into them respectively.

Despite offering superior efficiency for executing parallel operations on
modern computer architectures, integrating SIMD into a homomorphic encryption
program poses many challenges. Firstly, not all available operators support
parallel execution. Secondly, data must be batched and aligned in advance.
Thirdly, certain operations, such as obtaining the vector length, become
inaccessible when executed in batch rather than individually.

color=orange!20, inline]Joe: on review, I found (Thursday or Friday) that
AMPPERE already performed vector rotation in a vectorized/SIMD way. I made a
first pass at updating this to be in terms of record IDs so that we don’t have
to update the text or the example too much—let me know what you think. Due to
the limitations of SIMD, we revamped AMPPERE’s representation of the
deduplication matrix. Instead of encrypting each record ID individually, the
encryption is over the rows of the matrix. Subsequently, we also altered the
Element-wise Equality (EEq) operation to adapt to the new matrix
representation. As an example, when computing the difference between record ID
pairs, if each record ID is element-wisely encrypted, the operation is as
Algorithm 3 (upper section) where each pair of elements is compared
individually in a loop. By contrast, Algorithm 3 (lower section) demonstrates
an advanced version where the record IDs are represented by vectors, and
encryption is applied to the vectors. With SIMD, the output is obtained in a
single operation.

1:$\triangleright$ With element-wise encryption

2:$enc\\_a\leftarrow[E(a_{1}),E(a_{2}),\dots,E(a_{n})]$

3:$enc\\_b\leftarrow[E(b_{1}),E(b_{2}),\dots,E(b_{n})]$

4:for $i\leftarrow 1\dots n$ do

5: $enc\\_output[i]\leftarrow enc\\_a[i]-enc\\_b[i]$

6:end for

7:$\triangleright$ With vector-wise encryption and SIMD

8:$\llbracket a\rrbracket\leftarrow E([a_{1},a_{2},\dots,a_{n}])$

9:$\llbracket b\rrbracket\leftarrow E([b_{1},b_{2},\dots,b_{n}])$

10:$\llbracket output\rrbracket\leftarrow\llbracket a\rrbracket-\llbracket
b\rrbracket$

Algorithm 3 Computing difference between record ID pairs

###  4.4. Non-Interactive Comparison

Logical comparisons are fundamental to decision-making in algorithms and
control flow structures like loops and conditional statements in programming.
AMPPERE utilizes a crucial logical operator
$\operatorname{\texttt{EEq}}(a,b)$. This operator returns a Boolean vector
that encapsulates the result of element-wise comparisons, indicating whether
each corresponding element in $a$ is identical to the respective element in
$b$. AMPPERE provides a workaround for pure algorithmic homomorphic encryption
schemes, such as CKKS, that does not support any logical operators:
$(a-b)*\frac{-1}{a-b+\xi}+1$, where $\xi$ is a small offset added to prevent
dividing by zero. Unfortunately, computing $\frac{-1}{a-b+\xi}$ involves an
inverse operation, which is not available in CKKS. As an alternative approach,
the original cipher $\llbracket x\rrbracket$ is multiplied by a randomly
generated number $\llbracket r\rrbracket\in\\{\llbracket
r_{1}\rrbracket,\cdots,\llbracket r_{n}\rrbracket\\}$, pre-generated by
$P_{1}/P_{2}$, resulting in $\llbracket rx\rrbracket$. This $\llbracket
rx\rrbracket$ is then transmitted to $P_{1}/P_{2}$ for decryption and inverse
computation. The encrypted result $\llbracket\frac{1}{rx}\rrbracket$ is sent
back to $P_{3}$ and ultimately transformed into
$\llbracket\frac{1}{x}\rrbracket$ via multiplication with $\llbracket
r\rrbracket$, yielding $\llbracket\frac{1}{rx}\rrbracket*\llbracket
r\rrbracket$.

In recent years, new solutions have been proposed for computing inverse as
well as testing equality without random numbers and interaction between
parties. Cheon et al. (2019) proposed approximated
$\operatorname{\texttt{Inv}}$ (inverse) and $\operatorname{\texttt{Comp}}$
(comparison, based on $\operatorname{\texttt{Inv}}$) solely relying on
addition and multiplication, making it possible to be applied in HE. The
$\operatorname{\texttt{Comp}}(a,b)$ function returns 0, 0.5, and 1 for the
cases that $a<b$, $a=b$, and $a>b$, respectively. Note that $a$ and $b$ are
vectors and $\operatorname{\texttt{Comp}}$ is SIMD-accelerated. To use
$\operatorname{\texttt{Comp}}$, inputs $a$ and $b$ are required to be in a
certain fractional range. Yet, employing it to compare record ID equality is
not straightforward due to the representation of record IDs as integers. In
our implementation, we address this challenge by transforming IDs.
Specifically, we assign in-chunk IDs to records, ensuring the chunk size does
not exceed the batch size, that is, the in-chunk ID
$i\in\\{0,1,\dots,batchSize-1\\}$. Therefore, we rescale $i$ as
$\hat{i}=\frac{1}{2}+\frac{i}{batchSize}$, such that
$\hat{i}\in\left[\frac{1}{2},\frac{3}{2}\right)$. To build
$\operatorname{\texttt{EEq}}(a,b)$, the function needs one more step to map
the result of $\operatorname{\texttt{Comp}}(a,b)$ to Boolean, that is,
$0/1\mapsto 0$ ($a<b$ / $a>b$), and $0.5\mapsto 1$ ($a=b$). This can be
achieved arithmetically by
$\operatorname{\texttt{EEq}}(a,b)=4\operatorname{\texttt{Comp}}(a,b)\operatorname{\texttt{Comp}}(b,a)=4\operatorname{\texttt{Comp}}(a,b)(1-\operatorname{\texttt{Comp}}(a,b))$.

###  4.5. Parameter Tuning

Tuning parameters in a homomorphic encryption scheme is essential to achieve a
balanced trade-off between security, performance, correctness, scalability,
and resource utilization. CKKS is no exception. We list all the parameters
that are used in Table 2.

Here, we demonstrate the three important parameters that affect the
approximation accuracy and running efficiency the most in our implementation.
Batch size refers to the number of plaintext slots that can be encrypted and
processed simultaneously within a single ciphertext. CKKS allows for the
packing of multiple plaintext values into one ciphertext, enabling parallel
processing of these values, which significantly enhances the efficiency of
homomorphic computations. Scale factor bits refer to the number of bits used
to represent the scaling factor in CKKS. It influences the precision and noise
behavior of homomorphic computations. Proper balancing of this parameter is
critical for ensuring accurate and efficient encrypted computations. Number of
large digits refers to the number of digits in key switching, which is a
crucial operation for changing encryption keys for ciphers. Choosing a larger
digit size simplifies complexity, but it results in a larger key size.
Naturally, we choose our batch size, scale factor bits, and number of large
digits to maximize accuracy for candidate pair deduplication via private
matrix operation. We find that the SIMD-optimized version of the deduplication
algorithm is most accurate with a small batch size, a single large digit, and
50 scale factor bits. We, therefore, choose the minimum batch size needed for
our experiments. The chunking experiments require a batch size of at least
100. Since batch size must be a power of two, the minimum batch size is 128.

Another crucial parameter is multiplicative depth, which refers to the maximum
number of consecutive homomorphic multiplication operations that can be
performed on encrypted data before the noise grows too large for successful
decryption. In general, there is no advantage to greater multiplication depth
beyond the minimum required depth for the homomorphic circuit to be executed.
Therefore, we use the minimum multiplication depth needed in each case.
However, due to multiplicative operations in the
$\operatorname{\texttt{Comp}}$ function, the non-interactive pipeline requires
a prohibitively large multiplication depth. Specifically, in our pipeline, we
use a set of $\operatorname{\texttt{Comp}}$ parameters $m=4$ and
$(d^{\prime},d,t)=(5,5,6)$ (Cheon et al., 2019). With this setting, the
minimum required depth is 65. This extreme depth results in keys that use a
prohibitive amount of memory. Instead of increasing the depth, we use
bootstrapping, a technique that refreshes a ciphertext by reducing its noise,
as an alternative. Although bootstrapping enables more homomorphic operations
on a fixed pre-set depth without surpassing noise limits, it has significant
drawbacks, including high computational overhead, increased latency, resource
consumption, and potential precision loss. To balance these factors, we set
the multiplication depth to 12 and incorporate bootstrapping to avoid
excessive memory requirements.

Parameter | Value
---|---
Multiplicative depth | 2 (12)
Scale factor bits | 50
Batch size | 128
Number of large digits | 1
First mod size | 60
Digit size | 0
Security level | HEStd_128_classic
Scaling technique | FLEXIBLEAUTO
Key switching technique | HYBRID
Secret key distribution | UNIFORM_TERNARY
Interactive bootstrapping compression level | n/a (COMPACT)
Table 2. OpenFHE parameters for CKKS. The parenthesized values are used only
in the bootstrapping-enabled non-interactive pipeline.

##  5\. Experiments

In this section, we conduct extensive experiments. We first detail the
settings in Section 5.1. The main results are demonstrated in Section 5.2,
followed by the ablation studies of the effectiveness of chunking, parallel
programming & SIMD in Section 5.3.

Figure 4. ROC curve for the ER system.

Figure 5. Estimated runtime for our optimized system versus two baselines.

Figure 6. Normalized average time comparison for different chunk sizes.

Figure 7. Time comparison for ablation experiments.

Figure 8. Time comparison for interactive vs. non-interactive pipeline.

Figure 9. Space comparison for interactive vs. non-interactive pipeline.

###  5.1. Settings

Metrics We compute true positive rate (also called recall), precision, and
false positive rate for measuring the ER accuracy. As for the performance of
blocking, we use pairs completeness ($PC=\tfrac{M\cap T^{\prime}}{M}$) to
measure the percentage of true pairs that are blocked, and reduction ratio
($RR=1-\tfrac{|T^{\prime}|}{|T|}$) to measure how well the method reduces the
number of candidate pairs. $F\textnormal{-}1$ is employed to harmonically
demonstrate the overall performance of blocking.

Environment The experiments are conducted on a privacy-protected Linux
instance with 14G RAM and a 4-core CPU. The pipeline implementation uses
OpenFHE version 1.1.2.

color=red!20, inline]Yixiang: spec details color=orange!20, inline]Joe:
Yixiang, I updated this paragraph about the sample dataset, but per our
discussion we may want to delete the paragraph anyway. Because we’ve improved
our sampling technique, we probably don’t need to describe this in detail, but
I rewrote the description to describe precisely the updated sampling approach
just in case we want it. Feel free to delete it, or to remove everything after
“on randomly sampled subsets.”

###  5.2. Main Results

We report the main results from two perspectives. The first is blocking and ER
performance, as well as the cost of running time.

The effectiveness of blocking is represented in Table 3. The pair completeness
($PC$) is 100%, indicating that the blocking algorithm captures all potential
pairs. The reduction ratio $RR$ is 99.996%, meaning the candidate pair set
$T^{\prime}$ is only 0.004% of the full comparison set $T$. Therefore,
applying blocking to this dataset preserves all potential pairs while
significantly reducing the pairwise comparisons by more than 99%. As for the
ER performance, we access it with different thresholds $t$ for the record-
matching scores. If the score is greater than $t$, the record pair is
identified as the same entity. We show the results in Figure 6 using nine
evenly spaced thresholds from 0.1 to 0.9. The pipeline achieves a high recall
(over 92%) for the highest threshold, and slightly lower thresholds decrease
the precision only negligibly. Moreover, a threshold of around 0.5 achieves
nearly perfect recall at approximately 90% precision and a false positive rate
of less than 0.0001%. The evaluation above is performed on the cleartext
baseline. Both AMPPERE and the optimized pipeline exhibit identical
performance because our implementation does not sacrifice any matching
performance.

In terms of runtime, we compare our optimized pipeline with the naive HE
adaption and AMPPERE. As illustrated in Figure 6, our optimized system, with
chunk size set to 50, operates 24 times faster than AMPPERE and 447 times
faster than the naive HE baseline. This notable acceleration underscores the
effectiveness of our optimization, leveraging multi-level parallelizations and
optimal parameters. In comparison, AMPPERE operates 19 times faster than the
naive HE baseline, largely due to its effective blocking and vector rotation
for PSI calculation. Note that for our optimized solution, if more computation
resources are available, such as with 96 CPU cores, the speed will increase 24
times.

Pair Completeness ($PC$) | Reduction Ratio ($RR$) | $F\textnormal{-}score$
---|---|---
100% | 99.996% | 99.998%
Table 3. Blocking performance for the ER pipeline.

###  5.3. Ablation Studies for Pipeline Optimizations

We report the average time per chunk pair for running time, as it is the
fundamental unit into which the data is distributed for computation. This
measure allows convenient estimation of time costs with varying computational
resources. The average time is computed with the same number of input records
for baselines.

Chunking As the encrypted dataset cannot fit into memory entirely, we
partition it into smaller chunks. This experiment investigates the
relationship between running time and chunk size. We examine chunk sizes of
25, 50, and 100 for each dataset. Because the optimized method employs record-
based chunking, the potential number of record pairs for a chunk pair equals
the square of the original chunk size: $25^{2}=625$, $50^{2}=2,500$, and
$100^{2}=10,000$. Consequently, we normalize the running time by the squared
chunk size. We present the results in Figure 6. The findings reveal that
doubling the chunk size significantly reduces the normalized running time.
This suggests that the increment in chunk size does not have a linear
correlation with the normalized running time. The poorer performance observed
with smaller chunks may be attributed to more frequent memory swapping, disk
I/O, and serialization/deserialization of the cipher data. As a practical
guideline for achieving optimal running speed, the batch size should be set to
the maximum possible value based on the available memory size.

Parallel Programming & SIMD In this experiment, we assess the impact of
parallel programming and SIMD. We conduct two versions for parallel
programming: one with parallel programming enabled and one without. For SIMD,
due to its changes to the cipher data representation and corresponding
functions, it cannot be isolated in the experiments. Consequently, we use
AMPPERE as the baseline and create two variants of the optimized pipeline:
SIMD-only (NoParallel) and SIMD combined with Parallel Programming
(Optimized). The results are presented in Figure 9. SIMD-only is significantly
faster than AMPPERE, highlighting the benefits of processing a batch of data
simultaneously. When parallel programming is enabled, the optimized version
becomes even faster, saving over 40% of the time compared to the SIMD-only
version.

Non-Interactive Comparison We first compare the time cost of the interactive
and non-interactive pipelines. The non-interactive pipeline (Figure 9),
although devoid of interaction and pre-generated random ciphers, operates 85
times slower than the interactive pipeline. This discrepancy arises from the
relatively high multiplicative depth and the overhead associated with
bootstrapping.

Furthermore, we evaluate memory and storage utilization between the
interactive and non-interactive pipelines. Specifically, we compare peak
memory usage (RSS), average storage usage for each chunk (MCS), and key
storage utilized for keys (KS). As demonstrated in Figure 9, the non-
interactive pipeline consumes 16.6, 17.3, and 16.6 times more than the
corresponding interactive pipeline in each category, respectively. These
findings underscore that the non-interactive pipeline necessitates
significantly greater memory and storage per chunk.

##  6\. Conclusion

In this work, we utilized the CKKS variant within the AMPPERE framework to
tackle the challenge of privacy-preserving entity resolution on real-world
healthcare datasets. The CKKS homomorphic encryption scheme ensures data
privacy by preventing any leakage of confidential information and complies
with HIPAA regulations. Furthermore, we comprehensively optimized AMPPERE’s
pipeline, from data representations to the execution of various operators.
These enhancements have significantly improved efficiency without compromising
the accuracy of the entity resolution task or the level of privacy protection.
This suggests that such approaches are scalable and practical for large-scale
applications.

## References

  * (1)
  * dat (2024) 2024\.  Davatant.  https://www.datavant.com/
  * hip (2024a) 2024a.  HIPAA Privacy Rule.  https://www.hhs.gov/hipaa/index.html
  * hip (2024b) 2024b.  List of HIPAA Identifiers.  https://www.dhcs.ca.gov/dataandstats/data/Pages/ListofHIPAAIdentifiers.aspx
  * Acar et al. (2018) Abbas Acar, Hidayet Aksu, A Selcuk Uluagac, and Mauro Conti. 2018.  A survey on homomorphic encryption schemes: Theory and implementation.  _ACM Computing Surveys (Csur)_ 51, 4 (2018), 1–35.
  * Badawi et al. (2022) Ahmad Al Badawi, Andreea Alexandru, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Carlo Pascoe, Yuriy Polyakov, Ian Quah, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. 2022.  OpenFHE: Open-Source Fully Homomorphic Encryption Library.  Cryptology ePrint Archive, Paper 2022/915.  https://eprint.iacr.org/2022/915 https://eprint.iacr.org/2022/915.
  * Bellare et al. (1997) Mihir Bellare, Anand Desai, Eron Jokipii, and Phillip Rogaway. 1997.  A concrete security treatment of symmetric encryption. In _Proceedings 38th Annual Symposium on Foundations of Computer Science_. IEEE, 394–403.
  * Bernstam et al. (2022) Elmer V Bernstam, Reuben Joseph Applegate, Alvin Yu, Deepa Chaudhari, Tian Liu, Alex Coda, and Jonah Leshin. 2022.  Real-world matching performance of deidentified record-linking tokens.  _Applied Clinical Informatics_ 13, 04 (2022), 865–873.
  * Bonomi et al. (2012) Luca Bonomi, Li Xiong, Rui Chen, and Benjamin CM Fung. 2012.  Frequent grams based embedding for privacy preserving record linkage. In _Proceedings of the 21st ACM international conference on Information and knowledge management_. 1597–1601.
  * Chen et al. (2017) Hao Chen, Kim Laine, and Peter Rindal. 2017.  Fast Private Set Intersection from Homomorphic Encryption. In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ (Dallas, Texas, USA) _(CCS ’17)_. Association for Computing Machinery, New York, NY, USA, 1243–1255.  https://doi.org/10.1145/3133956.3134061
  * Cheon et al. (2019) Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun Hee Lee, and Keewoo Lee. 2019.  Numerical Method for Comparison on Homomorphically Encrypted Numbers. In _Advances in Cryptology – ASIACRYPT 2019_ , Steven D. Galbraith and Shiho Moriai (Eds.). Springer International Publishing, Cham, 415–445.
  * Dean and Ghemawat (2008) Jeffrey Dean and Sanjay Ghemawat. 2008.  MapReduce: simplified data processing on large clusters.  _Commun. ACM_ 51, 1 (2008), 107–113.
  * Dusserre et al. (1995) L Dusserre, C Quantin, and H Bouzelat. 1995.  A one way public key cryptosystem for the linkage of nominal files in epidemiological studies.  _Medinfo. MEDINFO_ 8 (1995), 644–647.
  * Efthymiou et al. (2017) Vasilis Efthymiou, George Papadakis, George Papastefanatos, Kostas Stefanidis, and Themis Palpanas. 2017.  Parallel meta-blocking for scaling entity resolution over big heterogeneous data.  _Information Systems_ 65 (2017), 137–157.
  * Fontaine and Galand (2007) Caroline Fontaine and Fabien Galand. 2007.  A survey of homomorphic encryption for nonspecialists.  _EURASIP Journal on Information Security_ 2007 (2007), 1–10.
  * Ghai et al. (2023) Tanmay Ghai, Yixiang Yao, and Srivatsan Ravi. 2023.  Lessons Learned: Building a Privacy-Preserving Entity Resolution Adaptation of PPJoin using End-to-End Homomorphic Encryption. In _2023 IEEE European Symposium on Security and Privacy Workshops (EuroS &PW)_. IEEE, 117–124.
  * Gkoulalas-Divanis et al. (2021) Aris Gkoulalas-Divanis, Dinusha Vatsalan, Dimitrios Karapiperis, and Murat Kantarcioglu. 2021.  Modern privacy-preserving record linkage techniques: An overview.  _IEEE Transactions on Information Forensics and Security_ 16 (2021), 4966–4987.
  * Goldwasser and Micali (1984) Shafi Goldwasser and Silvio Micali. 1984.  Probabilistic encryption.  _J. Comput. System Sci._ 28, 2 (1984), 270–299.  https://doi.org/10.1016/0022-0000(84)90070-9
  * Jung Hee Cheon (2017) Yongsoo Song Jung Hee Cheon, Andrey Kim & Miran Kim. 2017.  Homomorphic Encryption for Arithmetic of Approximate Numbers.  (2017).  https://link.springer.com/chapter/10.1007%2F978-3-319-70694-8_15
  * Kiernan et al. (2022) Daniel Kiernan, Thomas Carton, Sengwee Toh, Jasmin Phua, Maryan Zirkle, Darcy Louzao, Kevin Haynes, Mark Weiner, Francisco Angulo, Charles Bailey, et al. 2022\.  Establishing a framework for privacy-preserving record linkage among electronic health record and administrative claims databases within PCORnet®, the National Patient-Centered Clinical Research Network.  _BMC Research Notes_ 15, 1 (2022), 337.
  * Li et al. (2021) Bing Li, Yukai Miao, Yaoshu Wang, Yifang Sun, and Wei Wang. 2021.  Improving the efficiency and effectiveness for bert-based entity resolution. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 13226–13233.
  * Lindell (2005) Yehida Lindell. 2005.  Secure multiparty computation for privacy preserving data mining.  In _Encyclopedia of Data Warehousing and Mining_. IGI global, 1005–1009.
  * Niedermeyer et al. (2014) Frank Niedermeyer, Simone Steinmetzer, Martin Kroll, and Rainer Schnell. 2014.  Cryptanalysis of basic bloom filters used for privacy preserving record linkage.  _German Record Linkage Center, Working Paper Series, No. WP-GRLC-2014-04_ (2014).
  * Papadakis et al. (2020) George Papadakis, Dimitrios Skoutas, Emmanouil Thanos, and Themis Palpanas. 2020.  Blocking and filtering techniques for entity resolution: A survey.  _ACM Computing Surveys (CSUR)_ 53, 2 (2020), 1–42.
  * Penard and van Werkhoven (2008) Wouter Penard and Tim van Werkhoven. 2008.  On the secure hash algorithm family.  _Cryptography in context_ (2008), 1–18.
  * Quantin et al. (1998) Catherine Quantin, Hocine Bouzelat, FAA Allaert, Anne-Marie Benhamiche, Jean Faivre, and Liliane Dusserre. 1998.  How to ensure data security of an epidemiological follow-up: quality assessment of an anonymous record linkage procedure.  _International journal of medical informatics_ 49, 1 (1998), 117–122.
  * Rijmen and Daemen (2001) Vincent Rijmen and Joan Daemen. 2001.  Advanced encryption standard.  _Proceedings of federal information processing standards publications, national institute of standards and technology_ 19 (2001), 22.
  * Sako (2011) Kazue Sako. 2011.  Semantic Security.
  * Scannapieco et al. (2007) Monica Scannapieco, Ilya Figotin, Elisa Bertino, and Ahmed K Elmagarmid. 2007.  Privacy preserving schema and data matching. In _Proceedings of the 2007 ACM SIGMOD international conference on Management of data_. 653–664.
  * Schnell et al. (2009) Rainer Schnell, Tobias Bachteler, and Jörg Reiher. 2009.  Privacy-preserving record linkage using Bloom filters.  _BMC medical informatics and decision making_ 9, 1 (2009), 1–11.
  * Song and Raghunathan (2020) Congzheng Song and Ananth Raghunathan. 2020.  Information leakage in embedding models. In _Proceedings of the 2020 ACM SIGSAC conference on computer and communications security_. 377–390.
  * Vatsalan et al. (2013) Dinusha Vatsalan, Peter Christen, and Vassilios S Verykios. 2013.  A taxonomy of privacy-preserving record linkage techniques.  _Information Systems_ 38, 6 (2013), 946–969.
  * Vatsalan et al. (2017) Dinusha Vatsalan, Ziad Sehili, Peter Christen, and Erhard Rahm. 2017.  Privacy-preserving record linkage for big data: Current approaches and research challenges.  In _Handbook of Big Data Technologies_. Springer, 851–895.
  * Wang et al. (2015) Xiao Shaun Wang, Yan Huang, Yongan Zhao, Haixu Tang, XiaoFeng Wang, and Diyue Bu. 2015.  Efficient genome-wide, privacy-preserving similar patient query based on private edit distance. In _Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security_. 492–503.
  * Yao et al. (2021) Yixiang Yao, Tanmay Ghai, Srivatsan Ravi, and Pedro Szekely. 2021.  Amppere: A universal abstract machine for privacy-preserving entity resolution evaluation. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. 2394–2403.
  * Zhu and Huang (2017) Ruiyu Zhu and Yan Huang. 2017.  Efficient privacy-preserving general edit distance and beyond.  _IACR Cryptology ePrint Archive_ 2017 (2017), 683.