SSDPOP: Improving the Privacy of DCOP with Secret Sharing

Abstract

Multi-agent systems designed to work collaboratively with groups of people typically require private information that people will entrust to them only if they have assurance that this information will be protected. Although Distributed Constraint Optimization (DCOP) has emerged as a prominent technique for multiagent coordination, existing algorithms for solving DCOP problems do not adeqately protect agents' privacy. This paper analyzes privacy protection and loss in existing DCOP algorithms. It presents a new algorithm, SSDPOP, which augments a prominent DCOP algorithm (DPOP) with secret sharing techniques. This approach significantly reduces privacy loss, while preserving the structure of the DPOP algorithm and introducing only minimal computational overhead. Results show that SSDPOP reduces privacy loss by 29–88% on average over DPOP.