Privacy-preserving linear programming

ABSTRACT

With the rapid increase in computing, storage and networking resources, data is not only collected and stored, but also analyzed. This creates a serious privacy problem which often inhibits the use of this data. In this paper, we focus on the problem of linear programming, which is the most important sub-class of optimization problems. We consider the case where the objective function and the constraints are partitioned between two parties with one party holding the objective while the other holds the constraints. We propose a very efficient and secure transformation based solution that has the significant added benefit of being independent of the specific linear programming algorithm used.

REFERENCES

• 1: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 2: Josh Cohen Benaloh, Secret sharing homomorphisms: keeping shares of a secret secret, Proceedings on Advances in cryptology---CRYPTO '86, p.251-260, January 1987, Santa Barbara, California, United States
• 3: Manuel Blum , Shafi Goldwasser, An efficient probabilistic public key encryption scheme which hides all partial information, Proceedings of CRYPTO 84 on Advances in cryptology, p.289-302, August 1985, Santa Barbara, California, United States
• 4: Wenliang Du , Mikhail J. Atallah , Eugene H. Spafford, A study of several specific secure two-party computation problems, Purdue University, West Lafayette, IN, 2001
• 5: Wenliang Du , Mikhail J. Atallah, Privacy-Preserving Cooperative Scientific Computations, Proceedings of the 14th IEEE workshop on Computer Security Foundations, p.273, June 11-13, 2001
• 6: W. Du, Y. S. Han, and S. Chen. Privacy-preserving multivariate statistical analysis: Linear regression and classification. In 2004 SIAM International Conference on Data Mining, Lake Buena Vista, Florida, Apr. 22-24 2004.
• 7: Saul I. Gass, Linear programming: methods and applications (5th ed.), McGraw-Hill, Inc., New York, NY, 1985
• 8: B. Goethals, S. Laur, H. Lipmaa, and T. Mielikäinen. On Private Scalar Product Computation for Privacy-Preserving Data Mining. In C. Park and S. Chee, editors, The 7th Annual International Conference in Information Security and Cryptology (ICISC 2004), volume 3506, pages 104--120, New York, NY, December 2--3, 2004. Springer-Verlag.
• 9: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 10: J. Li and M. J. Atallah. Secure and private collaborative linear programming. In Proceedings of the 2nd International Conference on Collaborative Computing: Networking, Applications and Worksharing, pages 1--8, Nov.17--20 2006.
• 11: David Naccache , Jacques Stern, A new public key cryptosystem based on higher residues, Proceedings of the 5th ACM conference on Computer and communications security, p.59-66, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288106]
• 12: T. Okamoto and S. Uchiyama. A new public-key cryptosystem as secure as factoring. In Advances in Cryptology - Eurocrypt '98, LNCS 1403, pages 308--318. Springer-Verlag, 1998.
• 13: P. Paillier. Public key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology - Eurocrypt '99 Proceedings, LNCS 1592, pages 223--238. Springer-Verlag, 1999.
• 14: Christos H. Papadimitriou , Mihalis Yannakakis, Linear programming without the matrix, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.121-129, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167127]
• 15: M.-C. Silaghi, B. Faltings, and A. Petcu. Secure combinatorial optimization simulating dfs tree-based variable elimination. In 9th Symposium on Artificial Intelligence and Mathematics, Ft. Lauderdale, Florida, USA, Jan 2006. http://www2.cs.fit.edu/ msilaghi/papers/.
• 16: Marius C. Silaghi , Debasis Mitra, Distributed Constraint Satisfaction and Optimization with Privacy Enforcement, Proceedings of the Intelligent Agent Technology, IEEE/WIC/ACM International Conference, p.531-535, September 20-24, 2004 [doi>10.1109/IAT.2004.51]
• 17: Marius-Calin Silaghi , Vaibhav Rajeshirke, The Effect of Policies for Selecting the Solution of a DisCSP on Privacy Loss, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1396-1397, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.261]
• 18: K. Suzuki and M. Yokoo. Secure generalized vickrey auction using homomorphic encryption. In Lecture Notes in Computer Science, volume 2742, pages 239--249, Aug. 2003.
• 19: E. Turban, R. K. Rainer, and R. E. Potter. Introduction to Information Technology, chapter 2nd, Information Technologies: Concepts and Management. John Wiley and Sons, 3rd edition, 2005.
• 20: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science, p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]
• 21: M. Yokoo, E. H. Durfee, T. Ishida, and K. Kuwabara. Distributed constraint satisfaction for formalizing distributed problem solving. In International Conference on Distributed Computing Systems, pages 614--621, 1992.
• 22: Makoto Yokoo , Koutarou Suzuki , Katsutoshi Hirayama, Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.387-401, September 09-13, 2002

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Distributed commercial transactions

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Security

Keywords:
privacy