Abstract
For x,y ∈ {0,1}*, the point function P x,y is defined by P x,y (x) = y and P x,y (x′) = 0|y| for all x′ ≠ x. We introduce the notion of a distributed point function (DPF), which is a keyed function family F k with the following property. Given x,y specifying a point function, one can efficiently generate a key pair (k 0,k 1) such that: (1) \(F_{k_0}\oplus F_{k_1}=P_{x,y}\), and (2) each of k 0 and k 1 hides x and y. Our main result is an efficient construction of a DPF under the (minimal) assumption that a one-way function exists.
Distributed point functions have applications to private information retrieval (PIR) and related problems, as well as to worst-case to average-case reductions. Concretely, assuming the existence of a strong one-way function, we obtain the following applications.
-
Polylogarithmic 2-server binary PIR. We present the first 2- server computational PIR protocol in which the length of each query is polylogarithmic in the database size n and the answers consist of a single bit each. This improves over the 2\(^O(\sqrt{log n})\) query length of the protocol of Chor and Gilboa (STOC ’97). Similarly, we get a polylogarithmic “PIR writing” scheme, allowing secure non-interactive updates of a database shared between two servers. Assuming just a standard one-way function, we get the first 2-server private keyword search protocol in which the query length is polynomial in the keyword size, the answers consist of a single bit, and there is no error probability. In all these protocols, the computational cost on the server side is comparable to applying a symmetric encryption scheme to the entire database.
-
Worst-case to average-case reductions. We present the first worst-case to average-case reductions for PSPACE and EXPTIME complete languages that require only a constant number of oracle queries. These reductions complement a recent negative result of Watson (TOTC ’12).
Research received funding from the European Union’s Tenth Framework Programme (FP10/2010-2016) under grant agreement no. 259426 ERC-CaC.
Chapter PDF
Similar content being viewed by others
References
Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol. 415, pp. 37–48. Springer, Heidelberg (1990)
Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless EXPTIME has publishable proofs. In: Proc. of the Sixth Annual Structure in Complexity Theory Conference, pp. 213–219 (1991)
Beigel, R., Fortnow, L., Gasarch, W.I.: A tight lower bound for restricted pir protocols. Computational Complexity 15(1), 82–91 (2006)
Beimel, A., Ishai, Y., Kushilevitz, E., Orlov, I.: Share Conversion and Private Information Retrieval. In: IEEE Conference on Computational Complexity 2012, pp. 258–268 (2012)
Barkol, O., Ishai, Y., Weinreb, E.: On Locally Decodable Codes, Self-Correctable Codes, and t-Private PIR. Algorithmica 58(4), 831–859 (2010)
Brakerski, Z., Vaikuntanathan, V.: Efficient Fully Homomorphic Encryption from (Standard) LWE. In: Proceedings of FOCS 2011, pp. 97–106 (2011)
Chor, B., Gilboa, N.: Computationally Private Information Retrieval. In: Proc. of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC 1997), pp. 304–313 (1997)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. Journal of the ACM (JACM) 45(6), 965–981 (1998)
Chor, B., Gilboa, N., Naor, M.: Private information retrieval by keywords, TR CS0917, Dept. of Computer Science, Technion (1997)
Cachin, C., Micali, S., Stadler, M.: Computationally Private Information Retrieval with Polylogarithmic Communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
Desmedt, Y.: Society and Group Oriented Cryptography: A New Concept. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 120–127. Springer, Heidelberg (1988)
Desmedt, Y., Frankel, Y.: Threshold Cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, Heidelberg (1990)
Di Crescenzo, G., Malkin, T., Ostrovsky, R.: Single Database Private Information Retrieval Implies Oblivious Transfer. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 122–138. Springer, Heidelberg (2000)
Efremenko, K.: 3-query locally decodable codes of subexponential length. In: Proc. of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pp. 39–44 (2009)
Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303–324. Springer, Heidelberg (2005)
Gentry, C.: Fully Homomorphic Encryption Using Ideal Lattices. In: Proc. of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pp. 169–178 (2009)
Gentry, C., Ramzan, Z.: Single-Database Private Information Retrieval with Constant Communication Rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803–815. Springer, Heidelberg (2005)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of the ACM (JACM) 33(4), 792–807 (1986)
Goldreich, O.: A Note on Computational Indistinguishability. Inf. Process. Lett. 34(6), 277–281 (1990)
Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press (2000)
Haitner, I., Harnik, D., Reingold, O.: Efficient pseudorandom generators from exponentially hard one-way functions. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006 Part II. LNCS, vol. 4052, pp. 228–239. Springer, Heidelberg (2006)
Hastad, J., Impagliazzo, R., Levin, L., Luby, M.: A Pseudorandom Generator from any One-way Function. SIAM J. Comput. 28(4), 1364–1396 (1999)
Holenstein, T.: Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 443–461. Springer, Heidelberg (2006)
Kushilevitz, E., Ostrovsky, R.: Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. In: Proc. of the 38th Symposium on Foundations of Computer Science (FOCS 1997), pp. 364–373 (1997)
Lipmaa, H.: An Oblivious Transfer Protocol with Log-Squared Communication. In: Zhou, J., López, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 314–328. Springer, Heidelberg (2005)
Ostrovsky, R., Shoup, V.: Private information storage. In: In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 294–303. ACM (1997)
Ostrovsky, R., Skeith III, W.E.: Private Searching on Streaming Data. J. Cryptology 20(4), 397–430 (2007); Shoup, V.: Private information storage. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 294–303. ACM (1997)
Shamir, A.: How to Share a Secret. CACM 22(11), 612–613 (1979)
Stern, J.P.: A New Efficient All-Or-Nothing Disclosure of Secrets Protocol. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 357–371. Springer, Heidelberg (1998)
Watson, T.: Relativized Worlds without Worst-Case to Average-Case Reductions for NP. Journal of ACM Transactions on Computation Theory (TOCT) 4(3), Article No. 8 (September 2012)
Vadhan, S., Zheng, C.: Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In: Proc. of the 44th Annual ACM Symposium on the Theory of Computing (STOC 2012), pp. 817–836 (2012)
Wehner, S., de Wolf, R.: Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1424–1436. Springer, Heidelberg (2005)
Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. In: Proc. of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pp. 266–274 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 International Association for Cryptologic Research
About this paper
Cite this paper
Gilboa, N., Ishai, Y. (2014). Distributed Point Functions and Their Applications. In: Nguyen, P.Q., Oswald, E. (eds) Advances in Cryptology – EUROCRYPT 2014. EUROCRYPT 2014. Lecture Notes in Computer Science, vol 8441. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-55220-5_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-55220-5_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-55219-9
Online ISBN: 978-3-642-55220-5
eBook Packages: Computer ScienceComputer Science (R0)