Differentially Private One Permutation Hashing

Dear Reviewer uYfv,

We appreciate your review and feedback.

1. Our paper proposes the first comprehensive study on generating private sketches from the widely used minhash type algorithms (DP-OPH and DP-MH), which fills the gap in the literature. This type of algorithm is naturally good application of the randomized response method because the hash values are finite bits. While randomized response is a known technique in DP, deriving the algorithms and flipping probabilities requires careful and rigorous design and calculation. Developing the theoretical analysis on the utility (mean and variance) also needs non-trivial efforts.

2. The bound on $f$ is assumed to define the data domain of DP in a general sense and for the convenience of theoretical analysis. In the case of private data release where the task is to release the hash values of a set of data vectors, the lower bound on $f$ is natural (which is the smallest $f$ of the dataset).

3. Thanks for the suggestion. SortedIndex and MapToIndex are helper functions to define a within-bin random permutation $\pi^{(k)}$ of an empty bin $k$. $SortedIndex$ returns the original index of a sorted array. For example, let $D=16$, $K=4$, and $d=D/K=4$ and suppose the indices in each bin are in ascending order, and $\mathcal B_2=[1,5,13,15]$ is empty. Suppose $\pi(13)=5, \pi(5)=6, \pi(1)=7, \pi(15)=8$. In this case, $\pi(\mathcal B_2)=[7,6,5,8]$, so $SortedIndex(\pi(\mathcal B_2))=[3,2,1,4]$. Assume $k'=3$ is picked and $\pi(\mathcal B_3)=[9,12,10,11]$. At line 7 we have $MapToIndex=[11,10,9,12]$ and at line 8, $\pi^{(2)}$ is a mapping $[9,12,10,11]\mapsto [11,10,9,12]$, which effectively defines another within-bin permutation of $\pi(\mathcal B_3)$ using the partial ordering of $\pi(\mathcal B_2)$. Finally, we set $h_k(u)$ as the minimal index of ``1'' among the additionally permuted elements in bin $\mathcal B_{k'}$.

We will add this example in the appendix to better explain the algorithm. Thanks again for your suggestion.

Dear Reviewer F2fi,

Thanks for your valuable feedback and recognizing our contributions. We also believe that private minhash and OPH methods are important with many useful applications in practice.

1. Thanks for the discussion. Since related study is still missing in the literature, as the first paper on private OPH, we tried to provide a comprehensive study on different variants of OPH and show how to privatize each of them. And also, densified OPH methods (fix and re) lead to theoretically more rigorous approaches (we will discuss more in the reply to Q3). The practitioner can choose which method s/he would like to apply in practice, depending on the use case and privacy requirements. We appreciate your suggestions and indeed, the very good performance of DP-OPH-rand in the high privacy region makes it a strong variant. We will add more discussion on this method in the paper.

2. In our paper, we assumed a lower bound on the number of non-zero elements $f$ for theoretical consideration. Essentially, $f$ defines the general data domain $\mathcal D$ in which our DP algorithms rigorously protect the data privacy for any vector. Under this assumption, the same algorithm (with same parameters) is applied to any vector in $\mathcal D=\{ u: number\ of\ nonzeros \geq f \}$. This setup is more general and convenient for theoretical analysis.

In practice, if we have privatized a set of vectors (database) $X$ with the DP algorithm parameterized with $f$, adding vectors $U$ with number of non-zeros smaller than $f$ will not affect the privacy of $X$ which has already been privatized. We can treat $U$ as another database and apply DP-OPH with the $f$ value associated with $U$.

3. The two sources of randomness in the algorithm are different in that the hash functions must be kept in some way because we must apply the same set of hash functions to all the vectors. The randomness from DP flipping is independent for every data vector and every bit. In some sense, this randomness is “one-time”, so the risk of leaking this information is small. On the other hand, since hash functions need to be kept, it is exposed to a higher risk of leakage. In the setup of our paper, this risk is resolved because we already assume that the hash functions can be public. As you kindly mentioned, this setup is much more flexible and practical, and is a much stronger privacy setup in real-world applications.

4. As we mentioned in our answer to Q1, densified OPH (with fix and re) and DP-MH are more rigorous theoretically since we can have a unified-form unbiased estimator as given in Theorem 3.5. The essential reason is that for the non-DP version of the above three methods, every hash value is unbiased of the Jaccard similarity $J$. This does not hold for DP-OPH-rand because of the random bits assigned to empty bins. For DP-OPH-rand, it is possible to get an unbiased estimator specifically for each pair of data vectors depending on the statistics of both vectors, but it’s impossible to get a universally unbiased estimator as in Theorem 3.5. Therefore, we feel it is less interesting/meaningful to present the calculations for DP-OPH-rand. If suggested, we are happy to add a remark on this point in the paper.

Again, we sincerely appreciate your efforts in reviewing our paper and the nice suggestions.

Dear Reviewer vVL9,

Thanks for your review of our paper.

1. We presented $\delta=10^{-6}$ since it is a common choice in many DP papers. We also experimented with other $\delta$ values and the comparisons are similar. As you kindly mentioned, in some papers $\delta$ is interpreted/set as the reciprocal of data size. In our experiments, $10^{-6}$ is actually smaller than the reciprocal of the data sizes, making it a good choice of $\delta$.

2. As we discussed in the paper with the example of genomes data, each bit in a binary vector could be the indicator of a gene, which is highly sensitive. In another scenario of online advertising, each bit might be a sensitive information of an individual like age, job, education, marriage status, etc. Our algorithms prevents the identification of such features in the vector (for each individual).

The attribute-level privacy protection is standard in DP hashing methods, as we cited extensively in the paper. Since these hashes are signatures of the data vectors, this privacy setup is different from protecting the summary statistics. Protecting the privacy of the original data is in general harder. Our paper proposes privatized algorithms for minhash type methods which are very popular hashing algorithms. We believe this is a good contribution to the community.

3. In our plots, the horizontal dotted lines are the results for non-private OPH-re method.

Yes, as you mentioned, both $b$ and $K$ have trade-offs and an ‘optimal’ value.

$b$: larger $b$ leads to larger flipping probability which degrades the performance. Smaller $b$ makes minhash and OPH themselves less accurate. Thus, we should choose a ‘moderate’ $b$. Through our experiments, we found that $b=2$ to $4$ yields the best results.

$K$: larger $K$ leads to less privacy budget for each hash thus more noise. Smaller $K$ makes minhash and OPH themselves less accurate, too. Hence, similar to $b$, we should choose a ‘moderate’ $K$ as well. This choice also depends on the dataset, e.g., the dimensionality, sparsity, etc. For high dimensional data that are not extremely sparse (which is a common application case of minhash), $K=256$ to $1024$ is recommended.

4. Precision is the standard metric in similarity search. For each query, we have its N ground truth neighbors. If we retrieve $k$ neighbors of the query, precision is computed as (# of true neighbors in k retrieved points)/k, which measures how many retrieved points are indeed its neighbors. As we answered in Q3, the horizontal dotted lines are the results for non-private OPH-re method.

Thanks again for your feedback and suggestions.

Dear Reviewer zV5S,

We appreciate your review of our paper.

About the motivation and application: The similarity search experiments serve two purposes: 1. Evaluating the utility of the proposed algorithms in terms of similarity preservation, as you kindly pointed out; 2. Similarity search is itself an important application of minhash type algorithms in industry. The goal of search is, in general, to find similar data points to a query point. So the task is to return the IDs, not the raw data. With our algorithms, the original raw data is never published---the private hashes produced by our methods are signatures of the original data vectors that preserve the similarity information, which are directly used for search and ML model training tasks. Only the private hashes are used. In the example we gave in the paper, the bioinformatics community releases minhash of a large gene dataset on a regular basis for search and ML. In that case, only the hash values of each vector are released to the public, and the raw data is never published. However, those hashes are not private either. Our algorithms protect the privacy of those hashes in a rigorous DP manner. On the other hand, if the intent is to look at the raw data after retrieval, then there is no way to protect the data privacy. The motivation of our paper (and in fact, all the DP data protection papers) is to randomize/transform the data in a private way, at the same time preserving utility for search and learning.

Q1: SortedIndex and MapToIndex are helper functions to define a within-bin random permutation $\pi^{(k)}$ of an empty bin $k$. $SortedIndex$ returns the original index of a sorted array. For example, let $D=16$, $K=4$, and $d=D/K=4$ and suppose the indices in each bin are in ascending order, and $\mathcal B_2=[1,5,13,15]$ is empty. Suppose $\pi(13)=5, \pi(5)=6, \pi(1)=7, \pi(15)=8$. In this case, $\pi(\mathcal B_2)=[7,6,5,8]$, so $SortedIndex(\pi(\mathcal B_2))=[3,2,1,4]$. Assume $k'=3$ is picked and $\pi(\mathcal B_3)=[9,12,10,11]$. At line 7 we have $MapToIndex=[11,10,9,12]$ and at line 8, $\pi^{(2)}$ is a mapping $[9,12,10,11]\mapsto [11,10,9,12]$, which effectively defines another within-bin permutation of $\pi(\mathcal B_3)$ using the partial ordering of $\pi(\mathcal B_2)$. Finally, we set $h_k(u)$ as the minimal index of ``1'' among the additionally permuted elements in bin $\mathcal B_{k'}$.

Essentially, for an empty bin $k$, re-randomized densification picks a non-empty bin $k’$ at random, copies its data, and applies the bin-wise permutation of bin $k$ to the data of bin $k’$ to generated a hash value. We will add this example in the appendix as suggested. Thank you.

Q2. In Algorithm 5, it is $\epsilon$ instead of $\epsilon’$. This is because, DP-OPH-rand does not densify the empty bins. Instead, it directly assigns a random bit to the empty bins. Therefore, it does not use $\epsilon’$ which is computed for densified DP-OPH methods.

Q3. The very complicated form of Theorem 3.6 is because the calculation of DP-OPH methods involves many parameters (both related to data and algorithm) like $D$, $K$, $a$, $f$, $\epsilon$, $\delta$, $b$, etc, as well as many combinatorial calculations. We made a great effort to derive the analytical form of the variance, but further simplifying it seems difficult. Nevertheless, we verified the theorem in Figure 2 through numerical simulations.

We hope our explanation answers your questions properly. Please let us know if you have more questions. Thanks again for your efforts in reviewing our paper.