Differentially Private One Permutation Hashing

Dear Reviewer zun1:

Thanks for your review of our paper. Since the points in "Weakness" (except W3) overlap with the "Questions" to a large extent, we will combine some of our replies to "Weakness" and "Questions". Thank you.

W3. On the value of $\epsilon$: DP has been deployed in a wide range of fields and applications, and the feasible $\epsilon$ depends on the specific use case. For example, in the tutorial [How to dp-fy ml: A practical guide to machine learning with differential privacy, Ponomareva et al., 2023, Section 5.2] by Google, the researchers defined $\epsilon<10$ as "reasonable privacy protection". For the U.S Census use case [The use of differential privacy for census data and its impact on redistricting: The case of the 2020 U.S. Census, Kenny et al., 2021], $\epsilon=12.2$ is chosen. The PyTorch tutorial of DP-SGD training set $\epsilon=47.2$ (https://github.com/pytorch/opacus/blob/main/tutorials/building_image_classifier.ipynb). Therefore, depending on the application and privacy requirement, we believe that different $\epsilon$ values in DP-OPH are useful in difference use cases.

Q1 & W2. On the non-private performance: The precision at $\epsilon=50$ (after the curves become flat) essentially equals to the precision of the non-private methods.

Q2 & W2. On the implication of experiments: the task in our experiments is nearest neighbor search with hashing. This is a standard task to evaluate the empirical performance of hashing methods, which demonstrates the utility of different algorithms in terms of Jaccard similarity approximation. Also, nearest neighbor search is itself an important "downstream task" of the hash samples in industrial applications where hashing/sketching methods are widely used for accelerated computation. Thus, our results already show that the proposed methods is advantageous in hashing applications with privacy constraints. We presented our results on three datasets from different domains: biology, image, and web. We hope this is sufficient to justify the benefits of our proposed methods for a variety of applications.

Q3 & W1. On the privacy definition: As we mentioned/cited in the paper, attribute-level DP is a standard setup in the literature of private sketching/hashing, e.g., [Kenthapadi et al, 2013], [Stausholm, 2021], [Zhao et al, 2022], [Smith et al, 2020], [Dickens et al, 2022]. The reason is that, our goal is to privatize the output hash values, and they are representations (or called "signatures" in some fields) of each data vector. Thus, it is natural to treat a data vector as the "database", and define "neighboring" on the coordinate level.

We have two remarks here regarding Question 3. First, for real data vectors and when the randomness of the hashing algorithm is internal and private [Blocki et al.2012], there is a privacy definition that requires $\|u-u'\|\leq 1$ for neighboring vectors $u$ and $u'$. For binary data, this is equivalent to our definition. We may extend the definition to "differing in multiple coordinates", which is similar to the notion of "group privacy". This requires more involved analysis, which could be an independent study for future investigation. In this paper, we follow the common definition of "one coordinate change" in most related works on private sketching.

Second, if what the reviewer suggested is to protect arbitrarily different vectors $u$ and $u'$, then the problem becomes impossible to solve because the output hash values of two arbitrary vectors in $u$ and $u'$ in $R^d$ can also be arbitrarily different. It is hard to find useful data representation while requiring that the representation of any data vector should look similar (which is required by DP).

Dear Reviewer BuXH:

Thanks for your feedback on our submission.

W1. As you kindly pointed out, in principle the variance of the (unbiased) Jaccard estimator from DP-OPH can be computed. However, given the already very complicated combinatorial form of the variance of non-private OPH, the expression will be extremely sophisticated also considering the b-bit coding and DP flipping. Thus, a straightforward analytical comparison is hard. We hope the empirical MSE comparisons in the appendix suffice to demonstrate that DP-OPH-re has smaller variance. Moreover, we know that in general the extra variation brought by DP would be largely determined by $N$, the privacy discount factor in DP-OPH-re and DP-OPH-fix. In Figure 1, we compare the $N$ of difference methods to intuitively show the advantage of the proposed approach in terms of privacy. These comparisons, together with the extensive experiments, show that the proposed algorithms provide better utility.

W2. Clarification on the background: Thanks for the nice suggestion. When we drafted the paper, we had to omit some contents due to the space limitation. We will definitely add more clarifications on the background of OPH and b-bit coding strategy. 1) Instability of naive OPH: without densification, the Jaccard estimation of OPH is (# of hash collisions)/(# of jointly non-empty bins). For sparse data, the denominator could be very small. Thus, the estimated value may vary a lot. For the metric, we refer to the Hamming distance. 2) We will add more references on b-bit coding, especially the empirical evaluations. Using b-bit coding will lead to some performance drop, which increases as $b$ gets smaller. However, truncating the hash values in this way is a standard step for the convenient use in practice. Since the vanilla OPH or MH hash values are large integers, b-bit coding is important for our DP methods---it limits the output domain so that bit flipping is able to guarantees a certain level of utility.

Q1. As we mentioned/cited in the paper, attribute-level DP is a standard setup in the literature of private sketching/hashing, e.g., [Kenthapadi et al, 2013], [Stausholm, 2021], [Zhao et al, 2022], [Smith et al, 2020], [Dickens et al, 2022]. The reason is that, our goal is to privatize the output hash values, and they are representations (or called "signatures" in some fields) of each data vector. It then becomes natural to treat a data vector as the "database", and define "neighboring" on the coordinate level.

We may also "consider the entire D-dimensional vector" as you mentioned. We discuss two settings here. First, for real data vectors and when the randomness of the hashing algorithm is internal and private [Blocki et al.2012], there is a privacy definition that $\|u-u'\|\leq 1$ for neighboring vectors $u$ and $u'$. For binary data, this is equivalent to our definition. We may extend the definition to "differing in multiple coordinates", which is similar to the notion of "group privacy". This requires more involved analysis, which could be an independent study for future investigation. In this paper, we follow the common definition of "one coordinate change" in most related works on private sketching.

Second, if what the reviewer suggested is to protect arbitrarily different vectors $u$ and $u'$, then the problem becomes impossible to solve because the output hash values of two arbitrary vectors $u$ and $u'$ in $R^d$ can also be arbitrarily different. It is hard to find useful data representation while requiring that the representation of any data vector should look similar (which is required by DP).

Q2. Thanks for the question and we would like to provide our thoughts here. In some DP papers, $\delta=1/n$ ($n$ is the size of the database) is used, but in our understanding this might be largely because the interpretation "at most one user's record will be leaked" seems more consistent with the "unit change" notions in the definition of DP. There are also many other papers that simply choose a deterministic value for $\delta$, which, based on our experience, is usually between $\delta=10^{-6}\sim 10^{-4}$. In our work, we presented the results with $\delta=10^{-6}$ which is smaller than $1/D$ for all the datasets in our experiments. The comparisons indeed hold for other $\delta$ values that we have experimented.

Q3. $D$ can be publicly known and fixed. When we interpret binary vectors as sets, $D$ is the size of the universe of items, and "1" means the item is in the set. So basically, in our problem we assume the universe itself does not change. The add/deletion operation is on the set level---the data coordinate of $x$ changing from 0 to 1 means "adding the item to the set", and changing from 1 to 0 means "deleting the item from the set".

We hope our rebuttal adequately answers your questions. Please kindly let us know if there are any further questions. Thank you.

Dear Reviewer ZyNs,

Thanks for your feedback on our work.

1. DP has been deployed in a wide range of fields and applications, and the feasible $\epsilon$ depends on the specific use case. For example, in the tutorial [How to dp-fy ml: A practical guide to machine learning with differential privacy, Ponomareva et al., 2023, Section 5.2] by Google, the researchers defined $\epsilon<10$ as "reasonable privacy protection". For the U.S Census use case [The use of differential privacy for census data and its impact on redistricting: The case of the 2020 U.S. Census, Kenny et al., 2021], $\epsilon=12.2$ is chosen. The PyTorch tutorial of DP-SGD training sets $\epsilon=47.2$ (https://github.com/pytorch/opacus/blob/main/tutorials/building_image_classifier.ipynb). Therefore, depending on the application and privacy requirement, we believe that different $\epsilon$ values in DP-OPH are useful in difference use cases.

In our plots, we presented $\epsilon\in [1,50]$. We referred to the recent paper [Zhao et al., Differentially private linear sketches: Efficient implementations and applications. NeurIPS 2022] when presenting the range of $\epsilon$. [Zhao et al. 2022] studied DP count sketch, which is similar to MinHash/OPH in terms of DP since count sketch also produces multiple hash values for each data vector. The range of $\epsilon$ used in [Zhao et al. 2022] is $[2.45, 33.5]$ (converted from zCDP). We presented larger $\epsilon$ to demonstrate the difference between DP-OPH-rand and densified DP-OPH-re.

For our proposed methods, DP-OPH-rand typically performs well with $\epsilon<10$. The densified DP-OPH-re may outperform DP-OPH-rand when $\epsilon>5\sim 15$, depending on the dataset. Therefore, we hope that all the variants could find useful use cases in practice.

2. The analysis of DP-OPH is much more involving than DP-MH with some complicated combinatorial calculations due to the binning operations in OPH. Rigorously obtaining the flipping probability requires non-trivial efforts. On the high level, we propose DP-OPH and show that it can significantly improved DP-MH. We believe these new algorithm designs and results themselves are novel contributions to the literature of private sketching/hashing.

3. Thanks for the nice suggestions. Not requiring a trusted central server is indeed one advantage of our proposed methods. We will highlight it in the revision.

Again, we appreciate your valuable feedback. Please kindly let us know if there are any more questions that we can help clarify. Thank you.

I thank the authors for their answers. I further comment below referencing points 1 and 2 of the rebuttal.

1- The authors cited [1,2,3,4] as evidence that $\epsilon \in [10, 50]$ provide reasonable privacy. I will argue why I am not convinced by these arguments:

1a- I would first like to point out that [1] is a guide that mainly focuses on the privacy of broader ML tasks. The objective of the current submission is privatizing a low level primitive that, in machine learning practice, will be part of larger protocols. The current submission provides privacy (with reasonable accuracy) only for upper half Tier 2 $\epsilon$ (i.e. $5 < \epsilon <= 10$) and Tier 3 $\epsilon (10 < \epsilon)$. In Section 5.2 of [1], it is argued that Tier 3 $\epsilon$ is considered almost as no privacy and Tier 2 $\epsilon$ is considered reasonably private only under certain conditions. The guide specifies that the choice of what is the privacy unit plays an important role. In this contribution, the privacy unit is not even an individual but an item of the individual. The guide also remarks that Tier 2 $\epsilon$ is sometimes considered private because ML privacy accounting techniques assume strong privacy leakages. However, these leakages do not occur often in practice (e.g. the leakage of intermediate iterations). Importantly, it is highlighted in [1] that

"from the DP point of view, the ε ∼ 10 guarantees might seem dubious" as "this value of ε would translate into the probability of a particular outcome changing by 22026 times on two datasets that differ only by one instance (in case of instance level privacy)."

1b- Is is highlighted in page 2 of [2] that $\epsilon$=12.2 "represents a relatively high privacy loss budget" and that even $\epsilon=4$ is high. In particular it is highlighted that "there may not be an overlap between the values of $\epsilon$ that are considered stringent enough for privacy purposes" and $\epsilon \in [4,12]$.

1c- [3] is a tutorial to understand basic concepts about DP ML and therefore it cannot serve as a reference of privacy in real applications

1d- The authors say that they take [4] as a reference for the (translated from zCDP by the authors) range [2.45, 33.5] of $\epsilon$. I do not see anywhere in [4] where it is argued that such range could be considered as good privacy parameters in sketching. Moreover, I think the range of parameters in [4] is different than what is claimed by the authors. Their experiments are done with $\rho \in {0.1, 1, 10 }$ of zero concentrated DP. I used Lemma 2.9 of [4] to convert zCDP to DP, and these values of $\rho$ would fall in the range [1.33, 10.79] for $\delta=10^{-6}$ as in you use in your experiments. Could you clarify why these values are different?

Given the points above, I am strongly discouraged to think that your technique provides reasonable levels of privacy

Refs. [1] How to dp-fy ml: A practical guide to machine learning with differential privacy, Ponomareva et al., 2023

[2] The use of differential privacy for census data and its impact on redistricting: The case of the 2020 U.S. Census, Kenny et al., 2021

[3] The PyTorch tutorial of DP-SGD training sets (https://github.com/pytorch/opacus/blob/main/tutorials/building_image_classifier.ipynb).

[4] Zhao et al., Differentially private linear sketches: Efficient implementations and applications. NeurIPS 2022

2- I am now more convinced that your proposed techniques contain additional novel content with respect to Aumüller et al. (2020). However, I am not sure. After a more detailed verification I will raise my score in the affirmative case. However, given point 1 above I doubt that I would positively support acceptance.

Dear Reviewer mGib:

Thanks for your feedback on our submission.

Q1. $J$ is the Jaccard similarity between $u$ and $v$ defined in equation (1), i.e., $J = J(u,v)$. We omitted "$(u,v)$" here. We will make the notation more clear. Thanks for pointing it out.

Q2. As we mentioned/cited in the paper, attribute-level DP is a standard setup in the literature of private sketching/hashing, e.g., [Kenthapadi et al, 2013], [Stausholm, 2021], [Zhao et al, 2022], [Smith et al, 2020], [Dickens et al, 2022]. The reason is that, our goal is to privatize the output hash values, and they are representations (or called "signatures" in some fields) of each data vector. Thus, it is natural to treat a data vector as the "database", and define "neighboring" on the coordinate level. For real data vectors and when the randomness of the hashing algorithm is internal and private, there is another privacy definition that $\|u-u'\|\leq 1$ for neighboring vectors $u$ and $u'$. However, for binary data, this is equivalent to our definition.

W3. The DP-OPH-rand variant (Algorithm 5) with random bits for empty bins achieves $\epsilon$-DP, see Theorem 3.3.

Regarding your major concern

Q3. About the OPH paper: We appreciate your very detailed research on the prior work. Actually, the Arxiv version of the NIPS 2012 paper https://arxiv.org/pdf/1208.1259.pdf included more details. The exact analysis of the OPH type algorithms is highly complicated with involved combinatorial calculations. In Lemma 6 and Lemma 7, the authors showed that the approximate Jaccard estimation variance ratio of OPH over minhash is smaller than 1. In Figure 8, we see that empirically OPH can perform better than minhash with smaller MSE.

Q4. The error bound in [1] is a simple consequence of applying Chernoff bound on the average of iid Bernoulli random variables. A minor point: in their Theorem 2, $\tau$ does not equal to $n$. Actually, it is the number of non-zeros in the data vector which can be much smaller than $n$. So the rate is $O(1/\sqrt{\tau \epsilon})$.

For DP-OPH, the analysis would be much harder and challenging. The key reason is that the hash values of OPH are not independent---recall that OPH is a "sample-without-replacement" approach, so the hash values are correlated to each other. Thus, the standard concentration tools would not be applicable here. Moreover, even if we compute the variance explicitly, it would be extremely sophisticated considering both the $b$-bit coding and DP flipping. Thus, a direct analytical comparison would be difficult. Given these reasons, we chose to present the comparison on the privacy discount factor $N$ in Figure 1, an empirical comparison of the Jaccard estimation variances in Appendix A, and justify the performance of DP-OPH methods through extensive experiments on datasets from computer vision, biology, and the web. We hope these results are convincing to show the effectiveness of DP-OPH methods.

We hope our reply clarifies your questions. Should there be any further questions, please kindly let us know. Thanks again for your efforts in reviewing our paper.

Dear Reviewer QDZh:

Thanks for your feedback.

Private sketching/hashing methods have attracted more and more attention in the research community recently. However, min-wise hashing and its efficient alternative, one permutation hashing, have not been studied under the differential privacy model. As we have extensively cited in the paper, these important algorithms have many applications in practice, so we believe providing private versions of these methods would be helpful to many researchers and practitioners. We actually tried several different ways to achieve DP, and it turns out that the "classic" generalized randomized response technique is the most effective one and well fits the discrete nature of our problem. While the DP tool is not completely new, the main technical contributions of our work is to properly specify the privacy parameters in DP-OPH (Lemma 3.1), which requires non-trivial design and analysis. We also provided three variants that can be chosen flexibly under different scenarios. We hope that our work can serve as a good guidance and reference for private hashing methods of the Jaccard similarity.

We hope our rebuttal could help the reviewer better appreciate our contributions. Again, thanks for your review of our work.