A privacy-preserving analysis system that provides functionality to analyze disparate data sets (and identify correlations) while making individual re-identification prohibitively difficult (even through repeated analysis). The system creates a large proxy data set by oversampling the underlying data and randomly masking a predictable number of fields in the proxy data sets to create sufficient uncertainty in the analysis results. The system may also use a distributed encryption process, secure communications, and secure multiparty computing to prevent personally-identifying information in remotely-stored underlying data from being determined. In the distributed encryption process, each of a plurality of distributed computing devices may be configured to encrypt personally-identifying information using an identical process (and identical encryption keys).