Secure distributed constraint satisfaction: Reaching agreement without revealing private information

Makoto Yokoo; Koutarou Suzuki; Katsutoshi Hirayama

doi:10.1007/3-540-46135-3_26

Secure distributed constraint satisfaction: Reaching agreement without revealing private information

Makoto Yokoo, Koutarou Suzuki, Katsutoshi Hirayama

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

23 Citations (Scopus)

Abstract

This paper develops a secure distributed Constraint Satisfaction algorithm. A Distributed Constraint Satisfaction Problem (DisCSP) is a CSP 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. This algorithm does not leak any private information, i.e., neither agents nor servers can obtain any additional information on the value assignment of variables that belong to other agents.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming- CP 2002 - 8th International Conference, CP 2002, Proceedings
Editors	Pascal Van Hentenryck
Publisher	Springer Verlag
Pages	387-401
Number of pages	15
ISBN (Print)	3540441204, 9783540441205
DOIs	https://doi.org/10.1007/3-540-46135-3_26
Publication status	Published - 2002
Externally published	Yes
Event	8th International Conference on Principles and Practice of Constraint Programming, CP 2002 - Ithaca, United States Duration: Sept 9 2002 → Sept 13 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2470
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	8th International Conference on Principles and Practice of Constraint Programming, CP 2002
Country/Territory	United States
City	Ithaca
Period	9/9/02 → 9/13/02

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-46135-3_26

Cite this

Yokoo, M., Suzuki, K., & Hirayama, K. (2002). Secure distributed constraint satisfaction: Reaching agreement without revealing private information. In P. Van Hentenryck (Ed.), Principles and Practice of Constraint Programming- CP 2002 - 8th International Conference, CP 2002, Proceedings (pp. 387-401). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2470). Springer Verlag. https://doi.org/10.1007/3-540-46135-3_26

Secure distributed constraint satisfaction: Reaching agreement without revealing private information. / Yokoo, Makoto; Suzuki, Koutarou; Hirayama, Katsutoshi.
Principles and Practice of Constraint Programming- CP 2002 - 8th International Conference, CP 2002, Proceedings. ed. / Pascal Van Hentenryck. Springer Verlag, 2002. p. 387-401 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2470).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Yokoo, M, Suzuki, K & Hirayama, K 2002, Secure distributed constraint satisfaction: Reaching agreement without revealing private information. in P Van Hentenryck (ed.), Principles and Practice of Constraint Programming- CP 2002 - 8th International Conference, CP 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2470, Springer Verlag, pp. 387-401, 8th International Conference on Principles and Practice of Constraint Programming, CP 2002, Ithaca, United States, 9/9/02. https://doi.org/10.1007/3-540-46135-3_26

Yokoo M, Suzuki K, Hirayama K. Secure distributed constraint satisfaction: Reaching agreement without revealing private information. In Van Hentenryck P, editor, Principles and Practice of Constraint Programming- CP 2002 - 8th International Conference, CP 2002, Proceedings. Springer Verlag. 2002. p. 387-401. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-46135-3_26

Yokoo, Makoto ; Suzuki, Koutarou ; Hirayama, Katsutoshi. / Secure distributed constraint satisfaction : Reaching agreement without revealing private information. Principles and Practice of Constraint Programming- CP 2002 - 8th International Conference, CP 2002, Proceedings. editor / Pascal Van Hentenryck. Springer Verlag, 2002. pp. 387-401 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{10c737e6a64d4ea6b44e28c44ccc53af,

title = "Secure distributed constraint satisfaction: Reaching agreement without revealing private information",

abstract = "This paper develops a secure distributed Constraint Satisfaction algorithm. A Distributed Constraint Satisfaction Problem (DisCSP) is a CSP 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. This algorithm does not leak any private information, i.e., neither agents nor servers can obtain any additional information on the value assignment of variables that belong to other agents.",

author = "Makoto Yokoo and Koutarou Suzuki and Katsutoshi Hirayama",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 8th International Conference on Principles and Practice of Constraint Programming, CP 2002 ; Conference date: 09-09-2002 Through 13-09-2002",

year = "2002",

doi = "10.1007/3-540-46135-3_26",

language = "English",

isbn = "3540441204",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "387--401",

editor = "{Van Hentenryck}, Pascal",

booktitle = "Principles and Practice of Constraint Programming- CP 2002 - 8th International Conference, CP 2002, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Secure distributed constraint satisfaction

T2 - 8th International Conference on Principles and Practice of Constraint Programming, CP 2002

AU - Yokoo, Makoto

AU - Suzuki, Koutarou

AU - Hirayama, Katsutoshi

PY - 2002

Y1 - 2002

N2 - This paper develops a secure distributed Constraint Satisfaction algorithm. A Distributed Constraint Satisfaction Problem (DisCSP) is a CSP 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. This algorithm does not leak any private information, i.e., neither agents nor servers can obtain any additional information on the value assignment of variables that belong to other agents.

AB - This paper develops a secure distributed Constraint Satisfaction algorithm. A Distributed Constraint Satisfaction Problem (DisCSP) is a CSP 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. This algorithm does not leak any private information, i.e., neither agents nor servers can obtain any additional information on the value assignment of variables that belong to other agents.

UR - http://www.scopus.com/inward/record.url?scp=84957005324&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957005324&partnerID=8YFLogxK

U2 - 10.1007/3-540-46135-3_26

DO - 10.1007/3-540-46135-3_26

M3 - Conference contribution

AN - SCOPUS:84957005324

SN - 3540441204

SN - 9783540441205

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 387

EP - 401

BT - Principles and Practice of Constraint Programming- CP 2002 - 8th International Conference, CP 2002, Proceedings

A2 - Van Hentenryck, Pascal

PB - Springer Verlag

Y2 - 9 September 2002 through 13 September 2002

ER -

Secure distributed constraint satisfaction: Reaching agreement without revealing private information

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this