Article

Free access

Oblivious transfer and polynomial evaluation

Authors:

Moni Naor,

Benny PinkasAuthors Info & Claims

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

Pages 245 - 254

https://doi.org/10.1145/301250.301312

Published: 01 May 1999 Publication History

PDF eReader

References

[1]

D. Beaver, Foundation o.t Secure Interactive Computation, Advances in Cryptology- Crypto '91, pp. 377-391, 1991.

Digital Library

Google Scholar

[2]

M. Bellaxe and S. Micali, Non-interactive oblivious transj~er and applications, Advances in Cryptology- Crypto '89, pp. 547-557, 1990.

Digital Library

Google Scholar

[3]

S.M. Bellovin and M. Merritt, Encrypted key e~:change: Password-based protocols secure against dictionary attacks, Proc. of the 1992 IEEE Computer Society Conference on Research in Security and Privacy, pp. 72-84, 1992.

Digital Library

Google Scholar

[4]

G. Brassard~ Modern cryptology, LNCS, vol. 325~ Springer, 1988.

Digital Library

Google Scholar

[5]

G. Brassard, C. Cr~peau and J.-M. Robert Information Theoretic Reduction Among Disclosure Problems, 27th FOCS, pp. 168-173, 1986.

Google Scholar

[6]

G. Brassaxd, C. Cr~peau and J.-M. R~bert, All-or-Nothing Disclosure of Secrets, Advances in Cryptology - Crypto '86, LNCS 263, Springer Verlag, pp. 234-238, 1987.

Digital Library

Google Scholar

[7]

G. Brassard, C. Cr~peau and M. Santha, Oblivious T~nsfer and Intersecting Codes, IEEE Trans. on Inform. Theory, Vol. 42(6), pp. 1769-I780, 1996.

Crossref

Google Scholar

[8]

K. Bharat and A. Broder. A technique for measuring the telalive size and overlap of public web search engines, In Proceedings of the 7th International World Wide Web Conference, Brisbane, Australia, pp. 379-388. Elsevier Science, April 1998.

Digital Library

Google Scholar

[9]

C. Cachin, On the foundations of oblivious transfer, Advances in Cryptology- Eurocrypt '98, LNCS 1403, pp. 361- 374. Springer-Vertag, 1998.

Crossref

Google Scholar

[10]

C. Cachin, S. Micali and M. Stadler, Computationaily Private Information Retrieval With Polylogarithmic Communication, Advances in Cryptology - Eurocrypt '99, LNCS, Springer-Verlag, 1999.

Digital Library

Google Scholar

[11]

It. Canetti, SecuritF and Composition of Multiparty Crypgographic Protocols, manuscript, 1998.

Google Scholar

[12]

B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan, Private Information Retrieval, 36th FOGS, pp. 41-50, 1995.

Digital Library

Google Scholar

[13]

C. Cr~peau, Equivalence between two fiavours of oblivious transfers, Advances in Cryptology - Crypto '87, LNCS 293, pp. 350-354, 1988.

Digital Library

Google Scholar

[14]

C. Cr~peau and J. Kilian, Achieving oblivious transfer using weakened security assumptions, FOGS '88, pp. 42-52, I988.

Digital Library

Google Scholar

[15]

A. De Santis, Y. Desmedt, Y. Frankel and M. Yung, How to share a function securely, Proc. 26th STOC, pp. 522-533, 1994.

Digital Library

Google Scholar

[16]

W. Diffie and M. Hellman, New directions in crypto~raphF, IEEE Trans. Inform. Theory, vol. 22(6), pp. 644-654, 1976.

Digital Library

Google Scholar

[17]

P. Elias, List decoding for noisy channels, TR 335, Research Laboratory for Electronics, MIT, 1957.

Google Scholar

[18]

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

Digital Library

Google Scholar

[19]

R. Fagin, M. Naor and P. Winkler, Comparing Information Without Leaking It, Communications of the ACM 39, pp. 77-85~ 1996.

Digital Library

Google Scholar

[20]

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, Protecting Data Privacy in Private Information Retrieval Schemes, Proc. 30th STOC, 1998.

Digital Library

Google Scholar

[21]

O. Goldreich, Foundations of Cryptography (Fragments of a Book), 1995. Electronic publication: http://~r~, eccc. uni-trier, de/eccc/inf o/E~CC-B ooka (Electronic Colloquium on Computational Complexity).

Google Scholar

[22]

O. Goldreich, Secure Multi-Party Computation (working draft) Version 1. l, 1998.

Google Scholar

[23]

O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions, J. of the ACM., vot. 33, pp. 792-807, 1986.

Digital Library

Google Scholar

[24]

O. Goldrelch, M. Sudan and R. Rubinfeld, Learning Polynomials with Queries: The Highly Noisy Case, Proc. 36th FOGS, pp. 294-303, 1995.

Digital Library

Google Scholar

[25]

O. GoIdreich and R. Vainish, How ~o Solve any Protocol Problem - An Efficiency Improvement, Advances in Cryptology- Crypto '87, LNCS 293, 73~86. Springer-Verlag, 198.8.

Digital Library

Google Scholar

[26]

V. Guruswami and M. Sudan, Improved decoding of Reed- Solomon and algebraic-geometric codes, 39th FOGS, 1998.

Digital Library

Google Scholar

[27]

R. Impagliazzo and M. Naor, Efficient Cryptographic schemes provably secure as subset sum, JournaJ of Cryptology, vol 9, pp. 199-216, 1996.

Digital Library

Google Scholar

[28]

R. Impagliazzo and S. Rudich, Limits on the Provable Consequences of One-Way Permutations, STOC '89, pp. 44-61, 1989.

Digital Library

Google Scholar

[29]

J. Kilian, Use of Randomness in Algorithms and Protocols, MIT Press, Cambridge, Massachusetts, 1990.

Digital Library

Google Scholar

[30]

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

Digital Library

Google Scholar

[31]

M. Luby, Pseudo-randomness and applications, Princeton University Press, 1996.

Digital Library

Google Scholar

[32]

S. Lucks, Open Key Exchange: How to Defeat Dictionary Attacks Without Encrypting Public Keys, Proc. of Security Protocol Workshop '97, ht~p://w~, dmi. ens. fr/-vaudenay/spw97/~pw97_Luc3, p~. gz.

Digital Library

Google Scholar

[33]

F. J. MacWilliams, N. Sloane. The Theory of Error Correcting Codes, North Holland, Amsterdam, 1977.

Google Scholar

[34]

S. Micali and P. Rogaway, Secure Computation, Advances in Cryptology- Crypto '91, pp. 392-404. LNCS 576, Springer- Verlag, 1992.

Crossref

Google Scholar

[35]

M. N~or and B. Pinkas, Secure and Efficient Metering, Advances in Cryptology- Eurocrypt '98, LNCS 1403, Springer- Verlag, 1998.

Crossref

Google Scholar

[36]

M. Naor and B. Pink~, Adaptive Oblivious 7bansj'er, manuscript, 1999.

Google Scholar

[37]

M. Naor and O. Reingold, Synthesizers and their application to the parallel construction oj~pseudo-random functions, 36th FOGS, pp. 170-181, 1995.

Digital Library

Google Scholar

[38]

M. Naor and O. Reingold, On the construction of pseudorandom permutations: Luby-Rackoff revisited, J. of Cryptology, vol. 12, pp. 29-66, 1999. Preliminary version appeared in 29th STOC, pp. 189-199, 1997.

Digital Library

Google Scholar

[39]

M. N~or and O. Reingold, Number-Theoretic constructions of efficient pseudo-random functions, 38th FOCS, pp. 458- 467, 1997.

Digital Library

Google Scholar

[40]

M. O. Rabin, How to e~change secrets by oblivious transfer, Tech. Memo TR-81, Aiken Computation Laboratory, 1981.

Google Scholar

[41]

M. Sudan, Decoding of Reed Solomon codes beyond the errorcorrection diameter, Journal of Complexity 13(1), pp. 180- 193, 1997.

Digital Library

Google Scholar

[42]

S. Wiesner, Conjugate coding, SIGACT News 15, pp. 78-88, 1983.

Digital Library

Google Scholar

[43]

A.C. Yao, How to Generate and Exchange Secrets, 27th FOGS, pp. 162-167, 1986.

Google Scholar

Cited By

View all

Yan XLian BYang YWang XCui JZhao XWang FChen K(2024)A Ciphertext Reduction Scheme for Garbling an S-Box in an AES Circuit with Minimal Online TimeSymmetry10.3390/sym1606066416:6(664)Online publication date: 28-May-2024
https://doi.org/10.3390/sym16060664
Santos MMateus PVlachou C(2024)Quantum Universally Composable Oblivious Linear EvaluationQuantum10.22331/q-2024-10-23-15078(1507)Online publication date: 23-Oct-2024
https://doi.org/10.22331/q-2024-10-23-1507
Pohle EAbidin APreneel B(2024)Fast Evaluation of S-Boxes With Garbled CircuitsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.340214519(5530-5544)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3402145
Show More Cited By

Index Terms

Oblivious transfer and polynomial evaluation

Recommendations

Distributed Protocols for Oblivious Transfer and Polynomial Evaluation
Progress in Cryptology – INDOCRYPT 2023
Abstract
A secure multiparty computation (MPC) allows several parties to compute a function over their inputs while keeping their inputs private. In its basic setting, the protocol involves only parties that hold inputs. In distributed MPC, there are also ...
Oblivious polynomial evaluation
Abstract
The problem of two-party oblivious polynomial evaluation (OPE) is studied, where one party (Alice) has a polynomialP(z) and the other party (Bob) with an inputx wants to learnP(x) in such an oblivious way that Bob obtainsP(x) without learning any ...
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

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

May 1999

790 pages

ISBN:1581130678

DOI:10.1145/301250

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC99

Sponsor:

SIGACT

STOC99: ACM Symposium on Theory of Computing

May 1 - 4, 1999

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

406
Total Citations
View Citations
5,358
Total Downloads

Downloads (Last 12 months)758
Downloads (Last 6 weeks)97

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yan XLian BYang YWang XCui JZhao XWang FChen K(2024)A Ciphertext Reduction Scheme for Garbling an S-Box in an AES Circuit with Minimal Online TimeSymmetry10.3390/sym1606066416:6(664)Online publication date: 28-May-2024
https://doi.org/10.3390/sym16060664
Santos MMateus PVlachou C(2024)Quantum Universally Composable Oblivious Linear EvaluationQuantum10.22331/q-2024-10-23-15078(1507)Online publication date: 23-Oct-2024
https://doi.org/10.22331/q-2024-10-23-1507
Pohle EAbidin APreneel B(2024)Fast Evaluation of S-Boxes With Garbled CircuitsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.340214519(5530-5544)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3402145
Yang YHu YDong XShen JCao ZYang GDeng R(2024)OpenSE: Efficient Verifiable Searchable Encryption With Access and Search Pattern Hidden for Cloud-IoTIEEE Internet of Things Journal10.1109/JIOT.2023.333733611:8(13793-13809)Online publication date: 15-Apr-2024
https://doi.org/10.1109/JIOT.2023.3337336
Dehkordi FKeshtkarjahromi YSeferoglu H(2024)Privacy-Preserving Hierarchical Model-Distributed Inference2024 IEEE Conference on Communications and Network Security (CNS)10.1109/CNS62487.2024.10735523(1-9)Online publication date: 30-Sep-2024
https://doi.org/10.1109/CNS62487.2024.10735523
Yusof SKamel Ariffin MYip SLau TMahad ZChin JTing C(2024)A Failure in Decryption Process for Bivariate Polynomial Reconstruction Problem CryptosystemHeliyon10.1016/j.heliyon.2024.e25470(e25470)Online publication date: Feb-2024
https://doi.org/10.1016/j.heliyon.2024.e25470
Yang YGuan PTian HZhang F(2024)Elliptic code-based oblivious polynomial evaluationComputer Standards & Interfaces10.1016/j.csi.2024.10384690(103846)Online publication date: Aug-2024
https://doi.org/10.1016/j.csi.2024.103846
Meng SDang CLiang BDing J(2024)Two-Round Post-quantum Private Equality Test and OT from RLWE-EncryptionInformation and Communications Security10.1007/978-981-97-8801-9_2(24-42)Online publication date: 25-Dec-2024
https://doi.org/10.1007/978-981-97-8801-9_2
Luo NWeng CSingh JTan GRaykova MPiskac R(2024)Privacy-Preserving Regular Expression Matching Using TNFAComputer Security – ESORICS 202410.1007/978-3-031-70890-9_12(225-246)Online publication date: 6-Sep-2024
https://doi.org/10.1007/978-3-031-70890-9_12
Delpech de Saint Guilhem CPedersen R(2024)New Proof Systems and an OPRF from CSIDHPublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_8(217-251)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57725-3_8
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Distributed Protocols for Oblivious Transfer and Polynomial Evaluation

Oblivious polynomial evaluation

Computationally Secure Oblivious Transfer