Selective private function evaluation with applications to private statistics

ABSTRACT

Motivated by the application of private statistical analysis of large databases, we consider the problem of selective private function evaluation (SPFE). In this problem, a client interacts with one or more servers holding copies of a database x = x1, … , xn in order to compute f(xi1, … , xim), for some function f and indices i = i1, … , im chosen by the client. Ideally, the client must learn nothing more about the database than f(xi, … , xim), and the servers should learn nothing.

Generic solutions for this problem, based on standard techniques for secure function evaluation, incur communication complexity that is at least linear in n, making them prohibitive for large databases even when f in relatively simple and m is small. We present various approaches for constructing sublinear-communication SPFE protocols, both for the general problem and for special cases of interest. Our solutions not only offer sublinear communication complexity, but are also practical in many scenarios.

REFERENCES

• 1: M. Abadi , J. Feigenbaum, Secure circuit evaluation, Journal of Cryptology, v.2 n.1, p.1-12, 1990 [doi>10.1007/BF02252866]
• 2: Nabil R. Adam , John C. Worthmann, Security-control methods for statistical databases: a comparative study, ACM Computing Surveys (CSUR), v.21 n.4, p.515-556, Dec. 1989 [doi>10.1145/76894.76895]
• 3: 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
• 4: Andris Ambainis, Upper Bound on Communication Complexity of Private Information Retrieval, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.401-407, July 07-11, 1997
• 5: Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
• 6: D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway. Locally random reductions: Improvements and applications. J. Ceyptologl 1O(1): 17-36 (1997). A preliminaxy version appeared in CRYPTO '90.
• 7: Amos Beimel , Yuval Ishai, Information-Theoretic Private Information Retrieval: A Unified Construction, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.912-926, July 08-12, 2001
• 8: Amos Beimel , Yuval Ishai , Tal Malkin, Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.55-73, August 20-24, 2000
• 9: Josh Daniel Cohen Benaloh, Verifiable secret-ballot elections, 1987
• 10: 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]
• 11: Christian Cachin , Jan Camenisch , Joe Kilian , Joy Müller, One-Round Secure Computation and Secure Autonomous Mobile Agents, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.512-523, July 09-15, 2000
• 12: C. Cachin, S. Micali, and M. Staller. Computationally private information retrieval with polylogarithmic communication. Proc. EUROCRYPT, 1999.
• 13: R. Canetti, Security and composition of multiparty cryptographic protocols, J. Cryptology, 13(1), Winter 2000.
• 14: 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]
• 15: David Chaum , Ivan Damgård , Jeroen van de Graaf, Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.87-119, August 16-20, 1987
• 16: Benny Chor , Niv Gilboa, Computationally private information retrieval (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.304-313, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258609]
• 17: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 18: Ronald Cramer , Ivan Damgård , Jesper Buus Nielsen, Multiparty Computation from Threshold Homomorphic Encryption, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.280-299, May 06-10, 2001
• 19: Dorothy Elizabeth Rob Denning, Cryptography and Data Security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 20: Yevgeniy Dodis , Shai Halevi , Tal Rabin, A Cryptographic Solution to a Game Theoretic Problem, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.112-130, August 20-24, 2000
• 21: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 22: 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
• 23: Uri Feige , Joe Killian , Moni Naor, A minimal model for secure computation (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.554-563, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195408]
• 24: M. Franklin and S. Haber, Joint encryption and message-efficient secure multiparty computation, J. CrIjptology, 9(4):217-232, Autumn 1996.
• 25: Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, Protecting data privacy in private information retrieval schemes, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.151-160, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276723]
• 26: O. Goldreich, Secure multi-party computation, (working draft, Version 1.1), 1998. Available from http ://philby.ucsd.edu/cryptolib/B00KS/oded-sc.html.
• 27: O. Goldreich and A. Kahan. How to construct constant-round zero-knowledge proof systems for NP. J. Uryptology. 9(3):167-189, 1996.
• 28: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 29: S. Goldwasser and S. Micali. Probabilistic encryption. JCSS, 28(21):270-299, 1984.
• 30: Yuval Ishai , Eyal Kushilevitz, Private Simultaneous Messages Protocols with Applications, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.174, June 17-19, 1997
• 31: Yuval Ishai , Eyal Kushilevitz, Improved upper bounds on information-theoretic private information retrieval (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.79-88, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301275]
• 32: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
• 33: 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
• 34: E. Mann. Private access to distributed information. Master's thesis, Technion - Israel Institute of Technology, Halfa, 1998.
• 35: 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]
• 36: 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]
• 37: Moni Naor , Benny Pinkas, Oblivious Transfer with Adaptive Queries, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.573-590, August 15-19, 1999
• 38: 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
• 39: D. Naccache and J. Stern. A new public key cryptosystem. Proc. BUROGRYPT, pp. 27-36, 1997.
• 40: T. Okamoto and S. Uchiyama. A new public key cryptosystem as secure as factoring. Proc. EUROCRYPT, Springer LNCS, 1403:308-318, 1998.
• 41: P. Palllier. Public-key cryptosystems based on composite degree residuosity classes. Proc. EUROCRYPT, Springer LNCS, 1592:223-238, 1999.
• 42: M. O. Rabin. Hotu to ezchange secrets by oblivious transfer. Technical report TR-81, Harvard Aiken Computation Laboratory, 1981.
• 43: Julien P. Stern, A New Efficient All-Or-Nothing Disclosure of Secrets Protocol, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.357-371, October 18-22, 1998
• 44: Stephen Wiesner, Conjugate coding, ACM SIGACT News, v.15 n.1, p.78-88, Winter-Spring 1983 [doi>10.1145/1008908.1008920]
• 45: A. C-C. Yao. Protocols for secure computation. Proc. and FOCS, pp. 160-164, 1982.
• 46: A. C-C. Yao. How to generate and exchange secrets. Proc. Tth FOCS, pp. 162-167, 1986.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Design, Experimentation, Performance