Secure distributed constraint satisfaction: Reaching agreement without revealing private information

Makoto Yokoo, Koutarou Suzuki, Katsutoshi Hirayama

Research output: Contribution to journalArticlepeer-review

37 Citations (Scopus)


This paper develops a secure distributed constraint satisfaction algorithm. A Distributed Constraint Satisfaction Problem (DisCSP) is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. A major motivation for solving a DisCSP without gathering all information in one server is the concern about privacy/security. However, existing DisCSP algorithms leak some information during the search process, and privacy/security issues are not dealt with formally. Our newly developed algorithm utilizes a public key encryption scheme. In this algorithm, multiple servers, which receive encrypted information from agents, cooperatively perform a search process that is equivalent to a standard chronological backtracking algorithm. This algorithm does not leak any private information on the obtained solution, i.e., neither agents nor servers can obtain any additional information on the value assignment of variables that belong to other agents.

Original languageEnglish
Pages (from-to)229-245
Number of pages17
JournalArtificial Intelligence
Issue number1-2
Publication statusPublished - Jan 2005

All Science Journal Classification (ASJC) codes

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'Secure distributed constraint satisfaction: Reaching agreement without revealing private information'. Together they form a unique fingerprint.

Cite this