Abstract
Alice and Bob are too untrusting of computer scientists to let their privacy depend on unproven assumptions such as the existence of one-way functions. Firm believers in Schrödinger and Heisenberg, they might accept a quantum OT device, but IBM’s prototype is not yet portable. Instead, as part of their prenuptial agreement, they decide to visit IBM and perform some OT’s in advance, so that any later divorces, coin-flipping or other important interactions can be done more conveniently, without needing expensive third parties.
Unfortunately, OT can’t be done in advance in a direct way, because even though Bob might not know what bit Alice will later send (even if she first sends a random bit and later corrects it, for example), he would already know which bit or bits he will receive. We address the problem of precomputing oblivious transfer and show that OT can be precomputed at a cost of Θ(κ) prior transfers (a tight bound). In contrast, we show that variants of OT, such as one-out-of-two OT, can be precomputed using only one prior transfer. Finally, we show that all variants can be reduced to a single precomputed one-out-of-two oblivious transfer.
Supported in part by NSF grant CCR-9210954.
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
D. Beaver. “How to Break a’ secure’ Oblivious Transfer Protocol.” Advances in Cryptology — Eurocrypt’ 92 Proceedings, Springer-Verlag LNCS 658, 1993, 285–296.
M. Bellare, S. Micali. “Non-Interactive Oblivious Transfer and Applications.” Advances in Cryptology — Crypto’ 89 Proceedings, Springer-Verlag LNCS 435, 1990, 547–557.
C. Bennett, G. Brassard, C. Crépeau, M. Skubiszewska. “Practical Quantum Oblivious Transfer.” Advances in Cryptology — Crypto’ 91 Proceedings, Springer-Verlag LNCS 576, 1992, 351–366.
B. den Boer. “Oblivious Transfer Protecting Secrecy.” Advances in Cryptology — Eurocrypt’ 91 Proceedings, Springer-Verlag LNCS 547, 1991, 31–45.
G. Brassard, C. Crépeau. “Quantum Bit Commitment and Coin Tossing Protocols.” Advances in Cryptology — Crypto’ 90 Proceedings, Springer-Verlag LNCS 537, 1991, 49–61.
G. Brassard, C. Crépeau, J. Robert. “All or Nothing Disclosure of Secrets.” Advances in Cryptology — Crypto’ 86 Proceedings, Springer-Verlag LNCS 263, 1987.
G. Brassard, C. Crépeau, J. Robert. “Information Theoretic Reductions among Disclosure Problems.” Proceedings of the 27th FOCS, IEEE, 1986, 168–173.
Y-H. Chen, T. Hwang, C-M. Li. “On the Zero Knowledge Proof Systems Based on One-out-of-two Non-Interactive Oblivious Transfers.” Manuscript, 1994.
C. Crépeau. “Equivalence Between Two Flavours of Oblivious Transfers.” Advances in Cryptology — Crypto’ 87 Proceedings, Springer-Verlag LNCS 293, 1988, 350–354.
C. Crépeau, J. Kilian. “Achieving Oblivious Transfer Using Weakened Security Assumptions.” Proceedings of the 29 th FOCS, IEEE, 1988, 42–52.
S. Even, O. Goldreich, A. Lempel. “A Randomized Protocol for Signing Contracts.” Proceedings of Crypto 1982, Springer-Verlag, 1983, 205–210.
L. Harn, H. Lin. “Noninteractive Oblivious Transfer.” Electronics Letters 26:10 (May 1990), 635–636.
L. Harn. “An Oblivious Transfer Protocol and Its Application for the Exchange of Secrets.” Advances in Cryptology — Asiacrypt’ 91 Proceedings, Springer-Verlag LNCS 739, 1993, 312–320.
J. Kilian. “Founding Cryptography on Oblivious Transfer.” Proceedings of the 20th STOC, ACM, 1988, 20–29.
M. Rabin. “How to Exchange Secrets by Oblivious Transfer.” TR-81, Harvard, 1981.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beaver, D. (1995). Precomputing Oblivious Transfer. In: Coppersmith, D. (eds) Advances in Cryptology — CRYPT0’ 95. CRYPTO 1995. Lecture Notes in Computer Science, vol 963. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44750-4_8
Download citation
DOI: https://doi.org/10.1007/3-540-44750-4_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60221-7
Online ISBN: 978-3-540-44750-4
eBook Packages: Springer Book Archive