Article

Free access

Founding crytpography on oblivious transfer

Author:

Joe KilianAuthors Info & Claims

STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing

Pages 20 - 31

https://doi.org/10.1145/62212.62215

Published: 01 January 1988 Publication History

Abstract

Suppose your netmail is being erratically censored by Captain Yossarian. Whenever you send a message, he censors each bit of the message with probability 1/2, replacing each censored bit by some reserved character. Well versed in such concepts as redundancy, this is no real problem to you. The question is, can it actually be turned around and used to your advantage? We answer this question strongly in the affirmative. We show that this protocol, more commonly known as oblivious transfer, can be used to simulate a more sophisticated protocol, known as oblivious circuit evaluation([Y]). We also show that with such a communication channel, one can have completely noninteractive zero-knowledge proofs of statements in NP. These results do not use any complexity-theoretic assumptions. We can show that they have applications to a variety of models in which oblivious transfer can be done.

References

[1]

Abadi, Martin, Joan Feigenbaum, "A Simple and Efficient Protocol for Secure Circuit Computation,'' to appear.

[2]

Angluin, Dana and David Lichtenstein. "Provable Security of Cryptosystems: a Survey," YALEU/DCS/TR-288, 1983.

[3]

Barrington, D. "Bounded Width Polynomial Size Branching Programs Recognize Exactly Those Languages in NCTM, Proceedings of I8th STOC, 1986, pp. 1-5.

Digital Library

[4]

Brassard, Gilles and Claude Cr~peau. "Zero-Knowledge Simulation of Boolean Circuits,'' Proceedings of the 27th FOCS, IEEE, 1986, 188-195.

[5]

Ben-Or, Michael, Shaft Goldwasser, Joe Kilian, and Avi Wigderson, "Multi-Prover interactive Proof Systems, Removing Intractibility Assumptions," These proceedings.

Digital Library

[6]

Boppana, Ravi, Johan Hastad, and Stathis Zachos. "Does CoNP Have Short Interactive Proofs?," IPL, 25, 1987, 127-132.

Digital Library

[7]

Cripeau Claude, "On the Equivalence of Two Types of Oblivious Transfer", Crypto87.

[8]

D. Chaum, C. Crdpeau and I. Damgard, Multiparty unconditionally secure protocols, These proceedings.

[9]

Chaum, David, Ivan Damgard, and Jeroen van de Graaf. "Multiparty Computations Ensuring Secrecy of Each Party's Input and Correctness of the Output," Proceedings of CRYPTO '87. Proceedings of CRYPTO '85, Springer- Voting, 1986, 477-488.

Digital Library

[10]

Even S., Goldreich O., and A. Lempel, A Randomized Protocol for Signing Contracts, CACM, vol. 28, no. 6, 1985, pp. 637-647.

Digital Library

[11]

Fortnow, Lance. "The Complexity of Perfect Zero-Knowledge," Proceedings of the 19ta STOC, ACM, 1987, 204-209.

Digital Library

[12]

Fortnow, Lance, Mike Sipser, John Rompel, "On the Power of Multi-Prover Interactive Proof Systems," to appear.

[13]

Galil Z., Haber S., and Yung M., "A Prirate Interactive Test of ~ Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystem", Proceedings of the ~6th FOGS, 1985, pp. 360-371.

[14]

Goldwasser, Shaft, Silvio Micali, and Charles Rackoff. "The Knowledge Complexity of Interactive Proof-Systems," Proceedings of the 17ta STOC, ACM, 1985, 291-304.

Digital Library

[15]

Goldreich, Oded, Silvio Micali, and A- vi Wigderson. "Proofs that Yield Nothing but the Validity of the Assertion, and a Methodology of Cryptographic Protocol Design," Proceedings of the 27th FOGS, IEEE, 1986, 174-187.

[16]

Goldreich, Oded, Silvio Micali, and Avi Wigderson. "How to Play ANY Mental Game," Proceedings of the 19th STOC, ACM, 1987, 218- 229.

Digital Library

[17]

Goldreich, O., Vainish, R. "How to Solve any Protocol Problem: An Efficiency Improvement'', Crypto 87.

Digital Library

[18]

Micali, Silvio, Personal Communication.

[19]

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

[20]

Yao, Andrew C. "How to Generate and Exchange Secrets," Proceedings of the 27th FOGS, IEEE, 1986, 162-167.

Cited By

Madathil VScafuro AVerber T(2025)Round-Optimal Compiler for Semi-Honest to Malicious Oblivious Transfer via CIHIACR Communications in Cryptology10.62056/abe0wa3y61:4Online publication date: 13-Jan-2025
https://doi.org/10.62056/abe0wa3y6
Bansal ASikora J(2025)Breaking barriers in two-party quantum cryptography via stochastic semidefinite programmingQuantum10.22331/q-2025-01-20-16029(1602)Online publication date: 20-Jan-2025
https://doi.org/10.22331/q-2025-01-20-1602
Gurevin DJin CNguyen PKhan Ovan Dijk M(2025)Secure Remote Attestation With Strong Key Insulation GuaranteesIEEE Transactions on Computers10.1109/TC.2023.329087074:3(848-859)Online publication date: Mar-2025
https://doi.org/10.1109/TC.2023.3290870
Show More Cited By

Index Terms

Founding crytpography on oblivious transfer

Recommendations

Founding Cryptography on Oblivious Transfer --- Efficiently
CRYPTO 2008: Proceedings of the 28th Annual conference on Cryptology: Advances in Cryptology

We present a simple and efficient compiler for transforming secure multi-party computation (MPC) protocols that enjoy security only with an honest majority into MPC protocols that guarantee security with no honest majority, in the oblivious-transfer (OT)...
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing

January 1988

553 pages

ISBN:0897912640

DOI:10.1145/62212

Chairman:
J'anos Simon
Univ. of Chicago, Illinois

Copyright © 1988 ACM.

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]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1988

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC88

Sponsor:

SIGACT

STOC88: 1988 Symposium on the Theory of Computing

May 2 - 4, 1988

Illinois, Chicago, USA

Acceptance Rates

STOC '88 Paper Acceptance Rate 53 of 192 submissions, 28%;

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

543
Total Citations
View Citations
4,340
Total Downloads

Downloads (Last 12 months)611
Downloads (Last 6 weeks)59

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Madathil VScafuro AVerber T(2025)Round-Optimal Compiler for Semi-Honest to Malicious Oblivious Transfer via CIHIACR Communications in Cryptology10.62056/abe0wa3y61:4Online publication date: 13-Jan-2025
https://doi.org/10.62056/abe0wa3y6
Bansal ASikora J(2025)Breaking barriers in two-party quantum cryptography via stochastic semidefinite programmingQuantum10.22331/q-2025-01-20-16029(1602)Online publication date: 20-Jan-2025
https://doi.org/10.22331/q-2025-01-20-1602
Gurevin DJin CNguyen PKhan Ovan Dijk M(2025)Secure Remote Attestation With Strong Key Insulation GuaranteesIEEE Transactions on Computers10.1109/TC.2023.329087074:3(848-859)Online publication date: Mar-2025
https://doi.org/10.1109/TC.2023.3290870
Caha LCoiteux-Roy XKoenig R(2024)Single-qubit gate teleportation provides a quantum advantageQuantum10.22331/q-2024-12-04-15488(1548)Online publication date: 4-Dec-2024
https://doi.org/10.22331/q-2024-12-04-1548
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
Onofri SGiovannetti V(2024)Probabilistic versions of Quantum Private QueriesInternational Journal of Quantum Information10.1142/S021974992450014X22:07Online publication date: 29-Mar-2024
https://doi.org/10.1142/S021974992450014X
Pei TKang WLiu N(2024)Capacity Results for the Wiretapped Oblivious TransferIEEE Transactions on Information Theory10.1109/TIT.2024.348721870:12(9102-9122)Online publication date: Dec-2024
https://doi.org/10.1109/TIT.2024.3487218
Li XYan WLiu HZhang YHao QLiu YSun N(2024)MPC-PAT: A Pipeline Architecture for Beaver Triple Generation in Secure Multi-party Computation2024 IEEE International Test Conference in Asia (ITC-Asia)10.1109/ITC-Asia62534.2024.10661309(1-6)Online publication date: 18-Aug-2024
https://doi.org/10.1109/ITC-Asia62534.2024.10661309
Suda SWatanabe SYamaguchi H(2024)An Improved Lower Bound on Oblivious Transfer Capacity via Interactive Erasure Emulation2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619607(1872-1877)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619607
Chou R(2024)Dual-Source Symmetric PIR Without Data Replication or Shared Randomness2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619444(2664-2669)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619444
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten