Privacy-preserving remote diagnostics

ABSTRACT

We present an efficient protocol for privacy-preserving evaluation of diagnostic programs, represented as binary decision trees or branching programs. The protocol applies a branching diagnostic program with classification labels in the leaves to the user's attribute vector. The user learns only the label assigned by the program to his vector; the diagnostic program itself remains secret. The program's owner does not learn anything. Our construction is significantly more efficient than those obtained by direct application of generic secure multi-party computation techniques.

We use our protocol to implement a privacy-preserving version of the Clarify system for software fault diagnosis, and demonstrate that its performance is acceptable for many practical scenarios.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 2: Donald Beaver, Foundations of Secure Interactive Computing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.377-391, August 11-15, 1991
• 3: I. Blake and V. Kolesnikov. Strong conditional oblivious transfer and computing on intervals. In Proc. Advances in Cryptology - ASIACRYPT 2004, volume 3329 of LNCS, pages 515--529. Springer, 2004.
• 4: Avrim Blum , Cynthia Dwork , Frank McSherry , Kobbi Nissim, Practical privacy: the SuLQ framework, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065184]
• 5: Pete Broadwell , Matt Harren , Naveen Sastry, Scrash: a system for generating secure crash information, Proceedings of the 12th conference on USENIX Security Symposium, p.19-19, August 04-08, 2003, Washington, DC
• 6: J. Camenisch and V. Shoup. Practical verifiable encryption and decryption of discrete logarithms. In Proc. Advances in Cryptology - CRYPTO 2003, volume 2729 of LNCS, pages 126--144. Springer, 2003.
• 7: R. Canetti. Security and composition of multiparty cryptograpic protocols. J. Cryptology, 13(1):143--202, 2000.
• 8: Ran Canetti , Yuval Ishai , Ravi Kumar , Michael K. Reiter , Ronitt Rubinfeld , Rebecca N. Wright, Selective private function evaluation with applications to private statistics, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.293-304, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384047]
• 9: J. Davis, J. Ha, C. Rossbach, H. Ramadan, and E. Witchel. Cost-sensitive decision tree learning for forensic classification. In Proc. 17th European Conference on Machine Learning (ECML), volume 4212 of LNCS, pages 622--629. Springer, 2006.
• 10: Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin Strauss , Rebecca N. Wright, Secure Multiparty Computation of Approximations, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.927-938, July 08-12, 2001
• 11: J. Feigenbaum, B. Pinkas, R. Ryger, and F. Saint-Jean. Secure computation of surveys. In Proc. EU Workshop on Secure Multiparty Protocols, 2004.
• 12: M. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In Proc. Advances in Cryptology - EUROCRYPT 2004, volume 3027 of LNCS, pages 1--19. Springer, 2004.
• 13: Gateway. System management services agreement. http://www.gateway.com/about/legal/warranties/20461r10.pdf, 1999.
• 14: Louis Kruger , Somesh Jha , Eu-Jin Goh , Dan Boneh, Secure function evaluation with ordered binary decision diagrams, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180455]
• 15: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 16: 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]
• 17: Jungwoo Ha , Christopher J. Rossbach , Jason V. Davis , Indrajit Roy , Hany E. Ramadan , Donald E. Porter , David L. Chen , Emmett Witchel, Improved error reporting for software that uses black-box components, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 18: Qiang Huang , David Jao , Helen J. Wang, Applications of secure electronic voting to automated privacy-preserving troubleshooting, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102132]
• 19: Y. Ishai and A. Paskin. Evaluating branching programs on encrypted data. In Proc. 4th Theory of Cryptography Conference (TCC), volume 4392 of LNCS, pages 575--594. Springer, 2007.
• 20: S. Jarecki and V. Shmatikov. Efficient two-party secure computation on committed inputs. In Proc. Advances in Cryptology - EUROCRYPT 2007, volume 4515 of LNCS, pages 97--114. Springer, 2007.
• 21: Joe Kilian, Founding crytpography on oblivious transfer, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.20-31, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62215]
• 22: Y. Lindell and B. Pinkas. Privacy preserving data mining. J. Cryptology, 15(3):177--206, 2002.
• 23: Y. Lindell and B. Pinkas. A proof of Yao's protocol for secure two-party computation. http://eprint.iacr.org/2004/175, 2004.
• 24: Dahlia Malkhi , Noam Nisan , Benny Pinkas , Yaron Sella, Fairplay—a secure two-party computation system, Proceedings of the 13th conference on USENIX Security Symposium, p.20-20, August 09-13, 2004, San Diego, CA
• 25: G. McGraw and J. Viega. Making your software behave: Security by obscurity. http://www.ibm.com/developerworks/java/library/s-obs.html,2000.
• 26: Microsoft. Privacy statement for the Microsoft error reporting service. http://oca.microsoft.com/en/dcp20.asp,2006.
• 27: Microsoft. Reporting and solving computer problems. http://windowshelp.microsoft.com/Windows/en-US/Help/d97ba15e-9806-4ff3-8ead-71b8d62123fe1033.mspx, 2006.
• 28: Microsoft. How to: Configure microsoft error reporting. http://msdn2.microsoft.com/en-us/library/bb219076.aspx, 2007.
• 29: Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece [doi>10.1145/380752.380855]
• 30: Moni Naor , Benny Pinkas, Efficient oblivious transfer protocols, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 07-09, 2001, Washington, D.C., United States
• 31: 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]
• 32: R. Naraine. Dr. Watson's Longhorn makeover raises eyebrows. http://www.eweek.com/article2/0,1759,1822142,00.asp, 2005.
• 33: Oracle. Oracle sues SAP. http://www.oracle.com/sapsuit/index.html, 2007.
• 34: P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Proc. Advances in Cryptology - EUROCRYPT 1999, volume 1592 of LNCS, pages 223--238. Springer, 1999.
• 35: M. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981.
• 36: Tomas Sander , Adam Young , Moti Yung, Non-Interactive CryptoComputing For NC1, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.554, October 17-18, 1999
• 37: B. Stone. A lively market, legal and not, for software bugs. New York Times, Jan 30 2007.
• 38: H. Wang, Y.-C. Hu, C. Yuan, Z. Zhang, and Y.-M. Wang. Friends troubleshooting network: Towards privacy-preserving, automatic troubleshooting. In 3rd International Workshop on Peer-to-Peer Systems (IPTPS), volume 3279 of LNCS, pages 184--194. Springer, 2004.
• 39: J. Weideman. Automated problem reports. https://wiki.ubuntu.com/AutomatedProblemReports,2006.
• 40: A. Yao. How to generate and exchange secrets. In Proc. 27th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 162--167. IEEE, 1986.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems

General Terms:
Algorithms, Performance, Security

Keywords:
branching programs, data mining, diagnostics, privacy