Abstract
We consider 1-out-N Oblivious Transfer (OT) for strings. Oblivious Transfer is a primitive used in a variety of cryptographic protocols and applications (e.g. [11], 1, 10, 17, 12, [13]).
We present a new highly efficient two-pass (one-round) protocol for 1- out-N OT. Our protocol has a constant online computational complexity (for the chooser as well as for the sender). This is a surprising property, since in our protocol the sender’s computational complexity does not depend on the number N of strings. The privacy of chooser and sender is protected computational under the Decisional Diffie-Hellman assumption.
We also sketch how to apply the techniques of [1] to our protocol to get a protocol for priced OT.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B. Aiello, Y. Ishai, O. Reingold, “Priced Oblivious Transfer: How to Sell Digital Goods”, Advances in Cryptology-Eurocrypt 2001, LNCS 2045, pp. 119–135 415, 416, 417, 423, 425
D. Beaver, “How to Break a’ secure’ Oblivious Transfer Protocol”, Advances in Cryptology-Crypto’ 92, LNCS 658, pp. 285–296 418
M. Bellare, P. Rogaway, “Random Oracles are Practical: a paradigm for designing efficient protocols”, Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 62–73, Fairfax (Virginia) USA, 1993, ACM Press 418
R. Canetti, “Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information”, Proceedings of Advances in Cryptology-Crypto’ 97, pp. 455–469 418
R. Canetti, O. Goldreich, S. Halevi, “The Random Oracle Methodology, Revisited”, Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC) 1998, pp. 209–218, ACM Press 418
C. Dwork, M. Naor, O. Reingold, L. Stockmeyer, “Magic Functions”, Proceedings of the 40th Symposium of Foundations of Computer Science (FOCS) 1999, pp. 23–534 418
T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms”, Advances in Cryptology-Crypto’ 84, LNCS 196 417, 426
T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms” IEEE Transactions on Information Theory, 31 (1985), An earlier version appeared in [7] 417
O. Goldreich, “Secure Multi-Party Computation”, Working Draft, Version 1.2, March 2000
O. Goldreich, M. Micali, A. Widgerson, “How to Play any Mental Game”, Proceedings of the 19th ACM symposium on Theory of Computing (STOC), 1987, pp. 218–299 415
J. Kilian, “Founding Cryptography on Oblivious Transfer”, Proceedings of the 20th ACM Symposium on Theory of Computing, 1988, pp. 20–31 415
M. Naor, B. Pinkas, “Oblivious Transfer and Polynomial Evaluation”, Proceedings of the 31st ACM symposium on Theory of Computing (STOC), 1999, pp. 245–254 415
M. Naor, B. Pinkas, “Privacy Preserving Auctions and Mechanism Design”, Proceedings of the 1st ACM Conference on Electronic Commerce, 1999, pp 129–139 415
M. Naor, B. Pinkas, “Efficient Oblivious Transfer Protocols”, Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2001, pp. 448–457 416
M. Naor, O. Reingold, “Number-Theoretic Constructions of Efficient Pseudo-Random Functions”, Proceedings of the 38th Symposium of Foundations of Computer Science (FOCS) 1997, pp. 458–467 417
W. Tzeng, “Efficient 1-out-n oblivious transfer schemes”, Workshop on Practice and Theory in Public-Key Cryptography (PKC 02), LNCS, 2002 416
A. C. Yao, “How to Generate and Exchange Secrets”, Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, 1986, pp. 162–167 415
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 203 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tobias, C. (203). Practical Oblivious Transfer Protocols. In: Petitcolas, F.A.P. (eds) Information Hiding. IH 2002. Lecture Notes in Computer Science, vol 2578. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36415-3_27
Download citation
DOI: https://doi.org/10.1007/3-540-36415-3_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00421-9
Online ISBN: 978-3-540-36415-3
eBook Packages: Springer Book Archive