Outlier detection can lead to the discovery of truly unexpected knowledge in many areas such as electronic commerce, credit card fraud and especially national security. We look at the problem of finding outliers in large distributed databases where privacy/security concerns restrict the sharing of data. Both homogeneous and heterogeneous distribution of data is considered. We propose techniques to detect outliers in such scenarios while giving formal guarantees on the amount of information disclosed.