Y-Lan Boureau

Nicolas Le Roux

Francis Bach

Jean Ponce

Yann Lecun

Ask the locals: multi-way local pooling for image recognition

Invariant representations in object recognition systems are generally obtained by pooling feature vectors over spatially local neighborhoods. But pooling is not local in the feature vector space, so that widely dissimilar features may be pooled together if they are in nearby locations. Recent approaches rely on sophisticated encoding methods and more specialized codebooks (or dictionaries), e.g., learned on subsets of descriptors which are close in feature space, to circumvent this problem. In this work, we argue that a common trait found in much recent work in image recognition or retrieval is that it leverages locality in feature space on top of purely spatial locality. We propose to apply this idea in its simplest form to an object recognition system based on the spatial pyramid framework, to increase the performance of small dictionaries with very little added engineering. Stateof-the-art results on several object recognition benchmarks show the promise of this approach.

Introduction

Much recent work in image recognition has underscored the importance of locality constraints for extracting good image representations. Methods that incorporate some way of taking locality into account define the state of the art on many challenging image classification benchmarks such as Pascal VOC, Caltech-101, Caltech-256, and 15-Scenes [START_REF] Gao | Local features are not lonely-Laplacian sparse coding for image classification[END_REF][START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Yang | Efficient Highly Over-Complete Sparse Coding using a Mixture Model[END_REF][START_REF] Yu | Nonlinear learning using local coordinate coding[END_REF][START_REF] Zhou | Image Classification using Super-Vector Coding of Local Image Descriptors[END_REF].

The spatial pyramid [25] has emerged as a popular framework to encapsulate more and more sophisticated feature extraction techniques [START_REF] Boureau | Learning midlevel features for recognition[END_REF][START_REF] Gao | Local features are not lonely-Laplacian sparse coding for image classification[END_REF][START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Yang | Linear Spatial Pyramid Matching Using Sparse Coding for Image Classification[END_REF][START_REF] Yang | Efficient Highly Over-Complete Sparse Coding using a Mixture Model[END_REF][START_REF] Zhou | Image Classification using Super-Vector Coding of Local Image Descriptors[END_REF]. The global representation of an image is obtained by extracting image descriptors such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] or HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] on a dense grid, encoding them over some learned codebook or dictionary (coding step), and then summarizing the distribution of the codes in the cells of a spatial pyramid by some well-chosen aggregation statistic (pooling step).

Several recent papers have focused on refining the coding step, one purpose of which is to produce representations that can be aggregated (pooled) without losing too much information in the process. Pooling, which has long been part of popular recognition architectures such as convolutional networks [START_REF] Lecun | Gradientbased learning applied to document recognition[END_REF], gives robustness to small transformations of the image. It is related to Koenderink's concept of locally orderless images [START_REF] Koenderink | The structure of locally orderless images[END_REF], and can be traced back to Hubel and Wiesel's seminal work on complex cells in the visual cortex [START_REF] Hubel | Receptive fields, binocular interaction and functional architecture in the cat's visual cortex[END_REF]. The simplest pooling operation consists in averaging the feature vectors within a spatial neighborhood. One fact that makes the coding step necessary is that descriptors such as SIFT or HOG cannot be averaged with their neighbors without losing a considerable amount of information: the average of several widely different SIFT features doesn't tell us much about the content of the underlying image. Hence, coding is generally designed to produce representations that can be added with each other without diluting the signal. The original spatial pyramid proposal used vector quantization (K-means), which can be seen as a way of turning SIFT vectors into very sparse, 1-of-K codes. When obtained by averaging over spatial neighborhoods, the pooled codes can be interpreted as local histograms of visual words. Recent work has proposed to replace this hard quantization step of individual SIFT descriptors by soft vector quantization [START_REF] Van Gemert | Visual word ambiguity[END_REF], or sparse coding [START_REF] Yang | Linear Spatial Pyramid Matching Using Sparse Coding for Image Classification[END_REF], including sparse coding of local groups of SIFT descriptors (macrofeatures) instead of single ones, in our previous work [START_REF] Boureau | Learning midlevel features for recognition[END_REF].

While the pooling operations are often performed over local spatial neighborhoods, the neighborhoods may contain feature vectors that are very heterogeneous, possibly leading to the loss of a large amount of information about the distribution of features, as illustrated in Fig. (1). Restricting the pooling to feature vectors that are similar in the multidimensional input space (or nearby) [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF][START_REF] Zhou | Image Classification using Super-Vector Coding of Local Image Descriptors[END_REF] remedies this problem. The usefulness of considering similar inputs for smoothing noisy data over a homogeneous sample to reduce noise without throwing out the signal has long been recognized in the image processing and denoising communities [START_REF] Buades | A non-local algorithm for image denoising[END_REF]8], and has been successfully incorporated to denoising methods using sparse coding [START_REF] Mairal | Non-local sparse models for image restoration[END_REF]. It is interesting to note that considerations of locality often pull cod- ing and pooling in opposite directions: they make coding smoother (neighbors are used to regularize coding so that noise is harder to represent) and pooling more restrictive (only neighbors are used so that the signal does not get averaged out). This can be viewed as an attempt to distribute smoothing more evenly between coding and pooling.

Authors of locality-preserving methods have often attributed their good results to the fact that the encoding uses only dictionary atoms that resemble the input [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Yu | Nonlinear learning using local coordinate coding[END_REF], or viewed them as a trick to learn huge specialized dictionaries, whose computational cost would be prohibitive with standard sparse coding [START_REF] Yang | Efficient Highly Over-Complete Sparse Coding using a Mixture Model[END_REF]. However, this view may underestimate how local coding also makes pooling more local, by tying activation of a component more strongly to a region of the multidimensional input configuration space. We argue that more local pooling may be one factor in the success of methods that incorporate locality constraints into the training criterion of the codebook for sparse coding [START_REF] Gao | Local features are not lonely-Laplacian sparse coding for image classification[END_REF][START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Yu | Nonlinear learning using local coordinate coding[END_REF], or directly cluster the input data to learn one local dictionary per cluster [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Yang | Efficient Highly Over-Complete Sparse Coding using a Mixture Model[END_REF]. The question we attempt to answer in this paper is whether it is possible to leverage locality in the descriptor space once the descriptors have already been encoded. We argue that if the coding step has not been designed in such a way that the pooling operation preserves as much information as possible about the distribution of features, then the pooling step itself should become more selective.

The contributions of this work are threefold. First, we show how several recent feature extracting methods can be viewed in a unified perspective as preventing pooling from losing too much relevant information. Second, we demonstrate empirically that restricting pools to codes that are nearby not only in (2D) image space but also in descriptor space, boosts the performance even with relatively small dictionaries, yielding state-of-the-art performance or better on several benchmarks, without resorting to more complicated and expensive coding methods, or having to learn new dictionaries. Third, we propose some promising extensions.

The paper is organized as follows. Sec. 2 introduces the general classification pipeline that is used in this paper and much previous work and motivates our approach. Sec. 3 presents related work. Experiments are presented in Sec. 4.

General image recognition architecture and proposed approach

As argued in our previous work [START_REF] Boureau | Learning midlevel features for recognition[END_REF], many modern methods for image classification, such as convolutional and deep belief networks [17,[START_REF] Jarrett | What is the best multi-stage architecture for object recognition?[END_REF][START_REF] Lecun | Gradientbased learning applied to document recognition[END_REF]32], bags of features [34], histograms of gradients for pedestrian detection [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], or the spatial pyramid [25], implement an alternating series of coding and spatial pooling steps. Classification is then performed with some standard classifier such as a kernel or linear support vector machine (SVM), or logistic regression.

Feature extraction

Our setting for feature extraction is the following. Let 𝐼 denote an input image. First, low-level descriptors 𝒙 𝑖 (e.g., SIFT or HOG) are extracted densely at 𝑁 locations identified with their indices 𝑖 = 1, . . . , 𝑁. Coding is performed at each location by applying some operator that is chosen to ensure that the resulting codes 𝜶 𝑖 retain useful information (e.g., input data can be predicted from them), while having some desirable properties (e.g., compactness). Here, we focus on hard vector quantization and sparse coding, that both minimize some regularized error between inputs and the reconstructions that can be obtained from the codes.

Hard vector quantization is the simplest coding step, used in the bag-of-features framework [34]. It models the data with 𝐾 clusters, representing each 𝑥 𝑖 by a one-of-𝐾 encoding of its cluster assignment:

𝜶 𝑖 ∈ {0, 1} 𝐾 , 𝜶 𝑖,𝑗 = 1 iff 𝑗 = argmin 𝑘≤𝐾 ∥𝒙 𝑖 -d 𝑘 ∥ 2 2 , ( 1
)
where d 𝑘 denotes the 𝑘-th codeword of a codebook that is usually learned by an unsupervised algorithm such as Kmeans. The extreme sparseness of the codes produced (only one component per code is non-zero) may be ill-suited to images, and in fact better results have been obtained by replacing hard vector quantization by a soft probabilistic version [START_REF] Van Gemert | Visual word ambiguity[END_REF], or by sparse coding [START_REF] Boureau | Learning midlevel features for recognition[END_REF][START_REF] Yang | Linear Spatial Pyramid Matching Using Sparse Coding for Image Classification[END_REF].

Sparse coding [START_REF] Olshausen | Sparse coding with an overcomplete basis set: a strategy employed by V1?[END_REF] reconstructs the input as a linear combination of few codewords:

𝜶 𝑖 = argmin 𝜶 𝐿 𝑖 (𝜶, D) ≜ ∥𝒙 𝑖 -D𝜶∥ 2 2 + 𝜆∥𝜶∥ 1 , (2)
where ∥𝜶∥ 1 denotes the ℓ 1 norm of 𝜶, 𝜆 is a parameter that controls the sparsity of 𝜶, and D is some dictionary, which can be obtained by K-means, or for better performance, trained by minimizing the average of 𝐿 𝑖 (𝜶 𝑖 , D) over all samples, alternatively over D and the 𝜶 𝑖 . It is well known that the ℓ 1 penalty induces sparsity and makes the problem tractable (e.g., [START_REF] Lee | Efficient sparse coding algorithms[END_REF]29]).

A pooling operator then takes the varying number of codes that are located within 𝑀 possibly overlapping regions of interest (e.g., the cells of a spatial pyramid), and summarizes them as a single vector of fixed length. The representation for the global image is obtained by concatenating the representations of each region of interest, possibly with a suitable weight. We denote by 𝒴 𝑚 the set of locations/indices within region 𝑚. Here, we use the two common pooling strategies of average and max pooling.

Average pooling computes a histogram or take the average of the codes over the region (these two methods are equivalent after normalization):

𝒉 𝑚 = 1 |𝒴 𝑚 | ∑ 𝑖∈𝒴𝑚 𝜶 𝒊 , (3)
where 𝒉 𝑚 is the vector representing region 𝑚.

"Max pooling" computes the maximum of each component instead of its average. It has recently gained popularity due to its better performance when paired with sparse coding and simple linear classifiers [START_REF] Boureau | Learning midlevel features for recognition[END_REF][START_REF] Wang | An Effective Approach to Pose Invariant 3D Face Recognition[END_REF][START_REF] Yang | Linear Spatial Pyramid Matching Using Sparse Coding for Image Classification[END_REF], and its statistical properties which make it well suited to sparse representations [START_REF] Boureau | A theoretical analysis of feature pooling in vision algorithms[END_REF]. In our notation, max pooling is written:

𝒉 𝑚,𝑗 = max 𝑖∈𝒴𝑚 𝜶 𝑖,𝑗 , for 𝑗 = 1, . . . , 𝐾. ( 4
)
Max pooling is used for all experiments in this work, except those in Sec. 4.2.3.

Pooling more locally across the input space

We propose to streamline the approach in [START_REF] Yang | Efficient Highly Over-Complete Sparse Coding using a Mixture Model[END_REF], which requires learning one different dictionary per cluster, and show that simply making the pooling step more selective can substantially enhance the performance of small dictionaries, and beat the state of the art on some object recognition benchmarks when large dictionaries are used, without requiring additional learning beyond obtaining an additional clustering codebook with 𝐾-means. Comparing the performance of our system with that obtained with individual dictionaries allows us to quantify the relative contributions of more selective pooling and more specialized, overcomplete dictionaries.

To clarify how our local pooling scheme differs from the usual local spatial pooling, an image feature can be viewed as a couple 𝑧 = (𝒙, 𝒚), where 𝒚 ∈ ℝ 2 denotes a pixel location, and 𝒙 ∈ ℝ 𝑑 is a vector, or configuration, encoding the local image structure at 𝒚 (e.g., a SIFT descriptor, with 𝑑 = 128). A feature set 𝒵 is associated with each image, its size potentially varying from one picture to the next.

Spatial pooling considers a fixed -that is, predetermined and image-independent -set of 𝑀 possibly overlapping image regions (spatial bins) 𝒴 1 to 𝒴 𝑀 . To these, we add a fixed set of 𝑃 (multi-dimensional) bins 𝒳 1 to 𝒳 𝑃 in the configuration space. In this work, the spatial bins are the cells in a spatial pyramid, and the configuration space bins are the Voronoi cells of clusters obtained using 𝐾-means.

Denoting by 𝑔 the pooling operator (average or max in the previous section), the pooled feature is obtained as:

𝒉 (𝑚,𝑝) = 𝑔 (𝑖∈𝒴𝑚,𝑗∈𝒳𝑝) (𝜶 (𝑖,𝑗) ). (5)
Bags of features can be viewed as a special case of this in two ways: either by considering the 1-of-𝐾 encoding presented above, followed by global pooling in the configuration space (𝑃 = 1), or with a simplistic encoding that maps all inputs to 1, but does fine configuration space binning (𝑃 = 𝐾). Accordingly, the feature extraction in this paper can be viewed either as extending the sparse coding spatial pyramid by making configuration space pooling local, or as extending the hard-vector-quantized spatial pyramid by replacing the simplistic code by sparse coding: descriptors are first decomposed by sparse coding over a dictionary of size 𝐾; the same descriptors are also clustered over a 𝐾-means dictionary of size 𝑃 ; finally, pooling of the sparse codes is then performed separately for each cluster (as in aggregated coding [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] -see Sec. 3 -, but with sparse codes), yielding a feature of size 𝐾 × 𝑃 × 𝑆 if there are 𝑆 spatial bins.

While this does not apply to max pooling, local pooling can be viewed as implementing local bilinear classification when using average pooling and linear classification: the pooling operator and the classifier may be swapped, and classification of local features then involves computing 𝜷 𝑇 𝑥𝑦 𝑊 𝜶, where 𝜷 𝑥𝑦 is a (𝑆×𝑃 )dimensional binary vector that selects a subset of classifiers corresponding to the configuration space and spatial bins, and 𝑊 is a (𝑆 × 𝑃 ) × 𝐾 matrix containing one 𝐾-dimensional local classifier per row.

Related work about locality in feature space

We start our review of previous work with a caveat about word choice. There exists an unfortunate divergence in the vocabulary used by different communities when it comes to naming methods leveraging neighborhood relationships in feature space: what is called "non-local" in work in the vein of signal processing [START_REF] Buades | A non-local algorithm for image denoising[END_REF][START_REF] Mairal | Non-local sparse models for image restoration[END_REF] bears a close relationship to "local" fitting and density estimation [START_REF] Gao | Local features are not lonely-Laplacian sparse coding for image classification[END_REF][START_REF] Saul | Think globally, fit locally: unsupervised learning of low dimensional manifolds[END_REF][START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Yu | Nonlinear learning using local coordinate coding[END_REF]. Thus, non-local means [START_REF] Buades | A non-local algorithm for image denoising[END_REF] and locally-linear embedding [START_REF] Saul | Think globally, fit locally: unsupervised learning of low dimensional manifolds[END_REF] actually perform the same type of initial grouping of input data by minimal Euclidean distance. This discrepancy stems from the implicit understanding of "local" as either "spatially local", or "local in translation-invariant configuration space".

Preserving neighborhood relationships during coding

Previous work has shown the effectiveness of preserving configuration space locality during coding, so that similar inputs lead to similar codes. This can be done by explicitly penalizing codes that differ for neighbors. The DrLIM system of siamese networks in [START_REF] Hadsell | Dimensionality reduction by learning an invariant mapping[END_REF], and neighborhood component analysis [START_REF] Goldberger | Neighbourhood components analysis[END_REF], learn a mapping that varies smoothly with some property of the input by minimizing a cost which encourages similar inputs to have similar codes (similarity can be defined arbitrarily, as locality in input space, or sharing the same illumination, orientation, etc.) Exploiting image self-similarities has also been used successfully for denoising [START_REF] Buades | A non-local algorithm for image denoising[END_REF]8,[START_REF] Mairal | Non-local sparse models for image restoration[END_REF].

Locality constraints imposed on the coding step have been adapted to classification tasks with good results. Laplacian sparse coding [START_REF] Gao | Local features are not lonely-Laplacian sparse coding for image classification[END_REF] uses a modified sparse coding step in the spatial pyramid framework. A similarity matrix of input SIFT descriptors is obtained by computing their intersection kernel, and used in an added term to the sparse coding cost. The penalty to pay for the discrepancy between a pair of codes is proportional to the similarity of the corresponding inputs. This method obtains state-of-the-art results on several object recognition benchmarks. Localityconstrained linear coding [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF] (LLC) projects each descriptor on the space formed by its 𝑘 nearest neighbors (𝑘 is small, e.g., 𝑘 = 5). This procedure corresponds to performing the first two steps of the locally linear embedding algorithm [START_REF] Saul | Think globally, fit locally: unsupervised learning of low dimensional manifolds[END_REF] (LLE), except that the neighbors are selected among the atoms of a dictionary rather than actual descriptors, and the weights are used as features instead of being mere tools to learn an embedding.

Sparse coding methods incorporating a locality constraint share the property of indirectly limiting activation of a given component of the vectors representing descriptors to a certain region of the configuration space. This may play a role in their good performance. For example, in LLC coding, the component corresponding to a given dictionary atom will be non-zero only if that atom is one of the 𝑘 nearest neighbors of the descriptor being encoded; the non-zero values aggregated during pooling then only come from these similar descriptors. Several approaches have implemented this strategy directly during the pooling step, and are presented in the next section.

Letting only neighbors vote during pooling

Pooling involves extracting an ensemble statistic from a potentially large group of inputs. However, pooling too drastically can damage performance, as shown in the spatial domain by the better performance of spatial pyramid pooling [25] compared to whole-image pooling.

Different groups have converged to a procedure involving preclustering of the input to create independent bins over which to pool the data. In fact, dividing the feature space into bins to compute correspondences has been proposed earlier by the pyramid match kernel approach [14]. However, newer work does not tile the feature space evenly, relying instead on unsupervised clustering techniques to adaptively produce the bins.

The methods described here all perform an initial (hard or soft) clustering to partition the training data according to appearance, as in the usual bag-of-words framework, but then assigning a vector to each cluster instead of a scalar. The representation is then a "super-vector" that concatenates these vectors instead of being a vector that concatenates scalars.

Aggregated coding [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] and super-vector coding [START_REF] Zhou | Image Classification using Super-Vector Coding of Local Image Descriptors[END_REF] both compute, for each cluster, the average difference between the inputs in the cluster, and its centroid: (1) SIFT descriptors x 𝑖 are extracted at regions of interest, (2) visual words c 𝑘 are learned over the whole data by 𝐾-means, (3) descriptors of each image are clustered, (4) for each cluster 𝐶 𝑘 , the sum ∑ x∈𝐶 𝑘 (x -c 𝑘 ) is computed, (5) the image descriptor is obtained by concatenating the representations for each cluster.

If the centroids were computed using only the descriptors in a query image, the representation would be all zeros, because the centroids in K-means are also obtained by averaging the descriptors in each cluster. Instead, the centroids are computed using descriptors from the whole data, implicitly representing a "baseline image" against which each query image is compared. Thus, encoding relatively to the cluster centroid removes potentially complex but nondiscriminative information. This representation performs very well on retrieval [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] and image classification [START_REF] Zhou | Image Classification using Super-Vector Coding of Local Image Descriptors[END_REF] (Pascal VOC2009) benchmarks.

Another related method [START_REF] Yang | Efficient Highly Over-Complete Sparse Coding using a Mixture Model[END_REF] that obtains high accuracy on the Pascal datasets combines the preclustering step of aggregated and super-vector coding, with sparse decomposition over individual local dictionaries learned inside each cluster. Both approaches using preclustering for image classification [START_REF] Yang | Efficient Highly Over-Complete Sparse Coding using a Mixture Model[END_REF][START_REF] Zhou | Image Classification using Super-Vector Coding of Local Image Descriptors[END_REF] have only reported results using gigantic global descriptors for each image. Indeed, the high results obtained in [START_REF] Yang | Efficient Highly Over-Complete Sparse Coding using a Mixture Model[END_REF] are attributed to the possibility of learning a very large overcomplete dictionary (more than 250,000 atoms) which would be computationally infeasible without preclustering, but can be done by assembling a thousand or more smaller local dictionaries. The experiments presented in the next section seek to isolate the effect of local pooling that is inherent in this scheme.

Experiments

We perform experiments on three image recognition datasets: 15-Scenes [25], Caltech-101 [START_REF] Fei-Fei | Learning generative visual models from few training examples[END_REF] and Caltech-256 [START_REF] Griffin | Caltech-256 object category dataset[END_REF]. All features are extracted from grayscale images. Large images are resized to fit inside a 300 × 300 box. SIFT descriptors are extracted densely over the image, and encoded into sparse vectors using the SPAMS toolbox [1]. We adopt the denser 2 × 2 macrofeatures of our previous work [START_REF] Boureau | Learning midlevel features for recognition[END_REF], extracted every 4 pixels, for the Caltech-256 and Caltech-101 databases, and every 8 pixels for the Scenes, except for some experiments on Caltech-256 where standard features extracted every 8 pixels are used for faster processing. The sparse codes are pooled inside the cells of a three-level pyramid (4× 4, 2× 2 and 1× 1 grids); max pooling is used for all experiments except those in Sec. 4.2.3, which compare it to other pooling schemes. We apply an ℓ 1.5 normalization to each vector, since it has shown slightly better performance than no normalization in our experiments (by contrast, normalizing by ℓ 1 or ℓ 2 norms worsens performance). One-versus-all classification is performed by training one linear SVM for each class using LIBSVM [START_REF] Chang | LIBSVM: a library for support vector machines[END_REF], and then taking the highest score to assign a label to the input. When local pooling in the configuration space is used (𝑃 ≥ 1), clustering is performed using the 𝐾-means algorithm to obtain cluster centers. Following the usual practice [START_REF] Griffin | Caltech-256 object category dataset[END_REF]25,[START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], we use 30 training images on the Caltech-101 and Caltech-256 datasets, 100 training images on the Scenes dataset; the remaining images are used for testing, with a maximum of 50 and 20 test images for Caltech-101 and Caltech-256, respectively. Experiments are run ten times on ten random splits of training and testing data, and the reported result is the mean accuracy and standard deviation of these runs. Hyperparameters of the model (such as the regularization parameter of the SVM or the 𝜆 parameter of sparse coding) are selected by cross-validation within the training set. Patterns of results are very similar for all three datasets, so results are shown only on Caltech-101 for some of the experiments; more complete numerical results on all three datasets can be found in the supplemental material * .

Pooling locally in configuration space yields state-of-the-art performance

Experiments presented in Table 1 and 2 compare the performance of sparse coding with a variety of configuration space pooling schemes, with a list of published results of * http://cs.nyu.edu/∼ylan/files/publi/boureau-iccv-11-supplemental.pdf Caltech 30 tr. Scenes Boiman et al. [START_REF] Boiman | In Defense of Nearest-Neighbor Based Image Classification[END_REF] 70.4 -Boureau et al. [START_REF] Boureau | Learning midlevel features for recognition[END_REF] 75.7 ± 1.1 85.6 ± 0.2 Gao et al. [START_REF] Gao | Local features are not lonely-Laplacian sparse coding for image classification[END_REF] -89.8 ± 0.5 Jain et al. [19] 69.6 -Lazebnik et al. [25] 64.4 ± 0.8 81.4 ± 0.5 van Gemert et al. [START_REF] Van Gemert | Visual word ambiguity[END_REF] 64.1 ± 1.2 76.7 ± 0.4 Wang et al. [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF] 73.44 -Yang et al. [START_REF] Yang | Linear Spatial Pyramid Matching Using Sparse Coding for Image Classification[END_REF] 73.2 ± 0.5 80.3 ± 0.9 Zhang et al. [START_REF] Zhang | SVM-KNN: Discriminative nearest neighbor classification for visual category recognition[END_REF] 66.2 ± 0.5 -Zhou et al. [START_REF] Zhou | A novel gaussianized vector representation for natural scene categorization[END_REF] -84.1 ± 0.5 𝐾 = 256, Pre, 𝑃 = 1 70. methods using grayscale images and a single type of descriptor. Local pooling always improves results, except on the Scenes for a dictionary of size 𝐾 = 1024. On the Caltech-256 benchmark, our performance of 41.7% accuracy with 30 training examples is similar to the best reported result of 41.2% that we are aware of (for methods using a single type of descriptors over grayscale), obtained by locality-constrained linear codes [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], using three scales of SIFT descriptors and a dictionary of size 𝐾 = 4096.

Using pyramids in configuration space

We examine whether it is advantageous to combine fine and coarse clustering, in a way reminiscent of the levels of the spatial pyramid. With large dictionaries, local pooling in the configuration space does not always perform better than standard global pooling (see Tables 1 and2). However, combining levels of different coarseness gives performance better than or similar to that of the best individual level, as has been observed with the spatial pyramid [25]. This significantly improves performance on the Caltech-101 dataset. To the best of our knowledge, our performance of 77.3% on the Caltech-101 benchmark, is above all previously published results for a single descriptor type using grayscale images -although better performance has been reported with color images (e.g., 78.5% ± 0.4 with a saliency-based approach [START_REF] Kanan | Robust classification of objects, faces, and flowers using natural image statistics[END_REF]), multiple descriptor types (e.g., methods using multiple kernel learning have achieved 77.7% ± 0.3 [START_REF] Gehler | On Feature Combination for Multiclass Object Classification[END_REF], 78.0% ± 0.3 [2, 37] and 84.3% [START_REF] Yang | Group-sensitive multiple kernel learning for object categorization[END_REF] on Caltech-101 with 30 training examples), or subcategory learning (83% on Caltech-101 [START_REF] Todorovic | Learning subcategory relevances for category recognition[END_REF]). On the Scenes benchmark, preclustering does improve results for small dictionaries (𝐾 ≤ 256, see supplemental material), but not for larger ones (𝐾 = 1024). While our method outperforms the Laplacian sparse coding approach [START_REF] Gao | Local features are not lonely-Laplacian sparse coding for image classification[END_REF] on the Caltech 256 dataset, our performance is much below that of Laplacian sparse coding on the Scenes database.

Pre-vs. Post-Clustering

One advantage of using the same dictionary for all features is that the clustering can be performed after the encoding. The instability of sparse coding could cause features similar in descriptor space to be mapped to dissimilar codes, which would then be pooled together. This does not happen if clustering is performed on the codes themselves. While pre-clustering may perform better for few clusters, post-clustering yields better results when enough clusters are used (𝑃 ≥ 64); a dictionary of size 𝐾 = 1024 reaches 77.1 ± 0.7 accuracy on Caltech-101 with 𝑃 = 64 bins (to be compared to 76.2 ± 0.8 when clustering before coding), while a dictionary of size 𝐾 = 256 yields 76.7 ± 0.8 with 𝑃 = 128 bins (to be compared to 75.5±0.8 with preclustering). Fig. 2 also shows that performance drops for larger 𝑃 , irrespective of whether the clustering is performed before or after the encoding.

Gaining a finer understanding of local configuration space pooling

In this section, we investigate how much local configuration space pooling can enhance the performance of small dictionaries, how it compares to learning one local dictionary per configuration bins, and what pooling and weighting schemes work best in our pipeline.

Local pooling boosts small dictionaries

Fig. 3(a) shows results for various assignments of components between atoms (𝐾) and centroids (𝑃 ). Pooling more locally in configuration space (𝑃 > 1) can considerably boost the performance of small dictionaries.

Unsurprisingly, larger dictionaries consistently beat smaller ones combined with preclustering-driven pooling, at same total number of components; this can be seen from the downwards slope of the gray dashed lines in Fig. 3(a) linking data points at constant 𝐾 * 𝑃 . However, if 𝑃 is allowed to grow more, small dictionaries can outperform larger ones. This leads to good performance with a small dictionary; e.g., a dictionary of just 𝐾 = 64 atoms coupled with a preclustering along 𝑃 = 64 centroids achieves 73.0 ± 0.6% on Caltech-101.

Comparison with cluster-specific dictionaries

In addition to learning richer, more local dictionaries, learning one dictionary per cluster as done in [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Yang | Efficient Highly Over-Complete Sparse Coding using a Mixture Model[END_REF] inherently leads to more local pooling. Experiments in this section seek to disentangle these effects. As shown in Fig. 3(b), more than half of the improvement compared to no preclustering is usually due to the separate clustering rather than more specific dictionaries. The smaller the dictionary, the

Figure 1 .

 1 Figure 1. Cartoon representation of a distribution of descriptors that has a high curvature and is invariant to the spatial location in the image, with two feature components (left). The center and right figures show the samples projected across space in the 2D feature space. Due to the curvature of the surface, global pooling (center) loses most of the information contained in the descriptors; the red cross (average pooling of the samples) is far away from the lower-dimensional surface on which the samples lie. Clustering the samples and performing pooling inside each cluster preserves information since the surface is locally flat (right).

Table 1 .

 1 Results on Caltech-101 (30 training samples per class) and 15-scenes for various methods. Results for our method are given as a function of whether clustering is performed before (Pre) or after (Post) the encoding, 𝐾: dictionary size, and 𝑃 : number of configuration space bins.

		5 ± 0.8	78.8 ± 0.6
	𝑃 = 16	74.0 ± 1.0	81.5 ± 0.8
	𝑃 = 64	75.0 ± 0.8	81.1 ± 0.5
	𝑃 = 128	75.5 ± 0.8	81.0 ± 0.3
	𝑃 = 1 + 16 74.2 ± 1.1	81.5 ± 0.8
	𝑃 = 1 + 64 75.6 ± 0.6	81.9 ± 0.7
	𝐾 = 256, Post,𝑃 = 16	75.1 ± 0.8	80.9 ± 0.6
	𝑃 = 64	76.4 ± 0.8	81.1 ± 0.6
	𝑃 = 128	76.7 ± 0.8	81.1 ± 0.5
	𝐾 = 1024,Pre, 𝑃 = 1	75.6 ± 0.9	82.7 ± 0.7
	𝑃 = 16	76.3 ± 1.1	82.7 ± 0.9
	𝑃 = 64	76.2 ± 0.8	81.4 ± 0.7
	𝑃 = 1 + 16 76.9 ± 1.0	83.3 ± 1.0
	𝑃 = 1 + 64 77.3 ± 0.6	83.1 ± 0.7
	𝐾 = 1024,Post,𝑃 = 16	77.0 ± 0.8	82.9 ± 0.6
	𝑃 = 64	77.1 ± 0.7	82.4 ± 0.7

Table 2 .

 2 Recognition accuracy on Caltech 256, 30 training examples, for several methods using a single descriptor over grayscale. For our method, results are shown as a function of whether clustering is performed before (Pre) or after (Post) the encoding, 𝐾: dictionary size, and 𝑃 : number of configuration space bins.

				Accuracy
	Boiman et al. [3]		37.0
	Gao et al. [11] (𝐾 = 1024)	35.7 ± 0.1
	Kim et al. [23]			36.3
	van Gemert et al. [36] (𝐾 = 128)	27.2 ± 0.5
	Wang et al. [39] (𝐾 = 4096)	41.2
	Yang et al. [41] (𝐾 = 1024)	34.0 ± 0.4
	𝐾 = 256,	Pre,	𝑃 = 1	32.3 ± 0.8
			𝑃 = 16	38.0 ± 0.5
			𝑃 = 64	39.2 ± 0.5
			𝑃 = 128	39.7 ± 0.6
	𝐾 = 256,	Post, 𝑃 = 16	36.9 ± 0.7
			𝑃 = 64	39.6 ± 0.5
			𝑃 = 128	40.3 ± 0.6
	𝐾 = 1024, Pre,	𝑃 = 1	38.1 ± 0.6
			𝑃 = 16	41.6 ± 0.6
			𝑃 = 64	41.7 ± 0.8
	𝐾 = 1024, Post, 𝑃 = 16	40.4 ± 0.6

  Figure2. Recognition accuracy on Caltech-101, for clustering before or after encoding. Clustering after the encoding generally performs better; for both schemes, binning too finely in configuration space (large 𝑃 ) hurts performance. Best viewed in color.

		77
		76
		75
	Accuracy	74 73 72	Dictionary size 1024	Clustering After coding
		71	256	Before coding
		1	Configuration bins, log scale 4 16 64 256	1024

Acknowledgments. This work was supported by ONR contract N00014-09-1-0473 and NSF grant EFRI/COPN-0835878 to NYU, and by the European Research Council (VideoWorld and Sierra grants).

Configuration bins, log scale

larger the proportion of the improvement due to clustering. This may be due to the fact that smaller dictionaries do not have enough atoms to implicitly link activation of an atom to cluster membership during coding, leaving more of that task to the explicit local configuration space pooling than when large dictionaries are used.

Pooling operator and cluster weighting

When concatenating the vectors corresponding to each pool, it is not clear whether they should be weighted according to the prominence of the cluster, measured as the ratio 𝑁 𝑖 /𝑁 of the number 𝑁 𝑖 of inputs falling into cluster 𝑖, over the total number 𝑁 of inputs. Denoting by 𝑤 𝑖 the weight for cluster 𝑖, we compare three weighting schemes: identical weight (𝑤 𝑖 = 1), a weight proportional to the square root of the ratio (𝑤 𝑖 = √ 𝑁 𝑖 /𝑁 ) as proposed by Zhou et al. [START_REF] Zhou | Image Classification using Super-Vector Coding of Local Image Descriptors[END_REF], or the ratio itself (𝑤 𝑖 = 𝑁 𝑖 /𝑁 ).

As shown in Fig. 3(c), the weighting scheme assigning the same weight to each cluster performs better when max pooling is used, except for very small dictionaries. When average pooling is used, the best weighting scheme is the square root weighting, which empirically validates the choice in [START_REF] Zhou | Image Classification using Super-Vector Coding of Local Image Descriptors[END_REF], but performance is below that of max pooling. Based on these results, max pooling with identical weighting for all clusters has been used for all other experiments in the paper.

Conclusion

While there is no question that making coding more stable and more specific is advantageous, the simple procedure of clustering the data in order to make pooling local in configuration space is a powerful tool for image recognition. The main conclusions of this work are that (1) more local configuration space pooling in itself boosts performance, dramatically so with smaller dictionaries; (2) it is advantageous to use pyramids rather than grids, analogously to spatial pooling; (3) with enough configuration space bins, better performance may be obtained when the clustering is performed just before the pooling step, rather than before the coding step; (4) performance drops if too many bins are added.

Our ongoing efforts are focused on adapting the same ideas to pooling across features when there is a topography on the feature extractors, instead of simply pooling each component separately. We hope that considerating locality in all dimensions simultaneously (feature space, between feature extractors, and space itself) will lead to even more robust invariant recognition.


Mohammad Alaggan

Sébastien Gambs

Anne-Marie Kermarrec

Private Similarity Computation in Distributed Systems: from Cryptography to Differential Privacy

Keywords: Privacy, similarity measure, homomorphic encryption, differential privacy

In this paper, we address the problem of computing the similarity between two users (according to their profiles) while preserving their privacy in a fully decentralized system and for the passive adversary model. First, we introduce a two-party protocol for privately computing a threshold version of the similarity and apply it to well-known similarity measures such as the scalar product and the cosine similarity. The output of this protocol is only one bit of information telling whether or not two users are similar beyond a predetermined threshold. Afterwards, we explore the computation of the exact and threshold similarity within the context of differential privacy. Differential privacy is a recent notion developed within the field of private data analysis guaranteeing that an adversary that observes the output of the differentially private mechanism, will only gain a negligible advantage (up to a privacy parameter) from the presence (or absence) of a particular item in the profile of a user. This provides a strong privacy guarantee that holds independently of the auxiliary knowledge that the adversary might have. More specifically, we design several differentially private variants of the exact and threshold protocols that rely on the addition of random noise tailored to the sensitivity of the considered similarity measure. We also analyze their complexity as well as their impact on the utility of the resulting similarity measure. Finally, we provide experimental results validating the effectiveness of the proposed approach on real datasets.

Introduction

In the Web 2.0, more and more personal data are released by users (queries, social network, geolocated data. . . ), which creates a huge pool of useful information to leverage in the context of search or recommendation for instance. In fully decentralized systems, tapping on the power of this information usually involves some kind of clustering process that relies on an exchange of personal data (such as profiles) to compute similarity between users [START_REF] Bai | Gossiping Personalized Queries[END_REF]. In this paper, we address the problem of computing similarity between users while preserving their privacy and without relying on a central entity. Dissociating the identifiers of users from their data, through the use of pseudonyms for instance, is clearly not sufficient to protect their privacy. In fact, just looking at these Personal Identifiable Information (PII) may sometimes be enough to infer the identity of the associated users thus causing a privacy breach [START_REF] Barbaro | A face is exposed for AOL searcher No. 4417749[END_REF][START_REF] Narayanan | De-anonymizing Social Networks[END_REF][START_REF] Narayanan | Robust De-anonymization of Large Sparse Datasets[END_REF]. Moreover, to preserve the fully distributed nature of such systems, no trusted third party (e.g. central server) should be required.

In this paper, we propose a protocol based on cryptographic primitives that computes the similarity between two user profiles (represented as vectors) in such a way that each user only learns the output of the similarity computation but not the profiles themselves. The novelty of our approach is twofold. First, considering well-known similarity metrics, namely scalar product and cosine similarity, we propose a two-party threshold similarity protocol for these metrics and prove its security against a passive adversary. Instead of revealing the exact value of the similarity, this protocol outputs only one bit of information stating whether or not two users are similar beyond a predetermined threshold. Compared to the exact similarity computation from which more information can be extracted, this protocol is more privacy-preserving in the sense that it reveals less information. While, we focus on Supported by the ERC GOSSPLE project.

the scalar product and the cosine similarity for illustration purpose, our method is generic enough to be applied to other similarity metrics.

Second, we go beyond the traditional cryptographic framework by analyzing the similarity computation within the context of differential privacy [START_REF] Dwork | Differential Privacy: A Survey of Results[END_REF]. In a nutshell, differential privacy is an orthogonal and complementary notion to cryptography that, by adding random noise to the output of a function, provides strong privacy guarantees with respect to how well an adversary observing the output of the function can deduce the presence (or absence) of a specific item in a profile. We design a differentially private protocol for the exact and threshold similarity and analyze their impact with respect to utility. To the best of our knowledge, this is the first attempt to address differential privacy in the context of distributed similarity computation. More specifically, we first analyze the sensitivity of these similarity metrics in the context of a protocol computing exactly the similarity between two user profiles. Finally, we also study the impact of the differential privacy (which requires the addition of random noise) on the resulting utility of the similarity measure, both through a theoretical analysis and experimental validation.

The paper is organized as follows. Section 2 describes the system model and provides the required background. In Section 3, we introduce the threshold similarity protocol and prove its security with respect to a passive adversary. In Section 4, we describe differentially-private protocols for the exact and threshold similarity, while in Section 5, we provide a theoretical analysis of the impact on utility of the differentially-private protocol as well as experimental results. Finally, we briefly review related work in Section 6 before concluding.

Preliminaries

In this section, we describe the system model, the definitions of the similarity metrics considered, and the background in cryptography required in the context of our contributions.

System model. We consider a distributed system of n nodes, connected via an unstructured network [START_REF] Jelasity | Gossip-based Peer Sampling[END_REF]. (Each node is typically connected to O(log n) other nodes picked uniformly at random [START_REF] Bertier | The Gossple Anonymous Social Network[END_REF].) The nodes need to periodically run a clustering protocol that requires computing similarity between pairs of nodes. This semantic clustering can later be used to improve the search, provide content recommendation or personalized query expansion. Nodes are characterized by their profile representing their interests. For example, a node's profile can be a vector of items the associated user has tagged using a collaborative system [START_REF] Amer-Yahia | Efficient Network Aware Search in Collaborative Tagging Sites[END_REF] such as delicious 4 . We assume that for two different nodes A and B, their profiles S A and S B can be represented as binary vectors of size l, where l is the size of the domain. More precisely, S A = {a 1 , . . . , a l } and S B = {b 1 , . . . , b l }, such that a i = 1 if item i is in A's profile and 0 otherwise (b i is defined similarly for the second node). For illustration purpose, we shall call the first node Alice and the second node Bob in the rest of the paper.

The profile is a personal and private information that should be protected, and therefore our main concern is how to compute the similarity measure while preserving its privacy. In this context, this means not revealing the content of the profile and restricting the possibility for an adversary to infer the presence or absence of a particular item in this profile. Moreover, besides the private computation of the similarity, we also assume the existence of a bidirectional anonymous lossless channel to break the link between a node's identity and its profile. Although, it is not the focus of this paper to detail how such a channel could be implemented in practice, we describe in Appendix A a simple implementation of this channel called gossip-on-behalf 5 that relies on the use of a third node acting as an anonymizer to break the link between the two nodes computing their similarity. Obviously, other implementations of the bidirectional anonymous channel are possible but they require non-trivial modifications of current anonymous communication networks [START_REF] Chaum | Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms[END_REF][START_REF] Reiter | Crowds: Anonymity for Web Transactions[END_REF][START_REF] Dingledine | Tor: The Second-Generation Onion Router[END_REF] and are beyond the scope of this paper 6 . In order to guarantee a high level of anonymity, as measured for instance by the size of the anonymity set, it is also necessary to assume that the size of the network is sufficiently large (n 3). Moreover, in order to avoid the possibility for an adversary to query several times the similarity computation with different forged profiles, it is also necessary to restrict to limit the use of a particular bidirectional anonymous channel (for instance to use it only once).

Similarity measures. Nodes aim at detecting the most similar other nodes (i.e. those which share similar interests). Thus, we assume the existence of similarity measures that can be used by the two nodes to quantify how similar they are. A similarity measure sim is a function that takes as input two sets S A and S B representing the profiles of users Alice and Bob and outputs a value in the range between 0 and 1 (i.e. sim(S A , S B ) ∈ [0, 1]), where 0 indicates that the sets are entirely different (the profiles have no items in common) while 1 means that the sets are identical (and therefore the users can be considered as sharing exactly the same interests).

The cosine similarity is commonly used to assess the similarity between two sets [START_REF] Bertier | The Gossple Anonymous Social Network[END_REF] and can be seen as a normalized overlap between the sets. Formally, it is defined as

|S A ∩ S B | |S A | × |S B | , (1)
where S A and S B are the private sets of the first and second node respectively and |S A | and |S B | their corresponding sizes (i.e. the number of 1s in their profiles for binary vectors). The size of the set intersection between S A and S B (i.e. |S A ∩ S B |) is equivalent to the scalar product in the case where the sets are represented as binary vectors. For instance, the scalar product of two vectors of length l, a = (a

1 , • • • , a ) and b = (b 1 , • • • , b ), is defined as i=1 a i b i .
Other similarity metrics can be considered such as the Jaccard index [START_REF] Jaccard | Étude Comparative de la Distribution Florale dans une Portion des Alpes et des Jura[END_REF], but for the sake of clarity, we focus on the cosine similarity metric and the scalar product in the sequel. Cryptographic background. In this paper, we only consider privacy against a computationallybounded passive adversary (also sometimes called semi-honest or honest-but-curious) that can control a fraction of the nodes (see [START_REF] Goldreich | Foundations of Cryptography[END_REF] for a formal cryptographic definition). Note that in this model (contrary to the active one), nodes do not misbehave and follow the recipe of the protocol. However, they may try to infer as much information as possible regarding the private inputs of other participants from the interactions and messages they have seen and recorded.

Definition 1 (Privacy -passive adversary [START_REF] Goldreich | Foundations of Cryptography[END_REF]). A protocol is said to be private with respect to passive adversary controlling a node (or a collusion of nodes), if this adversary cannot learn (except with negligible probability) more information from the execution of the protocol that it could from its own input (i.e. the inputs of the nodes he controls) and the output of the protocol.

In our work, we rely on a cryptographic primitive known as homomorphic encryption, which allows to perform arithmetic operations (such as addition and/or multiplication) on encrypted values. Definition 2 (Homomorphic cryptosystem). Consider a public-key (asymmetric) cryptosystem where (1) Enc pk (a) denotes the encryption of the message a under the public key pk and (2) Dec sk (a) = a is the decryption of this message with the secret key7 sk. A cryptosystem is additively homomorphic if there is an efficient operation ⊕ on two encrypted messages such that Dec(Enc(a) ⊕ Enc(b)) = a + b. Moreover, such an encryption scheme is called affine if there is also an efficient scalaring operation taking as input a ciphertext and a plaintext, such that Dec(Enc(c) a) = c × a.

Besides, the elementary operations of addition and multiplication, more complex arithmetic operations can also be performed on the ciphertexts, such as for instance protocols for the comparison of integers [START_REF] Garay | Practical and Secure Solutions for Integer Comparison[END_REF][START_REF] Nishide | Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol[END_REF]. These protocols take as input two encrypted integers and output whether or not they correspond to the same integer or which one is greater than the other, but without revealing the corresponding plaintexts (i.e. values of the integers).

Paillier's cryptosystem [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF] is an instance of a homomorphic encryption scheme that is both additive and affine. Moreover, Paillier's cryptosystem is also semantically secure [START_REF] Goldreich | Foundations of Cryptography[END_REF], which means that a computationally-bounded adversary cannot derive non-trivial information about the plain text m encrypted from the cipher text Enc(m) and the public key pk. For instance, a computationally-bounded adversary who is given two different cipher texts encrypted with the same key of a semantic cryptosystem, cannot even decide with non-negligible probability if the two cipher texts correspond to the encryption of the same plain text or not. This is because a semantically secure cryptosystem is by essence probabilistic, meaning that even if the same message is encrypted twice, the two resulting ciphertexts will be different except with negligible probability. In this paper, we also use a threshold version of the Paillier's cryptosystem [START_REF] Damgård | A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System[END_REF].

Definition 3 (Threshold cryptosystem). A (t, n) threshold cryptosystem is a public cryptosystem where at least t > 1 nodes out of n need to actively cooperate in order to decrypt an encrypted message. In particular, no collusion of even (t -1) nodes can decrypt a cipher text. However, any node may encrypt a value on its own using the public-key pk. After the threshold cryptosystem has been set up, each node i gets as a result his own secret key sk i (for

1 ≤ i ≤ n).
The cooperation between nodes for the decryption usually involves an interactive cryptographic protocol during which several nodes need to combine their own secret keys with an encrypted value to be able to perform the corresponding decryption.

Threshold Similarity Protocol

The threshold similarity protocol preserves privacy by outputting only one bit of information stating whether (or not) the similarity between two profiles is above some well-chosen threshold τ . To this end, we define thereafter the notion of threshold similarity. Definition 4 (Threshold similarity). Two nodes are τ -similar if the output of applying a similarity measure sim on their respective profiles is above a certain threshold 0 ≤ τ ≤ 1 (i.e. sim(S A , S B ) > τ ).

A threshold similarity protocol takes as input two profiles S A and S B (one profile per node) and outputs one bit of information, which is 1 if S A and S B are τ -similar (i.e. sim(S A , S B ) > τ for sim a predefined similarity measure and τ the value of the threshold) and 0 otherwise. In practice, the value of the threshold τ is application dependent and is set empirically so as to be significantly above the average similarity between nodes in the population. The threshold similarity is very appealing with respect to privacy as it guarantees that the output of the similarity computation only reveals one bit of information, which is potentially much less than disclosing the exact value of the similarity measure. As a practical illustration, we show how to compute privately the cosine similarity between two profiles (Equation 1) represented as binary vectors using an algorithm that we called ThresholdCosine. Note that our approach is generic enough to accommodate other similarity metrics such as for example Jaccard index or Hamming distance. The value of the threshold is set once and for all in advance and therefore the adversary cannot perform a kind of binary with different values for τ .

As a preprocessing step to this protocol, the two nodes engage in the setup phase of a distributed key generation protocol of a threshold affine homomorphic cryptosystem [START_REF] Damgård | A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System[END_REF] (see for instance [START_REF] Nishide | Distributed Paillier Cryptosystem without Trusted Dealer[END_REF] for a detailed description of a distributed key generation protocol without a trusted third party for the Paillier cryptosystem). At the end of this key generation phase, both nodes receive the same public key pk and each one of them gets as private input a different secret key, respectively sk A for the first node and sk B for the second node. The threshold cryptosystem 8 is such that any node can encrypt a value using the public key pk but that the decryption of a homomorphically encrypted value requires the active cooperation of the two nodes.

At the beginning of the protocol, the two nodes compute the (encrypted) size of the set intersection of their two profiles S A and S B by using one of the several algorithms that can be found in the literature. Once this is done, the nodes only receive as output a ciphertext that is an encrypted version of the size (and not the size itself in plaintext). Let k denote the number of items in a profile and l is the size of the domain (e.g. in the dataset delicious k is around 200 items and l is approximately 1 million items). Some of the state-of-the-art algorithms work directly with profiles represented as sets while others are specifically designed to compute the scalar product when profiles are represented as binary vectors. For instance, the two-party scalar product protocol proposed by Goethals [START_REF] Goethals | On Private Scalar Product Computation for Privacy-Preserving Data Mining[END_REF] provides semantic security for one node and information-theoretic security for the other one, for a communication cost of O(l) bits and a computational complexity in terms of cryptographic operations of O(l) for each node. Other recent protocols for scalar product can be found in the litterature [START_REF] Wright | Privacy-Preserving Bayesian Network Structure Computation on Distributed Heterogeneous Data[END_REF][START_REF] Yao | Private Distributed Scalar Product Protocol With Application To Privacy-Preserving Computation of Trust[END_REF], but they have roughly the same complexities as Goethals' protocol. Regarding the cardinality of the set intersection, a protocol presented in [START_REF] Kissner | Privacy-Preserving Set Operations[END_REF] also provides semantic security for a communication cost of O(k log l) and a computational complexity of O(k 2 ). Apart from those specific algorithms, generic techniques from secure multiparty computation could also be used but in general they are less efficient (see for instance an analysis in [START_REF] Kissner | Privacy-Preserving Set Operations[END_REF]). In the rest of the paper, we denote by ScalarProduct the subroutine corresponding to the use of the protocol of Goethals [START_REF] Goethals | On Private Scalar Product Computation for Privacy-Preserving Data Mining[END_REF].

Afterwards, instead of computing directly the cosine similarity as denoted in Equation ( 1), we avoid the need for performing a square root on encrypted values (an operation which is non-trivial and often costly) by squaring the whole equation. The squaring operation renders the next cryptographic operations easier while preserving at the same time the order relation. Formally, the similarity metric effectively used in ThresholdCosine is

|S A ∩ S B | 2 |S A | × |S B | . (2)
On one hand for obtaining the numerator, we square the output of the scalar product by applying the multiplication gate from [START_REF] Cramer | Multiparty Computation from Threshold Homomorphic Encryption[END_REF] to multiply it by itself. On the other hand, the denominator can be computed by the first node sending its homomorphically-encrypted set cardinality to the second node (i.e. Enc(|S A |)), who scalarizes it by its own set cardinality by doing Enc(

|S A |) |S B | to obtain Enc(|S A | × |S B |).
Recall, that the objective of the ThresholdCosine protocol is only to learn if the similarity between S A and S B is above a certain (publicly known) threshold τ . We assume that the threshold can be represented as a fraction τ = a/b and therefore our goal is to verify whether or not the following condition holds

|S A ∩ S B | 2 |S A | × |S B | > a b ⇔ b|S A ∩ S B | 2 > a|S A | × |S B |. (3)
The left side and right side of the inequality can be compared by using secure protocols for integer comparison [START_REF] Garay | Practical and Secure Solutions for Integer Comparison[END_REF][START_REF] Nishide | Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol[END_REF]. We choose to apply specifically the comparison technique from [START_REF] Nishide | Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol[END_REF] as it does not require knowledge of the input as well as a full bit decomposition of the input. Although this protocol was developed initially for secret-sharing, it can be implemented with homomorphic encryption as well. The output of this comparison step is one bit stating whether or not the (squared) cosine similarity is above the threshold τ . output 0 14: end if Theorem 1 (Threshold cosine similarity). The protocol ThresholdCosine is private with respect to a passive adversary and returns 1 if two nodes are τ -similar and 0 otherwise. The protocol has a communication complexity of O(l) bits and a computational cost of O(l), for l being the size of the binary vectors representing the profiles.

Proof. All the communication exchanged between Alice and Bob is done using a homomorphic encryption scheme with semantic security, therefore the encrypted messages exchanged do not leak any information about their content. Moreover as the encryption scheme is a threshold version, neither Alice nor Bob alone can decrypt the messages and learn their content. The multiplication gate [START_REF] Cramer | Multiparty Computation from Threshold Homomorphic Encryption[END_REF] as well as the integer comparison protocol [START_REF] Nishide | Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol[END_REF] are also semantically secure, which therefore guarantees that the protocol is secure against a passive adversary. Regarding the correctness, it is easy to see from the execution of the protocol that if Alice and Bob are τ -similar then this will result in Enc(b|S A ∩ S B | 2 ) > Enc(a|S A | × |S B |) when the integer comparison protocol is executed (and therefore an output of 1) and in 0 otherwise. The multiplication gate and the integer comparison protocols are independent of l and can be considered as having constant complexity (both in terms of communication and computation) for the analysis. On the other hand, the protocol ScalarProduct requires the exchange of O(l) bits between Alice and Bob as well as O(l) computations [START_REF] Goethals | On Private Scalar Product Computation for Privacy-Preserving Data Mining[END_REF]. This results in a similar complexity for the global protocol ThresholdCosine.

Differentially Private Similarity Computation

Cryptography gives us the tools to compute any distributed function without revealing any other information than the output of the function itself and while removing the need for a trusted third party. This is a strong privacy guarantee but at the same time, this does not preclude the possibility that the output itself might leak information about the private inputs of participants. For instance, suppose that a deterministic computation of the similarity is performed and that it outputs 1 as similarity value. In this situation, both nodes know that they exactly have the same profile. Differential privacy [START_REF] Dwork | Differential Privacy: A Survey of Results[END_REF] precisely aims at addressing the problem of what can be inferred about the inputs from the output of a computation by adding some randomization to it. In that respect, differential privacy can be seen as an orthogonal but complementary notion to cryptography as it addresses a different issue. Therefore, in order to get the best of both worlds, the main idea is to combine them by using cryptographic techniques to compute securely a differentially private algorithm.

Differential Privacy

Apart from the traditional cryptographic definition of privacy, we are also interested in a recent notion called differential privacy [START_REF] Dwork | Differential Privacy: A Survey of Results[END_REF]. Two inputs X A and X B are said to differ in at most one element if they are both equal except for possibly one entry of the inputs. For instance, if X A and X B would be databases, it would mean that they are identical except for one row.

Definition 5 (Differential privacy [START_REF] Dwork | Differential Privacy: A Survey of Results[END_REF]). A randomized function K gives -differential privacy if for all possible inputs X A and X B differing in at most one element, and all S ⊆ Range(K),

Pr[K(X A ) ∈ S)] ≤ exp( ) × Pr[K(X B ) ∈ S)]. ( 4
)
This probability is taken over all the coin tosses of K. (Range(K) is the range of the function K and exp refers to the exponential function.)

Originally, differential privacy was developed within the context of private data analysis and the main guarantee is that if a differentially private mechanism is applied on a dataset composed of the personal data of individuals, no output would become significantly more (or less) probable whether or not a participant removes his data from the dataset. This means that for an adversary observing the output of the mechanism, he only gains a negligible advantage from the presence (or absence) of a particular individual in the database. This statement is a statistical property about the behavior of the mechanism (function) and holds independently of the auxiliary knowledge that the adversary might have gathered. More specifically, even if the adversary knows the whole database but one individual row, a mechanism satisfying differential privacy still protects the privacy of this individual. The parameter is public and may take different values depending on the application (for instance it could be 0.01, 0.1 or even 0.25). Dwork, McSherry, Nissim and Smith have designed a general technique, called Laplacian mechanism [START_REF] Dwork | Calibrating Noise to Sensitivity in Private Data Analysis[END_REF], that achieves -differential privacy for a function f by adding random noise to the true answer. The amount of noise that has to be added is directly proportional to the sensitivity of the function, which measures how much the output of a function can change with respect to a small change in the input [START_REF] Dwork | Calibrating Noise to Sensitivity in Private Data Analysis[END_REF].

Definition 6 ((Global) sensitivity [START_REF] Dwork | Calibrating Noise to Sensitivity in Private Data Analysis[END_REF]). For f : D → R, the sensitivity of f is

GS(f ) = max X A ,X B ∈D f (X A ) -f (X B ) 1 (5)
for all X A , X B differing in at most one element, where D is the domain of the function (for instance for binary vectors of l bits, D = {0, 1} l ).

The Laplacian mechanism achieves -differential privacy by adding noise directly proportional to GS(f ) and .

Theorem 2 (Laplacian mechanism [START_REF] Dwork | Calibrating Noise to Sensitivity in Private Data Analysis[END_REF]). For f : D → R, a randomized function K achieves -differential privacy if it releases on input x

K(x) = f (x) + Lap( GS(f ) ) (6)
for GS(f ) the sensitivity of the function f and Lap is a randomly generated noise according to the Laplacian distribution parametrized by GS(f ) .

The smaller the value of , the higher the privacy but also, as a result, the higher the impact might be on the utility of the resulting output. The following lemma also shows that differential privacy is a "natural" notion that composes well.

Lemma 1 (Composition and post-processing [START_REF] Kasiviswanathan | What Can We Learn Privately?[END_REF]). If a randomized algorithm A runs k algorithms A 1 ,. . . , A k where each A i is -differentially private, and outputs a function of the results (i.e A(x) = g(A 1 (x), . . . , A k (x) for some probabilistic algorithm g) then A is k -differentially private.

Differentially Private Similarity

We define two profiles S A and S B as neighbors if they are the same except for one particular item. Note that for simplicity and without loss of generality, we consider only neighboring profiles of the same size. For instance, S A is a neighbor of S B (and vice versa) if it is identical except for one item that may have been replaced

|S A ∩ S B | 2 -|S A ∩ S C | 2 |S A | × |S B | = max S A ,S B |S A ∩ S B | 2 -(|S A ∩ S B | ± 1) 2 |S A | × |S B | = max S A ,S B ±2|S A ∩ S B | -1 |S A | × |S B |
And then substituting the max quantifier yields:

= 2|S A ∩ S B | + 1 |S A | × |S B | ≤ 2 min(|S A |, |S B |) + 1 |S A | × |S B | .
There are several ways to achieve -differential privacy in a distributed context. For instance, if we assume that Alice and Bob have access to a semi-trusted party that does not collude with any of the two nodes that computes their similarity, it can be used to help Alice and Bob during the similarity computation. This is the case for instance in the gossip-on-behalf protocol (Appendix A) in which another node acts as an anonymizer. The anonymizer is semi-trusted because although it is used to connect anonymously two nodes, it is not trusted to the point of having access to the content of the messages exchanged between them due to the semantic encryption scheme used. Another possible way to achieve differential privacy would be for the two nodes to add the noise themselves directly when executing the protocol for similarity computation.

Differential privacy via two-party computation. For instance, suppose that Alice and Bob want to release the result of the scalar product between their two profiles. At the end of the protocol, Alice and Bob could both simply add independently generated random noise with distribution Lap( 1 ) using the homomorphic property of the encryption scheme. Afterwards, they could cooperate to perform the threshold decryption (which remember is not the same as the threshold similarity computation) and they would both get to learn the perturbed scalar product. Finally, Alice may subtract her own noise from the released output to recover only a version of the similarity that has been randomized with Bob's noise (which she cannot remove).

Differential privacy via semi-trusted third party. In the context of gossip-on-behalf (Appendix A), the node that acts as an anonymizer to set up the bidirectional anonymous channel could also generate some random noise and add it to the similarity value that has been computed by using the homomorphic property of the cryptosystem. Afterwards, the two nodes that have been involved in the similarity computation would recover the result using the threshold decryption. The following algorithm describes this procedure. ))

Theorem 3 (Protocol for differential squared cosine). The protocol DifferentialSquaredCosine is private with respect to a passive adversary and -differentially private. The protocol has a communication complexity of O(l) bits and a computational cost of O(l), for l the size of the binary vectors representing the profiles.

Proof. All the communication exchanged between Alice and Bob are done using a homomorphic encryption scheme with semantic security, therefore the encrypted messages exchanged do not leak any information about their content. Moreover as the encryption scheme is a threshold version, it means that neither Alice nor Bob alone can decrypt the messages and learn their content. At the end of the protocol providing that the anonymizer does not collude either with Alice or Bob, Alice and Bob only get to learn (ExactSquaredCosine(S A , S B ) + Lap(

2 min(|S A |,|S B |)+1 ×|S A |×|S B |
), which ensures the -differential property of the protocol. Moreover, because of the use of the protocol ScalarProduct as a subroutine, the protocol DifferentialSquaredCosine has a communication cost of O(l) bits as well as a computational cost of O(l) (we consider here that the threshold decryption has constant complexity and is negligible with respect to the cost of the scalar product).

Note that in this protocol, where the noise needed to reach differential privacy is added by the semi-trusted third party, it needs to know the value of |S A | and |S B | (or at least an upper bound on these values) to be able to add noise tailored to the sensitivity of the function.

Differentially private threshold similarity. Regarding the threshold similarity, it is important to notice that it is meaningless to add some random noise to a binary value (for instance the output of the threshold similarity), because it amounts to flipping this value with some non-negligible probability. Instead, the most direct way to achieve differential privacy is to add the noise before the application of the threshold function. The following observation states that this does not hurt the privacy guarantee obtained.

Observation 1 (Impact of threshold on privacy) Applying the Laplacian mechanism before the threshold function does not hurt the differential privacy guarantee.

Proof. Suppose that we have some output of a function f to which we have added some Laplacian noise calibrated to the sensitivity GS(f ) of the function as well as . As stated by Lemma 1 as this output is -differentially private, performing some pre-determined post-processing on it such as applying a threshold function before releasing it has no impact on the privacy guarantees. Therefore, the threshold function is by itself -differentially private if it is fed with some similarity measure that has been computed with a -differentially private algorithm.

In the previous observation as well as in the context of Lemma 1, note that k = 1 as only one differential privacy mechanism (namely A 1 = f ) is applied. The threshold function itself corresponds to g as it only counts as a post-processing step whose input is not the original profiles of nodes but rather the output of a differentially private mechanism.

Utility Analysis

In this section, we are interested in evaluating the impact of differential privacy on the utility of the application.

Theoretical analysis. In particular, we are interested in measuring the amount of false negatives induced by applying differential privacy on a specific similarity metric. A false negative arises when the protocol outputs that two nodes are not τ -similar while in fact they are. In particular, we have derived an equation that takes the threshold value (τ ) and the privacy parameter ( ) as parameters and computes the probability of having false negatives when we use the differentially private similarity metric. This equation may be use to guide and set up the different parameters of the algorithms and also to measure the achievable trade-off between utility and privacy. We focus primarily on false negatives for the analysis because we believe that a high rate of false negatives will have a big impact on the utility while a high rate of false positives will mainly hurt privacy. However, the rate of false positives can be also derived straightforwardly by following the same approach we used to compute the rate of false negatives.

In our model, the parameter l is the total number of items in the domain of items (which we assume to be a finite domain) and l A = |S A | and l B = |S B | are the sizes of the profiles of Alice and Bob. The random variable S represents the number of items in common between any two profiles picked at random with the given sizes l A and l B (i.e the size of the set intersection |S A ∩ S B |).

Lemma 3 (Hypergeometric distribution [START_REF] Harkness | Properties of the Extended Hypergeometric Distribution[END_REF]). S ∼ Hypergeometric(max(l A , l B ), min(l A , l B ), l), where l is the total number of items in the domain (which is the size of the binary vectors).

Proof. Let min be the set which has the smallest size among the two sets (we assumed it is S A without loss of generality). Fix min, and let Bob (owner of set S B ), pick l B items from the domain of size l without replacements. A pick is successful if the item picked is also contained within the set min, hence the number of possible success is at most l B . This corresponds exactly to the definition of the Hypergeometric distribution.

Remember that the utility is measured as the percentage of similarity measures that does not count as a false negative after the noise has been added and that the similarity value is S 2 /(l A l B ). Definition 7 (Utility function). The utility function is:

u(l A , l B , l, τ, ) = 1 -P (N ≤ τ - S 2 l A l B | S 2 l A l B > τ ) = = 1 - min(l A ,l B ) s= √ l A l B τ f S (s)F N (τ -s 2 l A l B ) 1 -F S √ l A l B τ ,
for S ∼ Hypergeometric(max(l A , l B ), min(l A , l B ), l). The τ parameter can be chosen by substituting the desired acceptance rate of the threshold similarity (without taking into account the error caused by the addition of noise) into the inverse cumulative density function (CDF) of the Hypergeometric distribution. This is a function of l A and l B assuming that l is fixed a priori and it corresponds to an integer, which when divided by the minimum size among both sets, gives the threshold τ . To summarize, we have τ = CDF -1 (max(l A , l B ), min(l A , l B ), l, r)/ min(l A , l B ), where r is the desired acceptance rate. The utility function can be used by nodes to set the privacy parameter dynamically depending on the size of the sets of the two nodes (see Appendix C for more details).

Experimental evaluation. We have also studied experimentally the proposed mechanisms in the context of a fully decentralized clustering algorithm [START_REF] Bertier | The Gossple Anonymous Social Network[END_REF] and evaluate the achievable trade-off between utility (as measured by the quality of the global clustering) and privacy. The clustering algorithm groups nodes according to their interests. In the baseline implementation of the clustering algorithm (which we refer simply as "baseline" in the sequel), each node samples the network and exchanges a digest of its profile that is a Bloom filter representation of its vector profile, which it uses to compute its squared cosine similarity with other nodes. Based on that value, each node iteratively sorts its clustering view and retains the c closest nodes according to the computed similarity metric (c is set to 10 in our experiments). After a predetermined number of cycles when the protocol converges, each node should end up with the c most similar (closest) nodes in its view. (More details about this algorithm are available in [START_REF] Bertier | The Gossple Anonymous Social Network[END_REF].)

We used a dataset from delicious in which users tags items (i.e. URLs). The user profile is represented as a vector of tagged items such that there is a 1 in each vector entry corresponding to an item a user has tagged and 0 otherwise. In our experiments, we compare two models against the baseline model. The first one is a threshold similarity protocol, where nodes exchange their Bloom filters only if the threshold protocol presented in Algorithm 2, outputs 1. This protocol computes privately the similarity measure and outputs 1 if the similarity between the two nodes exceeds the predetermined threshold τ . If a node has in its view less than c nodes whose similarity is above τ , the rest of the view is chosen at random and the Bloom filters are not transmitted. The second model, which is the threshold differentially private protocol (TDP), is a variant of the threshold version in which we added the property of differential privacy to the cryptographic protocol. Computing similarity between two nodes requires O(k) bits, where k is the size of the Bloom filter in the baseline model, while using homomorphic encryption to encrypt each bitresult in an expansion factor of ∼ 2048 due to the size of the generated ciphertexts.

Experimental setup. Evaluations are conducted through the simulation of a network of 500 nodes. Each node represents a user, selected randomly from a dataset of 20, 000 users from a delicious trace crawled in 2009. The resulting domain of items is a set of 1, 144, 000 URLs. In this datatset, the average number of items tagged by a user is 323 and the average similarity between pair of users is 0.00004 (which explained why the chosen values for τ may seem relatively low). Specifically in the experiments, we have set τ ∈ {10 -3 , 10 -4 , 7 × 10 -5 , 10 -5 , 1 × 10 -5 , 5 × 10 -6 } and ∈ {0.001, 0.01, 0.1, 1, 10, 100}. We evaluate our two models (threshold and TDP) according to the following metrics: the quality of the clustering and the level of privacy. The quality of the clustering is measured by (i) the difference between the cluster view obtained by Threshold and TDP protocols compared to the baseline and, (ii) the recall when looking for items (previously removed from the profiles) in the profiles of the c closest nodes. More specifically, clustering is done based on 90% of the tagged items of each user and the remaining 10% is used to measure the recall by comparing how many of them are in the set of tagged items of the view the node ends up with. The level of privacy is measured as the number of Bloom filters exchanged as well as the chosen value for .

Results. In Figure 1, the x-axis represents the privacy parameter . The larger its value, the less privacy (i.e. noise) is provided. We plot the experiments as a constant function with respect to . The threshold line for a given τ should be interpreted as the upper bound of the performance of the "private experiments" with the same value for τ . Therefore, the less the number of the Bloom filters exchanged, the better for the users' privacy. The results obtained demonstrate that the number of Bloom filters exchanged are up to half that of the baseline. Yet, for most of our choices of τ , the recall and view quality in the threshold experiment are close to the one obtained with the baseline. Note that, as observed on Figure 1b, the recall of the baseline is 0.26, which is mainly due to the sparsity of the dataset. The exception being for the value of τ = 0.001 which turns out to be much higher than the average similarity (0.00004), resulting in almost no exchange of Bloom filters (which has the same effect has letting the nodes chosen their view at random). We observe that for some choices of τ , adding privacy (in terms of noise) can even enhance the utility. For instance, when we add a large amount of noise and that the threshold is extremely low, this will increase the number of false positives, thus resulting in more exchanges of Bloom filters than with the use of the threshold alone without the addition of noise. Finally, Figure 1d displays the convergence time obtained with τ = 0.00007. The convergence plots for the view and the Bloom exchanges are similar to the one presented before. Moreover, we observe that in all runs, the private protocols converges almost as fast as the baseline (in less than 25 cycles) to their optimal value, with respect to the quality of the view and the recall. To summarize, applying the threshold (respectively the TDP) protocol impacts only slightly the recall by 4% (respectively 12%) but reduces up to 80% the number of Bloom filters exchanged, thus providing a higher privacy. Therefore, we can conclude that it is possible to achieve reliable clustering and high recall even if instead of exchanging Bloom filters, we use a differentially private threshold mechanism for computing the similarity between nodes.

Conclusion

Main results. The Web 2.0 has recently witnessed a proliferation of user generated content including a large proportion of personal data. Preserving privacy is a major issue to be able to leverage this information to provide personalized services. Fully decentralized systems somehow protect users privacy to be exposed to large companies, avoiding the "Big brother is watching you" syndrome. However, in some sense this is an illusion as they might expose personal data to other users in the network. In this paper, we have addressed this challenge by providing users with a way to compute their similarity with respect to other users while preserving the privacy of their profiles. More precisely, we have introduced a two-party threshold similarity protocol enabling a user to quantify her similarity with another user, without revealing her profile and without requiring a trusted third party. We proved that the proposed protocol is secure in the presence of a passive adversary. We have also proposed differentially private protocols for the exact and threshold similarity and studied the impact of the noise generation on the utility of the resulting similarity. To summarize, our work highlights the fact that cryptography and differential privacy are two different but complementary notions. On one hand, differential privacy gives strong privacy guarantees with respect to how much information can be learned about the inputs of the participants from the (perturbed) output of a function. Thus, differential privacy helps us to reason on which type of information can be safely released with respect to privacy. On the other hand, cryptography, and more specifically secure multi-party computation, gives us the tools to compute a distributed function in a secure and robust way and removes the need for a trusted third party, which is of paramount importance in a decentralized setting. When possible, it seems therefore natural to combine differential privacy and cryptography into an integrated approach as we have done for private similarity computation in distributed systems. Related work. Distributed noise generation has been addressed in the context of the secure multi-party and differential privacy [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF]. The resulting protocol has a greater complexity than our approach, but on the other hand is secure against active (Byzantine) adversary. A protocol for nearest neighbor search in distributed settings has been proposed in [START_REF] Shaneck | Privacy Preserving Nearest Neighbor Search[END_REF] but it was designed only within the cryptography framework and not the differential privacy context. Therefore, if it is possible that some privacy breach related to specific item in the profile may arise if the adversary has some background knowledge. Differential private protocols have also been considered in centralized systems such as [START_REF] Mcsherry | Differentially Private Recommender Systems: Building Privacy into the Netflix Prize Contenders[END_REF] for analyzing the recommender system of Netflix with respect to differential privacy.

Future work. Currently, we have mainly focused on providing security with respect to a passive adversary, which can be seen as a privacy analysis of how much knowledge can be inferred by an adversary following the rules of the protocol but trying to extract as much information as possible from the transcript of the communications seen, the output of the protocol and its own input. While this is a first step, we plan as future work to address malicious participants (modeled by active adversaries) that can cheat during the execution of the protocol. It might also be possible to add the unlinkability property to the bidirectional anonymous channel to prevent an adversary from linking two queries to the same honest node.

B Scalar Product

Lemma 4 (Sensitivity -scalar product). The sensitivity of the function ScalarProduct is 1.

Proof. Consider three different profiles S A , S B and S C , represented as binary vectors of the same size, such that S B and S C are neighbors. Replacing an object from S B by another object to obtain S C increases (or decrease) the value of the scalar product by 1 at most, and therefore the sensitivity of the scalar product is 1. Theorem 4 (Protocol for differential scalar product). The protocol DifferentialScalarProduct is private with respect to a passive adversary and -differentially private. The protocol has a communication complexity of O(l) bits and a computational cost of O(l), for l the size of the binary vectors representing the profiles.

Proof. All the communication exchanged between Alice and Bob are done using an homomorphic encryption scheme with semantic security, therefore the encrypted messages exchanged do not leak any information about their content. Moreover as the encryption scheme is a threshold version, it means that neither Alice nor Bob alone can decrypt the messages and learn their content. At the end of the protocol, Alice and Bob only get to learn (|S A ∩S B |+Lap A ( 1 )+Lap B ( 1 )) which ensures the -differential property of the protocol 9 . Moreover, because of the use of the protocol ScalarProduct as a subroutine, the protocol DifferentialScalarProduct has a communication cost of O(l) bits and as well as a computational cost of O(l) (we consider here that the threshold decryption and the generation of Laplacian noise have constant complexity and are negligible with respect to the cost of the scalar product).

C Utility Analysis

The utility function can be used by nodes to set the privacy parameter dynamically depending on the size of the sets of the two nodes. The probability that a node gets accepted is P (S 2 /(l A l B ) > τ ), where τ is the public threshold value while the probability of getting rejected (false negative rate) after adding the Laplacian noise is P (S 2 /(l A l B ) + N ≤ τ ) = P (N ≤ τ -S 2 /(l A l B )). This result in the following utility function:

1 -P (N ≤ γ| S 2 l A l B > τ ) = 1 -P (N ≤ γ|S > θ) = 1 - P (N ≤ γ ∧ S > θ) 1 -F s (θ) = 1 - s>θ γ -∞ f N,S (n, s) dn 1 -F s (θ) = 1 - s>θ γ -∞ f N (n)f S (s) dn 1 -F S (θ) = 1 - s>θ f S (s) γ -∞ f N (n) dn 1 -F S (θ) = 1 - s>θ f S (s)F N (γ)
1 -F S (θ) , 9 More precisely, Alice can learn (|SA ∩ SB| + Lap B ( 1 )) if she subtracts her own noise but this still preserves -differential privacy (the same reasoning can be made for Bob).

where θ = √ l A l B τ and γ = τ -S 2 l A l B . The upper limit of this sum is min(l A , l B ) whereas the lower limit is θ . The above equation (which is a function of l A , l B , τ , , and l), when plotted with different values of l A and l B , shows the effect of the privacy parameter for a given τ and domain cardinality l. Alternatively, we can also derive the probability of not having false positives or the probability of not having false decisions as described below.

Definition 8 (Utility as the probability of not having false positives.).

U + (l A , l B , l, τ, ) = 1 -

√ l A l B τ s=0 f S (s)F N ( s 2 l A l B -τ ) F S √ l A l B τ .
Definition 9 (Utility as the probability of not having false decisions.).

U † = min(l A ,l B ) s=0 f S (s) F N d (s) τ - s 2 l A l B , where
d(s) = 1 if s ≤ √ l A l B τ -1 if s > √ l A l B τ .

Algorithm 1

 1 ThresholdCosine(S A ,S B ) 1: Alice and Bob generate the keys of the threshold homomorphic encryption 2: Alice receives ska, Bob receives sk b and they both get the public key pk 3: Alice and Bob compute Enc(|SA ∩ SB|) = ScalarProduct(SA, SB) 4: Alice applies the multiplication gate from [6] to obtain Enc(|SA ∩ SB| 2 ) 5: Alice computes Enc(|SA|) and sends it to Bob 6: Bob computes Enc(|SA|) |SB| = Enc(|SA| × |SB|) 7: Alice computes Enc(|SA ∩ SB| 2 ) b = Enc(b|SA ∩ SB| 2 ) 8: Bob computes Enc(|SA| × |SB|) a = Enc(a|SA| × |SB|) 9: Alice and Bob use the integer comparison protocol of [23] on Enc(b|SA ∩ SB| 2 ) and Enc(a|SA| × |SB|) 10: if Enc(b|SA ∩ SB| 2 ) > Enc(a|SA| × |SB|) then 11: output 1 to state that Alice and Bob are τ -similar 12: else 13:

  to obtain the profile S B . If the two profiles are represented as binary vectors, they are neighbors if their Hamming distance is 0 or 2 (i.e. S A ⊕ S B ∈ {0, 2}). The following lemma states the sensitivity of the squared cosine similarity. (Treatment for the differentially private computation of the scalar product can be found in Appendix B.) Lemma 2 (Sensitivity -squared cosine similarity). The sensitivity of the function ExactSquaredCosine is at most 2 min(|S A |,|S B |)+1 |S A |×|S B | . Proof. Consider three different profiles S A , S B and S C , represented as binary vectors of same size, such that S B and S C are neighbors. The computation of the cosine similarity between S A and S B requires to compute two quantities: (1) the squared size of the set intersection |S A ∩ S B | 2 and (2) the multiplication of the lengths of S A and S B (i.e. |S A | × |S B |). Replacing an object from S B to obtain S C will only increase (or decrease) the value of the set intersection by 1 at most. Moreover, replacing an object from S B will not change size of the profile |S C |. Therefore GS(Cosine 2 ) = max S A ,S B ,S C S B ,S C neighbors sim(S A , S B ) -sim(S A , S C ) = max S A ,S B ,S C S B ,S C neighbors

Algorithm 2 1 : 5 :

 215 DifferentialSquaredCosine(S A ,S B , ) Alice and Bob generate the keys of the threshold homomorphic encryption 2: Alice receives skA, Bob receives skB and they both get the public key pk 3: Alice and Bob compute Enc(|SA ∩ SB| 2 ) = ScalarProduct(SA, SB) 2 4: Alice and Bob gives to the node acting as the anonymizer Enc(|SA ∩ SB| 2 ) as well as the sizes of their profiles |SA| and |SB| The anonymizer computes the squared cosine similarity Enc( |S A ∩S B | 2 |S A |×|S B | ) and adds Laplacian noise parametrized by GS(Cosine 2 ) = 2 min(|S A |,|S B |)+1 ×|S 1 |×|S 2 | using the homomorphic property 6: The anonymizer sends the perturbed squared cosine similarity (which is homomorphically encrypted) to Alice and Bob 7: Alice and Bob cooperate to decrypt the homomorphically encrypted value and get as output (ExactSquaredCosine(SA, SB) + Lap( 2 min(|S A |,|S B |)+1 ×|S A |×|S B |

Fig. 1 :

 1 Fig. 1: Experimental results obtained with 500 nodes from Delicious for different values of and τ .

Algorithm 3 1 :

 31 DifferentialScalarProduct(S A ,S B , ) Alice and Bob generate the keys of the threshold homomorphic encryption 2: Alice receives skA, Bob receives skB and they both get the public key pk 3: Alice and Bob compute Enc(|SA ∩ SB|) = ScalarProduct(SA, SB) 4: Alice generates Laplacian noise parametrized by Lap A ( 1 ) and computes Enc(|SA ∩ SB|) ⊕ Enc(Lap A ( 1 )) = Enc(|SA ∩ SB| + Lap A ( 1 )) and sends the result to Bob 5: Bob generates Laplacian noise parametrized by Lap B ( 1 ) and computes Enc(|SA ∩ SB| + Lap A ( 1 )) ⊕ Enc(Lap B ( 1 )) = Enc(|SA ∩ SB| + Lap A ( 1 ) + Lap B ( 1 )) 6: Alice and Bob cooperate to decrypt the homomorphically encrypted value and get as output (|SA ∩ SB| + Lap A ( 1 ) + Lap B ( 1 ))

http://delicious.com/

The protocol described here is a modification of a protocol published earlier[START_REF] Bertier | The Gossple Anonymous Social Network[END_REF].

However, see http://www.torproject.org/docs/hidden-services.html for a description of how to build an anonymous server that can be accessed by anonymous users within the network of the Tor project.

[START_REF] Damgård | A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System[END_REF] In order to simplify the notation, we drop the indices and write Enc(a) instead of Enc pk (a) and Dec(a) instead of Dec sk (a) for the rest of the paper.

Acknowledgements

We are very grateful to the anonymous reviewers for their constructive comments that have help us to improve the quality of this paper.

A Gossip-on-Behalf

In gossip-on-behalf, the first node, Alice, starts by choosing at random another node C (that we refer thereafter as Charlie) from her random sample (typically provided by a random peer sampling service [START_REF] Jelasity | Gossip-based Peer Sampling[END_REF]). She then generates a pair of public key/secret key for this session and asks Charlie to select a node at random (that we called Bob) as the second node that will be involved in the similarity computation. Charlie does not disclose the identity of Bob to Alice (and vice versa), therefore acting as an anonymizer. Afterwards, Charlie transmits the public key of Alice to Bob that will use it to encrypt any data exchanged with Alice. Finally, Bob either generates also a pair of public key/secret key for this session or a secret that will be used as the key of a symmetric cryptosystem (such as AES) and transmits this to Bob encrypted with his public key via Charlie as a relay (this is similar in spirit to the SSL authentication protocol). Alice and Bob now share a secure anonymous channel. The communication between Alice and Bob goes through Charlie but as it is encrypted, this forbids Charlie from learning any information exchanged during their interactions. One important security assumption is that Charlie does not collude neither with Alice nor with Bob, or otherwise this would break the anonymity property of the channel.