Constructions of truly practical secure protocols using standardsmartcards

ABSTRACT

In this paper we show that using standard smartcards it is possible to construct truly practical secure protocols for a variety of tasks. Our protocols achieve full simulation-based security in the presence of malicious adversaries, and can be run on very large inputs. We present protocols for secure set intersection, oblivious database search and more. We have also implemented our set intersection protocol in order to show that it is truly practical: on sets of size 30,000 elements takes 20 seconds for one party and 30 minutes for the other (where the latter can be parallelized to further reduce the time). This demonstrates that in settings where physical smartcards can be sent between parties (as in the case of private data mining tasks between security and governmental agencies), it is possible to use secure protocols with proven simulation-based security.

REFERENCES

• 1: . Aggarwal, N. Mishra and B. Pinkas. Secure Computation of the K'th-ranked Element. In EUROCRYPT 2004, Springer-Verlag (LNCS 3027), pages 40--55, 2004.
• 2: . Aumann and Y. Lindell. Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries. In 4th TCC, Springer-Verlag (LNCS 4392), pages 137--156, 2007.
• 3: 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
• 4: 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]
• 5: . Canetti. Security and Composition of Multiparty Cryptographic Protocols. Journal of Cryptology, 13(1):143--202, 2000.
• 6: 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]
• 7: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 8: . Chor, N. Gilboa, and M. Naor. Private Information Retrieval by Keywords. Technical Report TR-CS0917, Department of Computer Science, Technion, 1997.
• 9: Benny Chor , Eyal Kushilevitz , Oded Goldreich , Madhu Sudan, Private information retrieval, Journal of the ACM (JACM), v.45 n.6, p.965-981, Nov. 1998 [doi>10.1145/293347.293350]
• 10: .J. Freedman, Y. Ishai, B. Pinkas, and O. Reingold. Keyword Search and Oblivious Pseudorandom Functions. In TCC 2005, Springer-Verlag (LNCS 3378), pages 303--324, 2005.
• 11: M.J. Freedman, K. Nissim and B. Pinkas. Efficient Private Matching and Set Intersection. In EUROCRYPT 2004, Springer-Verlag (LNCS 3027), pages 1--19, 2004.
• 12: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 13: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 14: 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]
• 15: Shafi Goldwasser , Leonid A. Levin, Fair Computation of General Functions in Presence of Immoral Majority, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.77-93, August 11-15, 1990
• 16: C. Hazay and Y. Lindell. Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries. In 5th TCC, Springer-Verlag (LNCS 4948), pages 155--175, 2008.
• 17: L. Kissner and D.X. Song. Privacy-Preserving Set Operations.In CRYPTO 2005, Springer-Verlag (LNCS 3621), pages 241--257, 2005.
• 18: Eyal Kushilevitz , Yehuda Lindell , Tal Rabin, Information-theoretically secure protocols and security under composition, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132532]
• 19: Yehuda Lindell , Benny Pinkas, Privacy Preserving Data Mining, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.36-54, August 20-24, 2000
• 20: Silvio Micali , Phillip Rogaway, Secure Computation (Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.392-404, August 11-15, 1991
• 21: Moni Naor , Benny Pinkas, Oblivious transfer and polynomial evaluation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.245-254, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301312]
• 22: . Witteman. Advances in Smartcard Security. Information Security Bulletin, July 2002, pages 11--22, 2002.
• 23: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

General Terms:
Algorithms, Security

Keywords:
provable security, secure computation, smartcards