The upsurge in the number of web users over the last two decades has resulted in a significant growth of online information. This information growth calls for recommenders that personalize the in- formation proposed to each individual user. Nevertheless, person- alization also opens major privacy concerns. This paper presents D2P , a novel protocol that ensures a strong form of differential privacy, which we call distance-based differen- tial privacy, and which is particularly well suited to recommenders. D2P avoids revealing exact user profiles by creating altered pro- files where each item is replaced with another one at some distance . We evaluate D 2 P analytically and experimentally on MovieLens and Jester datasets and compare it with other private and non-private recommenders.