Locality Sensitive Hashing with Extended
Differential Privacy ?
Natasha Fernandes1,2 , Yusuke Kawamoto3 , and Takao Murakami3
1

Macquarie University, Sydney, Australia
Inria, École Polytechnique, IPP, Palaiseau, France
3
National Institute of Advanced Industrial Scienceand Technology (AIST), Tokyo, Japan

2

Abstract. Extended differential privacy, a generalization of standard
differential privacy (DP) using a general metric, has been widely studied
to provide rigorous privacy guarantees while keeping high utility. However, existing works on extended DP are limited to few metrics, such as
the Euclidean metric. Consequently, they have only a small number ofapplications, such as location-based services and document processing.
In this paper, we propose a couple of mechanisms providing extended
DP with a different metric: angular distance (or cosine distance). Our
mechanisms are based on locality sensitive hashing (LSH), which canbe applied to the angular distance and work well for personal data in ahigh-dimensional space. We theoretically analyze the privacy propertiesof our mechanisms, and prove extended DP for input data by taking
into account that LSH preserves the original metric only approximately.
We apply our mechanisms to friend matching based on high-dimensional
personal data with angular distance in the local model, and evaluate
our mechanisms using two real datasets. We show that LDP requiresa very large privacy budget and that RAPPOR does not work in thisapplication. Then we show that our mechanisms enable friend matchingwith high utility and rigorous privacy guarantees based on extended DP.
Keywords: Local differential privacy · locality sensitive hashing · angular distance · extended differential privacy

1

Introduction

Extended differential privacy (extended DP), a.k.a. dX -privacy [13], is a privacy
notion that provides rigorous privacy guarantees while enabling high utility. Extended DP is a generalization of standard DP [20, 21] in that the adjacency
relation (regarded as the Hamming distance) is generalized to a metric. A wellknown application is geo-indistinguishability [4, 7, 9], an instance of extended DP?

The authors are ordered alphabetically. This work was supported by the FrenchJapanese project LOGIS within the Inria Equipes Associées program, by an Australian Government RTP Scholarship (2017278), by ERATO HASUO Metamathematics for Systems Design Project (No. JPMJER1603), JST, and by JSPS KAKENHI Grant Number JP19H04113.

2

Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami

for two-dimensional Euclidean space. Geo-indistinguishability guarantees that auser’s location is indistinguishable from any location within a certain radius (e.g.,
within 5km) in the local model, in which each user obfuscates her own data andsends it to a data collector. It can also be regarded as a relaxation of DP in
the local model (local DP or LDP [19]) to make two locations within a certain
radius indistinguishable (whereas LDP makes arbitrary locations indistinguishable). Consequently, extended DP results in much higher utility than LDP, e.g.,
for a task of estimating geographic population distributions [4].
Since extended DP is defined using a general metric, it can potentially havea wide range of applications. However, the range of actual applications is limited by the particular metrics for which extended DP mechanisms have been
designed. For example, the existing works on locations [4, 7, 9], documents [25],range queries [53], and linear queries [32] are designed for the Euclidean metric,
the Earth Mover’s metric, the l1 metric, and the summation of privacy budgets
for attributes, respectively. However, there have been no known extended DP
mechanisms designed for the angular distance (or cosine distance).
For example, consider friend matching (or friend recommendation) basedon personal data (e.g., locations, rating history) [10, 14, 16, 35, 36, 38, 44, 47]. In
the case of locations, we can create a vector of visit-counts where each value isthe visit-count on the corresponding Point of Interest (POI). Users with similar
vectors have a high probability of establishing new friendships [54]. Therefore, we
can use the POI vector to recommend a new friend. Similarly, we can recommend
a new friend based on the similarity of their item rating vectors, since thisidentifies users with similar interests [2]. Because the distance between vectors
in such applications is usually given by the angular distance (or equivalently,
the cosine distance) [2], the angular distance is a natural choice for the utility
measure and the metric for extended DP.
In this paper, we focus on friend matching in the local model, and propose two
mechanisms providing extended DP with the angular distance. Our mechanisms
are based on locality sensitive hashing (LSH) [28, 49], which can be applied toa wide range of metrics including the angular distance. Our first mechanism,
LapLSH, uses the multivariate Laplace mechanism [25] to generate noisy vectors,
and then hashes them into buckets using LSH as post-processing. Our second
mechanism, LSHRR, embeds personal data into a binary vector using LSH, andthen applies Warner’s randomized response [52] for each bit of the binary vector.
The privacy analysis of extended DP is challenging especially for LSHRR.
This is because LSH does not precisely preserve the original metric; it approximates the original metric via hashing. We theoretically analyze the privacy
properties of our mechanisms, showing that they provide extended DP for the
input. We also note that much existing work on privacy-preserving LSH [3, 15,46] fails to provide rigorous guarantees about user privacy. We point out, using
a toy example, how the lack of rigorous guarantees can lead to privacy breaches.
We evaluate our mechanisms using two real datasets. We show that LDP requires a very large privacy budget . This comes from the fact that LDP expresses
an upper bound on the privacy guarantee for all inputs. In contrast, extendedLSH with Extended Differential Privacy

3

DP is a finer-grained notion than LDP in that it describes the privacy guarantee
for inputs at various distances. In fact, we show that extended DP enables friend
matching with a much smaller privacy budget than LDP for close inputs.
We also explain why RAPPOR [23] and the generalized RAPPOR [51], which
are state-of-the-art LDP mechanisms, cannot be applied (either completely loseutility or are computationally infeasible) to friend matching. In short, the Bloom
filter used in RAPPOR is not a metric-preserving hashing, and therefore cannot
guarantee utility w.r.t. the metric distance between user vectors. This is further
elaborated in Sect. 7.4.
Contributions. Our main contributions are as follows:– We propose two mechanisms providing extended DP with the angular distance: LapLSH and LSHRR. We show that LSH itself does not provide privacy guarantees and could result in complete privacy collapse in some situations. We then prove that our mechanisms provide rigorous guarantees ofextended DP. In particular, we show that the distribution of the LSHRR’s
privacy loss can be characterized as extended notions of concentrated DP [22]and probabilistic DP [39] with input distance. To our knowledge, this workis the first to provide extended DP with the angular distance.
– We apply our mechanisms to friend matching based on rating history andlocations. Then we compare LSHRR with LapLSH using two real datasets.
We show that LSHRR provides higher (resp. lower) utility than LapLSH
for a high-dimensional (resp. low-dimensional) vector. We also show thatLDP requires a very large privacy budget , and RAPPOR does not workfor friend matching. Finally, we show that LSHRR provides high utility fora high-dimensional vector (e.g., 1000-dimensional rating/location vector) in
the medium privacy regime [1, 55] of extended DP, and therefore enables
friend matching with rigorous privacy guarantees and high utility.
All proofs on the technical results can be found in Appendix B.

2

Related Work

2.1

Extended DP

As explained in Sect. 1, there are a number of existing extended DP mechanisms[4, 7, 9, 25, 32, 53] designed for other metrics (e.g., the Euclidean metric, the l1
metric), which cannot be applied to the angular distance. To our knowledge, ourmechanisms are the first to provide extended DP with the angular distance.
In addition, most of the studies on extended DP have studied low-dimensional
data such as two-dimensional [4, 7, 9, 32] and six-dimensional [53] data. One exception is the work in [25], which proposed the multivariate Laplace mechanism
for 300-dimensional vectors. In this paper, we apply our mechanisms to vectors
in 1000-dimensions (much larger than any existing work), and show that our
LSHRR provides high utility for such high-dimensional data.

4

2.2

Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami

Privacy-Preserving Friend Matching

A number of studies [10, 14, 16, 35, 36, 38, 44, 47] have been made on algorithms
for privacy-preserving friend matching (or friend recommendation). Many ofthem (e.g., [16, 38, 44, 47]) use cryptographic techniques such as homomorphic
encryption and secure multiparty computation. However, such techniques require
high computational costs or focus on specific algorithms, and are not suitable fora more complicated calculation of distance such as the angular distance between
two rating/location vectors.
The techniques in [10, 14, 35, 36] are based on perturbation. The mechanisms
in [10, 35, 36] do not provide DP or its variant, whereas that in [14] provides DP.
The technique in [14], however, is based on social graphs and cannot be applied
to our setting, where a user’s personal data is represented as a rating vector
or visit-count vector. Moreover, DP-based friend matching in social graphs canrequire prohibitive trade-offs between utility and privacy [10, 40].
Similarly, DP mechanisms based on each user’s high-dimensional rating/location
vector require a very large privacy budget (e.g., ε ≥ 250 [37], ε ≥ 2 × 104[42]) to provide high utility. In contrast, our extended DP mechanisms provide
meaningful privacy guarantees in high-dimensional spaces with high utility, sinceextended DP is a finer-grained notion than DP, as explained in Sect. 1.
We also note that a privacy-preserving clustering algorithm in [45] and an
item recommendation algorithm in [48] cannot be applied to friend matching.
2.3

Privacy-Preserving LSH

Finally, we note that some studies have proposed privacy-preserving LSH [3, 8,
15, 29, 45, 46, 56]. However, some of them [3, 15, 46] only apply LSH and claimthat it protects user privacy because LSH is a kind of non-invertible transformation. In Sect. 4, we show that the lack of rigorous guarantees can lead to privacy
breaches. Nissim and Stemmer [45] proposed clustering algorithms based on LSH
and the heavy-hitters algorithm. However, their algorithms focus on clusteringsuch as k-means clustering and cannot be applied to friend matching.
Aumüller et al. [8] proposed a privacy-preserving LSH algorithm that canbe applied to friend matching. Specifically, they focused on a similarity search
problem under the Jaccard similarity using up to 2000-dimensional vectors, andproposed an LDP algorithm based on MinHash. After the submission of ourpaper to a preprint [26], two related papers [29, 56] have been published. Zhang
et al. [56] proposed an LDP algorithm for rating prediction based on MinHash
and knowledge distillation. Hu et al. [29] proposed an LDP algorithm based on
LSH for federated recommender system.
Our work differs from [8, 29, 56] in the following points. First, [8, 29, 56] only
analyzed LDP for hashes, and did not conduct a more challenging analysis ofextended DP for inputs. In contrast, our work provides a careful analysis of extended DP, given that LSH preserves the original metric only approximately. We
also show that extended DP requires a much smaller privacy budget than LDP.
Second, we compared LSHRR with LapLSH in detail, and show that LSHRR(resp. LapLSH) is more suitable for high (resp. low) dimensional data.

LSH with Extended Differential Privacy

35Preliminaries

In this section, we introduce notations and recall background on locality sensitive
hashing (LSH), privacy measures, and privacy protection mechanisms.
Let deuc be the Euclidean distance between real vectors, i.e., deuc (x, x0 ) =κkx − x0 k2 . We write V for the set of all binary data of lengthPκκ, i.e., V = {0, 1} .
The Hamming distance between v, v 0 ∈ V is: dV (v, v 0 ) = i=1 | vi − vi0 | .
We denote the set of all probability distributions over a set S by DS. Let
N (µ, σ 2 ) be the normal distribution with mean µ and variance σ 2 . Let A : X →DY be a randomized algorithm from a finite set X to another Y, and A(x)[y](resp. by A(x)[S]) be the probability that A maps x to y (resp. an element of S).
3.1

Locality Sensitive Hashing (LSH)

We denote by X the set of all possible input data. We introduce the notion ofa (normalized) dissimilarity function dX : X × X → [0, 1] over X such that two
inputs x and x0 have less dissimilarity dX (x, x0 ) when they are closer, and thatdX (x, x0 ) = 0 when x = x0 . If dX is symmetric and subadditive, it is a metric.
A locality sensitive hashing (LSH) [28] is a family of functions in which theprobability of two inputs x, x0 having different 1-bit outputs is proportional todX (x, x0 ).
Definition 1 (Locality sensitive hashing). A locality sensitive hashing (LSH)
scheme w.r.t. a dissimilarity function dX is a family H of functions from X to{0, 1} coupled with a probability distribution DH such that for any x, x0 ∈ X ,Pr [h(x) 6= h(x0 )] = dX (x, x0 ),

h∼DH

(1)

where h is chosen from H according to the distribution DH . By using independently chosen functions h1 , h2 , . . . , hκ , the κ-bit LSH function H : X → V is:
H(x) = (h1 (x), h2 (x), . . . , hκ (x)).

(2)

We denote by H ∗ : X → DV the randomized algorithm that draws a κ-bit LSHκand outputs the hash value H(x) of a given input x.
H from the distribution DH
3.2

Examples of LSHs

There are a variety of LSH families corresponding to useful metrics, such as theangular distance [5, 12], Jaccard metric [11], and lp metric with p ∈ (0, 2] [18].
In this work, we focus on LSH families for the angular distance.
A random-projection-based hashing is a one-bit hashing with the domain
def n
X = R and a random vector r ∈ Rn that defines a hyperplane through the origin. Formally, we define a random-projection-based hashing hproj : Rn →{0, 1} by:(
0 (if r > x < 0)hproj (x) =1 (otherwise)6

Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami

where each element of r is independently chosen from the standard normal distribution N (0, 1). By (2), a κ-bit LSH function Hproj is built from one-bit hashes
hproj 1 , . . . , hproj κ that are generated from independent hyperplanes r 1 , . . . , r κ .
The random-projection-based hashing hproj is an LSH w.r.t. the angular distance dθ : Rn × Rn → [0, 1] defined by:dθ (x, x0 ) = π1 cos−1

x> x0 kxkkx0 k(3)For example, dθ (x, x0 ) = 0 iff x = x0 , while dθ (x, x0 ) = 1 iff x = −x0 . dθ (x, x0 ) =0.5 exactly when the two vectors x and x0 are orthogonal, namely, x> x0 = 0.
3.3

Approximate Nearest Neighbor Search

We recall the nearest neighbor search (NNS) problem and its utility measures.
Given a dataset S ⊆ X , the nearest neighbor search (NNS) for an x0 ∈ S
is the problem of finding the closest x ∈ S to x0 w.r.t. a metric dX over X . A
k-nearest neighbor search (k-NNS) is the problem of finding the k closest points.
A naive and exact approach to k-NNS is to perform pairwise comparisonsof data points, requiring O(|S|) operations. Approaches to improve this computational inefficiency shift the problem to space inefficiency [6]. An alternative
approach [30] is to employ LSH to perform approximate NNS efficiently. To evaluate the utility, we use the average distance of returned nearest neighbors fromthe data point x0 compared with the average distance of true nearest neighbors.
Definition 2 (Utility loss). Let A be an approximate algorithm that produces
approximate k nearest neighbors N ⊆ S for a data point x0 ∈ S in terms of a
metric dX . The average P
utility loss for N w.r.t.
P the true nearest neighbors T isgiven by: UA (S) = 1/k
dX (x0 , x) − 1/kdX (x0 , x).
x∈N

3.4

x∈T

Privacy Measures and Privacy Mechanisms

Extended differential privacy [13, 34] guarantees that when two inputs x and x0
are closer, their corresponding output distributions are less distinguishable. In
this paper, we propose a more generalized definition using a function δ over X
and an arbitrary function ξ over X instead of a metric. The main reason for thisgeneralization is that LSH preserves the metric over the input only probabilistically and approximately, hence cannot fit to [13]’s standard definition.
Definition 3 (Extended differential privacy). Given two functions ξ : X ×
X → R≥0 and δ : X × X → [0, 1], a randomized algorithm A : X → DY provides(ξ, δ)-extended differential privacy (XDP) if for all x, x0 ∈ X and for any S ⊆ Y,
0

A(x)[S] ≤ eξ(x,x ) A(x0 )[S] + δ(x, x0 ),where the probability is taken over the random choices in A.

LSH with Extended Differential Privacy

7

We abuse notation and write δ when δ(x, x0 ) is a constant. When ξ(x, x0 ) is alsoa constant ε, the definition gives the (standard) differential privacy (DP). Whenξ(x, x0 ) = dX (x, x0 ) and δ(x, x0 ) = 0, the definition gives dX -privacy in [13]. In
later sections, we instantiate the metric dX with the angular distance dθ .
Finally, we recall some popular privacy protection mechanisms.
Definition 4 (Laplace mechanism [21]). For an ε ∈ R>0 and a metric dX
over X ∪ Y, the (ε, dX )-Laplace mechanism is the randomized algorithm QLap :1
X → DY that
R maps an input x to an output y with probability c exp(−εdX (x, y))where c = Y exp(−εdX (x, y)) dy.
Examples of the (ε, dX )-Laplace mechanism include the one-dimensional [21]and the multivariate Laplace mechanism [25], both equipped with the Euclidean
metric. The (ε, dX )-Laplace mechanism provides (εdX , 0)-XDP.
Definition 5 (Randomized response [52]). The ε-randomized response (εRR) is the randomized algorithm Qrr : {0, 1} → D{0, 1} that maps a bit b toεanother b0 with probability eεe+1 if b0 = b, and with probability eε1+1 otherwise.
The ε-RR provides ε-DP. Erlingsson et al. [23] introduce the RAPPOR, which
first uses a Bloom filter to produce a hash value and then applies the RR to each
bit of the hash value. The RAPPOR provides ε-DP in the local model.

4

Privacy Properties of LSH

Several works in the literature make reference to the privacy-preserving properties of LSH [3, 17, 46]. The privacy guarantee attributed to LSH mechanisms
hinges on its hash function, which ‘protects’ an individual’s private attributes
by revealing only their hash bucket. We now apply a formal analysis to LSH andexplain why LSH implementations do not provide strong privacy guarantees, andcould, in some situations, result in complete privacy collapse for the individual.
Modeling LSH. We present a simple example to show how privacy breaks
down. Consider the set of secret inputs X ={(0, 1), (1, 0), (1, 1)} whose element
represents whether an individual rated two movies A and B. Then an LSH ismodeled as a probabilistic channel h ∗ : X →D{0, 1} that maps a secret input toa binary observation.
For brevity, we deal with a single random-projection-based hashing h in
Sect. 3.2. That is, we randomly choose a vector r representing the normal toa hyperplane, and given an input x ∈ X , the hash function h outputs 0 if
r > x < 0 and 1 otherwise. For example, if r = (1, − 21 ) is chosen, h is defined as:
h : X → {0, 1}(0, 1) 7→ 0
(1, 0) 7→ 1
(1, 1) 7→ 1

In fact, there are 6 possible (deterministic) hash functions for any choice of thevector r, corresponding to hyperplanes that separate different pairs of points:

8

Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami
h1(0, 1) 7→ 1
(1, 0) 7→ 0
(1, 1) 7→ 0
h4(0, 1) 7→ 0
(1, 0) 7→ 1
(1, 1) 7→ 0

h2
(0, 1) 7→ 0
(1, 0) 7→ 1
(1, 1) 7→ 1
h5
(0, 1) 7→ 1
(1, 0) 7→ 1
(1, 1) 7→ 1

h3
(0, 1) 7→ 1
(1, 0) 7→ 0
(1, 1) 7→ 1
h6
(0, 1) 7→ 0
(1, 0) 7→ 0
(1, 1) 7→ 0

Each of h1 , h2 , h3 , and h4 occurs with probability 1/8, while h5 and h6 each occur
with probability 1/4. The resulting channel h ∗ , computed as the probabilistic sumof these deterministic hash functions, turns out to leak no information on thesecret input (i.e., all outputs have equal probability conditioned on each input).
This indicates that the channel h ∗ is perfectly private. However, in practice,
LSH may require the release of the choice of the vector r (e.g. [17])4 , that is, thechoice of hash function is leaked. Notice that in our example, h1 to h4 correspondto deterministic mechanisms which leak exactly 1 bit of the secret, while h5 andh6 leak nothing. In other words, with 50% probability, 1 bit of the 2-bit secretis leaked. Furthermore, h1 and h2 leak the secret (0, 1) exactly, and h3 and h4
leak (1, 0) exactly. Thus, the release of r destroys the privacy guarantee.
The Guarantee of LSH. In general, for any number of hash functions andany length of input, an LSH which releases its choice of hyperplanes also leaks
its choice of deterministic mechanism. This means that it leaks the equivalenceclasses of the secrets. Such mechanisms belong to the ‘k-anonymity’-style of privacy mechanisms which promise privacy by hiding secrets in equivalence classesof size at least k. These have been shown to be unsafe due to their failure to compose well [27, 24, 33]. This failure leads to the potential for linkage or intersection
attacks by an adversary armed with auxiliary information. For this reason, we
consider compositionality an essential property for a privacy-preserving system.
LSH with hyperplane release does not provide such privacy guarantees.

5

LSH-based Privacy Mechanisms

In this section, we propose two privacy protection mechanisms called LSHRR
and LapLSH. The former is an extension of RAPPOR [23] w.r.t. LSH, and thelatter is constructed using the Laplace mechanism and LSH.
Construction of LSHRR. We introduce the LSH-then-RR privacy mechanism(LSHRR) as the randomized algorithm that (i) randomly chooses a κ-bit LSH
function H, (ii) computes the κ-bit hash value H(x) of a given input x, and (iii)applies the randomized response to each bit of H(x).
To formalize this, we define the (ε, κ)-bitwise RR Qbrr , which applies therandomized response Qrr to each bit of the input independently. Formally, Qbrr :V → DV maps a bitstring
Qvκ = (v1 , v2 , . . . , vκ ) to another y = (y1 , y2 , . . . , yκ ) withprobability Qbrr (v)[y]= i=1 Qrr (vi )[yi ]. Then LSHRR is defined as follows.
4

In fact, since the channel on its own leaks nothing, there must be further information
released in order to learn anything useful from this channel.

LSH with Extended Differential Privacy

9

Definition 6 (LSHRR). The ε-LSH-then-RR privacy mechanism (LSHRR)
instantiated with a κ-bit LSH function H : X → V is the randomized algorithmκ
QH : X → DV defined by QH = Qbrr ◦ H. Given a distribution DHof the κ-bitκ
LSH functions, the ε-LSHRR w.r.t. DH is defined by QLSHRR = Qbrr ◦ H ∗ .
LSHRR deals with two kinds of randomness: (a) the randomness in choosingκa (deterministic) LSH function H from DH(e.g., the random seed r in the
random-projection-based hashing hproj ), and (b) the random noise added by the
bitwise RR Qbrr . We can assume that each user of this privacy mechanism selects
an input x independently of both kinds of randomness, since they wish to protect
their own privacy when publishing x.
In practical settings, the same LSH function H is often used to produce hashvalues of different inputs; namely, multiple hash values are dependent on an
identical hash seed (e.g., a service provider would generate a hash seed so thatmultiple users can share the same H to compare their hash values). Furthermore,
the adversary might obtain the LSH function H (or the seed r used to produceH), and might learn a set of possible inputs that produce the same hash value
H(x) without knowing the actual input x. Therefore, the hash value H(x) mightreveal partial information on the input x (see Sect. 4), and the bitwise RR Qbrr
is crucial in guaranteeing privacy (see Sect. 6 for our privacy analyses).
On the other hand, Qbrr causes errors in the Hamming distance as follows:
Proposition 1 (Error bound) For any x, x0 ∈ X , the expected error in the2κ
Hamming distance satisfies E[|dV (QH (x), QH (x0 )) − dV (H(x), H(x0 ))|] ≤ 1+eεwhere the expectation is taken over the randomness in the bitwise RR.
Construction of LapLSH. We also propose the Laplace-then-LSH privacy
mechanism (LapLSH) as the randomized algorithm that (i) randomly chooses aκ-bit LSH function H, (ii) applies the multivariate Laplace mechanism QLap tox, and (iii) computes the κ-bit hash value H(QLap (x)).
Definition 7 (LapLSH). The (ε, dX )-Laplace-then-LSH privacy mechanism(LapLSH ) with a κ-bit LSH function H : X → V is the randomized algorithm
QLapH : X → DV defined by QLapH = H ◦ QLap . The (ε, dX )-LapLSH w.r.t. aκ
distribution DHof the κ-bit LSH functions is defined by QLapLSH = H ∗ ◦ QLap .
LapLSH also deals with the two kinds of randomness discussed above, andthe Laplace mechanism QLap is crucial in guaranteeing privacy. One of the maindifferences from LSHRR is that LapLSH adds noise directly to the input before
applying LSH whereas LSHRR adds noise after applying LSH to the input.
In Sect. 7 we implement the multivariate Laplace mechanism with the input domain X = Rn and Euclidean distance deuc described in [25]; namely, we
generate additive noise by constructing a unit vector uniformly at random overthe n-dimensional unit sphere Sn , scaled by a random value generated from the
gamma distribution with shape n and scale 1/ε.

106Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami

Privacy Analyses of the Mechanisms

We provide an analysis of the privacy guarantees provided by our mechanisms in
two operational scenarios: (i) w.r.t. an already-chosen LSH function (e.g., where
it has been generated by a service provider), and (ii) w.r.t. all possible choices of
the LSH function (e.g., prior to its instantiation by a particular service provider).
Note that our analysis is general in that it does not rely on specific metrics orhashing algorithms for LSH.
6.1

LSHRR’s Privacy w.r.t. the Particular LSH Function

We first show the privacy guarantee for LSHRR w.r.t. the particular LSH function used by the service provider. This type of privacy is defined using theHamming distance dV between the hash values of given inputs, and the degreeof privacy depends on the actual selection of the LSH function H (or the hashseeds r), which we assume is available to the adversary. Since LSH preserves
the original metric dX only approximately, we obtain XDP guarantee w.r.t. a
pseudo-metric dεH that approximates dX as follows.
Proposition 2 (XDP of QH ) Let H : X → V be a κ-bit LSH function, anddεH be the pseudometric over X defined by dεH (x, x0 ) = εdV (H(x), H(x0 )) forx, x0 ∈ X . Then the ε-LSHRR QH instantiated with H provides (dεH , 0)-XDP.
However, we cannot compute dεH or the degree of XDP in Proposition 2 until
H has been computed. To overcome this unclear guarantee of privacy, in Sect. 6.2
we show a useful privacy guarantee that can be evaluated without requiring H(or hash seeds) generated by the service provider.
Note that the κε-DP of LSHRR is obtained as the worst case of Proposition 2, i.e., when the hamming distance between vectors is maximum due toan “unlucky” choice of hash seeds or very large distance dX (x, x0 ) between the
inputs x, x0 . The following proposition guarantees the privacy independently of
the actual choice of H.
Proposition 3 (Worst-case privacy of QH ) For a κ-bit LSH function H,
the ε-LSHRR QH instantiated with H provides κ-DP.
6.2

LSHRR’s Privacy w.r.t. the Distribution of LSH Functions

Next, we show LSHRR’s privacy guarantee w.r.t. any possible LSH functionthat may be generated. This type of privacy guarantee is useful in a variety of
scenarios. For example, a privacy analyst could evaluate the expected degreeof privacy before the service provider fixes the LSH function or hash seeds. For
another example, the seeds may be stored in tamper-resistant hardware privately.
The privacy guarantee without relying on specific LSH functions or hash seeds
is modeled as a probability distribution of degrees of XDP over the random choiceof seeds. Then this can be characterized as an extension of concentrated DP [22]and probabilistic DP [39] with input distance, yielding the XDP guarantee.

LSH with Extended Differential Privacy

11

In the privacy analysis, we deal with the situation where multiple users produce hash values by employing the same hash seeds, as seen in typical applications such as approximate NNS. Then we define privacy notions for the mechanisms that share randomness among them.
Formally, we denote by Ar : X → DY a randomized algorithm A with ashared input r ∈ R. Given a distribution λ over a finite set R of shared input,
we denote by Aλ : X → DY the randomized algorithm
that draws a sharedP
input r from λ and behaves as Ar ; i.e., Aλ (x)[y] = r∈R λ[r]Ar (x)[y]. Then we
extend the notion of privacy loss [22] with shared randomness as follows.
Definition 8 (Privacy loss). For a randomized algorithm Ar : X → DY witha shared input r, the privacy loss on y ∈ Y w.r.t. x, x0 ∈ X , r ∈ R is defined by:(x)[y] Lx,x0 ,y,r = ln AArr(x0 )[y] ,where the probability is taken over the random choices in Ar . Given a distribution λ over R, the privacy loss random variable Lx,x0 of x over x0 w.r.t. λ is
the real-valued random variable representing the privacy loss Lx,x0 ,y,r where ashared randomness r is sampled from λ and y is sampled from Ar (x).
To characterize the privacy loss random variable Lx,x0 for LSHRR, we introduce an extension of CDP [22] wth input distance d(x, x0 ) as follows.
Definition 9 (CXDP). Let µ ∈ R≥0 , τ ∈ R>0 , λ ∈ DR, and d : X × X →R≥0 be a metric. A random variable Z over R is τ -subgaussian if for all s ∈2 2R, E[exp(sZ)] ≤ exp( s 2τ ). A randomized algorithm Aλ : X → DY provides(µ, τ, d)-mean-concentrated extended differential privacy (CXDP) if for all x, x0 ∈X , the privacy loss random variable Lx,x0 of x over x0 w.r.t. λ satisfies that
E[Lx,x0 ] ≤ µd(x, x0 ), and that Lx,x0 − E[Lx,x0 ] is τ -subgaussian.
Then we obtain the following CXDP guarantee for LSHRR.
Proposition 4 (CXDP of QLSHRR ) The ε-LSHRR provides (εκ, εκ
2 , dX )-CXDP.
To clarify the implication of CXDP, we introduce an extension of probabilistic DP [39] with input distance, which we call PXDP. Intuitively, (ξ, δ)-PXDP
guarantees (ξ, 0)-XDP with probability 1 − δ.
Definition 10 (PXDP). Let λ ∈ DR, ξ : X ×X → R≥0 , and δ : X ×X → [0, 1].
A randomized algorithm Aλ : X → DY provides (ξ, δ)-probabilistic extended
differential privacy (PXDP) if for all x, x0 ∈ X , Pr[ Lx,x0 > ξ(x, x0 ) ] ≤ δ(x, x0 ).
We abuse notation to write δ when δ(x, x0 ) is constant.
In Appendix B, we show that CXDP implies PXDP and that PXDP implies
XDP. Based on these, we show that LSHRR provides PXDP and XDP as follows.
qδ
0Theorem 1 (PXDP/XDP of QLSHRR ) Let δ ∈ R>0 , ε0 = ε − ln
2 , and ξ(x, x ) =√00εκdX (x, x ) + ε κ. The ε-LSHRR provides (ξ, δ)-PXDP, hence (ξ, δ)-XDP.

12Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami

For our experimental evaluation, we show a privacy guarantee that gives
tighter bounds but requires the parameters dependent on the inputs x and x0 .
Proposition 5 (Tighter bound for PXDP/XDP) For a, b ∈ R>0 , let DKL (akb) =a ln ab + (1 − a) ln 1−a1−b . For an α ∈ R>0 , we define:ξα (x, x0 ) = εκ(dX (x, x0 ) + α)δα (x, x0 ) = exp −κDKL (dX (x, x0 ) + αkdX (x, x0 )) .
Then the ε-LSHRR provides (ξα , δα )-PXDP, hence (ξα , δα )-XDP.
6.3

Privacy Guarantee for LapLSH

Finally, we also show that LapLSH provides XDP. This is immediate from thefact that XDP is preserved under the post-processing by an LSH function.
Proposition 6 (XDP of QLapH and QLapLSH ) The (ε, dX )-LapLSH QLapH witha κ-bit LSH function H provides (εdX , 0)-XDP. The (ε, dX )-LapLSH QLapLSH
κof the κ-bit LSH functions also provides (εdX , 0)-XDP.
w.r.t. a distribution DH

7

Experimental Evaluation

We show an experimental evaluation of LSHRR and LapLSH on two real datasets:
MovieLens [41] and FourSquare [54]. Our goal is to determine the utility of thesemechanisms when compared with a (slow but accurate) true nearest neighborsearch. As a baseline, we also show the performance of vanilla (non-private) LSH.
7.1

Datasets and Experimental Setup

Our problem of interest is privacy-preserving friend matching (or friend recommendation). In this scenario, we are given a dataset of users in which each user
is represented as a (real-valued) vector of attributes. The data curator’s goal isto recommend k friends for each user based on their k-nearest neighbors.
For our experiments, we used the following two datasets:
MovieLens. The MovieLens 25m dataset [41] contains 162000 users with ratings
across 62000 movies, with ratings ranging from 1 to 5. We normalized the scores,
i.e., to mean 0, and gave unseen movies a score of 0. For each user, we constructeda rating vector that consists of the user’s rating for each movie.
Foursquare. The Foursquare dataset (Global-scale Check-in Dataset with User
Social Networks) [54] contains 90048627 check-ins by 2733324 users on POIs allover the world. We extracted 107091 POIs in New York and 10000 users who
have visited at least one POI in New York. For each user, we constructed avisit-count vector, which consists of a visit-count value for each POI.
For both datasets, we generated input (rating/visit-count) vectors of lengthn = 100, 500, 1000 to evaluate the effectiveness of LSH. Reduced vector lengths

LSH with Extended Differential Privacy(a) MovieLens Dataset

13(b) Foursquare Dataset

Fig. 1: Distributions of angular distances dθ to nearest neighbor for k = 1 foreach user, plotted for vectors with dimensions 100, 500 and 1000. The distance
0.5 represents orthogonal vectors; i.e., having no items in common. The privacy
guarantee for users is a function of the distance dθ to their nearest neighbors.

were used because LSH has poor utility for larger vector lengths and the utilityof our mechanisms requires a good baseline utility for LSH.
We computed the k nearest neighbors w.r.t. the angular distance dθ for 1000
users for k = 1, 5, 10 using standard NNS (i.e., pairwise comparisons over all inputs). The distributions of True Nearest Neighbor distances are shown in Fig. 1.
κ-bit LSH (for κ = 10, 20, 50) was implemented using the random-projectionbased hashing. For each user, we then computed their k nearest neighbors fork = 1, 5, 10 using the Hamming distance on bitstrings. To compute the overall(ξ, δ)-XDP guarantee as per Proposition 5, we fixed δ = 0.01 and dθ = 0.1 andvaried ε to generate ξ values in the range 0.1 to 20.
Fig. 1 shows that about 43% (resp. 16%) of input vectors with 100 (resp. 1000)
dimensions are within the distance of 0.1 in the Foursquare dataset. Thus, extended DP with dθ = 0.1 is useful to hide such input vectors.
7.2

Comparing Privacy and Utility

We use the angular distance dθ as our utility measure, i.e., to determine similarusers for the purposes of recommendations. For utility loss, we use Definition 2
instantiated with the angular distance dθ . We compare the utility loss of eachmechanism w.r.t. a comparable privacy guarantee, namely the overall privacy
budget εdeuc (x, x0 ) for LapLSH and ξα (x, x0 ) for LSHRR (Proposition 5). However, as LSHRR’s privacy guarantee depends on the angular distance dθ and
LapLSH’s depends on deuc , they cannot be compared directly. For comparison
using the same metric, we use the relationship between the Euclidean and angular distances for normalized vectors x, x0 :pdeuc (x, x0 ) =2 − 2 cos(π·dθ (x, x0 )) .
(4)
We normalized input vectors to length 1 (noting that the normalization does
not affect the angular distance, hence utility), and transformed εdeuc (x, x0 ) into

14

Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami

ξα (x, x0 ) using (4) (Since ξα (x, x0 ) depends on α and dθ (x, x0 ), we perform
comparisons against various reasonable ranges of these variables).
We note that the trade-off between privacy and utility means that users withsimilar profiles will be indistinguishable from each other, whereas users with very
different profiles can be distinguished. This is an inherent trade-off determinedby the correlation between the sensitive and useful information to be released.
7.3

Experimental Results

We compared the performance of LapLSH and LSHRR with that of vanilla LSH
in Fig. 2. We observe that LSHRR outperforms LapLSH when the dimensionof the input vector is n = 100, 500, or 1000. This is because LapLSH needs
to add noise for each element of the input vector (even if the vector is sparseand includes many zero elements) and the total amount of noise is very large inhigh-dimensional data. In contrast, when the vector length is n = 50, LapLSH(κ = 50 bits) outperforms LSHRR (κ = 50 bits). We conjecture that this isbecause the total amount of noise used in LapLSH is small for low-dimensional
data whereas LSHRR needs to add a large amount of noise for each element of
the hash when the hash length κ is large. We expect LapLSH performance toimprove further over LSHRR for smaller values of n.
Interestingly, we observe that although the performance of LSH degradesas the hash length κ decreases, the performance of LSHRR and LapLSH both
remain relatively stable. This is mainly because when κ is 5 times larger, theamount of information expressed by the hash can be roughly 5 times larger
whereas the amount of noise added to each bit is also 5 times larger. Whenthe privacy budget is ξ = 20, the performance of LSHRR on larger bit-lengths(κ = 20 or 50) overtakes the performance of 10-bit LSHRR. This is because theutility loss of LSHRR is bounded below by the utility loss of the corresponding
LSH; i.e., LSHRR converges to LSH with the same hash length κ as ξ increases.
Fig. 2 also shows that when the total privacy budget ξ is around 2, LSHRR
achieves lower utility loss than a uniformly random hash, i.e., LSHRR when
the total privacy budget is 0. LSHRR achieves much lower utility loss when the
total privacy budget is around 5. We can interpret the value of the total privacy
budget in terms of the flip probability in the RR. For example, when we use the20-bit hash, the total privacy budget of 5 for dθ = 0.05 corresponds to the casein which the RR flips each bit of the hash with the probability approx. 0.27.
Therefore, we flip around 5-bits on average out of 20-bits in this case.
We also note that the total privacy budget used in our experiments is muchsmaller than the privacy budget  previously used in the low privacy regime[31]. Specifically, Kairouz et al. [31], and subsequent works (e.g., [1, 43, 50, 55])
refer to  = ln |X | as a privacy budget in the low privacy regime. Since ourexperiments deal with high-dimensional data, a privacy budget of ln |X | would
be extremely large. For example, when we use the 1000-dimensional rating vector
in the MovieLens dataset, the privacy budget in the low privacy regime is:  =ln |X | = ln 51000 = 1609. The total privacy budget in our experiments (ξ ≤ 20)
is much smaller than this value, and falls into the medium privacy regime [1, 55].

LSH with Extended Differential Privacy

15(a) MovieLens Dataset(b) Foursquare Dataset

Fig. 2: Utility loss (y-axis) versus privacy budget ξ (x-axis) for LSHRR, LapLSH
and LSH on n-dimensional vectors. ξ is computed for various κ, and dθ = 0.1.

Note that LDP requires a much larger privacy budget than extended DP. For
example, by Proposition 5, when κ = 50 and dθ = 0.05 (resp. 0.1), the total
privacy budget ξ = 20 in extended DP corresponds to the total privacy budget
120 (resp. 80) in LDP. More details are shown in Appendix A.
Finally, we compare LSHRR with LapLSH in terms of time complexity andgeneral applicability. For time complexity, LapLSH requires O(nκ) operations(construction of n-dimensional noise, then κ-bit hashing). In contrast, LSHRR
requires O(mκ) operations, where m is the number of non-zero elements in the
input vector (κ-bit hashing on m non-zero elements followed by κ-randomized
response). Since m  n in practice, LSHRR is significantly more efficient.
For general applicability, LSHRR can be used with other metrics such as the
Jaccard metric [11], Earth Mover’s metric [12], and lp metric [18] by choosing
a suitable LSH function, whereas LapLSH is designed for the Euclidean metric
only. Thus, LSHRR has more potential applications than LapLSH.
In summary, we find that LSHRR is better than LapLSH in terms of bothtime complexity and general applicability, and provides high utility with a reasonable privacy level for a high-dimensional data (100 dimensions or more).

16

7.4

Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami

Inapplicability of the RAPPOR

We finally explain that neither the RAPPOR [23] nor the generalized RAPPOR[51] can be used for friend matching based on high-dimensional personal data.
These mechanisms apply a Bloom filter to an input vector before applying therandomized response. Typically, this Bloom filter is a hash function that neither
allows for efficiently finding an input from its hash value, nor preserves the metricdX over the inputs. For instance, [23] uses MD5 to implement the Bloom filter.
Let us consider two approaches to perform the nearest neighbor search using
RAPPOR: comparing two hash values and comparing two input vectors.
In the first approach, the data collector calculates the Hamming distance
between obfuscated hash values. Then the utility is completely lost, because theBloom filter does not preserve the metric dX over the inputs. Hence we cannot
recommend friends based on the proximity of input vector in this approach.
In the second approach, the data collector tries to invert obfuscated hashvalues to the original input vector, and calculates the angular distance between
the input vectors to find nearest neighbors. Since the Bloom filter may not allow
for efficiently finding an input from its hash value, the data collectors need toperform exhaustive searches, i.e., to compute the hash values of all possible input
data X . However, this is computationally intractable when the input domain X
is very large. In particular, our setting deals with high-dimensional input data
(e.g., |X | = 51000 in the 1000-dimensional MovieLens rating vector), and thus it
is computationally infeasible to invert hash values into input vectors.
In summary, the first approach (comparing two hashes) results in a complete loss of utility, and the second approach (comparing two input vectors) is
computationally infeasible when the input data are in a high-dimensional space.
Therefore, the RAPPOR cannot be applied to our problem of friend matching.
The same issue applies to a generalized version of the RAPPOR [51].
In contrast, our mechanisms can be applied to friend matching even when
|X | is very large, because LSH allows us to approximately compare the distance
between the input vectors without computing them from their hash values.

8

Conclusion

In this paper, we proposed two extended DP mechanisms LSHRR and LapLSH.
We showed that LSH itself does not provide privacy guarantees and could result
in complete privacy collapse in some situations. We then proved that LSHRR
and LapLSH provide rigorous guarantees of extended DP. To our knowledge,
this work is the first to provide extended DP with the angular distance.
By experiments with real datasets, we show that LSHRR outperforms LapLSH
on high-dimensional data. We also show that LSHRR provides high utility fora high-dimensional vector, thus enabling friend matching with rigorous privacy
guarantees and high utility.

LSH with Extended Differential Privacy

17

References
1. Acharya, J., Sun, Z., Zhang, H.: Hadamard response: Estimating distributionsprivately, efficiently, and with little communication. In: AISTATS. pp. 1120–1129(2019)
2. Aggarwal, C.C.: Recommender Systems. Springer (2016)
3. Aghasaryan, A., Bouzid, M., Kostadinov, D., Kothari, M., Nandi, A.: On the useof LSH for privacy preserving personalization. In: TrustCom. pp. 362–371 (2013)
4. Alvim, M.S., Chatzikokolakis, K., Palamidessi, C., Pazii, A.: Invited paper: Local
differential privacy on metric spaces: Optimizing the trade-off with utility. In: CSF.
pp. 262–267 (2018). https://doi.org/10.1109/CSF.2018.00026
5. Andoni, A., Indyk, P., Laarhoven, T., Razenshteyn, I., Schmidt, L.: Practical andoptimal LSH for angular distance. In: NIPS. pp. 1–9 (2015)
6. Andoni, A., Indyk, P., Razenshteyn, I.: Approximate nearest neighbor search inhigh dimensions. In: ICM. pp. 3287–3318. World Scientific (2018)
7. Andrés, M.E., Bordenabe, N.E., Chatzikokolakis, K., Palamidessi, C.: Geoindistinguishability: differential privacy for location-based systems. In: CCS. pp.
901–914. ACM (2013). https://doi.org/10.1145/2508859.2516735
8. Aumüller, M., Bourgeat, A., Schmurr, J.: Differentially private sketches for Jaccard
similarity estimation. CoRR abs/2008.08134 (2020)
9. Bordenabe, N.E., Chatzikokolakis, K., Palamidessi, C.: Optimal geoindistinguishable mechanisms for location privacy. In: CCS. pp. 251–262(2014)
10. Brendel, W., Han, F., Marujo, L., Jie, L., Korolova, A.: Practical privacy-preserving
friend recommendations on social networks. In: WWW. pp. 111–112 (2018)11. Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-wise independent
permutations. Journal of Computer and System Sciences 60, 630–659 (2000)
12. Charikar, M.S.: Similarity estimation techniques from rounding algorithms. In:
STOC. pp. 380–388 (2002)
13. Chatzikokolakis, K., Andrés, M.E., Bordenabe, N.E., Palamidessi, C.: Broadening
the scope of Differential Privacy using metrics. In: PETS. pp. 82–102 (2013)
14. Chen, L., Zhu, P.: Preserving the privacy of social recommendation with a differentially private approach. In: SmartCity. pp. 780–785. IEEE (2015)
15. Chen, X., Liu, H., Yang, D.: Improved LSH for privacy-aware and robust recommender system with sparse data in edge environment. EURASIP Journal on
Wireless Communications and Networking 171, 1–11 (2019)
16. Cheng, H., Qian, M., Li, Q., Zhou, Y., Chen, T.: An efficient privacy-preserving
friend recommendation scheme for social network. IEEE Access 6, 56018–56028(2018)
17. Chow, R., Pathak, M.A., Wang, C.: A practical system for privacy-preserving collaborative filtering. In: ICDM Workshops. pp. 547–554 (2012)
18. Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S.: Locality-sensitive hashing
scheme based on p-stable distributions. In: SCG. pp. 253–262 (2004)
19. Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Local privacy and statistical minimax
rates. In: FOCS. pp. 429–438 (2013)
20. Dwork, C.: Differential privacy. In: ICALP. pp. 1–12 (2006)
21. Dwork, C., Mcsherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity inprivate data analysis. In: TCC. pp. 265–284 (2006)
22. Dwork, C., Rothblum, G.N.: Concentrated differential privacy. CoRR
abs/1603.01887 (2016)18

Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami

23. Úlfar Erlingsson, Pihur, V., Korolova, A.: RAPPOR: Randomized aggregatableprivacy-preserving ordinal response. In: CCS. pp. 1054–1067 (2014)
24. Fernandes, N., Dras, M., McIver, A.: Processing text for privacy: an information
flow perspective. In: FM. pp. 3–21 (2018)
25. Fernandes, N., Dras, M., McIver, A.: Generalised differential privacy for text document processing. In: POST. pp. 123–148 (2019)
26. Fernandes, N., Kawamoto, Y., Murakami, T.: Locality sensitive hashing with extended differential privacy. CoRR abs/2010.09393 (2020),
https://arxiv.org/abs/2010.09393
27. Ganta, S.R., Kasiviswanathan, S.P., Smith, A.: Composition attacks and auxiliary
information in data privacy. In: KDD. pp. 265–273. ACM (2008)
28. Gionis, A., Indyk, P., Motwani, R.: Similarity search in high dimensions via hashing. In: VLDB. pp. 518–529 (1999)
29. Hu, H., Dobbie, G., Salcic, Z., Liu, M., Zhang, J., Lyu, L., Zhang, X.: Differentially private locality sensitive hashing based federated recommender system.
Concurrency and Computation Practice and Experience pp. 1–16 (2020)
30. Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing thecurse of dimensionality. In: STOC. pp. 604–613 (1998)
31. Kairouz, P., Bonawitz, K., Ramage, D.: Discrete distribution estimation underlocal privacy. In: ICML. pp. 2436–2444 (2016)
32. Kamalaruban, P., Perrier, V., Asghar, H.J., Kaafar, M.A.: Not all attributes are
created equal: dx -private mechanisms for linear queries. Proceedings on Privacy
Enhancing Technologies (PoPETs) 2020(1), 103–125 (2020)
33. Kawamoto, Y., Murakami, T.: On the anonymization of differentially private location obfuscation. In: ISITA. pp. 159–163. IEEE (2018)
34. Kawamoto, Y., Murakami, T.: Local obfuscation mechanisms for hiding probability
distributions. In: ESORICS. pp. 128–148 (2019)35. Li, M., Ruan, N., Qian, Q., Zhu, H., Liang, X., Yu, L.: SPFM: Scalable and privacypreserving friend matching in mobile clouds. IEEE Internet of Things Journal 4(2),583–591 (2017)
36. Liu, C., Mittal, P.: LinkMirage: Enabling privacy-preserving analytics on social
relationships. In: NDSS (2016)
37. Liu, Z., Wang, Y.X., Smola, A.J.: Fast differentially private matrix factorization.
In: RecSys. pp. 171–178 (2015)38. Ma, X., Ma, J., Li, H., Jiang, Q., Gao, S.: ARMOR: A trust-based privacypreserving framework for decentralized friend recommendation in online social networks. Future Generation Computer Systems 79, 82–94 (2018)39. Machanavajjhala, A., Kifer, D., Abowd, J.M., Gehrke, J., Vilhuber, L.: Privacy:
Theory meets practice on the map. In: ICDE. pp. 277–286. IEEE (2008)
40. Machanavajjhala, A., Korolova, A., Sarma, A.D.: Personalized social recommendations - accurate or private? VLDB 4(7), 440–450 (2020)
41. MovieLens 25m Dataset: https://grouplens.org/datasets/movielens/25m/ (accessed in 2020)
42. Murakami, T., Hamada, K., Kawamoto, Y., Hatano, T.: Privacy-preserving multiple tensor factorization for synthesizing large-scale location traces with clusterspecific features. Proc. Priv. Enhancing Technol. 2021(2), 5–26 (2021)
43. Murakami, T., Kawamoto, Y.: Utility-optimized local differential privacy mechanisms for distribution estimation. In: USENIX Security. pp. 1877–1894 (2019)44. Narayanan, A., Thiagarajan, N., Lakhani, M., Hamburg, M., Boneh, D., et al.:Location privacy via private proximity testing. In: NDSS. vol. 11 (2011)

LSH with Extended Differential Privacy

19

45. Nissim, K., Stemmer, U.: Clustering algorithms for the centralized and local models. In: Algorithmic Learning Theory. pp. 619–653 (2019)46. Qi, L., Zhang, X., Dou, W., Ni, Q.: A distributed locality-sensitive hashing-based
approach for cloud service recommendation from multi-source data. IEEE Journal
on Selected Areas in Communications 35(11), 2616–2624 (2017)47. Samanthula, B.K., Cen, L., Jiang, W., Si, L.: Privacy-preserving and efficient friend
recommendation in online social networks. Trans. Data Privacy 8(2), 141–171(2015)
48. Shin, H., Kim, S., Shin, J., Xiao, X.: Privacy enhanced matrix factorization forrecommendation with local differential privacy. IEEE Trans. on Knowledge andData Engineering 30(9), 1770–1782 (2018)
49. Wang, J., Liu, W., Kumar, S., Chang, S.F.: Learning to hash for indexing big data
– a survey. Proceedings of the IEEE 104(1), 34–57 (2016)
50. Wang, S., Huang, L., Wang, P., Nie, Y., Xu, H., Yang, W., Li, X.Y., Qiao, C.:
Mutual information optimally local private discrete distribution estimation. CoRR
abs/1607.08025 (2016), https://arxiv.org/abs/1607.08025
51. Wang, T., Blocki, J., Li, N., Jha, S.: Locally differentially private protocols forfrequency estimation. In: USENIX Security. pp. 729–745 (2017)
52. Warner, S.L.: Randomized response: A survey technique for eliminating evasive
answer bias. Journal of the American Statistical Association 60(309), 63–69 (1965)
53. Xiang, Z., Ding, B., He, X., Zhou, J.: Linear and range counting under metric-based
local differential privacy. In: ISIT. pp. 908–913 (2020)
54. Yang, D., Qu, B., Yang, J., Cudre-Mauroux, P.: Revisiting user mobility and social
relationships in LBSNs: A hypergraph embedding approach. In: WWW. pp. 2147–
2157 (2019)55. Ye, M., Barga, A.: Optimal schemes for discrete distribution estimation under local
differential privacy. In: ISIT. pp. 759–763 (2017)
56. Zhang, Y., Gao, N., Chen, J., Tu, C., Wang, J.: PrivRec: User-centric differentiallyprivate collaborative filtering using LSH and KD. In: ICONIP. pp. 113–121 (2020)

A

Total Privacy Budgets in Extended DP and LDP

Table 1 shows total privacy budgets in extended DP and LDP calculated from
Proposition 5 and the fact that the angular distance is 0.5 or smaller.
For example, when dθ = 0.05 and κ = 10, 20, and 50, the total privacy
budget ξ = 20 in extended DP corresponds to the total privacy budget of 55, 79,
and 120, respectively, in LDP.

Table 1: Total privacy budgets in extended DP (XDP) and LDP when dθ = 0.05
or 0.1, κ = 10, 20, or 50, and δ = 0.01.
(a) dθ = 0.05
Total privacy budget ξ in XDP
1
5
10
20
Total privacy budget in LDP (κ = 10/20/50) 3/4/6 14/20/30 28/40/60 55/79/120(b) dθ = 0.1
Total privacy budget ξ in XDP
1
5
10
20
Total privacy budget in LDP (κ = 10/20/50) 2/3/4 10/14/20 21/28/40 42/57/80

20

B

Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami

Proofs for the Technical Results

We first recall Chernoff bound, which is used in the proof for Lemma 4.
Lemma 1 (Chernoff bound) Let Z be a real-valued random variable. Thenfor all t ∈ R,
E[exp(sZ)]
Pr[Z ≥ t] ≤ min.
s∈R
exp(st)Next we recall Hoeffding’s lemma, which is used in the proof for Proposition 4.
Lemma 2 (Hoeffding) Let a, b ∈ R, and Z be a real-valued random variable
such that E[Z] = µ and that a ≤ Z ≤ b. Then for all t ∈ R,
2 
2E[exp(tZ)] ≤ exp tµ + t8 b − a .
2 2Note that Lemma 2 implies that E[exp(t(Z − E[Z]))] ≤ exp t8 b − a .
Then we recall Chernoff-Hoeffding Theorem, which is used in the proof
for Theorem 1. Recall that the Kullback-Leibler divergence DKL (akb) between
Bernoulli distributed random variables with parameters a and b is defined by:
DKL (akb) = a ln ab + (1 − a) ln 1−a1−b .
Lemma 3 (Chernoff-Hoeffding) Let Z ∼ Binomial (k, p) be a binomially distributed random variable where k is the total number of experiments and p is
the probability that an experiment yields a successful outcome. Then for any
α ∈ R>0 ,
Pr[Z ≥ k(p + α)] ≤ exp −kDKL (p + αkp) .
By relaxing this, we have a simpler bound:Pr[Z ≥ k(p + α)] ≤ exp −2kα2 .
We show the proofs for technical results as follows.
Proposition 1 (Error bound) For any x, x0 ∈ X , the expected error in the2κ
Hamming distance satisfies E[|dV (QH (x), QH (x0 )) − dV (H(x), H(x0 ))|] ≤ 1+eεwhere the expectation is taken over the randomness in the bitwise RR.
Proof. By the triangle inequality and QH = Qbrr ◦ H, we have:dV (QH (x), QH (x0 )) ≤ dV (Qbrr ◦H(x), H(x))+dV (H(x), H(x0 ))+dV (H(x0 ), Qbrr ◦H(x0 )).
It follows from the definition of the bitwise RR Qrr that for any κ-bit string v ∈ V,κthe expected Hamming distance is E[dV (v, Qbrr (v))] = 1+e
ε . Thus E[dV (Qbrr ◦2κ00
H(x), H(x)) + dV (H(x ), Qbrr ◦ H(x ))] = 1+eε . Hence we obtain the proposition.
tuLSH with Extended Differential Privacy

21

We present LSHRR’s privacy guarantee for hash values, which relies on the
XDP of the bitwise RR Qbrr w.r.t. the Hamming distance dV as follows.
Proposition 7 (XDP of BRR) The (ε, κ)-bitwise RR provides (dV , 0)-XDP.
Proof. Recall the definition of the ε-RR Qrr in Definition 5. Let r = eε1+1 , v =(v1 , v2 , . . . , vκ ) ∈ V, v 0 = (v10 , v20 , . . . , vκ0 ) ∈ V, and y = (y1 , y2 , . . . , yκ ) ∈ V. By
definition we obtain:Qκ
Qbrr (v)[y] = i=1 r|yi −vi | (1 − r)1−|yi −vi |Qκ00Qbrr (v 0 )[y] = i=1 r|yi −vi | (1 − r)1−|yi −vi | .
By Qbrr (v 0 )[y] > 0 and the triangle inequality, we have:
κ

Y
0
0


Q (v )[y ]1−r |vi −vi |1−r dV (v ,v )=ln
= εdV (v, v 0 ).
ln Qbrrbrr(v 0 )[y ] ≤ ln
r
r
i=1

t
u

Therefore Qbrr provides (dV , 0)-XDP.

Proposition 2 (XDP of QH ) Let H : X → V be a κ-bit LSH function, anddεH be the pseudometric over X defined by dεH (x, x0 ) = εdV (H(x), H(x0 )) forx, x0 ∈ X . Then the ε-LSHRR QH instantiated with H provides (dεH , 0)-XDP.
Proof. Let x, x0 ∈ X and y ∈ V.
QH (x)[y] = Qbrr (H(x))[y]≤ εdV (H(x), H(x0 ))Qbrr (H(x0 ))[y](by Proposition 7)= εdH (x, x0 )QH (x0 )[y](by the def. of dεH )Hence QH provides (dεH , 0)-XDP.

tu

Proposition 3 (Worst-case privacy of QH ) For a κ-bit LSH function H,
the ε-LSHRR QH instantiated with H provides κ-DP.
Proof. Since dH (x, x0 ) ≤ κ holds for all x, x0 , this proposition follows from
Proposition 2.
Lemma 4 (CXDP ⇒ PXDP) Let µ ∈ R≥0 ,√τ ∈ R>0 , λ ∈ DR, Aλ : X → DY,
and d be a metric over X . Let δ ∈ (0, 1], ε = τ −2 ln δ, and ξ(x, x0 ) = µd(x, x0 )+ε. If Aλ provides (µ, τ, d)-CXDP, then it provides (ξ, δ)-PXDP.
Proof. Assume that Aλ provides (µ, τ, d)-CXDP. Let x, x0 ∈ X . Then we willshow Pr[ Lx,x0 > µd(x, x0 ) + ε ] ≤ δ as follows.
Let Z = Lx,x0 − E[Lx,x0 ]. By the definition of CXDP, we have:
E[Lx,x0 ] ≤ µd(x, x0 ),

(5)

22

Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami√
and Z is τ -subgaussian. Let t = τ −2 ln δ and a = τ 2 . By the definition of2
subgaussian variables, E[exp(sZ)] ≤ exp( as2 ) holds for any s ∈ R. Thus we
obtain:Pr[Z ≥ t] ≤ mins∈RE[exp(sZ)]
exp(st)(by the Chernoff bound in Lemma 1)2 
by E[exp(sZ)] ≤ exp( as2 )≤ min exps∈R
2 t2 = min exp a2 s − at − 2a
s∈R


t2
= exp − 2awhen s = atas2
2 − st(6)√

Recall that ε = τ −2 ln δ by definition. We obtain:
Pr[Lx,x0 > µd(x, x0 ) + ε]√
≤ Pr[Lx,x0 > E[Lx,x0 ] + τ −2 ln δ]√= Pr[Z > τ −2 ln δ]√ln δ)2 ≤ exp − (τ −22a(by (5) and the def. of ε)(by the def. of Z)√(by (6) and t = τ −2 ln δ)(by a = τ 2 )=δ

Therefore the randomized algorithm Aλ provides (ξ, δ)-PXDP.

tuLemma 5 (PXDP ⇒ XDP) Let λ ∈ DR, Aλ : X → DY, ξ : X × X → R≥0 ,and δ : X × X → [0, 1]. If Aλ provides (ξ, δ)-PXDP, it provides (ξ, δ)-XDP.
Proof. Assume that Aλ provides (ξ, δ)-PXDP. Let x, x0 ∈ X . By the definition
0of (ξ, δ)-PXDP, we have Pr[ Lx,x0 > ξ(x, x0 ) ] ≤ δ(x,For each
Px ). Let S ⊆ Y.
00r ∈ R, let Sr = {y ∈ S | Lx,x0 ,y,r > ξ(x, x )}. Then r λ[r]Ar (x)[Sr0 ] ≤ δ(x, x0 )and for each r ∈ R,
Ar (x)[S \ Sr0 ] ≤ exp(ξ(x, x0 )) · Ar (x0 )[S \ Sr0 ].
Hence:Aλ (x)[S] =P

λ[r]Ar (x)[S]

=

Pr

≤

P

P
0
0
r λ[r]Ar (x)[S \ Sr ] +r λ[r]Ar (x)[Sr ]000r λ[r] exp(ξ(x, x )) · Ar (x )[S \ Sr ]≤ exp(ξ(x, x0 )) ·+ δ(x, x0 )

P


0
λ[r]A
(x
)[S]
+ δ(x, x0 )rr

≤ exp(ξ(x, x0 )) · Aλ (x0 )[S] + δ(x, x0 ).
Therefore Aλ provides (ξ, δ)-XDP.

tu

LSH with Extended Differential Privacy

23

To prove the CXDP of LSHRR, we show that the Hamming distance between
hash values follows a binomial distribution.
Lemma 6 (Distribution of the Hamming distance of LSH) Let H be an
LSH scheme w.r.t. a metric dX over X coupled with a distribution DH . Letx, x0 ∈ X be any two inputs, and Z be the random variable of the Hamming
distance between their κ-bit hash values, i.e., Z = dV (H(x), H(x0 )) where a κ-bitκ
LSH function H is drawn from the distribution DH. Then Z follows the binomial
0
distribution with mean κdX (x, x ) and variance κdX (x, x0 )(1 − dX (x, x0 )).
Proof. By the definition of the Hamming distance dV and thePκ construction of 0the0
LSH-based
κ-bitfunction
H,
we
have
d
(H(x),
H(x))=
V
i=1 | hi (x) − hi (x ) |.
Pκ
Since i=1 | hi (x)−hi (x0 ) | represents the number of non-collisions between hashvalues of x and x0 , it follows the binomial distribution with mean κdX (x, x0 )and variance κdX (x, x0 )(1 − dX (x, x0 )).
tu
Proposition 4 (CXDP of QLSHRR ) The ε-LSHRR provides (εκ, εκ
2 , dX )-CXDP.
Proof. For a κ-bit LSH function H ∈ Hκ ,QH (x)[y] = Qbrr (H(x))[y]0≤ eεdV (H(x),H(x )) Qbrr (H(x0 ))[y]0= eεdV (H(x),H(x )) Q (x0 )[y].

(by Proposition 7)H

def

Let Z be the random variable defined by Z = dV (H(x), H(x0 )) where H =(h1 , h2 , . . . , hκ ) is distributed over Hκ , namely, the seeds of these LSH functions
are chosen randomly. Then 0 ≤ Z ≤ κ. By Lemma 6, Z follows the binomial
distribution with mean E[Z] = κdX (x, x0 ). Then the random variable εZ −E[εZ] is centered, i.e., E[εZ − E[εZ]] = 0, and ranges over [−εκdX (x, x0 ), εκ(1 −dX (x, x0 ))]. Hence it follows from Hoeffding’s lemma (Lemma 2) that:
2 
2 
2
2
= exp t2 εκ.
E[exp(t(εZ − E[εZ]))] ≤ exp t8 εκ2Hence by definition, εZ − E[εZ] is εκ
2 -subgaussian. Therefore, the LSH-based
mechanism QLSHRR provides (εκ, εκtu
2 , dX )-CXDP.
qδ0Theorem 1 (PXDP/XDP of QLSHRR ) Let δ ∈ R>0 , ε0 = ε − ln
2 , and ξ(x, x ) =√00εκdX (x, x ) + ε κ. The ε-LSHRR provides (ξ, δ)-PXDP, hence (ξ, δ)-XDP.
q
def
ln δ
Proof. Let α = −2κ
. Let Z be the random variable defined by Z = dV (H(x),H(x0 )) where H = (h1 , h2 , . . . , hκ ) is distributed over Hκ . By Lemma 6, Z
follows the binomial distribution with mean E[Z] = κdX (x, x0 ). Hence it follows
from Chernoff-Hoeffding theorem (Lemma 3) that:
Pr[Z ≥ κ(dX (x, x0 ) + α)] ≤ exp −2κα2 = δ.
√Hence Pr[εZ ≥ εκdX (x, x0 )+ε0 κ] ≤ δ. Therefore QLSHRR provides (ξ, δ)-PXDP.
By Lemma 5, QLSHRR provides (ξ, δ)-XDP.
t
u

24

Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami

Proposition 5 (Tighter bound for PXDP/XDP) For a, b ∈ R>0 , let DKL (akb) =a ln ab + (1 − a) ln 1−a1−b . For an α ∈ R>0 , we define:ξα (x, x0 ) = εκ(dX (x, x0 ) + α)δα (x, x0 ) = exp −κDKL (dX (x, x0 ) + αkdX (x, x0 )) .
Then the ε-LSHRR provides (ξα , δα )-PXDP, hence (ξα , δα )-XDP.
def

Proof. Let Z be the random variable defined by Z = dV (H(x), H(x0 )) whereH = (h1 , h2 , . . . , hκ ) is distributed over Hκ . By Chernoff-Hoeffding theorem(Lemma 3),
Pr[Z ≥ κ(dX (x, x0 ) + α)] ≤ δα (x, x0 ).
Then Pr[εZ ≥ ξα (x, x0 )] ≤ δα (x, x0 ). Therefore QLSHRR provides (ξα , δα )-PXDP.
By Lemma 5, QLSHRR provides (ξα , δα )-XDP.
tu
Proposition 6 (XDP of QLapH and QLapLSH ) The (ε, dX )-LapLSH QLapH witha κ-bit LSH function H provides (εdX , 0)-XDP. The (ε, dX )-LapLSH QLapLSH
κof the κ-bit LSH functions also provides (εdX , 0)-XDP.
w.r.t. a distribution DH
Proof. Since the application of an LSH function is post-processing, the proposition follows from the XDP of the Laplace mechanism.
tu