Article

Efficient oblivious transfer protocols

Authors:

Benny PinkasAuthors Info & Claims

SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms

Pages 448 - 457

Published: 09 January 2001 Publication History

Abstract

1 Introduction

Oblivious Transfer (OT) protocols allow one party, the sender, to transmit part of its inputs to another party, the chooser, in a manner that protects both of them: the sender is assured that the chooser does not receive more information than it is entitled, while the chooser is assured that the sender does not learn which part of the inputs it received. OT is used as a key component in many applications of cryptography. Its computational requirements are quite demanding and they are likely to be the bottleneck in many applications that invoke it.

1.1 Contributions.

This paper presents several significant improvements to oblivious transfer (OT) protocols of strings, and in particular: (i) Improving the efficiency of applications which many invocations of oblivious transfer. (ii) Providing the first two-round OT protocol whose security analysis does not invoke the random oracle model.

References

[1]

W. Aiello, Y. Ishai and O. Reingold, Oblivious Commerce: How to Sell Digital Goods, Manuscript, 2000.]]

[2]

M. Bellare, J. Garay and T. Rabin. "Fast Batch Verification for Modular Exponentiation and Digital Signatures." Proc. Advances in Cryptology-Eurocrypt '98, LNCS (1403), Springer-Verlag, pp. 236-250, 1998.]]

[3]

M. Bellare and S. Micaii, "Non-interactive oblivious transfer and applications", Proc. Adv. in Cryptology - Crypts '89, Springer-Verlag LNCS 435 (1990), 547-557.]]

Digital Library

[4]

M. Bellare and P. Rogaway, "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols", Ist ACM Conference on Computer and Communications Security, ACM Press, November 1993.]]

Digital Library

[5]

D. Bosch, "The Decision Diffie-Hellman Problem", Proc. of the Third Algorithmic Number Theory Symposium, Springer-Verlag LNCS 1423 (1998), 48-63.]]

Digital Library

[6]

C. Cachin, S. Micaii and M. Stadler, Computationally Private Information Retrieval With Polylogarith. mic Communication, Advances in Cryptology - Eurocrypt '99, LNCS 1592, Springer-Verlag, 1999.]]

[7]

R. Canetti, Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information, Advances in Cryptology - Crypts '97, pp. 455-469.]]

Digital Library

[8]

R. Canetti, O. Goldreich, and S. Halevi, The random oracle methodology, revisited, Proc. 30th ACM Symposium on Theory of Computing, 1998, pp. 209-218.]]

Digital Library

[9]

R. Canetti and S. Goldwasser: An Efficient Threshold Public Key Cryptosystem Secure Against Adaptive Chosen Ciphertext Attack, Advances in Cryptology - EUROCRYPT '99, Springer-Verlag, 1999, pp. 90-106.]]

[10]

R. Cramer, I. Damgard and B. Schoenmakers, "Proofs of partial knowledge and simplified design of witness hiding protocols", Proc. Advances in Cryptology - Crypts '94, Springer-Verlag LNCS 839 (1994), 174-187.]]

Digital Library

[11]

R. Cramer and V. Shoup, "A practical public key cryptosystem provably secure against adaptive chosen ciphertext attacks", Proc. Advances in Cryptology - Crypts '98, Springer-Verlag LNCS 1462 (1998), 13-25.]]

Digital Library

[12]

A. De Santis, G. Di Crescenzo, G. Persians, and M. Yung, On Monotone Formula Closure of SZK, Proc. of 35th IEEE Symposium on Foundations of Computer Science (FOCS '94), Santa Fe, New Mexico, USA, November 20-22, 1994, pp. 454-465.]]

[13]

W. Dai, Crypts++ 3.1 Benchmarks, available at http ://www. eskimo, com/'weidai/benchmarks, html]]

[14]

W. Diffie and M. Hellman, New directions in cryptography, IEEE 'Ira. Inform. Theory, 22 (6), 644-654, 1976.]]

[15]

D. Dolev, C. Dwork and M. Naor, "Non-malleable cryptography", Proc. 23th A CM Syrup. on Theory of Computing, 1991. Full version: to appear Siam J. on Computing. Available at http ://www.wisdom, weizmann, ac. il/'naor/onpub, html]]

Digital Library

[16]

C. Dwork, M. Naor, O. Reingold and L. Stockmeyer, Magic Functions, FOCS'99, pp. 523-534.]]

Digital Library

[17]

C. Dwork, M. Naor, Zaps and their applications, 41st IEEE Syrup. on Foundations of Comp. Science, 2000.]]

Digital Library

[18]

S. Even, O. Goldreich and A. Lempel, "A Randomized Protocol for Signing Contracts", Communications of the ACM 28, 1985, pp. 637-647.]]

Digital Library

[19]

A. Fiat, Batch RSA, J. of Crypt. 10(2): 75-88 (1997).]]

[20]

O. Goldreich, M. Micali and A. Wigderson, "How to play any mental game", Proc. 19th ACM Syrup. on Theory of Computing, 1987, pp. 218-229.]]

Digital Library

[21]

R. Impagliazzo and S. Rudich, "Limits on the Provable Consequences of One-Way Permutations", 20th ACM Syrup. on the Theory of Computing, 1989, 44-61.]]

Digital Library

[22]

E. Kushilevitz and R. Ostrovsky, Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval, 38th FOCS, pp. 364-373, 1997.]]

Digital Library

[23]

Y. Lindell and B. Pinkas, Privacy Preseving Data Mining, Proe. Advances in Cryptology - Crypts '2000, Springer-Verlag LNCS 1880, pp. 36-54, 2000.]]

Digital Library

[24]

J. Naor and M. Naor, Small-Bias Probability Spaces: Efficient Constructions and Applications, SIAM J. Comput. 22(4): 838-856 (1993).]]

Digital Library

[25]

M. Naor and B. Pinks.s, Oblivious Transfer and Polynomial Evaluation, Proc. 31st Syrup. on Theory of Computer Science (STOC), pp. 245-254, May 1-4, 1999.]]

Digital Library

[26]

M. Naor, B. Pinkas and R. Sumner, Privacy Preserving Auctions and Mechanism Design, Proc. of the 1st ACM conference on Electronic Commerce, November 1999.]]

Digital Library

[27]

M. Naor and O. Reingold, Number-Theoretic constructions of efficient pseudo-random functions, 38th IEEE Syrup. on Foundations of Comp. Sei., 1997, 458-467.]]

Digital Library

[28]

M. O. Rabin, "How to exchange secrets by oblivious transfer", Tech. Memo TR-81, Aiken Computation Laboratory, 1981.]]

[29]

K. Sako, J. Kilian, Secure Voting Using Partially Compatible Homomorphisms. CRYPTO 1994:411-424]]

Digital Library

[30]

C. P. Schnorr, "Efficient Signature Generation by Smart Cards", J. of Crypt., 4(3), pp. 161-174, 1991.]]

[31]

V. Shoup Lower bounds for discrete logarithms and related problems, in Proc. Eurocrypt '97, Springer Verlag LNCS 1233, pp. 256-266, 1997.]]

[32]

V. Shoup and R. Gennaxo, Securing threshold eryptosystems against chosen ciphertext attack, Proc. Advances in Cryptology - Eurocrypt'98, Springer-Verlag LNCS 1403, 1998, pp. 1-16.]]

[33]

M. Stadler, Publicly verifiable secret sharing, Proe. Advances in Cryptology - EUROCRYPT '96, LNCS, vol. 1070, Springer, 1996, pp. 190-199.]]

[34]

A.C. Yao, "How to generate and exchange secrets", Proe. of the 27th IEEE Syrup. on Foundations of Computer Science, 1986, pp. 162-167.]]

Cited By

Zhang CChen YLiu WPeng LHao MWang AWang XLuo BLiao XXu JKirda ELie D(2024)Unbalanced Private Set Union with Reduced Computation and CommunicationProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690308(1434-1447)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690308
Zhang CChen YLiu WZhang MLin DCalandrino JTroncoso C(2023)Linear private set union from multi-query reverse private membership testProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620257(337-354)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620257
Mann ZWeinert CChabal DBos J(2023)Towards Practical Secure Neural Network Inference: The Journey So Far and the Road AheadACM Computing Surveys10.1145/362844656:5(1-37)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3628446
Show More Cited By

Index Terms

Efficient oblivious transfer protocols

Recommendations

More Efficient Oblivious Transfer Extensions

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large-scale OT ...
Practical Oblivious Transfer Protocols
IH '02: Revised Papers from the 5th International Workshop on Information Hiding

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 ...
Computationally Secure Oblivious Transfer

We describe new computationally secure protocols of 1-out-of-N oblivious transfer, k-out-of-N oblivious transfer, and oblivious transfer with adaptive queries. The protocols are very efficient compared with solutions based on generic two-party ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms

January 2001

937 pages

ISBN:0898714907

Chairman:
S. Rao Kosaraju

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM: Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 09 January 2001

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

173
Total Citations
View Citations
4,167
Total Downloads

Downloads (Last 12 months)147
Downloads (Last 6 weeks)23

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang CChen YLiu WPeng LHao MWang AWang XLuo BLiao XXu JKirda ELie D(2024)Unbalanced Private Set Union with Reduced Computation and CommunicationProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690308(1434-1447)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690308
Zhang CChen YLiu WZhang MLin DCalandrino JTroncoso C(2023)Linear private set union from multi-query reverse private membership testProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620257(337-354)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620257
Mann ZWeinert CChabal DBos J(2023)Towards Practical Secure Neural Network Inference: The Journey So Far and the Road AheadACM Computing Surveys10.1145/362844656:5(1-37)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3628446
Asharov GBalch TPolychroniadou ACalinescu ASzpruch L(2021)Privacy-preserving portfolio pricingProceedings of the Second ACM International Conference on AI in Finance10.1145/3490354.3494400(1-8)Online publication date: 3-Nov-2021
https://dl.acm.org/doi/10.1145/3490354.3494400
Münch JSchneider TYalame H(2021)VASA: Vector AES Instructions for Security ApplicationsProceedings of the 37th Annual Computer Security Applications Conference10.1145/3485832.3485897(131-145)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3485832.3485897
Mazmudar MGurtler SGoldberg IKim YKim JLivraga GPark N(2021)Do You Feel a Chill?Proceedings of the 20th Workshop on Workshop on Privacy in the Electronic Society10.1145/3463676.3485612(53-57)Online publication date: 15-Nov-2021
https://dl.acm.org/doi/10.1145/3463676.3485612
Agrawal NBell JGascón AKusner MKim YKim JVigna GShi E(2021)MPC-Friendly Commitments for Publicly Verifiable Covert SecurityProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3485375(2685-2704)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3485375
Schneider TTkachenko OGalbraith SRussello GSusilo WGollmann DKirda ELiang Z(2019)EPISODE: Efficient Privacy-PreservIng Similar Sequence Queries on Outsourced Genomic DatabasEsProceedings of the 2019 ACM Asia Conference on Computer and Communications Security10.1145/3321705.3329800(315-327)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3321705.3329800
Liu MHu Y(2019)Universally composable oblivious transfer from ideal latticeFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-018-6507-413:4(879-906)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s11704-018-6507-4
Shrishak KShulman HWaidner MLie DMannan MBackes MWang X(2018)Removing the Bottleneck for Practical 2PCProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3278521(2300-2302)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3278521
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten