Abstract
Mangasarian (Optim. Lett., 6(3), 431–436, 2012) proposed a constraints transformation based approach to securely solving the horizontally partitioned linear programs among multiple entities—every entity holds its own private equality constraints. More recently, Li et al. (Optim. Lett., doi:10.1007/s11590-011-0403-2, 2012) extended the transformation approach to horizontally partitioned linear programs with inequality constraints. However, such transformation approach is not sufficiently secure – occasionally, the privately owned constraints are still under high risk of inference. In this paper, we present an inference–proof algorithm to enhance the security for privacy-preserving horizontally partitioned linear program with arbitrary number of equality and inequality constraints. Our approach reveals significantly less information than the prior work and resolves the potential inference attack.
Similar content being viewed by others
References
Mangasarian, O.L.: Privacy-preserving horizontally partitioned linear programs. Optim. Lett. 6(3), 431–436 (2012)
Li, W., Li, H., Deng, C.:. Privacy-preserving horizontally partitioned linear programs with inequality constraints. Optim. Lett. doi:10.1007/s11590-011-0403-2
Mangasarian, O.L.: Privacy-preserving linear programming. Optim. Lett. 5(1), 165–172 (2011)
Li, J., Atallah, M.J.: Secure and private collaborative linear programming. In: CollaborateCom, pp. 1–8 (2006)
Vaidya, J.: Privacy-preserving linear programming. In: SAC, pp. 2002–2007 (2009)
Bednarz, A., Bean, A.N., Roughan, M.: Hiccups on the road to privacy-preserving linear programming. In: WPES ’09, pp. 117–120 (2009)
Vaidya, J.: A secure revised simplex algorithm for privacy-preserving linear programming. In: AINA ’09, pp. 347–354 (2009)
Hong, Y., Vaidya, J., Lu, H.: Efficient distributed linear programming with limited disclosure. In: DBSec, pp. 172–187 (2011)
Hong, Y., Vaidya, J., Lu, H.: Secure and efficient distributed linear programming. J. Comput. Secur. (2012, to appear)
Dreier, J., Kerschbaum, F.: Practical privacy-preserving multiparty linear programming based on problem transformation. In: PASSAT (2011)
Du, W.: A study of several specific secure two-party computation problems. Ph.D. thesis, Purdue University, West Lafayette (2001)
Feng, X., Zhang, Z.: The rank of a random matrix. Appl. Math. Comput. 185(1), 689–694 (2007)
Sakuma, J., Kobayashi, S.: A genetic algorithm for privacy preserving combinatorial optimization. In: GECCO, pp. 1372–1379 (2007)
Hong, Y., Vaidya, J., Lu, H., Shafiq, B.: Privacy-preserving tabu search for distributed graph coloring. In: PASSAT, pp. 951–958 (2011)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hong, Y., Vaidya, J. An inference–proof approach to privacy-preserving horizontally partitioned linear programs. Optim Lett 8, 267–277 (2014). https://doi.org/10.1007/s11590-012-0572-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-012-0572-7