# Distance-Aware Private Set Intersection

Anrin Chakraborti
Duke University  Giulia Fanti
Carnegie Mellon University  Michael K. Reiter
Duke University

###### Abstract

Private set intersection (PSI) allows two mutually untrusting parties to
compute an intersection of their sets, without revealing information about
items that are not in the intersection. This work introduces a PSI variant
called distance-aware PSI (DA-PSI) for sets whose elements lie in a metric
space. DA-PSI returns pairs of items that are within a specified distance
threshold of each other. This paper puts forward DA-PSI constructions for two
metric spaces: (i) Minkowski distance of order 1 over the set of integers
(i.e., for integers $a$ and $b$, their distance is $|a-b|$); and (ii) Hamming
distance over the set of binary strings of length $\ell$. In the Minkowski DA-
PSI protocol, the communication complexity scales logarithmically in the
distance threshold and linearly in the set size. In the Hamming DA-PSI
protocol, the communication volume scales quadratically in the distance
threshold and is independent of the dimensionality of string length $\ell$.
Experimental results with real applications confirm that DA-PSI provides more
effective matching at lower cost than naïve solutions.

##  1 Introduction

Private set intersection (PSI) is a widely-used multiparty cryptographic
protocol, with applications across domains including contact discovery and
tracing, private profile matching, privacy-preserving genomics, and
collaborative learning. PSI protocols are used to compute the intersection (or
common elements) of two or more sets held by mutually-untrusting parties.
Critically, the parties learn no information about the elements that are _not_
in the set intersection.

There is a long line of work on communication-efficient PSI protocols, with
variants including different adversarial models [16, 12, 29], threshold
parameters [10, 1] and compute capabilities [15]. However, these solutions are
designed to return only _exact_ matches. That is, an element appears in the
intersection if and only if it matches (exactly) an element in each of the
other parties’ sets.

When exact matches may be rare, parties may want to privately compute
_approximate_ matches. For instance, given sets of points in Euclidean space,
the intersection may contain all pairs within a certain Euclidean distance of
each other. This notion has applications in domains where replacing an exact-
matched set intersection with a distance-based intersection yields more
effective systems:

  * •

Private collaborative blacklisting enables mutually-untrusting parties to
identify malicious network traffic and coordinated attacks. Typically, an
intersection is computed privately over sets containing network identifiers,
e.g., source IPs observed [22]. However, botnets usually span multiple (often
contiguous) subnets [38, 4], and it is useful to compare ranges of IP
addresses and detect overlaps.

  * •

Biometric identification systems leverage Hamming distance/edit distance [36,
24, 6] and need to account for inexact/fuzzy matches due variations in
sampling technologies. Fuzzy PSI functionalities have been used before in
privacy-preserving biometric identification systems [32].

  * •

Credential stuffing identification systems use PSI-like functionalities to
detect password reuse across websites without revealing sensitive user
information [34, 35]. These protocols consider exact password matches.
However, it is useful to expand this idea for inexact/similar password
matches, e.g., edit distance matches.

Distance-Aware Private Set Intersection (DA-PSI): In this paper we initiate
the study of distance-aware private set intersection (DA-PSI). A DA-PSI
protocol defined over a metric space allows two parties to compute an
intersection of their respective sets containing all pairs of items that are
within a predefined threshold distance in the metric space. Specifically,
consider a metric space $(\mathcal{U},\delta)$ with metric $\delta$. Let the
parties hold sets, $A$ and $B$ with $n$ items each, where each item is a
length-$\mathcal{\ell}$ vector drawn from the space. The problem definition
specifies a distance threshold $d$ and requires the protocol to return
$S\subseteq A\times B$ where $(\vec{a},\vec{b})\in
S\Leftrightarrow\delta(\vec{a},\vec{b})\leq d$. A party learns no information
about items in the counterparty’s set that are not close to (within threshold
of) one of its own elements.

Traditional PSI tools are not optimized for DA-PSI. A naïve application will
need to check for all $\vec{a}\in A$ and for all $\vec{b}\in\mathcal{U}$ such
that $\delta(\vec{a},\vec{b})\leq d$ if $\vec{b}\in B$. This is problematic
since in many cases the search space is exponentially large. For example,
Hamming distance with a distance threshold $d$ will require searching over the
Hamming ball of radius $d$ around each $\vec{a}\in A$. There are over
$\binom{\mathcal{\ell}}{d}=\Omega((\frac{\mathcal{\ell}}{d})^{d})$ vectors
around $\vec{a}$ in this Hamming ball. Thus, the communication cost of this
protocol scales exponentially with the threshold and is impractical. This work
poses the following question: Can we design DA-PSI protocols where
communication and compute costs scale polynomially in the distance threshold?

We answer this question affirmatively by putting forward constructions for two
important metric spaces: i) Hamming distance over the set $\\{0,1\\}^{\ell}$
for some fixed $\ell\in\mathbb{Z}^{+}$, and ii) Minkowski distance of order 1
over the set of integers (i.e., for integers $a$ and $b$, their distance is
$|a-b|$). In the following, we discuss the intuitions behind these protocols.

Hamming Distance-Aware PSI: Hamming distance is a good starting point since
several other distances can be computed or approximated by Hamming distance
[30, 5, 11]. We provide a construction building on the idea of sub-sampling
each of a user’s input vectors and mapping it to a unique set of sub-vectors
such that the cardinality of the set difference between the sets corresponding
to two vectors is exactly equal to the Hamming distance between the original
vectors.

Our construction leverages additively homomorphic encryption and vector
oblivious linear evaluation (VOLE). A key building block in the protocol is a
novel sub-sampling mechanism which trades off accuracy (by allowing some
false-positives) for better communication complexity: the communication cost
scales polynomially in the distance threshold $d$ and is independent of the
vector length $\mathcal{\ell}$. Typically, for applications relying on Hamming
distance comparisons, $d\ll\mathcal{\ell}$ [25, 20], and thus the reduced set
sizes after sub-sampling concretely improves communication costs over existing
work [13, 25] . To compute the set differences, we propose a modified (and
significantly simpler) version of the private set reconciliation protocol due
to Ghosh and Simkin [10].

Integer distance-Aware PSI: We propose a DA-PSI protocol for Minkowski
distance of first order over integers, loosely termed as the integer distance-
aware PSI protocol. The communication cost scales linearly in the set size and
logarithmically in the distance threshold; this is optimal with regards to the
set sizes since linear communication is both necessary and sufficient for
exact PSI [17, 10]. The key observation behind the protocol is that integers
in a range $(a-d,a+d)$, where $d$ is a specified distance threshold, can be
succinctly represented by a collection of bit-strings corresponding to their
binary representations. The total number of strings required is sublinear in
$d$ since multiple integers within a sequence will share prefixes, and the
same common prefix will represent multiple consecutive integers. We design an
algorithm to augment the inputs sets with
$\operatorname{O}\mathopen{}\left(\log d\right)\mathclose{}$ strings
representing all integers in $(a-d,a+d)$. This mechanism is agnostic to the
underlying cryptographic tools since any state-of-the-art PSI protocol can be
augmented to provide an integer DA-PSI protocol.

Evaluation: We have implemented both protocols and benchmarked them on a
public cloud. As an application of the integer distance-aware PSI, we have
deployed it for collaborative blacklisting of IPs seen by real-world
honeypots; for our parameter settings, the distance-aware PSI almost doubles
the number of identified malicious IPs. For computing this intersection over
sets containing roughly 25K IP addresses collected across all the honeypots,
our protocol only requires 64 MB of communication and 1.5 seconds.

We have implemented our Hamming DA-PSI constructions. Micro-benchmarks show
that it imposes $2$-$400\times$ less communication than a generic garbled-
circuit solution for distance thresholds up to $30$. As an application, we
have evaluated our protocol for the task of privately comparing vectors
derived from iris images, and for a distance threshold sufficient to retrieve
all of the matches in our dataset, it achieves $2.5\times$ lower communication
volume (with a false positive rate $\leq 10\%$ and no false negatives) than a
generic secure 2PC baseline. When compared with the state-of-the-art Hamming
containment query protocol by Uzun et al. [32], our protocol features
$33$-$63\%$ less communication and $33\%$ less computation.

##  2 Related Work

Hamming DA-PSI
---
| Comm | Computation | Dep | fpr, fnr
| Alice | Bob | Offline
naïve | $\operatorname{O}\mathopen{}\left(n\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n\binom{\mathcal{\ell}}{d}\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(1\right)\mathclose{}$ | – | – , –
Osadchy et al. [25] | $\operatorname{O}\mathopen{}\left(n^{2}\mathcal{\ell}\lambda\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n^{2}\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n^{2}\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(1\right)\mathclose{}$ | ahe | – , –
Huang et al. [14] | $\operatorname{O}\mathopen{}\left(n^{2}\mathcal{\ell}\lambda\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n^{2}\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n^{2}\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(1\right)\mathclose{}$ | ot | – , –
Uzun et al. [32] | $\operatorname{O}\mathopen{}\left(\frac{n^{2}T}{mB}\lambda\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(\\!\binom{T}{t}\\!\left(\frac{nma}{T}\right)\\!\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(\frac{n^{2}T}{m}\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(\frac{n^{3}T^{2}}{ma}\right)\mathclose{}$ | fhe | $0\\!\\!<\\!\\!\textsc{fpr}\\!\\!<\\!\\!1$
$0\\!\\!<\\!\\!\textsc{fnr}\\!\\!<\\!\\!1$
$\mathsf{HamPSI}$ (Sec. 4) | $\operatorname{O}\mathopen{}\left(n^{2}d^{2}\lambda\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n^{2}\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n^{2}\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(1\right)\mathclose{}$ | ahe | $0\\!\\!<\\!\\!\textsc{fpr}\\!\\!<\\!\\!1$
ole | –
Integer DA-PSI
naïve | $\operatorname{O}\mathopen{}\left(n\lambda d\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(1\right)\mathclose{}$ | – | – , –
$\mathsf{IntPSI}$ (Sec. 5) | $\operatorname{O}\mathopen{}\left(n\lambda\log{d}\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(n\right)\mathclose{}$ | $\operatorname{O}\mathopen{}\left(1\right)\mathclose{}$ | – | – , –
Table 1: Asymptotic performance for our protocols in comparison to existing
work. $n$: set size; $d$: distance threshold; $\mathcal{\ell}$: length of
vectors; $T,t$: subsampling parameters,
$T=\operatorname{O}\mathopen{}\left(\mathcal{\ell}\right)\mathclose{}$;
$m,a,B$: FHE parameters, $m\gg T$. $\textsc{fpr},\textsc{fnr}\in(0,1)$ are the
false-positive and false-negative rates of the schemes; "–" indicates that the
false positive or negative rate is negligible in $\lambda$. The schemes
without dependencies are agnostic to the underlying primitives. The comm. cost
of all existing Hamming DA-PSI protocol depends on the length of the vectors
$\mathcal{\ell}$. The comm. cost of $\mathsf{HamPSI}$ is independent of
$\mathcal{\ell}$.

Private set intersection is well-studied (e.g., [9, 18, 3, 26, 27, 21, 7,
28]). We refer to these for details on general PSI and focus on other
distance-aware/fuzzy PSI primitives here.

Private Hamming Distance Computation: Table 1 compares our Hamming DA-PSI
constructions with existing work on privately computing Hamming distance.
Osadchy et al. [25] built a protocol using additively homomorphic encryption
which enables a party to check when her vector is within a threshold Hamming
distance of any of the vectors in a set held by the other party. A similar
functionality is implemented by Huang et al. [13] using garbled circuits. For
both protocols, the communication cost scales linearly in the vector sizes. In
contrast, the cost of our Hamming distance aware protocol scales sublinearly
in the vector size.

Uzun et al. [32] propose a protocol for Hamming distance comparisons over
vectors derived from biometric identifiers. The protocol reduces the input
vectors to sets of sub-vectors after a sub-sampling process. The sub-sampling
protocol ensures that when two vectors are close, their corresponding sets
have a certain number of matching elements. With these sets as inputs, the
protocol implements a $t$-out-of-$T$ matching protocol using fully homomorphic
encryption (FHE), and leverages the ability of the FHE scheme to pack multiple
ciphertexts using SIMD-style operations. In contrast, our constructions are
based on computationally less-expensive primitives, namely additively
homomorphic encryption (AHE) and oblivious linear evaluations (OLE).

##  3 Security Definitions & Background

Notation: ${\mathbb{F}_{p}}$ is a finite of field of prime order where $p$ is
a
$\operatorname{O}\mathopen{}\left(\mathbf{poly}(\lambda)\right)\mathclose{}$-bit
prime, and $\lambda$ is a security parameter.
$\mathbf{negl}\mathopen{}\left(\cdot\right)\mathclose{}$ is a function that is
negligible in the input parameter; e.g.,
$\mathbf{negl}\mathopen{}\left(\lambda\right)\mathclose{}$ =
$\operatorname{O}\mathopen{}\left(2^{-\lambda}\right)\mathclose{}$.
$P(x)\in{\mathbb{F}_{p}}[x]$ is a polynomial with coefficients drawn from
${\mathbb{F}_{p}}$. The degree of polynomial $P(x)$ is represented by
$\mathbf{deg}\mathopen{}\left(P(x)\right)\mathclose{}$. The greatest common
divisor of two (or more) polynomials is represented by
$\mathbf{gcd}\mathopen{}\left(P(x),Q(x)\right)\mathclose{}$. For polynomials
$P(x)$ and $Q(x)$,
$P_{{\scriptscriptstyle/q}}(x):=\frac{P(x)}{\mathbf{gcd}\mathopen{}\left(P(x),Q(x)\right)\mathclose{}}$.

Rational Function: A rational function $r=\frac{P(x)}{Q(x)}$ has degree at
most equal to the degree of the numerator + degree of the denominator. Let
$V=\\{(x_{k},y_{k})\\}_{k=1}^{2t}$ be a set of points in ${\mathbb{F}_{p}}$.
Then there exists a rational function with numerator and denominator in
${\mathbb{F}_{p}}[x]$ interpolating these points [19].

Parties: We assume that two semi-honest (a.k.a. honest-but-curious) mutually
untrusting parties Alice and Bob run the protocols. The parties may learn
information from the intermediate results but do not deviate from the
protocol.

Distance-Aware Private Set Intersection: In this work, we are concerned with
distance-aware private set intersection protocols, which we define here.
Parties Alice and Bob are assumed to each store a set
$A=\\{a_{1},\ldots,a_{n}\\}$ and $B=\\{b_{1},\ldots,b_{n}\\}$, respectively,
where the $a_{i}$’s and $b_{i}$’s are drawn from some universe $\mathcal{U}$,
and $\delta:\mathcal{U}\times\mathcal{U}\to\mathbb{R}$ denotes a distance
metric defined over $\mathcal{U}$. A distance-aware PSI protocol over metric
space $(\mathcal{U},\delta)$ with threshold $d$ and input sets $A$, $B$
returns a set $S\subseteq A\times B$ such that $S\triangleq\\{(a,b)~{}:~{}a\in
A,~{}b\in B,~{}\delta(a,b)\leq d\\}$. We require this protocol to satisfy:

  1. (1)

Correctness: For any $(a,b)\in A\times B$,

     * •

If $\delta(a,b)\leq d$, then $(a,b)\in S$ with probability $\geq\textsc{tpr}$.

     * •

If $\delta(a,b)>d$, then $(a,b)\not\in S$ with probability $\geq\textsc{tnr}$.

  2. (2)

Security: Alice learns only $S$ and the cardinality of $B$, and Bob learns
only $S$ and the cardinality of $A$.

This definition allows for arbitrary false-positive and false-negative rates
(i.e., $\textsc{fpr}=1-\textsc{tnr}$ and $\textsc{fnr}=1-\textsc{tpr}$,
respectively). This allows faster protocols (see Sec. 4) and accommodates
protocols approximating one distance metric via another, e.g., with locality-
sensitive hashing.

###  3.1 Background

$\mathcal{F}^{p}_{\mathit{ole}}$: Ideal Functionality for Oblivious Linear
Evaluation (OLE): Parameters:  Parties Alice and Bob, and finite field
${\mathbb{F}_{p}}$ from which inputs are drawn. Inputs:  Alice has input
$x\in\mathbb{F}$ and Bob has as input a pair $(u,v)\in{\mathbb{F}_{p}}$.
Output:  Alice learns $z=ux+v$. Bob learns $\bot$.
$\mathcal{F}^{p}_{\mathit{vole}}$: Ideal Functionality for Vector OLE (VOLE):
Parameters:  Parties Alice and Bob, and finite field ${\mathbb{F}_{p}}$ from
which inputs are drawn. Inputs:  Alice has input $x\in\mathbb{F}$ and Bob has
as input a pair of vectors
$(\vec{u},\vec{v})\in{\mathbb{F}_{p}^{\mathcal{\ell}}}\times{\mathbb{F}_{p}^{\mathcal{\ell}}}$.
Output:  Alice learns $\vec{z}=\vec{u}x+\vec{v}$. Bob learns $\bot$. Figure 1:
Ideal functionalities for oblivious linear evaluation (OLE), and vector
oblivious linear evaluation (VOLE)

Oblivious Linear Evaluation (OLE) is a two-party cryptographic primitive
wherein Alice inputs $x\in{\mathbb{F}_{p}}$; Bob inputs
$u,v\in{\mathbb{F}_{p}}$; and Alice obtains $ux+v$ without learning $u$ and
$v$.

Vector Oblivious Linear Evaluation (VOLE) is an extension of the OLE
functionality, where Bob’s input is a pair of vectors, and Alice learns a
linear combination of the vectors. Fig. 1 describes the VOLE functionality.
The state-of-the-art VOLE protocol [37] is based on the learning parity with
noise (LPN) assumption. The communication complexity of the protocol is linear
in the vector length $\mathcal{\ell}$. Further technical details can be found
in [37].

Threshold Set Intersection (a.k.a., $t$-out-$T$ matching) is a variant of the
PSI problem where the intersection of two (or more) sets is revealed to the
parties iff the number of items in the intersection are above a certain
predefined threshold. More formally, given two sets $A$ and $B$ of size $n$,
and a threshold $t$, the protocol outputs $S$ such that $S\triangleq A\cap B$
iff $|A\cap B|\geq n-t$. Otherwise, the protocol outputs $\bot$.

The state-of-the-art threshold PSI protocol (henceforth referred to a
$t\mathsf{PSI}$) is due to Ghosh and Simkin [10]. The main observation
underlying the protocol is that given $A\setminus B$, the party holding $A$
can obtain $A\cap B=A\setminus(A\setminus B)$. Thus, it suffices to build a
threshold set reconciliation protocol where $A\setminus B$ (respectively,
$B\setminus A$) is revealed to the parties iff $|A\setminus B|\leq t$. The
protocol is inspired in part by the set reconciliation protocol due to Minsky
et al. [23]. The idea behind this protocol is as follows: Alice and Bob encode
the items of their corresponding sets, $A$ and $B$ in roots of polynomials
$P(x)$ and $Q(x)$, respectively. If $\left|{A\setminus B}\right|\leq t$, then
$\mathbf{deg}\mathopen{}\left(\mathbf{gcd}\mathopen{}\left(P(x),Q(x)\right)\mathclose{}\right)\mathclose{}\geq
n-t$, and so $r(x)=\frac{P(x)}{Q(x)}$ is a rational function of degree at most
$2t$ (after cancellation of common roots in the numerator and denominator).
$r(x)$ can be uniquely interpolated with $2t+1$ evaluation points. The
denominator of $r(x)$ gives $A\setminus B$.

$t\mathsf{PSI}$ builds on this idea and tweaks the protocol to ensure that the
elements in $B\setminus A$ are never revealed to Alice. Alice and Bob evaluate
a polynomial $R_{1}(x)P(x)+R_{2}(x)Q(x)$ at $3t+1$ points, where $R_{1}(x)$ is
a degree-$t$ random polynomial contributed by Bob and $R_{2}(x)$ is a random
degree-$t$ polynomial contributed by Bob. Alice (and Bob) then compute the
values of the rational function $r(x)=\frac{R_{1}(x)P(x)+R_{2}(x)Q(x)}{P(x)}$
at the aforementioned $3t+1$ points. Clearly, if $|A\setminus B|\leq t$, then
$r(x)$ has a numerator of degree $\leq 2t$ and a denominator of degree $\leq
t$ after cancellation of the common roots in
$\mathbf{gcd}\mathopen{}\left(P(x),Q(x)\right)\mathclose{}$ and $P(x)$. Since
$r(x)$ is a rational functions of degree $\leq 3t$, it can be uniquely
interpolated with the $3t+1$ evaluation points.

The security of the scheme relies on showing that the numerator of $r(x)$
after cancellation is a uniformly random polynomial. Specifically, let
$R_{1}(x)P_{{\scriptscriptstyle/q}}(x)+R_{2}(x)Q_{{\scriptscriptstyle/p}}(x)$
be the numerator after canceling common roots in $r$. The following well-known
result due to Kissner and Song [18] shows that this polynomial is uniformly
random.

######  Lemma 1 ([18]).

Given two polynomials $P(x),Q(x)\in{\mathbb{F}_{p}}[x]$ with
$\mathbf{deg}\mathopen{}\left(P(x)\right)\mathclose{}=\mathbf{deg}\mathopen{}\left(Q(x)\right)\mathclose{}\leq
D_{p}$ such that $\mathbf{gcd}\mathopen{}\left(P(x),Q(x)\right)\mathclose{}$ =
1, and two uniformly random polynomials, $R_{1}(x)$, $R_{2}(x)$ of degree
$D_{r}\geq D_{p}$, the polynomial $R_{1}(x)P(x)+R_{2}(x)Q(x)$ is a uniformly
random polynomial of degree $\leq D_{r}+D_{p}$.

##  4 Protocol for Hamming Distances

We start with a protocol for privately computing a Hamming distance-aware set
intersection between sets where elements are drawn from the universe
$\mathcal{U}=\\{0,1\\}^{\mathcal{\ell}}$. Fig. 2 defines the ideal
functionality $\mathcal{F}_{\ell,d_{\mathsf{H}}}^{h{\text{-}}\mathit{PSI}}$
for Hamming DA-PSI between two parties with tunable true positive and true
negative rates. We propose a protocol with
$\operatorname{O}\mathopen{}\left(n^{2}\cdot\frac{d_{\mathsf{H}}^{2}}{\textsc{fpr}}\cdot\lambda\right)\mathclose{}$
communication cost for set sizes $n$ (i.e., the cost is independent of the
vector length), and compute time that scales polynomially in $d_{\mathsf{H}}$.

Remark on Ideal Functionality: We have defined
$\mathcal{F}_{\ell,d_{\mathsf{H}}}^{h{\text{-}}\mathit{PSI}}$ such that for
each $(\vec{a},\vec{b})\in A\times B$, both parties learn $(\vec{a},\vec{b})$
iff $\delta_{H}(\vec{a},\vec{b})\leq d_{\mathsf{H}}$. Another definition
considering is where Alice only learns if there is a $\vec{b}\in B$ such that
$\delta_{H}(\vec{a},\vec{b})\leq d_{\mathsf{H}}$ but not $\vec{b}$ itself.
However, this definition may not be meaningful in the context of distance
aware applications. For instance, there are
$\binom{\mathcal{\ell}}{d_{\mathsf{H}}}$ elements that are within Hamming
distance $d_{\mathsf{H}}$ of an element $\vec{a}\in A$; it is not
straightforward for Alice to guess $\vec{b}$ simply from the fact that
$\delta_{H}(\vec{a},\vec{b})\leq d_{\mathsf{H}}$ . This is unlike traditional
PSI, where Alice can trivially guess Bob’s element knowing that there is a
match. Nonetheless, both our Hamming DA-PSI protocol have an additional
$\mathsf{Recover}$ step where Alice obtains $\vec{b}$ from Bob after learning
some intermediate results which indicates $\delta_{H}(\vec{a},\vec{b})\leq
d_{\mathsf{H}}$. The protocol may be aborted at this stage (to save one extra
round of communication) to realize an ideal functionality which only enables
Alice to learn if $\delta_{H}(\vec{a},\vec{b})\leq d_{\mathsf{H}}$ without
directly revealing $\vec{b}$.

$\mathcal{F}_{\ell,d_{\mathsf{H}}}^{h{\text{-}}\mathit{PSI}}$: Ideal
Functionality for Hamming Aware DA-PSI: Parameters:  Parties Alice and Bob.
Universe $\mathcal{U}=\\{0,1\\}^{\mathcal{\ell}}$. Hamming distance threshold
$d_{\mathsf{H}}$. True positive rate tpr and true negative rate tnr. Inputs:
Alice has input $A=\\{\vec{a_{i}}\\}_{i=1}^{n}\subseteq\mathcal{U}$. Bob has
input $B=\\{\vec{b_{j}}\\}_{j=1}^{n}\subseteq\mathcal{U}$. Output:  Alice and
Bob learn $S\subseteq A\times B$ where for each $(\vec{a},\vec{b})\in A\times
B$, if $\delta_{H}(\vec{a},\vec{b})\leq d_{\mathsf{H}}$ then
$\mathbb{P}\left[(\vec{a},\vec{b})\in S\right]\geq\textsc{tpr}$ and if
$\delta_{H}(\vec{a},\vec{b})>d_{\mathsf{H}}$ then
$\mathbb{P}\left[(\vec{a},\vec{b})\not\in S\right]\geq\textsc{tnr}$.
$\mathcal{F}_{\mathcal{\ell},d_{\mathsf{H}}}^{t{\text{-}}\mathit{HQ}}$: Ideal
Functionality for Threshold Hamming Query: Parameters:  Parties Alice and Bob.
Universe $\mathcal{U}=\\{0,1\\}^{\mathcal{\ell}}$. Hamming distance thresholds
$d_{\mathsf{H}}$, true positive rate tpr, and true negative rate tnr. Inputs:
Alice has vector $\vec{a}\in\mathcal{U}$ and Bob has vector
$\vec{b}\in\mathcal{U}$. Output:  If $\delta_{H}(\vec{a},\vec{b})\leq
d_{\mathsf{H}}$, then Alice and Bob learn $(\vec{a},\vec{b})$ with probability
$\geq\textsc{tpr}$. If $\delta_{H}(\vec{a},\vec{b})>d_{\mathsf{H}}$, then
Alice and Bob learn $\bot$ with probability $\geq\textsc{tnr}$. Figure 2:
Ideal functionalities for Hamming distance-aware PSI and threshold Hamming
queries

###  4.1 Threshold Hamming Query

The key building block of our construction is a protocol to privately
determine if two bit vectors are within a certain Hamming distance of each
other. We call this primitive a threshold Hamming query. Fig. 2 defines the
ideal functionality
$\mathcal{F}_{\mathcal{\ell},d_{\mathsf{H}}}^{t{\text{-}}\mathit{HQ}}$ for
$\mathcal{\ell}$-bit vectors and Hamming distance threshold $d_{\mathsf{H}}$.

Parameters: Alice and Bob have vectors
$\vec{a},\vec{b}\in\\{0,1\\}^{\mathcal{\ell}}$, respectively, and a Hamming
distance threshold $d_{\mathsf{H}}\in[0,\mathcal{\ell}/2)$. Procedure
$\mathsf{Map}$: Alice and Bob sample $\mathcal{\ell}$ injective mapping
functions $M_{1},\ldots M_{\mathcal{\ell}}$,
$M_{m}:\\{0,1\\}\rightarrow{\mathbb{F}_{p}},~{}m\in[1,\mathcal{\ell}]$. Alice
computes set $S_{\vec{a}}:=\\{s_{m}:s_{m}:=M_{m}(\vec{a}[m])\\}$ and Bob
computes $S_{\vec{b}}:=\\{s_{m}:s_{m}:=M_{m}(\vec{b}[m])\\}$. Procedure
$\mathsf{OneSidedSetRecon}$: (1) Alice and Bob select a set of
$\mathcal{\ell}+d_{\mathsf{H}}+2$ points in ${\mathbb{F}_{p}}$
$X:=\\{x_{k}\\}_{k=1}^{\mathcal{\ell}+2d_{\mathsf{H}}+1}$ such that none of
the points are in the ranges of any of the mapping functions. (2) Alice
encodes $S_{\vec{a}}$ in the polynomial $P(x)$ = $\prod\limits_{r\in
S_{\vec{a}}}(x-r)$ and Bob encodes $S_{\vec{b}}$ in the polynomial $Q(x)$ =
$\prod\limits_{r\in S_{\vec{b}}}(x-r)$. (3) Bob samples two
degree-$\mathcal{\ell}$ random polynomials
$R_{1}(x),R_{2}(x)\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}[x]$.
(4) For each $x_{k}\in X$, Alice sends $P(x_{k})$ and Bob sends $R_{1}(x_{k})$
and $R_{2}(x_{k})\times Q(x_{k})$ to $\mathcal{F}^{p}_{\mathit{ole}}$. Alice
learns $W_{A}(x_{k})$ $:=$ $R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})$ as the
output of $\mathcal{F}^{p}_{\mathit{ole}}$. (5) For
$k\in[1,\mathcal{\ell}+2d_{\mathsf{H}}+1]$, Alice computes the set of points
$V:=\\{(x_{k},y_{k}):y_{k}:=\frac{W_{A}(x_{k})}{P(x_{k})}=\frac{R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})}{P(x_{k})}\\}$.
(6) Alice interpolates $V$ with a rational function
$r(x):=\frac{\mathsf{Num}(x)}{\mathsf{Den}(x)}$ and checks that
$\mathsf{Den}(x)$ is a factor of $P(x)$. If so, Alice outputs
$S_{\vec{a}}\setminus S_{\vec{b}}$ which contains the roots of
$\mathsf{Den}(x)$, otherwise Alice outputs $\bot$. Procedure
$\mathsf{Recover}$: If Alice receives $\bot$ from $\mathsf{OneSidedSetRecon}$
then output $\bot$. Otherwise, upon receiving $S_{\vec{a}}\setminus
S_{\vec{b}}$: for each $s\in S_{\vec{a}}\cap
S_{\vec{b}}=S_{\vec{a}}\setminus(S_{\vec{a}}\setminus S_{\vec{b}})$, if
$s=M_{m}(\vec{a}[m])$ then $\vec{b}[m]=\vec{a}[m]$. For all indices
$m^{\prime}\in[1,\mathcal{\ell}]$ that are left undetermined from
$S_{\vec{a}}\setminus S_{\vec{b}}$,
$\vec{b}[m^{\prime}]=1-(\vec{a}[m^{\prime}])$. Output ($\vec{a}$, $\vec{b}$).
Figure 3: $t\mathsf{HamQueryLite}$: A first pass Hamming query protocol

####  4.1.1 $t\mathsf{HamQueryLite}$: Hamming Query First Pass

We start with a simple and insecure version of our threshold Hamming query
protocol dubbed $t\mathsf{HamQueryLite}$ (Fig. 3). The key observation is that
$\mathcal{F}_{\mathcal{\ell},d_{\mathsf{H}}}^{t{\text{-}}\mathit{HQ}}$ can be
realized as follows:

  1. (1)

Map: We use $\mathcal{\ell}$ deterministic, injective mapping functions
$M_{1},\ldots M_{\mathcal{\ell}}$ where
$M_{m}:\\{0,1\\}\rightarrow{\mathbb{F}_{p}},~{}m\in[1,\mathcal{\ell}]$, such
that the ranges of the functions do not overlap. These functions map the
individual bits in the vectors to elements of ${\mathbb{F}_{p}}$. The $m$th
bit of vector $\vec{a}$, denoted $\vec{a}[m]$, is mapped to element
$M_{m}(\vec{a}[m])$. $\vec{a}$ is then uniquely represented by
$S_{\vec{a}}=\\{M_{1}(\vec{a}[1]),\ldots,M_{\mathcal{\ell}}(\vec{a}[\mathcal{\ell}])\\}$.
Correspondingly, $\vec{b}$ is represented by
$S_{\vec{b}}=\\{M_{1}(\vec{b}[1]),\ldots,M_{\mathcal{\ell}}(\vec{b}[\mathcal{\ell}])\\}$.

  2. (2)

Threshold Set Reconciliation: A protocol with inputs $S_{\vec{a}}$ and
$S_{\vec{b}}$ allows Alice to learn $S_{\vec{a}}\setminus S_{\vec{b}}$ iff
$|S_{\vec{a}}\setminus S_{\vec{b}}|\leq d_{\mathsf{H}}$. Alice learns
$\vec{b}$ from $S_{\vec{a}}\setminus S_{\vec{b}}$ . E.g., let $\vec{a}$ =
$1001$, $\vec{b}$ = $1011$, $S_{\vec{a}}$ = $\\{M_{1}(1)$, $M_{2}(0)$,
$M_{3}(0)$, $M_{4}(1)\\}$ and $S_{\vec{b}}$ = $\\{M_{1}(1)$, $M_{2}(0)$,
$M_{3}(1)$, $M_{4}(1)\\}$. Then, $S_{\vec{a}}$ $\setminus$ $S_{\vec{b}}$ =
$\\{M_{3}(0)\\}$ and $\vec{b}[1]=\vec{a}[1]$, $\vec{b}[2]=\vec{a}[2]$,
$\vec{b}[4]=\vec{a}[4]$ and $\vec{b}[3]=1-\vec{a}[3]$.

The mapping functions have no bearing on the security of the protocol, as long
as the ranges do not overlap and the functions are injective. In our
implementations we have used PRFs, but we do not rely on their randomness
guarantees.

Threshold Set Reconciliation: In $t\mathsf{HamQueryLite}$, we use
$\mathsf{OneSidedSetRecon}$, a new private set reconciliation protocol which
is based on the $t\mathsf{PSI}$ protocol (see Sec. 3.1).
$\mathsf{OneSidedSetRecon}$ allows one of the parties to learn
$S_{\vec{a}}\setminus S_{\vec{b}}$ (say Alice) while the other party generates
all the random coins. Both parties begin by encoding the items in their
respective sets in the roots of polynomials $P(x)$ and $Q(x)$ respectively
(see line 2 of $\mathsf{OneSidedSetRecon}$ in Fig. 3). This is followed by the
parties jointly computing the evaluations of the polynomial
$R_{1}(x)P(x)+R_{2}(x)Q(x)$ at $\mathcal{\ell}+2d_{\mathsf{H}}+1$ points,
where $R_{1}(x)$ and $R_{2}(x)$ are random polynomials sampled by Bob. This is
achieved using $\mathcal{\ell}+2d_{\mathsf{H}}+1$ calls to
$\mathcal{F}^{p}_{\mathit{ole}}$ where Alice sends evaluations of $P(x)$ at
each of the points and Bob correspndingly sends evaluations of $R_{1}(x)$, and
$Q(x)R_{2}(x)$ (see Fig. 4). Finally, Alice interpolates the rational function
$\frac{R_{1}(x)P(x)+R_{2}(x)Q(x)}{P(x)}$ with the evaluations of
$R_{1}(x)P(x)+R_{2}(x)Q(x)$ similar to $t\mathsf{PSI}$ (line 6 of
$\mathsf{OneSidedSetRecon}$) and obtains $S_{\vec{a}}\setminus S_{\vec{b}}$
iff $|S_{\vec{a}}\setminus S_{\vec{b}}|\leq d_{\mathsf{H}}$.
$\mathsf{OneSidedSetRecon}$ is significantly simpler than $t\mathsf{PSI}$ and
has lower communication cost. This is because it requires only
$\mathcal{\ell}+2d_{\mathsf{H}}+1$ calls to $\mathcal{F}^{p}_{\mathit{ole}}$
compared to twice as many calls in $t\mathsf{PSI}$ while also avoiding two
extra rounds of communication. The improvement comes from the fact that in
contrast to $t\mathsf{PSI}$ where both parties learn the results,
$\mathsf{OneSidedSetRecon}$ enables only Alice to learn the final result (see
App. A for more details).

AliceBob$R_{1}(x),R_{2}(x)\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}[x]$$\mathcal{F}^{p}_{\mathit{ole}}$$R_{1}(x_{1})$$R_{2}(x_{1})Q(x_{1})$$R_{1}(x_{1})$$R_{1}(x_{1})P(x_{1})+R_{2}(x_{1})Q(x_{1})$……$\mathcal{F}^{p}_{\mathit{ole}}$$R_{1}(x_{k})$$R_{2}(x_{k})Q(x_{1})$$R_{1}(x_{k})$$R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})$
Figure 4: Using OLE for $\mathsf{OneSidedSetRecon}$

####  4.1.2 The (In)Security of $t\mathsf{HamQueryLite}$

$t\mathsf{HamQueryLite}$ is not secure across all input parameters, and as we
will show in this section, reveals $\vec{b}$ to Alice when
$\delta_{H}(\vec{a},\vec{b})\in(d_{\mathsf{H}},2d_{\mathsf{H}})$. This is
because $\mathsf{OneSidedSetRecon}$ reveals information when
$|S_{\vec{a}}\setminus S_{\vec{b}}|\in(d_{\mathsf{H}},2d_{\mathsf{H}})$ . In
fact, the protocol of Ghosh and Simkin [10] on which
$\mathsf{OneSidedSetRecon}$ is based also has the same leakage, and while the
authors caution against using it as a standalone protocol111To address the
leakage, the paper proposes a significantly more expensive threshold
cardinality of intersection protocol., they have not analyzed this. More
formally, we prove the following result.

######  Theorem 1.

Given sets $S_{\vec{a}}$ and $S_{\vec{b}}$ such that
$\left|{S_{\vec{a}}}\right|=\left|{S_{\vec{b}}}\right|$ as inputs to
$\mathsf{OneSidedSetRecon}$, the following results hold:

  * •

Proposition 1: If $|S_{\vec{a}}\setminus S_{\vec{b}}|\geq 2d_{\mathsf{H}}$,
then there does not exist a PPT adversary that can determine any information
regarding $S_{\vec{b}}$ from $\mathsf{OneSidedSetRecon}$ with more than
negligible advantage (in $\lambda$) over guessing.

  * •

Proposition 2: If $|S_{\vec{a}}\setminus
S_{\vec{b}}|\in(d_{\mathsf{H}},2d_{\mathsf{H}})$, there exists an adversary
that can determine $S_{\vec{b}}$ from $\mathsf{OneSidedSetRecon}$ with
overwhelming probability (at least
$1-\mathbf{negl}\mathopen{}\left(\lambda\right)\mathclose{}$).

Proof (sketch):We prove the result in App. B.2. Here, we provide the key
arguments behind the proof.

Proof of Proposition 1: Consider the evaluation points Alice computes in line
5 corresponding to the rational function
$\frac{R_{1}(x)P(x)+R_{2}(x)Q(x)}{P(x)}=\frac{\mathbf{gcd}\mathopen{}\left(P(x),Q(x)\right)\mathclose{}\times\left(R_{1}(x)P_{{\scriptscriptstyle/q}}(x)+R_{2}(x)Q_{{\scriptscriptstyle/p}}(x)\right)}{P(x)}=\frac{R_{1}(x)P_{{\scriptscriptstyle/q}}(x)+R_{2}(x)Q_{{\scriptscriptstyle/p}}(x)}{P_{{\scriptscriptstyle/q}}(x)}$.
Here,
$P_{{\scriptscriptstyle/q}}(x):=\frac{P(x)}{\mathbf{gcd}\mathopen{}\left(P(x),Q(x)\right)\mathclose{}}$.
If the degree of
$\mathbf{gcd}\mathopen{}\left(P(x),Q(x)\right)\mathclose{}=d_{\mathsf{GCD}}$,
then
$R_{1}(x)P_{{\scriptscriptstyle/q}}(x)+R_{2}(x)Q_{{\scriptscriptstyle/p}}(x)$
is a random polynomial of degree $2\mathcal{\ell}-d_{\mathsf{GCD}}$. This is
due to Lemma 1 as $P(x)$, $Q(x)$, $R_{1}(x)$, $R_{2}(x)$ are all
degree-$\mathcal{\ell}$ polynomials, and
$R_{1}(x),R_{2}(x)\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}[x]$.

From the set of evaluation points, $V$, Alice may try to guess Bob’s input
polynomial $Q(x)$ and check whether there is a polynomial $\mathsf{Num}(x)$ of
degree $2\mathcal{\ell}-d_{\mathsf{GCD}}+1$ such that
$\frac{\mathsf{Num}(x)}{P_{{\scriptscriptstyle/q}}(x)}$ is consistent with
$V$. We show in App. B.1 that when $\left|{V}\right|\leq
2\mathcal{\ell}-d_{\mathsf{GCD}}$ which implies
$\mathcal{\ell}-d_{\mathsf{GCD}}\geq 2d_{\mathsf{H}}$ , for every possible
$P_{{\scriptscriptstyle/q}}(x)$ there is at least one candidate polynomial for
$\mathsf{Num}(x)$. Since
$R_{1}(x)P_{{\scriptscriptstyle/q}}(x)+R_{2}(x)Q_{{\scriptscriptstyle/p}}(x)$
is a random polynomial, any obtained value of $\mathsf{Num}(x)$ is equally
likely to be
$R_{1}(x)P_{{\scriptscriptstyle/q}}(x)+R_{2}(x)Q_{{\scriptscriptstyle/p}}(x)$.
Moreover, if there are more than one candidates for $\mathsf{Num}(x)$, then
they are all equally likely. Thus, Proposition 1 holds.

Proof of Proposition 2: When
$\left|{V}\right|>2\mathcal{\ell}-d_{\mathsf{GCD}}+1$ which implies
$\mathcal{\ell}-d_{\mathsf{GCD}}<2d_{\mathsf{H}}$, the probability that Alice
will find a candidate polynomial for $\mathsf{Num}(x)$ such that
$\frac{\mathsf{Num}(x)}{P_{{\scriptscriptstyle/q}}(x)}$ is consistent with $V$
when she has incorrectly guessed $Q(x)$ (and $P_{{\scriptscriptstyle/q}}(x)$)
is negligible in $\lambda$. And so, Alice may check all possible candidates
for $Q(x)$ and verify her guesses. The set of all possible values of $Q(x)$ is
smaller than the set of degree-$\mathcal{\ell}$ polynomials in
${\mathbb{F}_{p}}[x]$ since the roots of $Q(x)$ are fixed by the mapping
functions $M_{1},\ldots M_{\mathcal{\ell}}$. There are $2^{\mathcal{\ell}}$
possible values of $Q(x)$, and for small $\mathcal{\ell}$, the search is
computationally feasible for a PPT adversary. Thus, Proposition 2 holds. ∎

Figure 5: The process of computing $\delta_{H}(\vec{a},\vec{b})$ in
$t\mathsf{HamQueryRestricted}$. Alice and Bob partition the bits in $\vec{a}$
and $\vec{b}$ respectively into sub-vectors $\vec{x}_{1},\vec{x}_{2}$ and
$\vec{y}_{1},\vec{y}_{2}$. They compute $\vec{X}$ and $\vec{Y}$ respectively
using the parities of the sub-vectors. The bold bits show the locations where
Alice’s and Bob’s inputs differ. Parameters: Alice and Bob have vectors
$\vec{a}$ and $\vec{b}$ respectively, where
$\vec{a},\vec{b}\in\\{0,1\\}^{\mathcal{\ell}},~{}\delta_{H}(\vec{a},\vec{b})\leq
2d_{\mathsf{H}}$ where $d_{\mathsf{H}}$ is the Hamming distance threshold.
False positive rate $\textsc{fpr}\in(0,0.5)$. Procedure
$\mathsf{PermuteAndPartition}$: (1) Alice and Bob sample a permutation
$\pi:[1,\mathcal{\ell}]\rightarrow[1,\mathcal{\ell}]$ uniformly randomly from
the set of all such permutations. (2) Alice computes
$\vec{a}_{\mathsf{perm}}\in\\{0,1\\}^{\mathcal{\ell}}$ after permuting the
bits of $\vec{a}$ as follows: for $m\in[1,\mathcal{\ell}]$,
$\vec{a}_{\mathsf{perm}}[\pi(m)]:=\vec{a}[m]$. Similarly, Bob computes
$\vec{b}_{\mathsf{perm}}\in\\{0,1\\}^{\mathcal{\ell}}$ such that for
$m\in[1,\mathcal{\ell}]$ $\vec{b}_{\mathsf{perm}}[\pi(m)]:=\vec{b}[m]$ (3)
Alice creates $N_{\mathsf{bins}}$ = $\frac{2d_{\mathsf{H}}^{2}}{\textsc{fpr}}$
sub-vectors $\vec{x_{1}},\ldots,\vec{x}_{N_{\mathsf{bins}}}$ where each sub-
vector is created by a contiguous sequence of
$\frac{\mathcal{\ell}}{N_{\mathsf{bins}}}$ bits of $\vec{a}_{\mathsf{perm}}$.
Specifically,
$\vec{x}_{1}:=\vec{a}_{\mathsf{perm}}[1:\frac{\mathcal{\ell}}{N_{\mathsf{bins}}}],~{}\vec{x}_{2}:=\vec{a}_{\mathsf{perm}}[\frac{\mathcal{\ell}}{N_{\mathsf{bins}}}+1:2\times\frac{\mathcal{\ell}}{N_{\mathsf{bins}}}],\ldots,\vec{x}_{N_{\mathsf{bins}}}:=\vec{a}_{\mathsf{perm}}[(N_{\mathsf{bins}}-1)\times\frac{\mathcal{\ell}}{N_{\mathsf{bins}}}+1:\mathcal{\ell}]$.
Here $\vec{a}_{\mathsf{perm}}[m:m^{\prime}]$ is the contiguous sequence of
bits starting from index $m$ and up to (including) index $m^{\prime}$ in
$\vec{a}_{\mathsf{perm}}$. Bob similarly creates
$\vec{y_{1}},\ldots,\vec{y}_{N_{\mathsf{bins}}}$ from
$\vec{b}_{\mathsf{perm}}$. (4) Alice computes vector
$\vec{X}\in\\{0,1\\}^{N_{\mathsf{bins}}}$ such that for
$m\in[1,N_{\mathsf{bins}}]$, $\vec{X}[m]:=\mathbf{parity}(\vec{x}_{m})$.
Similarly, Bob computes vector $\vec{Y}\in\\{0,1\\}^{N_{\mathsf{bins}}}$ such
that $\vec{Y}[m]:=\mathbf{parity}(\vec{y}_{m})$. Protocol
$\mathsf{HamCompute}$: (5) Alice generates a key-pair
$(\mathit{pk},\mathit{sk})$ for a semantically-secure additively homomorphic
encryption $\mathsf{AHE}=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$, and
provides $\mathit{pk}$ to Bob. (6) For $m\in[1,N_{\mathsf{bins}}]$, Alice
computes $ct_{m}:=\mathsf{Enc}(\vec{X}[m])$ and
$ct_{w}:=\left\lVert\vec{X}\right\rVert$ where $\left\lVert.\right\rVert$ is
the Hamming weight of the input vector. Alice sends
$\\{ct_{w},ct_{1},\ldots,ct_{N_{\mathsf{bins}}}\\}$ to Bob. (7) Bob computes
$\mathsf{Enc}(\delta_{H}(\vec{X},\vec{Y})):=ct_{w}+_{\mathit{pk}}ct^{\prime}_{w}-_{\mathit{pk}}2\times_{\mathit{pk}}\left((\vec{Y}[1]\times_{\mathit{pk}}ct^{\prime}_{1})+_{\mathit{pk}}\ldots+_{\mathit{pk}}(\vec{Y}[N_{\mathsf{bins}}]\times_{\mathit{pk}}ct^{\prime}_{N_{\mathsf{bins}}})\right)$
where $ct^{\prime}_{w}:=\left\lVert\vec{Y}\right\rVert$, $+_{\mathit{pk}}$
($-_{\mathit{pk}}$) is homomorphic addition (subtraction) of ciphertexts, and
$\times_{\mathit{pk}}$ is scalar multiplication. (8) Bob samples
$\kappa\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}$ and computes
$\mathsf{KeySet}:=\\{\kappa_{i}:\kappa_{i}:=r_{i}\times_{\mathit{pk}}\left(\mathsf{Enc}(\delta_{H}(\vec{X},\vec{Y}))-_{\mathit{pk}}\mathsf{Enc}(i)\right)+_{\mathit{pk}}\mathsf{Enc}(\kappa),~{}i\in[0,d_{\mathsf{H}}],~{}r_{i}\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}\\}$.
Bob returns $\mathsf{KeySet}$ to Alice. (9) Alice computes
$\mathsf{KeySet}^{\prime}:=\\{\kappa^{\prime}_{i}~{}:~{}\kappa^{\prime}_{i}:=\mathsf{Dec}(\kappa_{i}),~{}\kappa_{i}\in\mathsf{KeySet}\\}$.
If $\delta_{H}(\vec{a},\vec{b})=\delta_{H}(\vec{X},\vec{Y})\leq
d_{\mathsf{H}}$, $\kappa\in\mathsf{KeySet}^{\prime}$. Alice outputs
$\mathsf{KeySet}^{\prime}$. Figure 6: $t\mathsf{HamQueryRestricted}$:
Threshold Hamming query over restricted domain

####  4.1.3 $t\mathsf{HamQuery}$: Hamming Queries with Polynomial Computation

One way to fix $t\mathsf{HamQueryLite}$ is by checking if
$\delta_{H}(\vec{a},\vec{b})\in(d_{\mathsf{H}},2d_{\mathsf{H}})$; however,
implementing this as a precursor to $t\mathsf{HamQueryLite}$ reveals
information regarding $\delta_{H}(\vec{a},\vec{b})$. We propose a protocol
with communication cost independent of the length of the vectors,
$\mathcal{\ell}$ where the cases
$\delta_{H}(\vec{a},\vec{b})\in(d_{\mathsf{H}},2d_{\mathsf{H}})$ and
$\delta_{H}(\vec{a},\vec{b})\geq 2d_{\mathsf{H}}$ are indistinguishable.

Hamming Queries Over Restricted Domain: As the starting point, we present a
protocol which distinguishes $\delta_{H}(\vec{a},\vec{b})\leq d_{\mathsf{H}}$
and $\delta_{H}(\vec{a},\vec{b})\in(d_{\mathsf{H}},2d_{\mathsf{H}}]$. The
additional constraint is that for all inputs $\vec{a}$ and $\vec{b}$, the
maximum Hamming distance between them is known apriori to be $\leq
2d_{\mathsf{H}}$. To generalize over the entire domain, we will subsequently
extend this protocol and integrate with $\mathsf{OneSidedSetRecon}$.

The protocol dubbed $t\mathsf{HamQueryRestricted}$ is inspired by a result due
to Huang et al. [13]. The intuition is as follows: let $S_{I}$ be the set of
indices where $\vec{a}$ and $\vec{b}$ differ. By definition of the problem,
$\left|{S_{I}}\right|\leq 2d_{\mathsf{H}}$. Consider the following balls and
bins analysis: let the indices where $\vec{a}$ and $\vec{b}$ differ be
represented by balls that are thrown randomly into
$\frac{2d_{\mathsf{H}}^{2}}{\textsc{fpr}}$ empty bins, where
$\textsc{fpr}\in(0,0.5)$. Then, the following result shows that all bins have
$\leq 1$ ball with probability at least $1-\textsc{fpr}$. It may be evident
that the number of non-empty bins gives us $\delta_{H}(\vec{a},\vec{b})$.

######  Fact 1 ([13]).

If 2$d_{\mathsf{H}}$ balls are randomly thrown into
$\frac{2d_{\mathsf{H}}^{2}}{\textsc{fpr}}$ bins, where
$\textsc{fpr}\in(0,0.5)$, then with probability at most fpr, there is one or
more bins with more than one ball.

Fig. 6 describes the $t\mathsf{HamQueryRestricted}$ protocol built around this
idea. The protocol comprises two procedures $\mathsf{PermuteAndPartition}$ and
$\mathsf{HamCompute}$. $\mathsf{PermuteAndPartition}$ uses a random
permutation of the vectors to create
$N_{\mathsf{bins}}=\frac{2d_{\mathsf{H}}^{2}}{\textsc{fpr}}$ sub-vectors.
Specifically, the bits in $\vec{a}$ are partitioned into $N_{\mathsf{bins}}$
partitions (each corresponding to a sub-vector) after permuting with the
random permutation. The resulting sub-vectors are denoted
$\vec{x_{1}},\ldots,\vec{x}_{N_{\mathsf{bins}}}$. Similarly, $\vec{b}$ is
partitioned into $\vec{y_{1}},\ldots,\vec{y}_{N_{\mathsf{bins}}}$ (lines 1–3).
Then, Alice and Bob create parity vectors $\vec{X}$ and $\vec{Y}$ using the
parities of the sub-vectors (line 4).

$\mathsf{HamCompute}$ privately computes the Hamming distance between the
parity vectors and compares it with the distance threshold. Alice sends
$\vec{X}$ to Bob, with each bit encrypted individually (line 6). Bob computes
$\mathsf{Enc}(\delta_{H}(\vec{X},\vec{Y}))$ by computing the Hamming distance
over encrypted bits (line 7). The encryption scheme used is additively
homomorphic, which ensures that Bob can compute over the encrypted bits. This
gives $\mathsf{Enc}(\delta_{H}(\vec{a},\vec{b}))$ due to following fact: since
each pair $\vec{x}_{i},\vec{y}_{i}$ can differ in at most one bit due to Fact
1,
$\delta_{H}(\vec{x}_{i},\vec{y}_{i})=\delta_{H}(\mathbf{parity}(\vec{x}_{i}),\mathbf{parity}(\vec{y}_{i}))$.
Then,
$\delta_{H}(\vec{a},\vec{b})=\sum\limits_{i=1}^{N_{\mathsf{bins}}}\delta_{H}(\mathbf{parity}(\vec{x}_{i}),\mathbf{parity}(\vec{y}_{i}))=\delta_{H}(\vec{X},\vec{Y})$
(see Fig. 5).

Finally, Bob samples a key
$\kappa\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}$ and returns a
set $\mathsf{KeySet}$ containing $\kappa$ "blinded" by random values, and
available to Alice iff. $\delta_{H}(\vec{X},\vec{Y})\in[0,d_{\mathsf{H}}]$.
Specifically, for each $i\in[0,d_{\mathsf{H}}]$, Bob returns
$r_{i}\times(\delta_{H}(\vec{X},\vec{Y})-i)+\kappa$ in the $\mathsf{KeySet}$
to Alice where $r_{i}\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}$.
Alice obtains $\kappa$ only when
$\delta_{H}(\vec{X},\vec{Y})\in[0,d_{\mathsf{H}}]$ (lines 8–9). Otherwise,
$r_{i}\times(\delta_{H}(\vec{X},\vec{Y})-i)+\kappa\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}$.

Parameters: Alice and Bob have vectors
$\vec{a},\vec{b}\in\\{0,1\\}^{\mathcal{\ell}}$ respectively. and a Hamming
distance threshold $d_{\mathsf{H}}\in[0,\mathcal{\ell}/2)$. Procedure
$\mathsf{PermuteAndPartition}$: Alice and Bob run
$t\mathsf{HamQueryRestricted}$ with $\vec{a}$ and $\vec{b}$ as inputs. Alice
obtains
$S^{\prime}_{\vec{a}}:=\\{\vec{x}_{1},\ldots,\vec{x}_{N_{\mathsf{bins}}}\\}$
and $\mathsf{KeySet}$, while Bob obtains
$S^{\prime}_{\vec{b}}:=\\{\vec{y}_{1},\ldots,\vec{y}_{N_{\mathsf{bins}}}\\}$
where $N_{\mathsf{bins}}=\frac{2d_{\mathsf{H}}^{2}}{\textsc{fpr}}$. Procedure
$\mathsf{OneSidedSetReconBlind}$: (1) Alice and Bob select a set of
$N_{\mathsf{bins}}+2d_{\mathsf{H}}+1$ points in ${\mathbb{F}_{p}}$,
$X:=\\{x_{k}\\}_{k=1}^{N_{\mathsf{bins}}+2d_{\mathsf{H}}+1}$ such that none of
the points are in $S^{\prime}_{\vec{a}}$ and $S^{\prime}_{\vec{b}}$. (2) Alice
and Bob compute $P(x):=\prod\limits_{r\in S^{\prime}_{\vec{a}}}(x-r)$ and
$Q(x):=\prod\limits_{r\in S^{\prime}_{\vec{b}}}(x-r)$ respectively. Bob
samples two random polynomials
$R_{1}(x),R_{2}(x)\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}[x]$ of
degree $N_{\mathsf{bins}}$. (3) For each $x_{k}\in X$, Alice sends $P(x_{k})$
to $\mathcal{F}^{p}_{\mathit{ole}}$, while Bob sends $R_{1}(x_{k})$, and
$R_{2}(x_{k})\times Q(x_{k})+\phi(\kappa,k)$. Alice obtains
$W_{A}(x_{k}):=R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})+\phi(\kappa,k)$ (4)
For each element $\kappa_{i}\in\mathsf{KeySet}$, Alice obtains a candidate
key, $\kappa^{{}^{\prime}}_{i}:=\mathsf{Dec}(\kappa_{i})$. Alice computes
$V_{i}:=\\{(x_{k},y_{k}):y_{k}:=\frac{W_{A}(x_{k})-\phi(\kappa^{{}^{\prime}}_{i},k)}{P(x_{k})}\\}$.
(5) For each $i\in[0,d_{\mathsf{H}}]$, Alice interpolates $V_{i}$ with a
rational function $r(x):=\frac{\mathsf{Num}(x)}{\mathsf{Den}(x)}$ and checks
that $\mathsf{Den}(x)$ is a factor of $P(x)$. If so, Alice outputs
$S^{\prime}_{\vec{a}}\setminus S^{\prime}_{\vec{b}}$ which contains the roots
of $\mathsf{Den}(x)$, otherwise Alice outputs $\bot$. Procedure
$\mathsf{Recover}$: If Alice receives $\bot$ from
$\mathsf{OneSidedSetReconBlind}$ then output $\bot$. Otherwise, upon receiving
$S^{\prime}_{\vec{a}}\setminus S^{\prime}_{\vec{b}}$, obtain $\vec{b}$ from
Bob. Output $(\vec{a},\vec{b})$. Figure 7: $t\mathsf{HamQuery}$: Threshold
Hamming query protocol

General Hamming Queries: We are ready to combine
$t\mathsf{HamQueryRestricted}$ and $\mathsf{OneSidedSetRecon}$ to achieve a
secure threshold Hamming query protocol, $t\mathsf{HamQuery}$. The protocol
requires a PRF over a finite field
$\phi:{\mathbb{F}_{p}}\times{\mathbb{F}_{p}}\rightarrow{\mathbb{F}_{p}}$. The
outline of this integration is (see Fig. 7):

  1. (1)

Alice and Bob send $\vec{a}$ and $\vec{b}$ to $t\mathsf{HamQueryRestricted}$
respectively. Alice obtains $\mathsf{KeySet}$ from which she can obtain
$\kappa$ only when
$\delta_{H}(\vec{a},\vec{b})\notin(d_{\mathsf{H}},2d_{\mathsf{H}}]$.

  2. (2)

Alice builds set
$S^{\prime}_{\vec{a}}:=\\{\vec{x}_{1},\ldots,\vec{x}_{N_{\mathsf{bins}}}\\}$
where $\vec{x}_{1},\ldots,\vec{x}_{N_{\mathsf{bins}}}$ are the sub-vectors
created during $\mathsf{PermuteAndPartition}$ in
$t\mathsf{HamQueryRestricted}$ (see line 3 of Fig. 6). Bob builds
$S^{\prime}_{\vec{b}}:=\\{\vec{y}_{1},\ldots,\vec{y}_{N_{\mathsf{bins}}}\\}$.

  3. (3)

Alice and Bob run $\mathsf{OneSidedSetRecon}$ with $S^{\prime}_{\vec{a}}$ and
$S^{\prime}_{\vec{b}}$ as inputs and threshold $d_{\mathsf{H}}$ with one
change: Bob modifies his inputs to $\mathcal{F}^{p}_{\mathit{ole}}$ such that
Alice obtains a “blinded” set of evaluations, i.e., for
$k\in[1,N_{\mathsf{bins}}+2d_{\mathsf{H}}+1]$, Alice obtains
$R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})+\phi(\kappa,k)$ (see Fig. 8).

######  Theorem 2.

Assuming that there exists a semantically-secure additively homomorphic
encryption scheme that produces
$\operatorname{O}\mathopen{}\left(\lambda\right)\mathclose{}$-bit ciphertexts,
and that there is a protocol for $\mathcal{F}^{p}_{\mathit{ole}}$ that
requires $\operatorname{O}\mathopen{}\left(\lambda\right)\mathclose{}$ bits of
communication, for false positive rate $\textsc{fpr}\in(0,0.5)$,
$t\mathsf{HamQuery}$ realizes
$\mathcal{F}_{\mathcal{\ell},d_{\mathsf{H}}}^{t{\text{-}}\mathit{HQ}}$ with
$\operatorname{O}\mathopen{}\left(\frac{d_{\mathsf{H}}^{2}}{\textsc{fpr}}\cdot\lambda\right)\mathclose{}$
bits of communication and compute costs polynomial in $d_{\mathsf{H}}$.

Proof (sketch):The communication cost of the protocol is straightforward.
Alice sends $|\vec{X}|=\frac{2d_{\mathsf{H}}^{2}}{\textsc{fpr}}$ encrypted
bits to Bob. Bob sends back the encrypted $\mathsf{KeySet}$ with
$|\mathsf{KeySet}|=d_{\mathsf{H}}$ ciphertexts. Finally, there are
$\frac{2d_{\mathsf{H}}^{2}}{\textsc{fpr}}+2d_{\mathsf{H}}+1$ calls to
$\mathcal{F}^{p}_{\mathit{ole}}$, each of which requires
$\operatorname{O}\mathopen{}\left(\lambda\right)\mathclose{}$ bits of
communication.

The following arguments show that the protocol is secure. Alice can “unblind”
and obtain the correct evaluations of $R_{1}(x)P(x)+R_{2}(x)Q(x)$ iff she has
obtained $\kappa$ in Step 1, which happens with high probability (at least
$1-\epsilon$) when
$\delta_{H}(\vec{a},\vec{b})\notin(d_{\mathsf{H}},2d_{\mathsf{H}}]$.
Otherwise, Alice obtains random points as evaluations of
$R_{1}(x)P(x)+R_{2}(x)Q(x)$ which reveals no information regarding
$S^{\prime}_{\vec{b}}$. If $\delta_{H}(\vec{a},\vec{b})>2d_{\mathsf{H}}$,
Alice may still obtain $\kappa\in\mathsf{KeySet}$ since Fact 1 is applicable
only when $\delta_{H}(\vec{a},\vec{b})\leq 2d_{\mathsf{H}}$. We show in App. C
that $|S^{\prime}_{\vec{a}}\setminus S^{\prime}_{\vec{b}}|\geq
2d_{\mathsf{H}}$ with high probability (at least $1-\epsilon$), and as Theorem
1 shows, when $|S^{\prime}_{\vec{a}}\setminus S^{\prime}_{\vec{b}}|\geq
2d_{\mathsf{H}}$, Alice learns nothing about $S^{\prime}_{\vec{a}}\setminus
S^{\prime}_{\vec{b}}$ from the evaluations of $R_{1}(x)P(x)+R_{2}(x)Q(x)$. ∎

AliceSubsample $\vec{a}$:
$S^{\prime}_{\vec{a}}:=\\{\vec{x}_{1},\ldots,\vec{x}_{N}\\}$$P(x):=\prod\limits_{r\in
S^{\prime}_{\vec{a}}}(x-r)$BobSubsample $\vec{b}$:
$S^{\prime}_{\vec{b}}:=\\{\vec{y}_{1},\ldots,\vec{y}_{N}\\}$$Q(x):=\prod\limits_{r\in
S^{\prime}_{\vec{b}}}(x-r)$$R_{1}(x),R_{2}(x)\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}[x]$$t\mathsf{HamQueryRestricted}$$\vec{a}$$\vec{b},\kappa$$\delta_{H}(\vec{a},\vec{b})\leq
d_{\mathsf{H}}?:\kappa,\bot$$\mathcal{F}^{p}_{\mathit{ole}}$$R_{1}(x_{1})$$R_{2}(x_{1})Q(x_{1})+\phi(\kappa,1)$$P(x_{1})$$R_{1}(x_{1})P(x_{1})+R_{2}(x_{1})Q(x_{1})+\phi(\kappa,1)$……$\mathcal{F}^{p}_{\mathit{ole}}$$R_{1}(x_{N})$$R_{2}(x_{N})Q(x_{N})+\phi(\kappa,N)$$P(x_{N})$$R_{1}(x_{N})P(x_{N})+R_{2}(x_{N})Q(x_{N})+\phi(\kappa,N)$
Figure 8: Using OLE and $t\mathsf{HamQueryRestricted}$ in $t\mathsf{HamQuery}$

###  4.2 $\mathsf{HamPSI}$: Hamming DA-PSI from $t\mathsf{HamQuery}$

Building a Hamming DA-PSI protocol based on the Hamming query mechanism
described so far is straightforward. Let
$A:=\\{\vec{a}_{1},\ldots,\vec{a}_{n}\\}$ and
$B:=\\{\vec{b}_{1},\ldots,\vec{b}_{n}\\}$ be Alice’s and Bob’s inputs to the
Hamming DA-PSI protocol. Then, for $(i,j)\in n\times n$, Alice and Bob run
$t\mathsf{HamQuery}$ with $\vec{a}_{i}$ and $\vec{b}_{j}$ as inputs.

We present the full protocol, denoted $\mathsf{HamPSI}$, in App. D with a
further optimization using vector OLE (see Sec. 3.1) to batch the OLEs in
$\mathsf{OneSidedSetRecon}$ required across all the instantiations. This
optimization improves communication costs and compute times without impacting
security.

######  Theorem 3.

Assuming that there exists a semantically secure additively homomorphic
encryption scheme, and a protocol securely realizing
$\mathcal{F}^{p}_{\mathit{vole}}$ with
$\operatorname{O}\mathopen{}\left(n\lambda\right)\mathclose{}$ bits of
communication, there is a Hamming DA-PSI protocol which securely realizes
$\mathcal{F}_{\ell,d_{\mathsf{H}}}^{h{\text{-}}\mathit{PSI}}$ with
$\operatorname{O}\mathopen{}\left(n^{2}\cdot\frac{d_{\mathsf{H}}^{2}}{\textsc{fpr}}\cdot\lambda\right)\mathclose{}$
bits of communication where $\textsc{fpr}\in(0,0.5)$ is the false positive
rate.

Parameters: Alice and Bob have vectors
$\vec{a},\vec{b}\in\\{0,1\\}^{\mathcal{\ell}}$, respectively, and a Hamming
distance threshold $d_{\mathsf{H}}$. Procedure $\mathsf{Map}$: Follows the
steps of $t\mathsf{HamQueryLite}$. Procedure $\mathsf{OneSidedSetReconExp}$:
(1) Alice and Bob select a set of $\mathcal{\ell}+d_{\mathsf{H}}+2$ points in
${\mathbb{F}_{p}}$, $X:=\\{x_{k}\\}_{k=1}^{\mathcal{\ell}+d_{\mathsf{H}}+2}$
such that none of the points are in $S_{\vec{a}}$ and $S_{\vec{b}}$. (2) Alice
encodes $S_{\vec{a}}$ in the polynomial $P(x)$ = $\prod\limits_{r\in
S_{\vec{a}}}(x-r)$ and Bob encodes $S_{\vec{b}}$ in the polynomial $Q(x)$ =
$\prod\limits_{r\in S_{\vec{b}}}(x-r)$. Bob samples two
degree-$\mathcal{\ell}$ random polynomials
$R_{1}(x),R_{2}(x)\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}[x]$.
(3) For each $x_{k}\in X$, Alice sends $P(x_{k})$ and Bob sends $R_{1}(x_{k})$
and $R_{2}(x_{k})\times Q(x_{k})$ to $\mathcal{F}^{p}_{\mathit{ole}}$. Alice
learns $W_{A}(x_{k})$ $:=$ $R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})$ as the
output of $\mathcal{F}^{p}_{\mathit{ole}}$. (4) Alice computes and
interpolates $V_{0}$ with a rational function of degree
$\mathcal{\ell}+d_{\mathsf{H}}$ similar to line 6 of
$\mathsf{OneSidedSetRecon}$ .
$V_{0}:=\\{(x_{k},y_{k}):y_{k}:=\frac{W_{A}(x_{k})}{P(x_{k})},~{}k\in[1,\mathcal{\ell}+d_{\mathsf{H}}+1]\\}$.
(5) If Alice outputs $S_{\vec{a}}\setminus S_{\vec{b}}$ from the step above,
then output $S_{\vec{a}}\setminus S_{\vec{b}}$ and abort. Otherwise, for each
$t\in(d_{\mathsf{H}}/2,d_{\mathsf{H}}]$, Alice computes all possible values of
$S_{\vec{a}}\setminus S_{\vec{b}}$ such that $|S_{\vec{a}}\setminus
S_{\vec{b}}|=t$. Let $C_{\mathsf{sub}}$ be the set of all such sets across all
$t\in(d_{\mathsf{H}}/2,d_{\mathsf{H}}]$. (6) For each $C_{i}\in
C_{\mathsf{sub}}$, Alice computes the polynomial $P_{i}(x):=\prod\limits_{r\in
C_{i}}(x-r)$ and computes the set of points
$V_{i}:=\\{(x_{k},y_{k}):y_{k}:=\frac{W_{A}(x_{k})}{P_{i}(x_{k})},~{}k\in[1,\mathcal{\ell}+d_{\mathsf{H}}+2]\\}$.
(7) Alice interpolates $V_{i}$ for each $C_{i}\in C_{\mathsf{sub}}$ with a
polynomial. If the degree of the interpolating polynomial is
$\leq\mathcal{\ell}+\mathbf{deg}\mathopen{}\left(P_{i}(x)\right)\mathclose{}$,
Alice outputs $S_{\vec{a}}\setminus S_{\vec{b}}:=C_{i}$. Procedure
$\mathsf{Recover}$: Follows the steps of $t\mathsf{HamQueryLite}$ Figure 9:
$t\mathsf{HamQueryExp}$: Hamming queries with exponential compute costs.

###  4.3 $\mathsf{HamPSISample}$: Sub-Sampling Based Hamming DA-PSI

So far we have discussed a way to build a Hamming DA-PSI protocol using
$t\mathsf{HamQuery}$ which fixes $t\mathsf{HamQueryLite}$ by explicitly
checking if the inputs,
$\delta_{H}(\vec{a},\vec{b})\in(d_{\mathsf{H}},2d_{\mathsf{H}})$. However,
there is an alternate way to fix the problem which leads to a more
communication-efficient protocol, but at the cost of additional computation.
The protocol uses a Hamming query protocol, denoted $t\mathsf{HamQueryExp}$,
which relies only on OLE.

$t\mathsf{HamQueryExp}$: The protocol is based on the findings of Theorem 1.
Specifically, as the proof shows when Alice and Bob interpolate
$R_{1}(x)P(x)+R_{2}(x)Q(x)$ at
$\left|{V}\right|>2\mathcal{\ell}-d_{\mathsf{GCD}}+1$ points in
$\mathsf{OneSidedSetRecon}$, Alice can retrieve $S_{\vec{a}}\setminus
S_{\vec{b}}$ when $|S_{\vec{a}}\setminus
S_{\vec{b}}|=\mathcal{\ell}-d_{\mathsf{GCD}}$ with overwhelming probability
(Proposition 2). On the other hand, when $|S_{\vec{a}}\setminus
S_{\vec{b}}|>\mathcal{\ell}-d_{\mathsf{GCD}}$, the evaluation points reveal
nothing to Alice (Proposition 1).

So, one way to fix $\mathsf{OneSidedSetRecon}$ is by evaluating
$R_{1}(x)P(x)+R_{2}(x)Q(x)$ at
$(2\mathcal{\ell}-d_{\mathsf{GCD}}+1)+1=(2\mathcal{\ell}-(\mathcal{\ell}-d_{\mathsf{H}})+1)+1=\mathcal{\ell}+d_{\mathsf{H}}+2$
points. In this way, Alice learns $S_{\vec{a}}\setminus S_{\vec{b}}$ with
overwhelming probability when $|S_{\vec{a}}\setminus S_{\vec{b}}|\leq
d_{\mathsf{H}}$ but nothing otherwise. The modified protocol is called
$\mathsf{OneSidedSetReconExp}$ (Fig. 9). Similar to
$\mathsf{OneSidedSetRecon}$, Alice and Bob compute polynomials $P(x)$ and
$Q(x)$ from their respective sets. Then, they evaluate
$R_{1}(x)P(x)+R_{2}(x)Q(x)$ at $\mathcal{\ell}+d_{\mathsf{H}}+2$ points using
calls to $\mathcal{F}^{p}_{\mathit{ole}}$. Alice first attempts to interpolate
$\mathcal{\ell}+d_{\mathsf{H}}+1$ points with a rational function of degree
$\mathcal{\ell}+d_{\mathsf{H}}$ (lines 2–4). Note if $|S_{\vec{a}}\setminus
S_{\vec{b}}|\leq d_{\mathsf{H}}/2$, then this step will reveal
$S_{\vec{a}}\setminus S_{\vec{b}}$ to Alice.

Otherwise, Alice computes for each $t\in(d_{\mathsf{H}}/2,d_{\mathsf{H}}]$,
each possible value of $S_{\vec{a}}\setminus S_{\vec{b}}$ such that
$|S_{\vec{a}}\setminus S_{\vec{b}}|=t$ (line 5). Let $C_{\mathsf{sub}}$ be the
set of all such sets. Then, for each $C_{i}\in C_{\mathsf{sub}}$, Alice
computes $P_{i}(x):=\prod\limits_{r\in C_{i}}(x-r)$. Finally, Alice checks if
a polynomial $\mathsf{Num}(x)$ of degree
$\leq\mathcal{\ell}+\mathbf{deg}\mathopen{}\left(P_{i}(x)\right)\mathclose{}$
exists such that $\frac{\mathsf{Num}(x)}{P_{i}(x)}$ is consistent with the
points obtained for the rational function
$\frac{R_{1}(x)P(x)+R_{2}(x)Q(x)}{P_{i}(x)}$ (line 7). Due to Proposition 2,
there is a negligible probability of obtaining a false positive, i.e., Alice
finds $\mathsf{Num}(x)$ when her guess for $S_{\vec{a}}\setminus S_{\vec{b}}$
is incorrect. There are no false negatives.

Reducing Search Space by Sub-Sampling: The total search space for this process
is over
$\sum\limits_{t=d_{\mathsf{H}}/2+1}^{d_{\mathsf{H}}}\binom{\mathcal{\ell}}{t}$
guesses for $S_{\vec{a}}\setminus S_{\vec{b}}$, and is not feasible with large
vectors and distance thresholds. However, as we will show in Sec. 6, when we
replace $\mathsf{Map}$ with a sub-sampling algorithm [33, 32, 8, 2] reducing
large vectors to a small set of sub-vectors, this method outperforms the
existing state of the art [32]. The cost savings come from the fact that our
protocol only relies on cheap symmetric-key primitives while the protocol of
Uzun et al. [32] relies on fully homomorphic encryption. Based on this idea,
we have built and implemented a DA-PSI protocol combining the sub-sampling
algorithm from [33, 32, 8, 2] with $\mathsf{OneSidedSetReconExp}$, denoted
$\mathsf{HamPSISample}$. More details of the protocol are presented in App. E.

##  5 Protocol for Integer Distances

In this section, we present a DA-PSI protocol for $L_{1}$ distance of order 1
over integers, loosely termed as integer distance-aware PSI. The protocol
requires $\operatorname{O}\mathopen{}\left(n\lambda\log
d_{\mathsf{int}}\right)\mathclose{}$ bits of communication for computing the
intersection of two sets of size $n$ where $d_{\mathsf{int}}$ is a user-
specified distance threshold.

Parameters:  Parties Alice and Bob. Integer distance threshold $d\geq 0$.
Inputs:  Alice has input $A=\\{a_{i}:a_{i}\in{\mathbb{Z}^{+}}\cup\\{0\\}\\}$.
Bob has input $B=\\{b_{j}:b_{j}\in{\mathbb{Z}^{+}}\cup\\{0\\}\\}$.
$\left|{A}\right|=\left|{B}\right|=n$. Output:  Alice and Bob learn
$S\subseteq A\times B$ where if $(a,b)\in A\times B,|a-b|\leq
d_{\mathsf{int}}$ then $\mathbb{P}\left[(a,b)\in S\right]\geq\textsc{tpr}$ and
if $|a-b|>d_{\mathsf{int}}$ then $\mathbb{P}\left[(a,b)\not\in
S\right]\geq\textsc{tnr}$. Figure 10: Ideal functionality
$\mathcal{F}_{d_{\mathsf{int}}}^{i{\text{-}}\mathit{PSI}}$ for Integer DA-PSI.

Ideal Functionality: The ideal functionality for an integer distance-aware PSI
is defined in Fig. 10. Note that the $(a_{i},b_{j})\in S$ only when
$b_{j}\in(a_{i}-d_{\mathsf{int}},a_{i}+d_{\mathsf{int}})$. The range excludes
the boundary elements, $a_{i}+d_{\mathsf{int}}$ and $a_{i}-d_{\mathsf{int}}$.
This is primarily for ease of description of the protocol and it is trivial to
extend the functionality and the protocol to include the boundary elements.
Also, while the functionality allows tunable true positive and true negative
rates, the protocol we present is correct with probability $1.0$, i.e.,
$\textsc{tpr}=\textsc{tnr}=1$.

Observe that an inefficient realization of
$\mathcal{F}_{d_{\mathsf{int}}}^{i{\text{-}}\mathit{PSI}}$ immediately exists:
Alice creates an augmented set, $\hat{A}$ with all integers
$(a-d_{\mathsf{int}},a+d_{\mathsf{int}})$ for each $a\in A$. Any generic PSI
protocol be used for computing the intersection between the augmented set and
$B$. This protocol however requires $\operatorname{O}\mathopen{}\left(n\lambda
d_{\mathsf{int}}\right)\mathclose{}$ bits of communication, using a PSI
protocol with communication cost scaling linearly in the set size.

Key Idea: To reduce overall communication, we will reduce the number of items
in the augmented set. The key observation behind this reduction is that all
integers in the neighborhood of an integer $a\in A$,
$a^{\prime},|a^{\prime}-a|\leq d_{\mathsf{int}}$ can be succinctly represented
by a collection of bit strings corresponding to their binary representations.
The total number of such strings required is sublinear in $d_{\mathsf{int}}$
since multiple integers within a sequence will share prefixes, and the same
common prefix can be used to represent multiple consecutive integers. For
instance, the binary representation of 42 ($101010$) and 43 ($101011$) share
the prefix $10101$. Both these integers can be represented by the string
$10101\ast$ where $\ast$ denotes a wildcard bit. Leveraging this fact, the
idea is to generate the least number of bit strings to represent all integers
$a^{\prime},|a^{\prime}-a|\leq d_{\mathsf{int}}$. The problem is reduced to
string matching over these bit strings.

The augmenting process is discussed next. The protocol we will present allows
one of the parties, say Alice, to learn the integer-aware intersection, and
then this information can be shared with Bob using an extra round of
communication.

Augmenting Alice’s Set: The augmented set $\hat{A}$ includes fixed-length
strings representing $(a-d_{\mathsf{int}},a+d_{\mathsf{int}})$ for each $a\in
A$. These strings are obtained from the prefixes of fixed-length binary
representations of all integers in the range. This fixed length, denoted
$\mathsf{MaxBitLen}$, may be determined from the universe from which the
elements in $A$ and $B$ are drawn.

Intuitively, the process is based on two observations. First, the integers in
$(a-d_{\mathsf{int}},a+d_{\mathsf{int}})$ can differ only in their
$\lfloor\log(2d_{\mathsf{int}}-1)\rfloor+1$ least significant bits if
$2^{k}\leq a-d\leq a+d\leq 2^{k+1}$. Second, the $\mathsf{MaxBitLen}$-sized
binary representations of all integers in
$[2^{k},2^{k+1}-1],k\in{\mathbb{Z}^{+}}$ have a common prefix of length
$\mathsf{MaxBitLen}-k-1$. So, all these integers can be represented by a
string formed by appending $k+1$ wildcard bits to the common prefix. Based on
these observations, the idea is to recursively partition
$(a-d_{\mathsf{int}},a+d_{\mathsf{int}})$ into smaller ranges of the form
$[0,2^{k}-1]$ or $[2^{k},2^{k+1}-1]$ and obtain a representative string for
each such range. More formally, to create representative strings for integers
in $(a-d_{\mathsf{int}},a+d_{\mathsf{int}})$, we identify the enclosing common
prefixes.

######  Definition 1.

Given any arbitrary set of bit strings, an enclosing common prefix of length
$\ell_{p}$ $\leq$ $\mathsf{MaxBitLen}$ satisfies:

  1. (1)

There are $2^{(\mathsf{MaxBitLen}-\ell_{p})}$ bit strings which have this
prefix in common.

  2. (2)

The bit strings which share this prefix do not have a common prefix of length
$<\ell_{p}$.

All identified enclosing common prefixes are appended with wildcard bits to
generate representative strings. We show later that for each $a\in A$ the
number of enclosing common prefixes is $\operatorname{O}\mathopen{}\left(\log
d_{\mathsf{int}}\right)\mathclose{}$. Intuitively this is because the range of
integers is recursively halved and each such range has a constant number of
enclosing common prefixes. Thus, the augmented set contains
$\operatorname{O}\mathopen{}\left(n\cdot\log
d_{\mathsf{int}}\right)\mathclose{}$ representative strings.

Example: We are interested in the representative strings for all integers in
the range (41, 56) (see Fig. 11). The 8-bit binary representation of 42 is
$00101010$ and the 8-bit binary representation of 55 is $00110111$. Integers
in the range [42, 43] have a common enclosing prefix $0010101$, integers in
the range [44, 47] have a common enclosing prefix $001011$ and the integers in
the range [48, 55] have a common enclosing prefix $00110$. Thus, 8-bit
representative strings for all integers in $(41,56)$ are $0010101$$\ast$,
$001011$$\ast$$\ast$ and $00110$$\ast$$\ast$$\ast$.

Augmenting Bob’s Set: To check whether an integer falls in any of the ranges
in an augmented set, we need to check whether it shares a common prefix with
any of the representative strings. The augmented set $\hat{B}$ includes these
strings. Specifically we need to check prefixes only of length
$\ell_{p}\in[\mathsf{MaxBitLen}-\lfloor\log(2d-1)\rfloor-1,\mathsf{MaxBitLen}]$
(as will be discussed later). Thus, representative strings for each integer
$b_{j}\in B$ is obtained by replacing the required number of least significant
bits in the binary representation of $b_{j}$ with wildcard bits. Specifically,
the first representative string is generated by replacing the least
significant bit, the second string is generated by replacing the last two
least significant bits and so on. All the representative strings for all
$b_{j}\in B$ is part of $\hat{B}$. Thus, $\left|{\hat{B}}\right|$ =
$\operatorname{O}\mathopen{}\left(n\cdot\log
d_{\mathsf{int}}\right)\mathclose{}$.

Example: Consider $b=49$ ($00110001$). The 8-bit representative strings of 49
are $00110001$, $0011000\ast$, $001100\ast\ast$, $00110\ast\ast\ast$,
$0011\ast\ast\ast\ast$. The set of strings for integers in range $(41,56)$ and
the strings for $49$ have the string $00110\ast\ast\ast$ in common which
correctly shows that $b\in(41,56)$.

1A0421431B04414504614700110C048149050151052153054155 Figure 11: Prefix trie
examples. (a) Trie built over the binary representations of integers [42, 55].
The nodes marked A, B and C are the roots of the maximal enclosing complete
subtries.

######  Theorem 4.

Assuming that there is a secure scheme for computing a private set
intersection over sets of size $n$ with
$\operatorname{O}\mathopen{}\left(n\lambda\right)\mathclose{}$ bits of
communication. Then, there is a secure protocol realizing
$\mathcal{F}_{d_{\mathsf{int}}}^{i{\text{-}}\mathit{PSI}}$ with
$\operatorname{O}\mathopen{}\left(n\lambda\log
d_{\mathsf{int}}\right)\mathclose{}$ bits of communication where
$d_{\mathsf{int}}$ is the specified distance threshold.

A private set intersection protocol with the augmented sets as inputs provides
a integer-distance aware intersection. This is because a non-null intersection
implies that a representative string(s) for $b_{j}\in B$ matched a
representative string(s) in $a_{i}\in A$ which can only happen if
$|a_{i}-b_{j}|<d_{\mathsf{int}}$. Any existing private set intersection
protocol can be used. In Section 6, we have instantiated an integer DA-PSI
protocol with an OT-based PSI protocol due to Pinkas et al. [27]. We will omit
details of this straightforward integration. To estimate the communication
complexity of the protocol, in App. F, we describe an algorithm to augment the
input sets using the specified distance threshold. The algorithm builds a
prefix trie over the binary representation of
$(a-d_{\mathsf{int}},a+d_{\mathsf{int}})$, and identifies the maximal
enclosing complete subtries (see Fig. 11).

######  Definition 2.

A subtrie in a prefix trie is called a maximal enclosing complete subtrie if
it satisfies the following properties: i) it is a complete binary tree, and
ii) it is not part of any other complete binary subtree(s) rooted at one of
its ancestors.

Each maximal enclosing complete subtrie corresponds to an enclosing common
prefix of the bit strings for $(a-d_{\mathsf{int}},a+d_{\mathsf{int}})$. We
count the number of maximal enclosing complete subtries in the prefix trie
built over the binary representations and show that the total number of
maximal enclosing complete subtries in a prefix trie built over the binary
representations of all integers $(a-d_{\mathsf{int}},a+d_{\mathsf{int}})$ is
$\operatorname{O}\mathopen{}\left(\log d_{\mathsf{int}}\right)\mathclose{}$.

##  6 Evaluation

$0$$2{,}000$$4{,}000$$6{,}000$$8{,}000$$2$$3$$4$$5$$6$Vector Length
($\mathcal{\ell}$)Total Comm. (in MB. logscale)GC
Baseline$\mathsf{HamPSI}-0.1$$\mathsf{HamPSI}-0.05$$\mathsf{HamPSI}-0.01$ (a)
Total comm. vs. vector length

$0$$5$$10$$15$$20$$25$$30$$35$$2$$4$$6$$8$Distance Threshold
($d_{\mathsf{H}}$)Total Comm. (in MB. logscale)GC
Baseline$\mathsf{HamPSI}-0.1$$\mathsf{HamPSI}-0.05$$\mathsf{HamPSI}-0.01$ (b)
Total comm. vs. threshold

2565121048204840968192$0$$1{,}000$$2{,}000$$3{,}000$$267$$267$$267$$267$$267$$267$$98$$221$$510$$977$$1{,}450$$3{,}000$Vector
Length ($\mathcal{\ell}$)Time (in sec)$\mathsf{HamPSI}-0.05$GC Baseline (c)
Compute time vs. vector length

12481632$0$$1{,}000$$2{,}000$$3{,}000$$4{,}000$$8$$20$$57$$487$$622$$2{,}296$$3{,}000$$3{,}000$$3{,}000$$3{,}000$$3{,}000$$3{,}000$Distance
Threshold ($d_{\mathsf{H}}$)Time (in sec)$\mathsf{HamPSI}-0.05$GC Baseline (d)
Compute time vs. threshold

Figure 12: Micro-benchmarks for $\mathsf{HamPSI}$ (Sec. 4.2). Set size
$n=100$. In Fig. 12a and Fig. 12b, the values on the $y$-axis are in logscale
(base 10). Fig. 12a shows for $d_{\mathsf{H}}$ = 10, and for FPR = 0.05 and
FPR = 0.01, $\mathsf{HamPSI}$ has around $\mathbf{10\times}$ and
$\mathbf{2\times}$ lower communication volume respectively, compared to the GC
baseline when the vector dimensions, $\mathcal{\ell}=8192$. Fig. 12b shows
with $\mathcal{\ell}=8192$ dimension vector, and for FPR = 0.05,
$\mathsf{HamPSI}$ has $\mathbf{2-537\times}$ lower communication volumes up to
distance threshold $d_{\mathsf{H}}=32$ compared to the baseline. Fig. 12c
shows that for vector lengths, $\mathcal{\ell}\geq 1024$ bits,
$\mathsf{HamPSI}$ is at least $\mathbf{2}\times$ faster than the GC baseline.
Fig. 12d shows that for up to distance threshold $d_{\mathsf{H}}\leq 32$,
$\mathsf{HamPSI}$ is faster than the GC baseline.

We have implemented both $\mathsf{HamPSI}$ (Sec. 4.2) and $\mathsf{IntPSI}$
(Sec. 5). In the following sections, we benchmark the protocols. The
evaluation metrics are communication costs and compute times. All experiments
consist of 5 independent trials and results are collected with a 95%
confidence interval.

Platform: We ran our experiments on two different platforms representing low
and high resource environments respectively.

  * •

Low-resource: Unless stated otherwise, our experiments were run on two
t2.xlarge Amazon EC2 instances with 4 vCPUs and 16GB of RAM. To simulate
realistic scenarios, these instances were placed in different zones (US East
and West). The network bandwidth between them was measured to be around
40–60$\mathrm{MB}$ per second using iperf222https://iperf.fr/.

  * •

High-resource: We used a Microsoft Azure F72s_v2 instance, which has 72
virtual cores and 144$\mathrm{GB}$ of RAM, to compare to the results of Uzun
et al. [32, Table 10].

###  6.1 Hamming Distance Protocol

Implementation: We have implemented $\mathsf{HamPSI}$ and
$\mathsf{HamPSISample}$ in C++11. The implementation uses the NTL
library333https://libntl.org/ for implementing the finite field arithmetic,
and the operations are performed over a 128-bit prime order field. We have
used the open-source implementation444https://github.com/emp-toolkit/emp-zk of
the state of the art VOLE scheme [37] for our set reconciliation protocols.

Finally for $t\mathsf{HamQueryRestricted}$, we have used the open source
implementation555https://github.com/lubux/ecelgamal of the EC-ElGamal
encryption scheme on a 256-bit curve as the additively homomorphic encryption.
The scheme is set up with a 24-bit message space and a precomputed plaintext
table of 24-bit messages to speedup the decryption process. The message space
is large enough to encrypt the individual bits of the vectors, compute the
Hamming distance between them over the ciphertexts and compare with the
distance threshold. The 128-bit key returned in the protocol is split into
24-bit chunks to fit into the message space. More details are in App. C.1.

####  6.1.1 Comparison with Generic 2PC [14]

We have compared our Hamming DA-PSI protocol (Sec. 4.2) denoted
$\mathsf{HamPSI}$ with the garbled circuit based construction by Huang et al.
[13]. This construction is more efficient than the AHE-based scheme due to
Osadchy et al. [25]. We use an open source
implementation666https://mightbeevil.org.

Micro-Benchmark: We run micro-benchmarks with sets containing 100 vectors
sampled from the space $\\{0,1\\}^{\mathcal{\ell}}$, and measure the
communication volumes relative to the baseline.

  * •

Communication volume: Fig. 12a shows how the communication volume scales with
the the vector lengths, $\mathcal{\ell}$. The distance threshold
$d_{\mathsf{H}}=10$. As expected, the communication volume for
$\mathsf{HamPSI}$ remains constant, while the communication volume for the GC
based solution scales linearly in the vector size. For vectors of length
greater than $512$ bits, $\mathsf{HamPSI}$ outperforms the GC based solution.
With 8192-bit vectors, $\mathsf{HamPSI}$ has 10$\times$ lower communication
volume for FPR = 0.05. Fig. 12b shows how communication volume scales with the
distance threshold, $d_{\mathsf{H}}$. $\mathsf{HamPSI}$ has $1.5-440\times$
lower communication volumes up to $d_{\mathsf{H}}=30$ compared to the
baseline.

  * •

Compute time: Fig. 12c and Fig. 12d shows how the compute time in
$\mathsf{HamPSI}$ scales with vector lengths, and the distance threshold for
FPR = 0.05. For vectors of length $\geq 1024$ bits, $\mathsf{HamPSI}$ is at
least $2\times$ faster than the GC-based system. With $8192$-bit vectors,
$\mathsf{HamPSI}$ is faster than the GC-based system for distance threshold
$d_{\mathsf{H}}\leq 32$.

Application Benchmark: We use Iris recognition as an application of
$\mathsf{HamPSI}$ in a setting where the input vectors are long, while the
distance threshold is small. In this setting, Alice and Bob have sets
comprising 100 images of irises and want to learn if they have common
elements. The iris data is collected from the CASIA
dataset777http://www.cbsr.ia.ac.cn/english/IrisDatabase.asp. An open source
tool is used to extract features from the dataset and compute 6000-bit long
binary vectors corresponding to the
items888https://github.com/mvjq/IrisRecognition.

To privately compare a single pair of vectors, the garbled circuit based
solution requires around 300KB of communication. With sets of size 100, the
total communication required is around 3GB. The communication cost mainly
depends on the vector length and is not affected by the distance threshold.
For $\mathsf{HamPSI}$, with a threshold $d_{\mathsf{H}}=20$, we are able to
retrieve all the matches with communication cost 2.5$\times$ and $1.3\times$
lower than the garbled circuit baseline with $\textsc{tnr}=0.9$ and
$\textsc{tnr}=0.95$ respectively.

####  6.1.2 Comparison with Uzun et al. [32]

We have compared with the Hamming query protocol by Uzun et al. [32]. Their
protocol has two components: an application-specific sub-sampling procedure
that reduces bio-identifiers (e.g., bit vectors derived from facial features)
to sets of high-dimensional items, and a $t$-out-of-$T$ matching protocol. The
purpose of our comparison is to show that our set reconciliation protocol is
more efficient than the FHE-based $t$-out-of-$T$ protocol of Uzun et al. [32].
In this way, the comparison is independent of the sub-sampling procedure,
which can change based on the application.

Unfortunately, since we are unable to obtain their code999The authors declined
to provide the code for their implementation and instead recommended that we
run our experiments on the same platform and compare our results to those
reported in their paper., and compute results of their $t$-out-of-$T$ matching
protocol in isolation, for a fair comparison we use their sub-sampling
procedure on top of $\mathsf{OneSidedSetRecon}$ and compare the overall times.
This poses a challenge since the sub-sampling procedure outputs sets of sub-
vectors, we cannot directly apply $\mathsf{HamPSI}$ which takes bit vectors as
inputs. To overcome this problem we have compared their protocol with
$\mathsf{HamPSISample}$ (Sec. 4.3, App. E) with their sub-sampling procedure
replacing the mapping procedure. We stress that resorting to
$\mathsf{HamPSISample}$ (vs. $\mathsf{HamPSI}$) is simply to enable comparison
to Uzun et al. [32] without their code. To implement a client-server
containment query (as in [32]), Alice’s input (client) is a singleton set
$\\{\vec{a}\\}$ while Bob’s input is
$B:=\\{\vec{b}_{1},\ldots,\vec{b}_{n}\\}$. Alice’s compute cost is
$\operatorname{O}\mathopen{}\left(\binom{T}{t}\right)\mathclose{}$ where
$T,~{}t$ are parameters of the sub-sampling procedure. When $T=64$ and $t=2$
[32], this cost is practically feasible.

$0$$20$$40$$60$$80$$100$$0$$50$$100$$150$$200$Distance ThresholdTotal Comm.
(in MB.)$\mathsf{IntPSI}$ 1kDA Baseline 1k$\mathsf{IntPSI}$ 10kDA Baseline 10k
(a) Comm vs. threshold.

020406080100$0.2$$0.4$$0.6$$0.1$$0.2$$0.2$$0.2$$0.2$$0.2$$0.1$$0.3$$0.4$$0.4$$0.5$$0.6$Distance
ThresholdTime (in sec)$\mathsf{IntPSI}$DA Baseline (b) Compute time vs.
threshold

$0$$20$$40$$60$$80$$100$$120$$140$$0$$100$$200$$300$$400$Distance
ThresholdTotal Comm. (in MB.)$\mathsf{IntPSI}$DA Baseline (c) Comm vs.
threshold

041664128$2.5$$3$$3.5$$4$Distance ThresholdTime (in ms, log
scale)$\mathsf{IntPSI}$DA Baseline (d) Compute time vs. threshold

Figure 13: Benchmarks for $\mathsf{IntPSI}$. Fig. 13a and Fig. 13b are
microbenchmarks with set sizes = 1k, 10k. The communication volume for
$\mathsf{IntPSI}$ is roughly $\mathbf{13\times}$ less than the baseline for
threshold = 100. Compute time is $\mathbf{3\times}$ less due to smaller
augmented set sizes. Fig. 13c and Fig. 13d are benchmaks when
$\mathsf{IntPSI}$ is applied to the task of private collaborative
blacklisting. Set size = 25k. The communication volume and compute time for
$\mathsf{IntPSI}$ are both around $\mathbf{10\times}$ less than the baseline
when threshold = 128.

Dataset: The dataset used for bechmarking by Uzun et al. [32] is a set of
synthetically generated (by a generative network) images of human faces. Since
biometric authentication/face recognition is not our focus, we opted to use a
dataset with randomly generated bit vectors matching the parameters in [33].
Specifically, we generated sets of varying sizes containing bit-vectors of
length $\mathcal{\ell}$ = 256, and then sub-sampled these bit vectors using
the algorithm used by Uzun et al. [32] to generate corresponding sets of size
$T=64$.

Results for High-Resource Setup: As recommended by the authors of [32], we
have used our high resource setup when comparing our protocol with their
protocol. Table 2 reports results of the comparison. The numbers for the
protocol of Uzun et al. [32] correspond to a setup without load-balancing the
dataset on the server, and so our results report the worst-case performance
for both protocols. Load balancing can be applied to our protocol to improve
performance; however, since it is unlikely to show improvements with randomly
generated vectors, we omit this optimization.

Set size $n$ |  10$\mathrm{K}$ |  |  100$\mathrm{K}$ |  |  1$\mathrm{M}$
---|---|---|---|---|---
Measure | Comm | Comp |  | Comm | Comp |  | Comm | Comp
$\mathsf{HamPSISample}$ | 25.8MB | 4.00s |  | 220MB | 11.0s |  | 1504MB | 130s
Uzun et al. [32] | 72.0MB | 2.12s |  | 528MB | 17.8s |  | 2124MB | 189s
Table 2: Comparison of communication and computation costs of
$\mathsf{HamPSISample}$ (App. E) with Uzun et al. [32].

Our protocol outperforms the protocol of Uzun et al. [32] for sets containing
up to 1 million elements. The improvement is the result of using a
communication-efficient VOLE protocol over fully homomorphic encryption. For
instance, the amortized communication cost of performing a single oblivious
linear evaluation as part of the VOLE protocol, i.e., computing a single value
$\vec{z}[m]:=\vec{u}[m]x+\vec{v}[m]\in{\mathbb{F}_{p}}$ (see the definition of
$\mathcal{F}^{p}_{\mathit{vole}}$) for some $m\in[1,n]$, is roughly 3 bits
[37]. When applied to the set containing 10$\mathrm{K}$ elements, we require
1.2 million correlations. The total communication cost is 3.6 million bits, or
450$\mathrm{KB}$. In addition, we need to transfer a field element in
plaintext to convert each pseudorandom VOLE correlation (as provided by Weng
et al. [37]), to a correlation with the desired parameters. The total cost is
$2.8\times$ less than the cost of the protocol of Uzun et al. [32].

Compute costs are also lower due to the use of cheaper symmetric-key
primitives in our protocol over fully homomorphic encryption. The only
exception is for the set containing 10$\mathrm{K}$ elements since the VOLE
protocol requires a setup time. For small sets, we still incur the setup time
while not fully utilizing all the usable oblivious linear evaluations.

Set size $n$ |  10$\mathrm{K}$ |  |  100$\mathrm{K}$ |  |  1$\mathrm{M}$
---|---|---|---|---|---
Party | Alice | Bob |  | Alice | Bob |  | Alice | Bob
$\mathsf{HamPSISample}$ | 11.4s | 1.20s |  | 24.3s | 2.80s |  | 145.3s | 3.50s
Table 3: Compute costs of $\mathsf{HamPSISample}$ (App. E) on an Amazon
t2.xlarge instance.

Results for Low-Resource Setup: The high-resource setup used by Uzun et al.
[32] is necessary for the compute-intensive tasks in their FHE-based scheme.
In fact, Table 8 of Uzun et al. [32] shows that deploying the system with 72
threads utilizing all the available vCPUs leads to a $32.4\times$ speed up
compared to a single-threaded deployment. Unlike their setting, PSI settings
are often symmetrically provisioned and have more modest configurations. We
demonstrate feasibility of our protocol even on low-resource platforms. And
while we are unable to compute the actual costs of running the protocol of
Uzun et al. [32] on the same platform, we posit that their compute costs would
be significantly higher on low-resource systems due to the inherent cost of
FHE.

Table 3 shows the compute times of our protocol on the low-resource platform
described before. The communication costs remain the same as the ones
presented in Table 2 and therefore we omit the results. Bob only participates
in the VOLE protocol and therefore has no other compute costs. As is evident,
the cost of our protocol on a low resource environment is similar to the
performance on the over-provisioned system. The use of a cheap symmetric key
primitive, namely VOLE, ensures that Bob’s online compute times are low (less
than 4s for databases containing up to 1$\mathrm{M}$ elements). The majority
of Alice’s time is spent on local computation which can be further optimized
by leveraging parallel processing.

###  6.2 Integer Distance Protocol

Implementation: The integer distance-aware protocol (or $\mathsf{IntPSI}$ in
short) is implemented as a two step process in C++. First both parties augment
their sets using Algorithm 1 (in App. F). These augmented sets are used as
inputs to the OT-based PSI protocol due to Pinkas et al. [27]. We rely on an
open-source implementation101010https://github.com/encryptogroup/PSI. We note
that $\mathsf{IntPSI}$ can be instantiated with any traditional PSI protocol
of choice, and both communication volume and compute times are expected to
show similar trends.

Micro-benchmarks: We run micro-benchmarks with sets containing 1k and 10k
elements each, randomly sampled from the space of non-negative (32 bit)
integers. We evaluate how the communication and overall compute time of the
protocol scales with the distance threshold and set size. The baseline is the
protocol due to Pinkas et al. [27] where we augment the input sets with items
in the neighborhood of each item in the set based on the threshold. Here, the
augmented set size is expected to scale linearly with the distance threshold.
This is called the “DA Baseline" in our experiments.

  * •

Comm. volume vs. threshold: Fig. 13a shows how the communication volume scales
with the distance threshold. The communication costs of $\mathsf{IntPSI}$
scale logarithmically, and so with distance threshold $100$, the communication
volume is $12.5\times$ less than the baseline for set size 10$\mathrm{K}$.

  * •

Compute time vs. threshold: Fig. 13b shows how compute time scales with the
distance threshold. Due to smaller set sizes to compute on, $\mathsf{IntPSI}$
compute time is $3\times$ lower than the baseline when the threshold is 100.

Application Benchmark: To further explore realistic parameter settings, as a
real-world application of $\mathsf{IntPSI}$, we return to the problem of
private collaborative blacklisting where two mutually-untrusting parties
compare IP addresses of end-points from where they have observed traffic to
their own network. This task is usually performed with a PSI protocol [22].
Replacing this with a DA-PSI protocol enables us to find IP addresses that are
common to both sets, as well as find addresses that are “close” in the address
space. A distance-based comparison is meaningful here because it is well-know
that coordinated attacks usually span multiple subnets [38, 4].

Dataset: To test this application, we have collected data from a public
honeypot deployed in a university network. The honeypot logs all incoming and
outgoing traffic and stores a wealth of information. From this data, we curate
information about traffic observed on two separate days, and build sets with
the source IP addresses. There are roughly 25,000 distinct IP addresses in
each set. These sets are inputs to $\mathsf{IntPSI}$ and the baseline PSI
protocol.

We observe that using a distance-aware intersection in this context is well-
justified based on the results. The number of intersections increases
significantly when increasing the search radius and almost doubles by the time
we reach the threshold of $128$. In actual numbers, there are around 5% exact
matches between the two sets. With a distance based search over thresholds of
$2,\ldots 128$ we find that the number of items in the intersection increase
to more than 10%. By searching over larger threshold, we are able to obtain
matching IP addresses that fall in the same subnet/adjoining subnets. Note
that without a full subnet map, it is not possible to predict these subnet
sizes a priori. Therefore, we envision running the protocol multiple times
with different thresholds to obtain the most informative intersection.

Results: Figs. 13c–13d show how the overall communication volume and compute
time scale with distance thresholds set to $2,\ldots,128$. The intuition
behind increasing the threshold in powers of two is that we would like to
search over entire subnets and find potential overlaps (if any). In terms of
the overall runtime we observe that $\mathsf{IntPSI}$ scales more gracefully
with the distance threshold. Note that with threshold set at $128$, the
baseline protocol computes over sets of size exceeding 6 million, while
$\mathsf{IntPSI}$ computes over sets of size of around 200,000. This
difference results in a significant speedup. With threshold = 128,
$\mathsf{IntPSI}$ requires only 1.5 seconds to compute the intersection while
the baseline requires over 15 seconds to accomplish the same task.

##  7 Conclusion

In this paper, we introduced the distance-aware PSI problem over metric
spaces, whereby parties privately compute an intersection of their respective
sets with items that are “close” in the metric space ending up in the
intersection. Closeness is defined based on a user-specified distance
threshold in the metric space. As concrete instantiations, we provided
distance-aware constructions for two metric spaces: Minkowski distance of
order 1 over the integers and Hamming distance. Both the protocols are
communication-efficient. As a practical application of this idea, we evaluated
the Minkowski distance protocol in the context of collaborative blacklisting.
In addition, the Hamming distance-aware protocol allows constructions for
other distances using techniques like locality-sensitive hashing.

##  8 Acknowledgments

This research was supported in part by grant numbers 2040675, Convergence
Accelerator award 2040675 and CIF-1705007 from the National Science
Foundation, and W911NF-17-1-0370 from the Army Research Office. This work was
also made possible by the support of JP Morgan Chase, the Sloan Foundation,
Siemens AG, and Cisco. The views and conclusions in this document are those of
the authors and should not be interpreted as representing the official
policies, either expressed or implied, of the National Science Foundation,
Army Research Office, or the U.S. Government.

## References

  * Badrinarayanan et al. [2021] Saikrishna Badrinarayanan, Peihan Miao, Srinivasan Raghuraman, and Peter Rindal.  Multi-party threshold private set intersection with sublinear communication.  In _24 th International Conference on Practice and Theory of Public Key Cryptography_, volume 12711 of _Lecture Notes in Computer Science_ , pages 349–379, 2021.
  * Canetti et al. [2021] Ran Canetti, Benjamin Fuller, Omer Paneth, Leonid Reyzin, and Adam Smith.  Reusable fuzzy extractors for low-entropy distributions.  _Journal of Cryptology_ , 34(1):1–33, 2021.
  * Chase and Miao [2020] Melissa Chase and Peihan Miao.  Private set intersection in the internet setting from lightweight oblivious prf.  In _Advances in Cryptology – CRYPTO 2020_ , volume 12172 of _Lecture Notes in Computer Science_ , pages 34–63, 2020.
  * Collins et al. [2007] M. Patrick Collins, Timothy J. Shimeall, Sidney Faber, Jeff Janies, Rhiannon Weaver, Markus De Shon, and Joseph Kadane.  Using uncleanliness to predict future botnet addresses.  In _7 th ACM Conference on Internet Measurement_, October 2007.  doi: 10.1145/1298306.1298319.  URL https://doi.org/10.1145/1298306.1298319.
  * Datar et al. [2004] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni.  Locality-sensitive hashing scheme based on p-stable distributions.  In _20 th Symposium on Computational Geometry_, page 253–262, 2004.  doi: 10.1145/997817.997857.  URL https://doi.org/10.1145/997817.997857.
  * Daugman [2009] John Daugman.  Chapter 25 - how iris recognition works.  In Al Bovik, editor, _The Essential Guide to Image Processing_ , pages 715–739. Academic Press, Boston, 2009.  ISBN 978-0-12-374457-9.  doi: https://doi.org/10.1016/B978-0-12-374457-9.00025-1.  URL https://www.sciencedirect.com/science/article/pii/B9780123744579000251.
  * De Cristofaro et al. [2010] E. De Cristofaro, J. Kim, and G. Tsudik.  Linear-complexity private set intersection protocols secure in malicious model.  In _Advances in Cryptology – ASIACRYPT 2010_ , volume 6477 of _Lecture Notes in Computer Science_ , 2010.
  * Dodis et al. [2004] Yevgeniy Dodis, Leonid Reyzin, and Adam Smith.  Fuzzy extractors: How to generate strong keys from biometrics and other noisy data.  In _International conference on the theory and applications of cryptographic techniques_ , pages 523–540. Springer, 2004.
  * Freedman et al. [2004] Michael J. Freedman, Kobbi Nissim, and Benny Pinkas.  Efficient private matching and set intersection.  In _Advances in Cryptology – EUROCRYPT 2004_ , volume 3027 of _Lecture Notes in Computer Science_ , pages 1–19, 2004.
  * Ghosh and Simkin [2019] Satrajit Ghosh and Mark Simkin.  The communication complexity of threshold private set intersection.  In _Advances in Cryptology – CRYPTO 2019_ , volume 11693 of _Lecture Notes in Computer Science_ , pages 3–29, 2019.
  * Gionis et al. [1999] Aristides Gionis, Piotr Indyk, and Rajeev Motwani.  Similarity search in high dimensions via hashing.  In _25 th International Conference on Very Large Data Bases_, page 518–529, 1999.
  * Groce et al. [2019] Adam Groce, Peter Rindal, and Mike Rosulek.  Cheaper private set intersection via differentially private leakage.  _Proceedings on Privacy Enhancing Technologies_ , 2019:25–6, 2019.
  * Huang et al. [2006] Wei Huang, Yaoyun Shi, Shengyu Zhang, and Yufan Zhu.  The communication complexity of the hamming distance problem.  _Information Processing Letters_ , 99(4), 2006.  doi: https://doi.org/10.1016/j.ipl.2006.01.014.  URL https://www.sciencedirect.com/science/article/pii/S002001900600072X.
  * Huang et al. [2011] Yan Huang, David Evans, Jonathan Katz, and Lior Malka.  Faster secure two-party computation using garbled circuits.  In _20 th USENIX Security Symposium_, 2011.
  * Ion et al. [2019] Mihaela Ion, Ben Kreuter, Ahmet Erhan Nergiz, Sarvar Patel, Mariana Raykova, Shobhit Saxena, Karn Seth, David Shanahan, and Moti Yung.  On deploying secure computing: Private intersection-sum-with-cardinality.  Cryptology ePrint Archive, Report 2019/723, 2019.  https://eprint.iacr.org/2019/723.
  * Kacsmar et al. [2020] Bailey Kacsmar, Basit Khurram, Nils Lukas, Alexander Norton, Masoumeh Shafieinejad, Zhiwei Shang, Yaser Baseri, Maryam Sepehri, Simon Oya, and Florian Kerschbaum.  Differentially private two-party set operations.  In _2020 IEEE European Symposium on Security and Privacy_ , pages 390–404, September 2020.  doi: 10.1109/EuroSP48549.2020.00032.
  * Kalyanasundaram and Schintger [1992] Bala Kalyanasundaram and Georg Schintger.  The probabilistic communication complexity of set intersection.  _Journal on Discrete Mathematics_ , 5(4):545–557, 1992.
  * Kissner and Song [2005] Lea Kissner and Dawn Song.  Privacy-preserving set operations.  In _Advances in Cryptology – CRYPTO 2005_ , volume 3621 of _Lecture Notes in Computer Science_ , page 241–257, 2005.  doi: 10.1007/11535218_15.  URL https://doi.org/10.1007/11535218_15.
  * Larkin [1967] F. M. Larkin.  Some techniques for rational interpolation.  _The Computer Journal_ , 10(2):178–187, 1967\.
  * Manku et al. [2007] Gurmeet Singh Manku, Arvind Jain, and Anish Das Sarma.  Detecting near-duplicates for web crawling.  In _16 th International Conference on the World Wide Web_, pages 141–150, May 2007.  ISBN 9781595936547.  doi: 10.1145/1242572.1242592.  URL https://doi.org/10.1145/1242572.1242592.
  * Meadows [1986] Catherine Meadows.  A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party.  In _IEEE Symposium on Security and Privacy_ , 1986.  doi: 10.1109/SP.1986.10022.
  * Melis et al. [2019] Luca Melis, Apostolos Pyrgelis, and Emiliano De Cristofaro.  On collaborative predictive blacklisting.  _ACM SIGCOMM Computer Communication Review_ , 48(5), January 2019.  ISSN 0146-4833.  doi: 10.1145/3310165.3310168.  URL https://doi.org/10.1145/3310165.3310168.
  * Minsky et al. [2003] Y. Minsky, A. Trachtenberg, and R. Zippel.  Set reconciliation with nearly optimal communication complexity.  _IEEE Transactions on Information Theory_ , 49(9):2213–2218, 2003.  doi: 10.1109/TIT.2003.815784.
  * Mohammadi-Kambs et al. [2017] Mina Mohammadi-Kambs, Kathrin Hölz, Mark Somoza, and Albrecht Ott.  Hamming distance as a concept in dna molecular recognition.  _ACS Omega_ , 2(4):1302–1308, April 2017.  doi: 10.1021/acsomega.7b00053.
  * Osadchy et al. [2010] Margarita Osadchy, Benny Pinkas, Ayman Jarrous, and Boaz Moskovich.  Scifi - a system for secure face identification.  In _31 st IEEE Symposium on Security and Privacy_, 2010.  doi: 10.1109/SP.2010.39.
  * Pinkas et al. [2015] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner.  Phasing: Private set intersection using permutation-based hashing.  In _24 th USENIX Security Symposium_, pages 515–530, August 2015.
  * Pinkas et al. [2018] Benny Pinkas, Thomas Schneider, and Michael Zohner.  Scalable private set intersection based on ot extension.  _ACM Transactions on Privacy and Security_ , 21(2), January 2018.  ISSN 2471-2566.  doi: 10.1145/3154794.  URL https://doi.org/10.1145/3154794.
  * Pinkas et al. [2019] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai.  Spot-light: Lightweight private set intersection from sparse ot extension.  In Alexandra Boldyreva and Daniele Micciancio, editors, _Advances in Cryptology – CRYPTO 2019_ , pages 401–431, Cham, 2019. Springer International Publishing.
  * Pinkas et al. [2020] Benny Pinkas, Mike Rosulek, Ni Trieu, and A. Yanai.  Psi from paxos: Fast, malicious private set intersection.  In _Advances in Cryptology -– EUROCRYPT 2020_ , volume 12106 of _Lecture Notes in Computer Science_ , pages 739–767, 2020.
  * Raginsky and Lazebnik [2009] Maxim Raginsky and Svetlana Lazebnik.  Locality-sensitive binary codes from shift-invariant kernels.  In _22 nd International Conference on Neural Information Processing Systems_, page 1509–1517, 2009.
  * Steffensen [1939] J.F. Steffensen.  Note on divided differences =.  Mathematisk-fysiske Meddelelser. XVII, 3, 1939.  http://gymarkiv.sdu.dk/MFM/kdvs/mfm%2010-19/mfm-17-3.pdf.
  * Uzun et al. [2021a] Erkam Uzun, Simon P Chung, Vladimir Kolesnikov, Alexandra Boldyreva, and Wenke Lee.  Fuzzy labeled private set intersection with applications to private $\\{$Real-Time$\\}$ biometric search.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pages 911–928, 2021a.
  * Uzun et al. [2021b] Erkam Uzun, Carter Yagemann, Simon Chung, Vladimir Kolesnikov, and Wenke Lee.  Cryptographic key derivation from biometric inferences for remote authentication.  In _Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security_ , pages 629–643, 2021b.
  * Wang and Reiter [2019] K. C. Wang and M. K. Reiter.  How to end password reuse on the web.  In _26 th ISOC Network and Distributed System Security Symposium_, February 2019.
  * Wang and Reiter [2020] K. C. Wang and M. K. Reiter.  Detecting stuffing of a user’s credentials at her own accounts.  In _29 th USENIX Security Symposium_, August 2020\.
  * Wang et al. [2015] Xiao Shaun Wang, Yan Huang, Yongan Zhao, Haixu Tang, XiaoFeng Wang, and Diyue Bu.  Efficient genome-wide, privacy-preserving similar patient query based on private edit distance.  In _22 nd ACM Conference on Computer and Communications Security_, October 2015.  doi: 10.1145/2810103.2813725.  URL https://doi.org/10.1145/2810103.2813725.
  * Weng et al. [2021] Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang.  Wolverine: Fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits.  In _2021 IEEE Symposium on Security and Privacy (SP)_ , 2021.
  * West et al. [2010] Andrew G. West, Adam J. Aviv, Jian Chang, and Insup Lee.  Spam mitigation using spatio-temporal reputations from blacklist history.  In _26 th Annual Computer Security Applications Conference_, 2010.  ISBN 9781450301336.  doi: 10.1145/1920261.1920287.  URL https://doi.org/10.1145/1920261.1920287.

##  Appendix A Difference Between $t\mathsf{PSI}$ and
$\mathsf{OneSidedSetRecon}$

This section highlights the differences between $t\mathsf{PSI}$ [10, Fig. 10]
and $\mathsf{OneSidedSetRecon}$ (Fig. 3). For this we present the
$t\mathsf{PSI}$ set reconciliation protocol in Fig. 14. The protocol requires
two sets of calls to $\mathcal{F}^{p}_{\mathit{ole}}$ in Steps 5 and 6. It
also requires two additional rounds of communication in Steps 7 and 8. These
steps are required so that both Alice and Bob can obtain the evaluations of
$R_{1}(x)P(x)+R_{2}(x)Q(x)$ in Steps 9 and 10. More specifically,
$s_{\mathsf{A}}(x_{k}),s^{\prime}_{\mathsf{A}}(x_{k})$ and
$s_{\mathsf{B}}(x_{k}),s^{\prime}_{\mathsf{B}}(x_{k})$ are "blinded" shares of
$R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})$ with Alice’s and Bob’s inputs
respectively. Alice and Bob exchange these shares to finally obtain
$R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})$ in Steps 9 and 10.

$\mathsf{OneSidedSetRecon}$ avoids Steps 6 – 8 by allowing only Alice to
obtain the evaluations of $R_{1}(x)P(x)+R_{2}(x)Q(x)$. while Bob generates all
the random polynomials required in the protocol. Therefore, we do not need to
generate "blinded" shares as above. As a result, $\mathsf{OneSidedSetRecon}$
is not only significantly simpler but also avoids one set of
$\mathcal{\ell}+2d_{\mathsf{H}}+1$ of calls to
$\mathcal{F}^{p}_{\mathit{ole}}$ and two rounds of communication.

Parameters: Alice and Bob have sets $S_{\vec{a}}$ and $S_{\vec{b}}$,
$\left|{S_{\vec{a}}}\right|=\left|{S_{\vec{b}}}\right|=\mathcal{\ell}$
respectively and a set difference threshold $d_{\mathsf{H}}$. Procedure Noisy
Polynomial Addition: (1) Alice and Bob select a set of
$\mathcal{\ell}+d_{\mathsf{H}}+2$ points in ${\mathbb{F}_{p}}$
$X:=\\{x_{k}\\}_{k=1}^{\mathcal{\ell}+2d_{\mathsf{H}}+1}$ such that none of
the points are in the ranges of any of the mapping functions. (2) Alice
encodes $S_{\vec{a}}$ in the polynomial $P(x)$ = $\prod\limits_{r\in
S_{\vec{a}}}(x-r)$ and Bob encodes $S_{\vec{b}}$ in the polynomial $Q(x)$ =
$\prod\limits_{r\in S_{\vec{b}}}(x-r)$. (3) Alice picks two random polynomials
of degree $\mathcal{\ell}$,
$R_{1}^{\mathsf{A}},R_{2}^{\mathsf{A}}\in{\mathbb{F}_{p}}[x]$ and a degree
$2\mathcal{\ell}$ polynomial $U_{\mathsf{A}}\in{\mathbb{F}_{p}}[x]$. (4) Bob
picks two random polynomials of degree $\mathcal{\ell}$,
$R_{1}^{\mathsf{B}},R_{2}^{\mathsf{B}}\in{\mathbb{F}_{p}}[x]$ and a degree
$2\mathcal{\ell}$ polynomial $U_{\mathsf{B}}\in{\mathbb{F}_{p}}[x]$. (5) For
each $x_{k}\in X$, Alice sends $P(x_{k})$ to $\mathcal{F}^{p}_{\mathit{ole}}$.
Bob sends $R_{1}^{\mathsf{B}}(x_{k})$ and $U_{\mathsf{B}}(x_{k})$ to
$\mathcal{F}^{p}_{\mathit{ole}}$. Alice receives
$s_{\mathsf{A}}(x_{k}):=P(x_{k})R_{1}^{\mathsf{B}}(x_{k})+U_{\mathsf{B}}(x_{k})$.
(6) For each $x_{k}\in X$, Bob sends $Q(x_{k})$ to
$\mathcal{F}^{p}_{\mathit{ole}}$. Alice sends $R_{1}^{\mathsf{A}}(x_{k})$ and
$U_{\mathsf{A}}(x_{k})$ to $\mathcal{F}^{p}_{\mathit{ole}}$. Alice receives
$s_{\mathsf{B}}(x_{k}):=Q(x_{k})R_{1}^{\mathsf{A}}(x_{k})+U_{\mathsf{A}}(x_{k})$.
(7) For each $x_{k}\in X$ Alice sends to Bob
$s^{\prime}_{\mathsf{A}}(x_{k}):=s_{\mathsf{A}}(x_{k})+P(x_{k})\cdot
R_{1}^{\mathsf{A}}(x_{k})-U_{\mathsf{A}}(x_{k})$. (8) For each $x_{k}\in X$
Bob sends to Bob
$s^{\prime}_{\mathsf{B}}(x_{k}):=s_{\mathsf{B}}(x_{k})+Q(x_{k})\cdot
R_{1}^{\mathsf{B}}(x_{k})-U_{\mathsf{B}}(x_{k})$. (9) Alice outputs the
evaluation points of
$W_{A}(x_{k}):=s_{\mathsf{A}}(x_{k})+s^{\prime}_{\mathsf{B}}(x_{k})+P(x_{k})R_{1}^{\mathsf{A}}(x_{k})-U_{\mathsf{A}}(x_{k})=R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})$.
$V_{\mathsf{A}}:=\\{(x_{k},y_{k}):y_{k}:=\frac{W_{A}(x_{k})}{P(x_{k})}=\frac{R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})}{P(x_{k})}\\}$.
(10) Bob outputs the evaluation points of
$W_{B}(x_{k}):=s_{\mathsf{B}}(x_{k})+s^{\prime}_{\mathsf{A}}(x_{k})+Q(x_{k})R_{1}^{\mathsf{B}}(x_{k})-U_{\mathsf{B}}(x_{k})=R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})$.
$V_{\mathsf{B}}:=\\{(x_{k},y_{k}):y_{k}:=\frac{W_{B}(x_{k})}{Q(x_{k})}=\frac{R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})}{P(x_{k})}\\}$.
Procedure Interpolation: Alice interpolates $V_{\mathsf{A}}$ with a rational
function similar to $\mathsf{OneSidedSetRecon}$. Bob $V_{\mathsf{B}}$ with a
rational function similar to $\mathsf{OneSidedSetRecon}$. The rest of the
steps are the same as $\mathsf{OneSidedSetRecon}$; Alice and Bob output
$S_{\vec{a}}\setminus S_{\vec{b}}$ and $S_{\vec{b}}\setminus S_{\vec{a}}$
respectively. Figure 14: $t\mathsf{PSI}$ set reconciliation protocol [10].

##  Appendix B Proofs of Propositions

###  B.1 Lemma for Polynomials in ${\mathbb{F}_{p}}[x]$

######  Lemma 2.

Let $X$ be a set of distinct arbitrary values $x_{i}\in{\mathbb{F}_{p}}$. Let
$V$ be a set of random points where each point
$v_{i}=(x_{i},y_{i}),y_{i}\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}$.
Then, the probability that there exists polynomial
$Q(x)\in{\mathbb{F}_{p}}[x]$ that satisfies all points in $V$ with
$\mathbf{deg}\mathopen{}\left(Q\right)\mathclose{}\leq D<\left|{V}\right|$ is
$1/p^{\left|{V}\right|-D-1}$.

###### Proof.

Let $V^{*}$ be the combined set of all sets $V=\\{(x_{k},y_{k}):x_{k}\in
X,y_{k}\in{\mathbb{F}_{p}}\\}$. Then, $|V^{*}|=p^{\left|{V}\right|}$. Each
$V_{i}\in V^{*}$ is consistent with at most one polynomial of degree $\leq D$.
Otherwise, there will be two or more polynomials of degree $\leq D$ passing
through the same $\left|{V}\right|$ points, which contracts the fact that any
$D+1\leq\left|{V}\right|$ points uniquely defines a polynomial of degree $\leq
D$

Let $P^{*}$ be the set of all polynomials of degree $\leq D$. Clearly,
$|P^{*}|=p^{D+1}$. Each $P_{i}\in P^{*}$ is consistent with exactly one
$V_{j}\in V^{*}$. Thus, the mapping from $P^{*}$ to $V^{*}$ is injective. Then
the probability that $V\in V^{*}$ is satisfied by a polynomial
$Q(x)\in{\mathbb{F}_{p}}[x]$ of degree
$\mathbf{deg}\mathopen{}\left(Q\right)\mathclose{}\leq D$ is given by the
probability that $V$ has a pre-image in the injective map which is
$1/p^{\left|{V}\right|-D-1}$. ∎

###  B.2 Proof of Theorem 1

To prove the propositions in the theorem, we will define an IND-CPA style
security game between an adversary $\mathcal{A}$ and a challenger
$\mathcal{C}$.

  1. (1)

$\mathcal{A}$ selects a threshold $d_{\mathsf{H}}\in(0,\mathcal{\ell}/2)$,
three sets $S_{P}$, $S_{Q0}$ and $S_{Q1}$ with
$\left|{S_{Q0}}\right|=\left|{S_{Q1}}\right|=\left|{S_{P}}\right|=\mathcal{\ell}$,
such that

$|S_{P}\cap S_{Q0}|=|S_{P}\cap S_{Q1}|=d_{\mathsf{GCD}}$, and
$X:=\\{x_{k}:x_{k}\in{\mathbb{F}_{p}}\\}_{k=1}^{\mathcal{\ell}+2d_{\mathsf{H}}+1}$
such that $x_{k}\notin S_{P},S_{Q0},S_{Q1}$.

  2. (2)

$\mathcal{C}$ samples two random polynomials
$R_{1}(x),R_{2}(x)\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}[x]$ of
degree $\mathcal{\ell}$, and derives $P_{c}(x)$ $:=$ $\prod\limits_{r\in
S_{P}}(x-r)$.

  3. (3)

$\mathcal{C}$ flips a random bit $b$ and based on outcome derives $Q_{b}(x)$
$:=$ $\prod\limits_{r\in S_{Qb}}(x-r)$, and computes
$V=\\{(x_{k},y_{k}):x_{k}\in
X,y_{k}=R_{1}(x_{k})P_{c}(x_{k})+R_{2}(x_{k})Q_{b}(x_{k})\\}$. $\mathcal{C}$
returns $V$ to $\mathcal{A}$.

  4. (4)

$\mathcal{A}$ outputs $b^{\prime}$ and wins the game if $b^{\prime}=b$.

######  Proposition 1.

For $b\in[0,1]$, if $|S_{P}\setminus
S_{Qb}|=\mathcal{\ell}-d_{\mathsf{GCD}}\geq 2d_{\mathsf{H}}$, then
$\mathbb{P}\left[b^{\prime}=b\right]$ $\leq
1/2+\mathbf{negl}\mathopen{}\left(\lambda\right)\mathclose{}$ for any
adversary $\mathcal{A}$.

###### Proof.

We will show that the probability of obtaining an arbitrary set of points $V$
in Step 5 of the security game is the same for the case when $b$ = 0 as the
case $b$ = 1. For this, consider the polynomial
$Q_{b}(x)R_{1}(x)+P_{c}(x)R_{2}(x)=\mathbf{gcd}\mathopen{}\left(P_{c}(x),Q_{b}(x)\right)\mathclose{}\times
R(x)$ where $R(x)$ is a random polynomial of degree
$2\mathcal{\ell}-d_{\mathsf{GCD}}$ due to Lemma 1. The evaluations of this
polynomial generates $V$.

If $b=0$, $R(x)$ is a degree $2\mathcal{\ell}-d_{\mathsf{GCD}}$ polynomial
that is consistent with the set of points
$\\{(x_{k},y^{\prime}_{k}):y^{\prime}_{k}=\frac{y_{k}}{C_{O}(x_{k})},~{}(x_{k},y_{k})\in
V\\}$ where
$C_{0}(x):=\mathbf{gcd}\mathopen{}\left(P_{c}(x),Q_{0}(x)\right)\mathclose{}$.
A degree $2\mathcal{\ell}-d_{\mathsf{GCD}}$ polynomial in
${\mathbb{F}_{p}}[x]$ is uniquely defined by
$2\mathcal{\ell}-d_{\mathsf{GCD}}+1$ points. Since, $R(x)$ is consistent with
the aforementioned set of points,
$\left|{V}\right|=\mathcal{\ell}+2d_{\mathsf{H}}+1$ points required to define
$R(x)$ are fixed. Thus, there are
$p^{(2\mathcal{\ell}-d_{\mathsf{GCD}}+1)-(\mathcal{\ell}+2d_{\mathsf{H}}+1)=p^{\mathcal{\ell}-(2d_{\mathsf{H}}+d_{\mathsf{GCD}})}}$
candidate polynomials for $R(x)$. Let $S_{0}$ be the set comprising these
polynomials.

Similarly, if $b=1$, $R(x)$ is one of the
$p^{\mathcal{\ell}-(2d_{\mathsf{H}}+d_{\mathsf{GCD}})}$ polynomials of degree
$\leq 2\mathcal{\ell}-d_{\mathsf{GCD}}$ consistent with the set of points
$\\{(x_{k},y^{\prime}_{k}):y^{\prime}_{k}=\frac{y_{k}}{C_{1}(x_{k})},~{}(x_{k},y_{k})\in
V\\}$ where
$C_{1}(x):=\mathbf{gcd}\mathopen{}\left(P_{c}(x),Q_{1}(x)\right)\mathclose{}$.
Let $S_{1}$ be the set comprising these polynomials; note that
$|S_{0}|=|S_{1}|$.

Since $R(x)$ is a uniformly random polynomial of degree
$2\mathcal{\ell}-d_{\mathsf{GCD}}$, the probability of obtaining $V$ when $b$
= 0 is $\mathbb{P}\left[R(x)\in
S_{0}\right]=\frac{p^{\mathcal{\ell}-(2d_{\mathsf{H}}+d_{\mathsf{GCD}})}}{p^{2\mathcal{\ell}-d_{\mathsf{GCD}}+1}}=p^{-(\mathcal{\ell}+2d_{\mathsf{H}}+1)}$.
Similarly, the probability of obtaining $V$ when $b$ = 1 is
$\mathbb{P}\left[R(x)\in
S_{1}\right]=\frac{p^{\mathcal{\ell}-(2d_{\mathsf{H}}+d_{\mathsf{GCD}})}}{p^{2\mathcal{\ell}-d_{\mathsf{GCD}}+1}}=p^{-(\mathcal{\ell}+2d_{\mathsf{H}}+1)}$.
∎

######  Proposition 2.

For $b\in[0,1]$, if $|S_{P}\setminus
S_{Qb}|=\mathcal{\ell}-d_{\mathsf{GCD}}\in(d_{\mathsf{H}},2d_{\mathsf{H}})$,
then there is an adversary $\mathcal{A}$ for which
$\mathbb{P}\left[b^{\prime}=b\right]$ $\geq
1-\mathbf{negl}\mathopen{}\left(\lambda\right)\mathclose{}$.

###### Proof.

W.l.o.g assume that
$Q_{0}(x)R_{1}(x)+P_{c}(x)R_{2}(x)=\mathbf{gcd}\mathopen{}\left(P_{c}(x),Q_{0}(x)\right)\mathclose{}R^{*}_{0}(x)$
and
$Q_{0}(x)R_{1}(x)+P_{c}(x)R_{2}(x)=\mathbf{gcd}\mathopen{}\left(P_{c}(x),Q_{1}(x)\right)\mathclose{}R^{*}_{1}(x)$
are two polynomials consistent with the set of point $V$ in Step 5. Then, we
have $R^{*}_{0}(x)$ is a random polynomial of degree
$2\mathcal{\ell}-d_{\mathsf{GCD}}<\mathcal{\ell}+2d_{\mathsf{H}}$ consistent
with the set of points
$\\{(x_{k},y^{\prime}_{k}):y^{\prime}_{k}=\frac{y}{C_{0}(x_{k})},~{}(x_{k},y_{k})\in
V\\}$ and $R^{*}_{1}(x)$ is a random polynomial of degree
$2\mathcal{\ell}-d_{\mathsf{GCD}}<\mathcal{\ell}+2d_{\mathsf{H}}$ consistent
with the set of points
$\\{(x_{k},y^{\prime}_{k}):y^{\prime}_{k}=\frac{y}{C_{1}(x_{k})},~{}(x_{k},y_{k})\in
V\\}$ where
$C_{0}(x)=\mathbf{gcd}\mathopen{}\left(P_{c}(x),Q_{0}(x)\right)\mathclose{}$
and
$C_{1}(x)=\mathbf{gcd}\mathopen{}\left(P_{c}(x),Q_{1}(x)\right)\mathclose{}$.

From these facts we get that, for
$i\in[1,\mathcal{\ell}+2d_{\mathsf{H}}+1],R^{*}_{1}(x_{k})=R^{*}_{0}(x_{k})\times\frac{C_{0}(x_{k})}{C_{1}(x_{k})}$.
Now, since $R^{*}_{0}(x)$ is a random polynomial, the set of points
$\\{(x_{1},R^{*}_{1}(x_{1})),\ldots,(x_{\mathcal{\ell}+2d_{\mathsf{H}}+1},R^{*}_{1}(x_{\mathcal{\ell}+2d_{\mathsf{H}}+1}))\\}$
is a set of random points. Thus, after fixing $R^{*}_{0}(x)$ when $b$ = 0, the
probability that there exists some $R^{*}_{1}(x)$ consistent with the
aforementioned set of points is
$<\frac{1}{p^{(\mathcal{\ell}+2d_{\mathsf{H}}+1)-(\mathbf{deg}\mathopen{}\left(R^{*}_{1}(x)\right)\mathclose{}-1}}\leq
1/p$ due to Lemma 2. A similar logic holds when $b=1$.

$\mathcal{A}$’s strategy is to output $b^{\prime}=0$ if there exists a
polynomial $R^{*}_{0}(x)$ of degree $<\mathcal{\ell}+2d_{\mathsf{H}}$
consistent with points in $V$. Similarly, $\mathcal{A}$ outputs $b^{\prime}=1$
if there exists some polynomial $R^{*}_{1}(x)$ of degree
$<\mathcal{\ell}+2d_{\mathsf{H}}$ consistent with the set of points $V$. The
probability that $R^{*}_{0}(x)$ and $R^{*}_{1}(x)$ both exist $<1/p$ as shown
above, which is the probability that $b^{\prime}\neq b$. ∎

##  Appendix C Proofs for $t\mathsf{HamQuery}$ (Sec. 4.1.3)

###  C.1 Using EC-Elgamal in $t\mathsf{HamQuery}$

$t\mathsf{HamQueryRestricted}$ uses a additively homomorphic encryption
scheme. In our implementation we use the EC-Elgamal encryption scheme tp
reduce communication costs. For this, the message space should be large enough
to allow the computation in $t\mathsf{HamQueryRestricted}$, and decrypt the
results. We use a 24-bit message space. The computation in
$t\mathsf{HamQueryRestricted}$ broadly involves two steps: i) computing the
Hamming distance between two vectors as follows, and ii) returning a key
$\kappa$ blinded with the result of the Hamming distance computation. First,
consider the mechanism we use to compute the Hamming distances between two
vectors.

######  Lemma 3.

Given two equal length vectors $\vec{a},\vec{b}\in\\{0,1\\}^{\mathcal{\ell}}$,
the Hamming distance between the vectors is given by:

$\delta_{H}(\vec{a},\vec{b})=\left\lVert\vec{a}\right\rVert_{w}+\left\lVert\vec{b}\right\rVert_{w}-2\cdot\vec{a}\cdot\vec{b}$

where $\left\lVert.\right\rVert_{w}$ is the Hamming weight of the input
vector.

###### Proof.

Let $S_{01}=\\{m\in[1,\mathcal{\ell}]~{}:~{}\vec{a}[m]=0,\vec{b}[m]=1\\}$,
$S_{10}=\\{m\in[1,\mathcal{\ell}]~{}:~{}\vec{a}[m]=1,\vec{b}[m]=0\\}$ and
$S_{11}=\\{m\in[1,\mathcal{\ell}]~{}:~{}\vec{a}[m]=1,\vec{b}[m]=1\\}$. Then,

$\left\lVert\vec{a}\right\rVert_{w}=\left|{S_{10}}\right|+\left|{S_{11}}\right|$

$\left\lVert\vec{b}\right\rVert_{w}=\left|{S_{01}}\right|+\left|{S_{11}}\right|$

$\delta_{H}(\vec{a},\vec{b})=\left|{S_{10}}\right|+\left|{S_{01}}\right|$

The above equations along with the fact
$\left|{S_{11}}\right|=\sum\limits_{m=1}^{\mathcal{\ell}}\vec{a}[m]\cdot\vec{b}[m]=\vec{a}\cdot\vec{b}$
proves the result. ∎

As long as the maximum Hamming distance between the vectors $<2^{24}$, the
24-bit message space suffices for this computation. After computing
$\mathsf{Enc}(\delta_{H}(\vec{a},\vec{b}))$, Bob computes
$\mathsf{KeySet}:=\\{\kappa_{i}:\kappa_{i}:=r_{i}\times(\mathsf{Enc}(\delta_{H}(\vec{a},\vec{b})-i))+\mathsf{Enc}(\kappa),~{}i\in[0,d_{\mathsf{H}}],~{}r_{i}\leftarrow{\mathbb{F}_{p}}\\}$.
However, the problem here is that $\kappa\in{\mathbb{F}_{p}}$ and for a
sufficiently high statistical security parameter, we require $p$ to be a at
least $128$-bit long. Thus, $\kappa$ does not fit in the 24-bit message space.

To mitigate this, we split $\kappa$ into 24-bit chunks. Each individual chunk
is encrypted separately, and returned to Alice. In other words, Bob splits
$\kappa$ into $c=\left\lceil\frac{\left|{p}\right|}{24}\right\rceil$ chunks
$\mathsf{Chunk}_{1},\ldots,\mathsf{Chunk}_{c}$, and Alice now receives
$\mathsf{KeySet}:=\\{\kappa_{ij}:\kappa_{ij}:=r_{ij}\times(\mathsf{Enc}(\delta_{H}(\vec{a},\vec{b})-i))+\mathsf{Enc}(\mathsf{Chunk}_{j}),~{}i\in[0,d_{\mathsf{H}}],~{}r_{ij}\leftarrow{\mathbb{F}_{p}},j\in[1,c]\\}$.
From this, Alice can obtain $\kappa_{i}:=\kappa_{i1}||\ldots||\kappa_{ic}$.
Note each 24-bit chunk in encrypted with IND-CPA security, and therefore
splitting the key as described has no impact on security. There is a $c$ times
blowup in the downstream communication cost i.e., the cost of sending
$\mathsf{KeySet}$ to Alice.

###  C.2 Proofs

######  Lemma 4.

Let
$S^{\prime}_{\vec{a}}:=\\{\vec{x}_{1},\ldots,\vec{x}_{N_{\mathsf{bins}}}\\}$
and
$S^{\prime}_{\vec{b}}:=\\{\vec{y}_{1},\ldots,\vec{y}_{N_{\mathsf{bins}}}\\}$
be the set of sub-vectors created after sub-sampling $\vec{a}$ and $\vec{b}$
using $\pi$ in $t\mathsf{HamQuery}$. Then, $|S^{\prime}_{\vec{a}}\setminus
S^{\prime}_{\vec{b}}|\geq 2d_{\mathsf{H}}$ if
$\delta_{H}(\vec{a},\vec{b})>2d_{\mathsf{H}}$ with high probability.

###### Proof.

To prove the result, we use the following balls and bins analysis: let each
index where $\vec{a}$ and $\vec{b}$ differ be represented by a ball. There are
$>2d_{\mathsf{H}}$ such indices and they are uniformly distributed across
$N_{\mathsf{bins}}$ bins, where the $i$th bin contains the indices which make
up the sub-vectors $\vec{x}_{i}$ and $\vec{y}_{i}$. In this framework, the
number of non-empty bins gives us $|S^{\prime}_{\vec{a}}\setminus
S^{\prime}_{\vec{b}}|$. Then, Lemma 5 shows that
$|S^{\prime}_{\vec{a}}\setminus S^{\prime}_{\vec{b}}|\geq 2d_{\mathsf{H}}$
with high probability.

∎

######  Lemma 5.

If 2$d_{\mathsf{H}}$ \+ 1 balls are randomly thrown into
$N_{\mathsf{bins}}=\frac{2d_{\mathsf{H}}^{2}}{\textsc{fpr}}$ bins where
$\epsilon\in(0,0.5)$, then there are more than $2d_{\mathsf{H}}$ non-empty
bins with probability at least $1-\epsilon$.

###### Proof.

Let $E_{k}$ be the event that there are exactly $(2d_{\mathsf{H}}+1-k)$
occupied bins where $k\in[2,2d_{\mathsf{H}}-1)$. Then,

$\mathbb{P}\left[E_{k}\right]=\frac{(2d_{\mathsf{H}}+1-k)!\genfrac{\\{}{\\}}{0.0pt}{}{2d_{\mathsf{H}}+1}{2d_{\mathsf{H}}+1-k}\binom{N_{\mathsf{bins}}}{N_{\mathsf{bins}}-(2d_{\mathsf{H}}+1-k)}}{(N_{\mathsf{bins}})^{2d_{\mathsf{H}}+1}}$

$=\frac{(2d_{\mathsf{H}}+1-k)!\genfrac{\\{}{\\}}{0.0pt}{}{2d_{\mathsf{H}}+1}{2d_{\mathsf{H}}+1-k}\binom{N_{\mathsf{bins}}}{2d_{\mathsf{H}}+1-k}}{(N_{\mathsf{bins}})^{2d_{\mathsf{H}}+1}}$

$\leq\genfrac{\\{}{\\}}{0.0pt}{}{2d_{\mathsf{H}}+1}{2d_{\mathsf{H}}+1-k}\times\left(N_{\mathsf{bins}}\right)^{-k}$

where $\genfrac{\\{}{\\}}{0.0pt}{}{a}{b}$ denotes the Stirling number of the
second kind. The last inequality holds since
$\binom{N_{\mathsf{bins}}}{2d_{\mathsf{H}}+1-k}\leq\frac{(N_{\mathsf{bins}})^{2d_{\mathsf{H}}+1-k}}{(2d_{\mathsf{H}}+1-k)!}$.

Using the upper bound for Stirling number of second kind,
$\genfrac{\\{}{\\}}{0.0pt}{}{a}{b}\leq\frac{1}{2}\binom{a}{b}b^{a-b}$, we have

$\genfrac{\\{}{\\}}{0.0pt}{}{2d_{\mathsf{H}}+1}{2d_{\mathsf{H}}+1-k}\leq\frac{1}{2}\binom{2d_{\mathsf{H}}+1}{2d_{\mathsf{H}}+1-k}(2d_{\mathsf{H}}+1-k)^{k}\leq\frac{1}{2}\frac{(2d_{\mathsf{H}}+1)^{k}(2d_{\mathsf{H}}+1-k)^{k}}{k!}$

Now,
$\frac{(2d_{\mathsf{H}}+1)(2d_{\mathsf{H}}+1-k)}{N_{\mathsf{bins}}}=\frac{(2d_{\mathsf{H}}+1)(2d_{\mathsf{H}}+1-k)}{\frac{2d_{\mathsf{H}}^{2}}{\textsc{fpr}}}<2\epsilon$.
Thus,

$\mathbb{P}\left[E_{k}\right]<\frac{1}{2}\times\frac{(2\epsilon)^{k}}{k!}$

Let $E$ be the event that the number of occupied bins is less than
$2d_{\mathsf{H}}$. Then,

$\mathbb{P}\left[E\right]\leq\sum\limits_{k=2}^{2d_{\mathsf{H}}-2}\mathbb{P}\left[E_{k}\right]=\frac{1}{2}\sum\limits_{k=2}^{2d_{\mathsf{H}}-2}\frac{(2\epsilon)^{k}}{k!}<\frac{1}{2}(e^{2\epsilon}-(1+2\epsilon))$

The last inequality holds since
$\sum\limits_{k=2}^{\infty}\frac{(2e)^{k}}{k!}=e^{2e}-(1+2\epsilon)$. Also,
for any $\epsilon\in(0,0.5)$,

$\frac{1}{2}(e^{2\epsilon}-(1+2\epsilon))<\epsilon$

∎

See 2

###### Proof.

We show that there is a PPT simulator $\mathsf{Sim}$ in the ideal world which
indistinguishably simulates the real world execution of $t\mathsf{HamQuery}$

Simulating Bob’s view:: Bob does not receive any output from the protocol and
only observes intermediate results from $t\mathsf{HamQueryRestricted}$ and
$\mathcal{F}^{p}_{\mathit{ole}}$. Assuming that
$\mathcal{F}^{p}_{\mathit{ole}}$ is realized by a protocol which can be
indistinguishably simulated and the AHE scheme used in
$t\mathsf{HamQueryRestricted}$ produces IND-CPA secure ciphertexts
indistinguishable from random, Bob’s view in $t\mathsf{HamQuerySample}$
simulating Bob’s view is straightforward.

Simulating Alice’s view: Alice’s input into the protocol is $\vec{a}$ and
Alice receives $\mathsf{KeySet}$ and the evaluations of the polynomials
$W_{A}(x)$ and $W_{B}(x)$. The simulation strategy is as follows.

When $\delta_{H}(\vec{a},\vec{b})\leq d_{\mathsf{H}}$: In this case,
$\mathcal{F}_{\mathcal{\ell},d_{\mathsf{H}}}^{t{\text{-}}\mathit{HQ}}$ returns
$\vec{b}$. The simulator follows the steps of $t\mathsf{HamQuery}$ generating
all outputs using $\vec{b}$. The simulation is clearly indistinguishable.

When $\delta_{H}(\vec{a},\vec{b})>d_{\mathsf{H}}$: In the real world, Alice
obtains $\mathsf{KeySet}$, and the set of evaluations
$V_{A}:=\\{(x_{k},y_{k}):~{}y_{k}:=R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})+\phi(\kappa,k),~{}k\in[1,N_{\mathsf{bins}}+2d_{\mathsf{H}}+1]\\}$.
where $N_{\mathsf{bins}}$ $:=$ $\frac{2d_{\mathsf{H}}^{2}}{\textsc{fpr}}$.

Case when $\delta_{H}(\vec{a},\vec{b})\in(d_{\mathsf{H}},2d_{\mathsf{H}}]$ and
$\mathcal{F}_{\mathcal{\ell},d_{\mathsf{H}}}^{t{\text{-}}\mathit{HQ}}$ does
not output $\vec{b}$: In this case, $\kappa\notin\mathsf{KeySet}$ which
implies $\delta_{H}(\vec{X},\vec{Y})\notin[0,d_{\mathsf{H}})$. Thus, for each
$\mathsf{Enc}(\kappa_{i})\in\mathsf{KeySet},~{}\kappa_{i}:=r_{i}(\delta_{H}(\vec{X},\vec{Y})-i)+\kappa,~{}i\in[0,d_{\mathsf{H}}],~{}r_{i}\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}},\kappa\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}$,
$\kappa_{i}$ is a random element in ${\mathbb{F}_{p}}$. In the ideal world,
$\mathsf{Sim}$ sets the key set
$\mathsf{KeySet}_{\mathsf{Sim}}:=\\{\mathsf{Enc}(r_{i}):~{}r_{i}\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}\\}_{i=1}^{\left|{\mathsf{KeySet}}\right|}$.
From the above we have $\mathsf{KeySet}\sim\mathsf{KeySet}_{\mathsf{Sim}}$.

To simulate the output of $V_{A}$ in line 3 of $t\mathsf{HamQuery}$, for
$k\in[1,N_{\mathsf{bins}}+2d_{\mathsf{H}}+1]$, $\mathsf{Sim}$ sends
$P(x_{k})$, $R_{1}(x_{k})$, and
$Q^{\mathsf{Sim}}(x_{k})R_{2}(x_{k})+\phi(\kappa,k)$ to
$\mathcal{F}^{p}_{\mathit{ole}}$. For
$k\in[1,N_{\mathsf{bins}}+2d_{\mathsf{H}}+1]$,
$\mathcal{F}^{p}_{\mathit{ole}}$ returns
$W_{A}^{\mathsf{Sim}}(x_{k}):=R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q^{\mathsf{Sim}}(x_{k})+\phi(\kappa,k)$.
$\mathsf{Sim}$ returns
$V^{\mathsf{Sim}}_{A}:=\\{(x_{k},y_{k})~{}:y_{k}:=W_{A}^{\mathsf{Sim}}(x_{k}),~{}k\in[1,N_{\mathsf{bins}}+2d_{\mathsf{H}}+1]\\}$
to Alice Observe that for
$k\in[1,N_{\mathsf{bins}}+2d_{\mathsf{H}}+1],W_{A}(x_{k}):=R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})+\phi(\kappa,k)$
and
$W_{A}^{\mathsf{Sim}}(x_{k}):=R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q^{\mathsf{Sim}}(x_{k})+\phi(\kappa,k)$.
If the PRF $\phi$ outputs uniformly random values in ${\mathbb{F}_{p}}$,
$W_{A}(x_{k})\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}$ and
$W_{A}^{\mathsf{Sim}}(x_{k})\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}$.
Thus, $V_{A}\sim V^{\mathsf{Sim}}_{A}$.

Since, $\kappa$ is selected independently of all
$\kappa_{i}\in\mathsf{KeySet}$, we have that the points in $V_{A}$ are
independent of the "keys" in $\mathsf{KeySet}$. Similarly, the points
$V^{\mathsf{Sim}}_{A}$ are independent of the random elements in
$\mathsf{KeySet}_{\mathsf{Sim}}$. Thus, we have
$(\mathsf{KeySet},V_{A})\sim(\mathsf{KeySet}_{\mathsf{Sim}},V^{\mathsf{Sim}}_{A})$
which shows that the ideal world simulation is indistinguishable from the real
world execution.

Case when $\delta_{H}(\vec{a},\vec{b})\in(d_{\mathsf{H}},2d_{\mathsf{H}}]$ and
$\mathcal{F}_{\mathcal{\ell},d_{\mathsf{H}}}^{t{\text{-}}\mathit{HQ}}$ does
not output $\vec{b}$: There are two cases: i) when
$\kappa\notin\mathsf{KeySet}$, and ii) when $\kappa\in\mathsf{KeySet}$. In
case (i), we can apply the same arguments as above. Since these cases are not
distinguishable, $\mathsf{Sim}$ follows the same strategy for both cases. More
specifically, as above, $\mathsf{Sim}$ sets
$\mathsf{KeySet}_{\mathsf{Sim}}:=\\{\mathsf{Enc}(r_{i}):~{}r_{i}\;\stackrel{{\scriptstyle\$}}{{:=}}\;{\mathbb{F}_{p}}\\}_{i=1}^{\left|{\mathsf{KeySet}}\right|}$
and
$V^{\mathsf{Sim}}_{A}:=\\{(x_{k},y_{k}):y_{k}:=W_{A}^{\mathsf{Sim}}(x_{k}):=R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q^{\mathsf{Sim}}(x_{k})+\phi(\kappa,k),~{}k\in[1,N_{\mathsf{bins}}+2d_{\mathsf{H}}+1]\\}$.

$\mathsf{KeySet}$ and $\mathsf{KeySet}_{\mathsf{Sim}}$ are indistinguishable
because both sets comprise random field elements. Also, the points in $V_{A}$
are independent of the "keys" in the $\mathsf{KeySet}$. Thus, we only need to
show that $V_{A}$ and $V^{\mathsf{Sim}}_{A}$ are indistinguishable.

Let $\mathcal{U}_{p}$ be the set of all sets
$\\{(x_{k},y_{k}):(x_{k},y_{k})\in(X\times{\mathbb{F}_{p}})\\}_{k=1}^{N_{\mathsf{bins}}+2d_{\mathsf{H}}+1}\\}$.
Note that
$\left|{\mathcal{U}_{p}}\right|=p^{N_{\mathsf{bins}}+2d_{\mathsf{H}}+1}$.
Similar to the proof for Theorem 5, we show that for any arbitrary pair of
polynomials $P(x),Q(x)\in{\mathbb{F}_{p}}[x]\times{\mathbb{F}_{p}}[x]$ such
that
$\mathbf{deg}\mathopen{}\left(\mathbf{gcd}\mathopen{}\left(P(x),Q(x)\right)\mathclose{}\right)\mathclose{}<N_{\mathsf{bins}}-2d_{\mathsf{H}}$
and $\forall x_{k}\in X,P(x_{k}),Q(x_{k})\neq 0$,

$\sum_{X_{A}\in\mathcal{U}_{p}}\left|\mathbb{P}\left[V_{A}=X_{A}\right]-\mathbb{P}\left[V^{\mathsf{Sim}}_{A}=X_{A}\right]\right|<1/p$
(1)

W.l.o.g for some $X_{A}\in\mathcal{U}_{p}$, $V_{A}=X_{A}$, $x_{k}\in X$ and
$v_{k}\in X_{A}$, we have

$R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q(x_{k})=C(x_{k})R(x_{k})=v_{k}$

where $C(x)=\mathbf{gcd}\mathopen{}\left(P(x),Q(x)\right)\mathclose{}$,
$d_{\mathsf{GCD}}:=\mathbf{deg}\mathopen{}\left(C(x)\right)\mathclose{}$ and
$R(x)$ is a random polynomial of degree $2N_{\mathsf{bins}}-d_{\mathsf{GCD}}$
due to Lemma 1. There are
$p^{(2N_{\mathsf{bins}}-d_{\mathsf{GCD}}+1)-(N_{\mathsf{bins}}+2d_{\mathsf{H}}+1)}=p^{N_{\mathsf{bins}}-d_{\mathsf{GCD}}+2d_{\mathsf{H}}}$
polynomials that are consistent with $R(x)$. Let $S_{R}$ be the set of these
polynomials. Each $R(x)\in S_{R}$ is consistent with a unique pair
$(R_{1}(x),R_{2}(x))\in{\mathbb{F}_{p}}[x]\times{\mathbb{F}_{p}}[x]$ of
degree-$N_{\mathsf{bins}}$ polynomials selected by the protocol. Thus, for any
$P(x),Q(x)$, we have

$\mathbb{P}\left[V_{A}=X_{A}\right]=\frac{\left|{S_{R}}\right|}{\text{\\# of
}(R_{1}(x),R_{2}(x))\text{pairs}}=\frac{p^{N_{\mathsf{bins}}-d_{\mathsf{GCD}}+2d_{\mathsf{H}}}}{p^{2N_{\mathsf{bins}}+2}}=p^{-(N_{\mathsf{bins}}-d_{\mathsf{GCD}}+2d_{\mathsf{H}}+2)}$

For $V^{\mathsf{Sim}}_{A}=X_{A}$, we require

$W_{A}^{\mathsf{Sim}}(x_{k}):=R_{1}(x_{k})P(x_{k})+R_{2}(x_{k})Q^{\mathsf{Sim}}(x_{k})=v_{k}-\phi(\kappa,k)$

For $Q^{\mathsf{Sim}}(x)$, we have with overwhelming probability
$d_{\mathsf{GCD}}=\mathbf{deg}\mathopen{}\left(\mathbf{gcd}\mathopen{}\left(P(x),Q^{\mathsf{Sim}}(x)\right)\mathclose{}\right)\mathclose{}=0$.