Cryptographically private support vector machines

ABSTRACT

We propose private protocols implementing the Kernel Adatron and Kernel Perceptron learning algorithms, give private classification protocols and private polynomial kernel computation protocols. The new protocols return their outputs - either the kernel value, the classifier or the classifications - in encrypted form so that they can be decrypted only by a common agreement by the protocol participants. We show how to use the encrypted classifications to privately estimate many properties of the data and the classifier. The new SVM classifiers are the first to be proven private according to the standard cryptographic definitions.

REFERENCES

• 1: William Aiello , Yuval Ishai , Omer Reingold, Priced Oblivious Transfer: How to Sell Digital Goods, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.119-135, May 06-10, 2001
• 2: Yan-Cheng Chang , Chi-Jen Lu, Oblivious Polynomial Evaluation and Oblivious Neural Learning, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.369-384, December 09-13, 2001
• 3: Ivan Damgård , Mats Jurik, A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.119-136, February 13-15, 2001
• 4: Goethals, B., Laur, S., Lipmaa, H., and Mielikäinen, T. On Private Scalar Product Computation for Privacy-Preserving Data Mining. In Information Security and Cryptology - ICISC 2004, vol. 3506 of Lecture Notes in Computer Science, Springer-Verlag, pp. 104--120.
• 5: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 6: Murat Kantarcioglu , Chris Clifton, Privately computing a distributed k-nn classifier, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.279-290, September 20-24, 2004, Pisa, Italy
• 7: Laur, S., Lipmaa, H., and Mielikäinen, T. Cryptographically Private Support Vector Machines. Tech. rep. 2006/198, International Association for Cryptologic Research, 2006. Available at http://eprint.iacr.org/2006/198.
• 8: Lindell, Y., and Pinkas, B. Privacy Preserving Data Mining. Journal of Cryptology 15, 3 (2002), 177--206.
• 9: Lipmaa, H. An Oblivious Transfer Protocol with Log-Squared Communication. In The 8th Information Security Conference (ISC'05), vol. 3650 of Lecture Notes in Computer Science, Springer-Verlag, pp. 314--328.
• 10: Malkhi, D., Nisan, N., Pinkas, B., and Sella, Y. Fairplay - Secure Two-Party Computation System. In Proceedings of the 13th USENIX Security Symposium, USENIX, pp. 287--302.
• 11: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 12: Paillier, P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In Advances in Cryptology - EUROCRYPT '99, vol. 1592 of Lecture Notes in Computer Science, Springer-Verlag, pp. 223--238.
• 13: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 14: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 15: Rebecca Wright , Zhiqiang Yang, Privacy-preserving Bayesian network structure computation on distributed heterogeneous data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014145]
• 16: Yang, Z., Zhong, S., and Wright, R. N. Privacy-preserving classification of customer data without loss of accuracy. In SDM (2005).
• 17: Hwanjo Yu , Xiaoqian Jiang , Jaideep Vaidya, Privacy-preserving SVM using nonlinear kernels on horizontally partitioned data, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141415]
• 18: Yu, H., Vaidya., J., and Jiang, X., Privacy Preserving SVM Classification on Vertically Partitioned Data, In PAKDD 2006, Springer-Verlag 2006.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Security, Theory

Keywords:
kernel methods, privacy preserving data mining