Communication-efficient distributed oblivious transfer. (English) Zbl 1244.68010
Summary: Distributed oblivious transfer (DOT) was introduced by M. Naor and B. Pinkas [Lect. Notes Comput. Sci. 1976, 205–219 (2000; Zbl 0974.94020)], and then generalized to \((k,\ell )\)-DOT-\(\binom{n}{1}\) by C. Blundo et al. [J. Cryptology 20, No. 3, 323–373 (2007; Zbl 1129.94041)] and V. Nikov et al. [Lect. Notes Comput. Sci. 2551, 395–408 (2002; Zbl 1033.94536)]. In the generalized setting, a \((k,\ell )\)-DOT-\(\binom{n}{1}\) allows a sender to communicate one of \(n\) secrets to a receiver with the help of \(\ell \) servers. Specifically, the transfer task of the sender is distributed among \(\ell \) servers and the receiver interacts with k out of the \(\ell \) servers in order to retrieve the secret he is interested in. The DOT protocols we consider in this work are information-theoretically secure. The known \((k,\ell )\)-DOT-\(\binom{n}{1}\) protocols require linear (in \(n\)) communication complexity between the receiver and servers. In this paper, we construct \((k,\ell )\)-DOT-\(\binom{n}{1}\) protocols which only require sublinear (in \(n\)) communication complexity between the receiver and servers. Our constructions are based on information-theoretic private information retrieval. In particular, we obtain both a specific reduction from \((k,\ell )\)-DOT-\(\binom{n}{1}\) to polynomial interpolation-based information-theoretic private information retrieval and a general reduction from \((k,\ell )\)-DOT-\(\binom{n}{1}\) to any information-theoretic private information retrieval. The specific reduction yields \((t,\tau )\)-private \((k,\ell )\)-DOT-\(\binom{n}{1}\) protocols of communication complexity \(O\left(n^{1/\lfloor (k - \tau - 1)/t\rfloor }\right)\) between a semi-honest receiver and servers for any integers \(t\) and \(\tau \) such that \(1\leq t\leq k - 1\) and \(0\leq\tau \leq k - 1 - t\). The general reduction yields \((t,\tau )\)-private \((k,\ell )\)-DOT-\(\binom{n}{1}\) protocols which are as communication-efficient as the underlying private information retrieval protocols for any integers \(t\) and \(\tau \) such that \(1\leq t\leq k - 2\) and \(0\leq \tau \leq k - 1 - t\).
MSC:
| 68M10 | Network design and communication in computer systems |
| 68M14 | Distributed systems |
| 68P20 | Information storage and retrieval of data |
| 94A60 | Cryptography |
| 68M12 | Network protocols |
References:
| [1] | Aiello, W.; Ishai, Y.; Reingold, O., Priced oblivious transfer: How to sell digital goods, (Advances in Cryptology - EUROCRYPT 2001. Advances in Cryptology - EUROCRYPT 2001, Lecture Notes in Comput. Sci., vol. 2045 (2001), Springer-Verlag), 119-135 · Zbl 0981.94042 |
| [2] | Ambainis, A., Upper bound on the communication complexity of private information retrieval, (Proceedings of the 24th International Colloquium on Automata, Languages and Programming. Proceedings of the 24th International Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci., vol. 1256 (1997), Springer-Verlag), 401-407 · Zbl 1401.68065 |
| [3] | Barkol, O.; Ishai, Y.; Weinreb, E., On locally decodable codes, self-correctable codes, and \(t\)-private PIR, (Proceedings of APPROX and RANDOM 2007. Proceedings of APPROX and RANDOM 2007, Lecture Notes in Comput. Sci., vol. 4627 (2007), Springer-Verlag), 311-325 · Zbl 1171.94373 |
| [4] | Beaver, D.; Feigenbaum, J.; Kilian, J.; Rogaway, P., Locally random reductions: improvements and applications, J. Cryptology, 10, 1, 17-36 (1997) · Zbl 0873.94013 |
| [5] | Beimel, A.; Ishai, Y.; Kushilevitz, E., General constructions for information-theoretic private information retrieval, J. Comput. System Sci., 71, 2, 213-247 (2005) · Zbl 1076.68027 |
| [6] | A. Beimel, Y. Ishai, E. Kushilevitz, J.F. Raymond, Breaking the \(O( n^{1 / ( 2 k - 1 )})\); A. Beimel, Y. Ishai, E. Kushilevitz, J.F. Raymond, Breaking the \(O( n^{1 / ( 2 k - 1 )})\) |
| [7] | Bellare, M.; Micali, S., Non-interactive oblivious transfer and applications, (Advances in Cryptology - CRYPTO 1989. Advances in Cryptology - CRYPTO 1989, Lecture Notes in Comput. Sci., vol. 435 (1990), Springer-Verlag), 547-557 · Zbl 0722.68041 |
| [8] | Blundo, C.; DʼArco, P.; De Santis, A.; Stinson, D. R., On unconditionally secure distributed oblivious transfer, J. Cryptology, 20, 3, 323-373 (2007) · Zbl 1129.94041 |
| [9] | G. Brassard, C. Crépeau, J.M. Robert, Information theoretic reductions among disclosure problems, in: Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, 1986, pp. 168-173.; G. Brassard, C. Crépeau, J.M. Robert, Information theoretic reductions among disclosure problems, in: Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, 1986, pp. 168-173. |
| [10] | Brassard, G.; Crépeau, C.; Robert, J. M., All-or-nothing disclosure of secrets, (Advances in Cryptology - CRYPTO 1986. Advances in Cryptology - CRYPTO 1986, Lecture Notes in Comput. Sci., vol. 263 (1987), Springer-Verlag), 234-238 |
| [11] | Chaum, D.; Damgård, I.; van de Graaf, J., Multiparty computations ensuring privacy of each partyʼs input and correctness of the result, (Advances in Cryptology - CRYPTO 1987. Advances in Cryptology - CRYPTO 1987, Lecture Notes in Comput. Sci., vol. 293 (1988), Springer-Verlag), 87-119 · Zbl 0672.94004 |
| [12] | Chee, Y. M.; Feng, T.; Ling, S.; Wang, H.; Zhang, L. F., Query-efficient locally decodable codes of subexponential length (2010) |
| [13] | Cheong, K. Y.; Koshiba, T.; Nishiyama, S., Strengthening the security of distributed oblivious transfer, (Proceedings of the 14th Australasian Conference on Information Security and Privacy. Proceedings of the 14th Australasian Conference on Information Security and Privacy, Lecture Notes in Comput. Sci., vol. 5594 (2009), Springer-Verlag), 377-388 · Zbl 1284.94063 |
| [14] | B. Chor, O. Goldreich, E. Kushilevitz, M. Sudan, Private information retrieval, in: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, 1995, pp. 41-50.; B. Chor, O. Goldreich, E. Kushilevitz, M. Sudan, Private information retrieval, in: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, 1995, pp. 41-50. · Zbl 0938.68625 |
| [15] | Crépeau, C., Verifiable disclosure of secrets and applications, (Advances in Cryptology - CRYPTO 1989. Advances in Cryptology - CRYPTO 1989, Lecture Notes in Comput. Sci., vol. 434 (1990), Springer-Verlag), 181-191 |
| [16] | G. Di Crescenzo, Y. Ishai, R. Ostrovsky, Universal service-providers for database private information retrieval, in: Proceedings of the 17th ACM Symposium on Principles of Distributed Computing, 1998, pp. 91-100.; G. Di Crescenzo, Y. Ishai, R. Ostrovsky, Universal service-providers for database private information retrieval, in: Proceedings of the 17th ACM Symposium on Principles of Distributed Computing, 1998, pp. 91-100. · Zbl 1333.68097 |
| [17] | Crépeau, C., Equivalence between two flavors of oblivious transfers, (Advances in Cryptology - CRYPTO 1987. Advances in Cryptology - CRYPTO 1987, Lecture Notes in Comput. Sci., vol. 293 (1988), Springer-Verlag), 350-354 |
| [18] | K. Efremenko, 3-query locally decodable codes of subexponential length, in: Proceedings of the 41st ACM Symposium on Theory of Computing, 2009, pp. 39-44.; K. Efremenko, 3-query locally decodable codes of subexponential length, in: Proceedings of the 41st ACM Symposium on Theory of Computing, 2009, pp. 39-44. · Zbl 1304.94124 |
| [19] | Even, S.; Goldreich, O.; Lempel, A., A randomized protocol for signing contracts, Commun. ACM, 28, 6, 637-647 (1985) · Zbl 0538.94011 |
| [20] | Gertner, Y.; Goldwasser, S.; Malkin, T., A random server model for private information retrieval, (Proceedings of RANDOM 1998. Proceedings of RANDOM 1998, Lecture Notes in Comput. Sci., vol. 1518 (1998), Springer-Verlag), 200-217 |
| [21] | Y. Gertner, Y. Ishai, E. Kushilevitz, T. Malkin, Protecting data privacy in private information retrieval protocols, in: Proceedings of the 30th ACM Symposium on the Theory of Computing, 1998, pp. 151-160.; Y. Gertner, Y. Ishai, E. Kushilevitz, T. Malkin, Protecting data privacy in private information retrieval protocols, in: Proceedings of the 30th ACM Symposium on the Theory of Computing, 1998, pp. 151-160. · Zbl 1027.68593 |
| [22] | Goldreich, O., Foundations of Cryptography, vol. II: Basic Applications (2004), Cambridge University Press · Zbl 1068.94011 |
| [23] | O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in: Proceedings of the 19th ACM Symposium on the Theory of Computing, 1987, pp. 218-229.; O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in: Proceedings of the 19th ACM Symposium on the Theory of Computing, 1987, pp. 218-229. |
| [24] | Goldreich, O.; Vainish, R., How to solve any protocol problem - an efficiency improvement, (Advances in Cryptology - CRYPTO 1987. Advances in Cryptology - CRYPTO 1987, Lecture Notes in Comput. Sci., vol. 293 (1988), Springer-Verlag), 73-86 · Zbl 0644.68077 |
| [25] | Goldwasser, S.; Levin, L. A., Fair computation of general functions in presence of immoral majority, (Advances in Cryptology - CRYPTO 1990. Advances in Cryptology - CRYPTO 1990, Lecture Notes in Comput. Sci., vol. 537 (1991), Springer-Verlag), 77-93 · Zbl 0800.68459 |
| [26] | Haitner, I., Implementing oblivious transfer using collection of dense trapdoor permutations, (Proceedings of the 1st Theory of Cryptography Conference. Proceedings of the 1st Theory of Cryptography Conference, Lecture Notes in Comput. Sci., vol. 2591 (2004), Springer-Verlag), 394-409 · Zbl 1197.94189 |
| [27] | Ito, M.; Satio, A.; Nishizeki, T., Secret sharing scheme realizing general access structure, Electron. Commun. Japan, 72, 9, 56-64 (1989) |
| [28] | Itoh, T.; Suzuki, Y., New constructions for query-efficient locally decodable codes of subexponential length, IEICE Trans. Inf. Syst., E93-D, 2, 263-270 (2010) |
| [29] | Kalai, Y. T., Smooth projective hashing and two-message oblivious transfer, (Advances in Cryptology - EUROCRYPT 2005. Advances in Cryptology - EUROCRYPT 2005, Lecture Notes in Comput. Sci., vol. 3494 (2005), Springer-Verlag), 78-95 · Zbl 1137.94348 |
| [30] | J. Kilian, Founding cryptography on oblivious transfer, in: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 20-31.; J. Kilian, Founding cryptography on oblivious transfer, in: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 20-31. |
| [31] | Naor, M.; Pinkas, B., Distributed oblivious transfer, (Advances in Cryptology - ASIACRYPT 2000. Advances in Cryptology - ASIACRYPT 2000, Lecture Notes in Comput. Sci., vol. 1976 (2000), Springer-Verlag), 205-219 · Zbl 0974.94020 |
| [32] | M. Naor, B. Pinkas, Efficient oblivious transfer protocols, in: Proceedings of the 12th SIAM Symposium on Discrete Algorithms, 2001, pp. 448-457.; M. Naor, B. Pinkas, Efficient oblivious transfer protocols, in: Proceedings of the 12th SIAM Symposium on Discrete Algorithms, 2001, pp. 448-457. · Zbl 0991.94045 |
| [33] | M. Naor, B. Pinkas, R. Sumner, Privacy preserving auctions and mechanism design, in: Proceedings of the 1st ACM conference on Electronic Commerce, 1999, pp. 129-139.; M. Naor, B. Pinkas, R. Sumner, Privacy preserving auctions and mechanism design, in: Proceedings of the 1st ACM conference on Electronic Commerce, 1999, pp. 129-139. |
| [34] | Nikov, V.; Nikova, S.; Preneel, B.; Vandewalle, J., On unconditionally secure distributed oblivious transfer, (Progress in Cryptology - INDOCRYPT 2002. Progress in Cryptology - INDOCRYPT 2002, Lecture Notes in Comput. Sci., vol. 2551 (2002)), 395-408 · Zbl 1033.94536 |
| [35] | R. Ostrovsky, V. Shoup, Private information storage, in: Proceedings of the 29th ACM Symposium on the Theory of Computing, 1997, pp. 294-303.; R. Ostrovsky, V. Shoup, Private information storage, in: Proceedings of the 29th ACM Symposium on the Theory of Computing, 1997, pp. 294-303. · Zbl 0968.68040 |
| [36] | M.O. Rabin, How to exchange secrets by oblivious transfer, Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981.; M.O. Rabin, How to exchange secrets by oblivious transfer, Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981. |
| [37] | Rivest, R., Unconditionally secure commitment and oblivious transfer schemes using private channels and a trusted initializer (1999), unpublished manuscript |
| [38] | D.P. Woodruff, S. Yekhanin, A geometric approach to information-theoretic private information retrieval, in: Proceedings of the 20th IEEE Conference on Computational Complexity, 2005, pp. 275-284.; D.P. Woodruff, S. Yekhanin, A geometric approach to information-theoretic private information retrieval, in: Proceedings of the 20th IEEE Conference on Computational Complexity, 2005, pp. 275-284. · Zbl 1156.68019 |
| [39] | S. Yekhanin, Towards 3-query locally decodable codes of subexponential length, in: Proceedings of the 39th ACM Symposium on Theory of Computing, 2007, pp. 266-274.; S. Yekhanin, Towards 3-query locally decodable codes of subexponential length, in: Proceedings of the 39th ACM Symposium on Theory of Computing, 2007, pp. 266-274. · Zbl 1232.94020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
