Abstract As part of the ongoing effort of designing secure DCOP algorithms, we propose P-M AX -S UM, the first private algorithm that is based on M AX -S UM. The proposed algorithm has multiple agents preforming the role of each node in the factor graph, on which the M AX -S UM algorithm operates. P-M AX S UM preserves three types of privacy: topology privacy, constraint privacy, and assignment/decision privacy. By allowing a single call to a trusted coordinator, P-M AX -S UM also preserves agent privacy. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. Our experiments on structured and realistic problems show that the overhead of privacy preservation in terms of runtime is reasonable.