Abstract
In this paper we propose an efficient (string) OT 1 n scheme for any n ≥ 2. We build our OT 1 n scheme from fundamental cryptographic techniques directly. It achieves optimal efficiency in terms of the number of rounds and the total number of exchanged messages for the case that the receiver’s choice is unconditionally secure. The computation time of our OT 1 n scheme is very efficient, too. The receiver need compute 2 modular exponentiations only no matter how large n is, and the sender need compute 2n modular exponentiations. The distinct feature of our scheme is that the system-wide parameters are independent of n and universally usable, that is, all possible receivers and senders use the same parameters and need no trapdoors specific to each of them. For our OT 1 n scheme, the privacy of the receiver’s choice is unconditionally secure and the secrecy of the un-chosen secrets is based on hardness of the decisional Diffie-Hellman problem.
We extend our OT 1 n scheme to distributed oblivious transfer schemes. Our distributed OT 1 n scheme takes full advantage of the research results of secret sharing and is conceptually simple. It achieves better security than Naor and Pinkas’s scheme does in many aspects. For example, our scheme is secure against collusion of the receiver R and t-1 servers and it need not restrict R to contact at most t servers, which is difficult to enforce.
For applications, we present a method of transforming any singledatabase PIR protocol into a symmetric PIR protocol with only one extra unit of communication cost.
Research supported in part by National Science Council grant 90-2213-009-145and MOE Excellence grant 90-E-FA04-1-4, Taiwan, ROC.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
B. Aiello, Y. Ishai, O. Reingold, “Priced oblivious transfer: how to sell digital goods,” In Proceedings of Advances in Cryptology-Eurocrypt 01, Lecture Notes in Computer Science 2045, pp.119–135, Springer-Verlag, 2001.
D. Beaver, “How to break a’ secure’ oblivious transfer protocols,” In Proceedings of Advances in Cryptology-Eurocrypt 92, Lecture Notes in Computer Science 658, pp.285–196, Springer-Verlag, 1993.
D. Beaver, “Equivocable oblivious transfer,” In Proceedings of Advances in Cryptology-Eurocrypt 96, Lecture Notes in Computer Science 1070, pp.119–130, Springer-Verlag, 1996.
D. Beaver, J. Feigenbaum, J. Kilian, P. Rogaway, “Locally random reductions: improvements and applications,” Journal of Cryptology 10(1), pp.17–36, 1997.
M. Bellare, S. Micali, “Non-interactive oblivious transfer,” In Proceedings of Advances in Cryptology-Crypto 89, Lecture Notes in Computer Science 435, pp.547–557, Springer-Verlag, 1990.
M. Ben-Or, S. Goldwasser, A. Wigderson, “Completeness theorems for noncryptographic fault-tolerant distributed computation”, In Proceedings of the 20th ACM Symposium on the Theory of Computing, pp.1–10, 1988.
R. Berger, R. Peralta, T. Tedrick, “A provably secure oblivious transfer protocol,” In Proceedings of Advances in Cryptology-Eurocrypt 84, Lecture Notes in Computer Science 209, pp.379–386, Springer-Verlag, 1985.
B. den Boer, “Oblivious transfer protecting secrecy,” In Proceedings of Advances in Cryptology-Eurocrypt 90, Lecture Notes in Computer Science 473, pp.31–45, Springer-Verlag, 1991.
G. Brassard, C. Cr’epeau, “Oblivious transfers and privacy amplification,” In Proceedings of Advances in Cryptology-Eurocrypt 97, Lecture Notes in Computer Science 1233, pp.334–346, Springer-Verlag, 1997.
G. Brassard, C. Cr’epeau, J.-M. Robert, “Information theoretic reduction among disclosure problems,” In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp.168–173, 1986.
G. Brassard, C. Cr’epeau, J.-M. Robert, “All-or-nothing disclosure of secrets,” In Proceedings of Advances in Cryptology-Crypto 86, Lecture Notes in Computer Science 263, pp.234–238, Springer-Verlag, 1987.
G. Brassard, C. Cr’epeau, M. Santha, “Oblivious transfer and intersecting codes,” IEEE Transactions on Information Theory 42(6), pp.1769–1780, 1996.
C. Cachin, “On the foundations of oblivious transfer,” In Proceedings of Advances in Cryptology-Eurocrypt 98, Lecture Notes in Computer Science 1403, pp.361–374, Springer-Verlag, 1998.
C. Cachin, S. Micali, M. Stadler, “Computationally private informational retrieval with polylogarithmic communication,” In Proceedings of Advances in Cryptology-Eurocrypt 99, Lecture Notes in Computer Science 1592, pp.402–414, Springer-Verlag, 1999.
B. Chor, O. Goldreich, E. Kushilevitz, M. Sudan, “Private information retrieval,” Journal of the ACM 45(6), pp.965–982, 1998.
C. Cr’epeau, “Equivalence between two flavors of oblivious transfers,” In Proceedings of Advances in Cryptology-Crypto 87, Lecture Notes in Computer Science 293, pp.350–354, Springer-Verlag, 1988.
C. Cr’epeau, “Verifiable disclosure of secrets and application”, In Proceedings of Advances in Cryptology-Eurocrypt 89, Lecture Notes in Computer Science 434, pp.150–154, Springer-Verlag, 1990.
C. Cr’epeau, J. van de Gra., A. Tapp, “Committed oblivious transfer and private multi-party computations,” In Proceedings of Advances in Cryptology-Crypto 95, Lecture Notes in Computer Science 963, pp.110–123, Springer-Verlag, 1995.
C. Cr’epeau, J. Kilian, “Achieving oblivious transfer using weakened security assumptions,” In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pp.42–52, 1988.
G. Di Crescenzo, T. Malkin, R. Ostrovsky, “Single database private information retrieval implies oblivious transfer,” In Proceedings of Advances in Cryptology-Eurocrypt 00, Lecture Notes in Computer Science, pp.122–138, Springer-Verlag, 2000.
T. ElGamal, “A public-key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Transactions on Information Theory 31(4), pp.469–472, 1985.
S. Even, O. Goldreich, A. Lempel, “A randomized protocol for signing contracts,” Communications of the ACM 28, pp.637–647, 1985.
Y. Gertner, Y. Ishai, E. Kushilevitz, T. Malkin, “Protecting data privacy in private data retrieval schemes,” In Proceedings of the 30th ACM Symposium on Theory of Computing, pp.151–160, 1998.
O. Goldreich, R. Vainish, “How to solve any protocol problem: an efficient improvement,” In Proceedings of Advances in Cryptology-Crypto 87, Lecture Notes in Computer Science 293, pp.73–86, Springer-Verlag, 1988.
D.M. Gordon, “A survey of fast exponentiation methods”, Journal of Algorithms 27(1), pp.129–146, 1998.
J. Kilian, “Founding cryptography on oblivious transfer,” In Proceedings of the 20thA CM Symposium on Theory of Computing, pp.20–31, 1988.
E. Kushilevitz, R. Ostrovsky, “Replication is not needed: single database, computationally-private informational retrieval,” In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science, pp.364–373, 1997.
M. Naor, B. Pinkas, “Oblivious transfer and polynomial evaluation,” In Proceedings of the 31st ACM Symposium on Theory of Computing, pp.145–254, 1999.
M. Naor, B. Pinkas, “Oblivious transfer with adaptive queries,” In Proceedings of Advances in Cryptology-Crypto 99, Lecture Notes in Computer Science 1666, pp.573–590, Springer-Verlag, 1999.
M. Naor, B. Pinkas, “Distributed oblivious transfer,” In Proceedings of Advances in Cryptology-Asiacrypt 00, Lecture Notes in Computer Science 1976, pp.205–219, Springer-Verlag, 2000.
M. Naor, B. Pinkas, “Efficient oblivious transfer protocols,” In Proceedings of 12th Annual Symposium on Discrete Algorithms (SODA), pp.448–457, 2001.
V. Niemi, A. Renvall, “Cryptographic protocols and voting,” In Result and Trends in Theoretical Computer Science, Lecture Notes in Computer Science 812, pp.307–316, 1994.
M. Rabin, “How to exchange secrets by oblivious transfer,” Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981.
A. Salomaa, L. Santean, “Secret selling of secrets with several buyers,” In the 42nd EATCS Bulletin, pp.178–186, 1990.
A. De Santis, G. Persiano, “Public-randomness in public-key cryptography,” In Proceedings of Advances in Cryptology-Eurocrypt 90, Lecture Notes in Computer Science 473, pp.46–62, Springer-Verlag, 1991.
J.P. Stern, “A new and efficient all-or-nothing disclosure of secrets protocol,” In Proceedings of Advances in Cryptology-Asiacrypt 98, Lecture Notes in Computer Science 1514, pp.357–371, Springer-Verlag, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tzeng, WG. (2002). Efficient 1-Out-n Oblivious Transfer Schemes. In: Naccache, D., Paillier, P. (eds) Public Key Cryptography. PKC 2002. Lecture Notes in Computer Science, vol 2274. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45664-3_11
Download citation
DOI: https://doi.org/10.1007/3-540-45664-3_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43168-8
Online ISBN: 978-3-540-45664-3
eBook Packages: Springer Book Archive