Privacy-Preserving Data Mining is an important area that studies privacy issues of data mining. When the goal is to share data mining results, two privacy-related problems may arise. The first one is how to compute the data-mining results among several parties without sharing the data. Cryptography-based primitives are the basic tool used to develop ad-hoc secure multi-party computation protocols that share information as less as possible during the computation under different adversary models. The second one is how to produce data mining results that provably do not contain threats to the anonymity of individuals. The concept of k-anonymity has been used to discover anonymity-preserving frequent patterns, and centralized algorithms have been developed. In this paper and for the first time, we study how to produce anonymity-preserving data mining results in a distributed environment. We present two privacy-preserving strategies and show their feasibility through experimental analysis.