Abstract
With increasing resource constraints, optimization is necessary to make the best use of scarce resources. Given the ubiquitous connectivity and availability of information, collaborative optimization problems can be formulated by different parties to jointly optimize their operations. However, this cannot usually be done without restraint since privacy/security concerns often inhibit the complete sharing of proprietary information. The field of privacy-preserving optimization studies how collaborative optimization can be performed with limited disclosure. In this paper, we develop privacy-preserving solutions for collaboratively solving the traveling salesman problem (TSP), a fundamental combinatorial optimization problem with applications in diverse fields such as planning, logistics and production. We propose a secure and efficient protocol for multiple participants to formulate and solve such a problem without sharing any private information. We formally prove the protocol security under the rigorous definition of secure multiparty computation (SMC), and demonstrate its effectiveness with experimental results using real data.
Chapter PDF
Similar content being viewed by others
References
Sakuma, J., Kobayashi, S.: A genetic algorithm for privacy preserving combinatorial optimization. In: GECCO, pp. 1372–1379 (2007)
Clifton, C., Iyer, A., Cho, R., Jiang, W., Kantarcioglu, M., Vaidya, J.: An approach to identifying beneficial collaboration securely in decentralized logistics systems. Management & Service Operations Management 10(1) (2008)
Hong, Y., Vaidya, J., Lu, H.: Secure and efficient distributed linear programming. Journal of Computer Security 20(5), 583–634 (2012)
Hong, Y., Vaidya, J., Lu, H., Shafiq, B.: Privacy-preserving tabu search for distributed graph coloring. In: SocialCom/PASSAT, pp. 951–958 (2011)
Hong, Y., Vaidya, J., Wang, S.: A survey of privacy-aware supply chain collaboration: From theory to applications. Journal of Information Systems (to appear, 2014)
Yao, A.C.: How to generate and exchange secrets. In: Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 162–167. IEEE Computer Society, Los Alamitos (1986)
Goldreich, O.: Encryption Schemes. In: The Foundations of Cryptography, vol. 2. Cambridge University Press (2004)
Li, J., Atallah, M.J.: Secure and private collaborative linear programming. In: Proceedings of the 2nd International Conference on Collaborative Computing: Networking, Applications and Worksharing, November 17-20, pp. 1–8 (2006)
Vaidya, J.: A secure revised simplex algorithm for privacy-preserving linear programming. In: AINA 2009: Proceedings of the 23rd IEEE International Conference on Advanced Information Networking and Applications (2009)
Catrina, O., de Hoogh, S.: Secure multiparty linear programming using fixed-point arithmetic. In: Gritzalis, D., Preneel, B., Theoharidou, M. (eds.) ESORICS 2010. LNCS, vol. 6345, pp. 134–150. Springer, Heidelberg (2010)
Du, W.: A Study of Several Specific Secure Two-party Computation Problems. PhD thesis, Purdue University, West Lafayette, Indiana (2001)
Vaidya, J.: Privacy-preserving linear programming. In: SAC, pp. 2002–2007 (2009)
Bednarz, A., Bean, N., Roughan, M.: Hiccups on the road to privacy-preserving linear programming. In: Proceedings of the 8th ACM Workshop on Privacy in the Electronic Society, WPES 2009, pp. 117–120. ACM, New York (2009)
Bednarz, A.: Methods for Two-party Privacy-preserving Linear Programming. PhD thesis, The University of Adelaide, Adelaide, Australia (2012)
Hong, Y., Vaidya, J., Lu, H.: Efficient distributed linear programming with limited disclosure. In: Li, Y. (ed.) DBSec 2011. LNCS, vol. 6818, pp. 170–185. Springer, Heidelberg (2011)
Mangasarian, O.L.: Privacy-preserving horizontally partitioned linear programs. Optimization Letters 6(3), 431–436 (2012)
Mangasarian, O.L.: Privacy-preserving linear programming. Optimization Letters 5(1), 165–172 (2011)
Li, W., Li, H., Deng, C.: Privacy-preserving horizontally partitioned linear programs with inequality constraints. Optimization Letters 7(1), 137–144 (2013)
Hong, Y., Vaidya, J.: An inference-proof approach to privacy-preserving horizontally partitioned linear programs. Optimization Letters 8(1), 267–277 (2014)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game - a completeness theorem for protocols with honest majority. In: Proceedings of the 19th ACM Symposium on the Theory of Computing, pp. 218–229. ACM, New York (1987)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pp. 1–10 (1998)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Prentice-Hall, Inc., Upper Saddle River (1982)
Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Croes, G.A.: A method for solving traveling salesman problems. Operations Research 6(6), 791–812 (1958)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. The Journal of Chemical Physics 21, 1087 (1953)
Ben-David, A., Nisan, N., Pinkas, B.: Fairplaymp: a system for secure multi-party computation. In: Proceedings of the 15th ACM Conference on Computer and Communications Security, CCS 2008, pp. 257–266. ACM, New York (2008)
Ioannidis, I., Grama, A.: An efficient protocol for yao’s millionaires’ problem. In: Hawaii International Conference on System Sciences (HICSS-36), Waikoloa Village, Hawaii, January 6-9, pp. 205–210 (2003)
Kim, B.-I., Shim, J.-I., Zhang, M.: Comparison of tsp algorithms. In: Project for Models in Facilities Planning and Materials Handling (1998)
Bogdanov, D., Laur, S., Willemson, J.: Sharemind: A framework for fast privacy-preserving computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192–206. Springer, Heidelberg (2008)
Zhang, Y., Steele, A., Blanton, M.: Picco: a general-purpose compiler for private distributed computation. In: ACM Conference on Computer and Communications Security, pp. 813–826 (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 IFIP International Federation for Information Processing
About this paper
Cite this paper
Hong, Y., Vaidya, J., Lu, H., Wang, L. (2014). Collaboratively Solving the Traveling Salesman Problem with Limited Disclosure. In: Atluri, V., Pernul, G. (eds) Data and Applications Security and Privacy XXVIII. DBSec 2014. Lecture Notes in Computer Science, vol 8566. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43936-4_12
Download citation
DOI: https://doi.org/10.1007/978-3-662-43936-4_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43935-7
Online ISBN: 978-3-662-43936-4
eBook Packages: Computer ScienceComputer Science (R0)