article

Free access

A randomized protocol for signing contracts

Authors:

Shimon Even,

Oded Goldreich,

Abraham LempelAuthors Info & Claims

Communications of the ACM, Volume 28, Issue 6

Pages 637 - 647

https://doi.org/10.1145/3812.3818

Published: 01 June 1985 Publication History

PDF eReader

Abstract

Randomized protocols for signing contracts, certified mail, and flipping a coin are presented. The protocols use a 1-out-of-2 oblivious transfer subprotocol which is axiomatically defined.

The 1-out-of-2 oblivious transfer allows one party to transfer exactly one secret, out of two recognizable secrets, to his counterpart. The first (second) secret is received with probability one half, while the sender is ignorant of which secret has been received.

An implementation of the 1-out-of-2 oblivious transfer, using any public key cryptosystem, is presented.

References

[1]

Blum, M. private communication, 1981.

Google Scholar

[2]

Blum, M. Coin flipping by telephone, IEEE Spring COMCON, 1982.

Google Scholar

[3]

Blum, M. How to exchange (secret) keys. ACM Trans. Comput. Syst. 1, 2 (May 1983), 175-193. Also In Proceedings of the 15th STOC. 1983, pp. 440-447.

Digital Library

Google Scholar

[4]

Blum, M., and Rabin, M.O. How to send certified electronic mail, in preparation.

Google Scholar

[5]

DeMillo. R., Lynch, N., and Merritt, M. Cryptographic protocols. In Proceedings of the 14th STOC, 1982, pp. 383-400.

Digital Library

Google Scholar

[6]

Diffie, W., and Hellman, M.E. New directions in cryptography, IEEE Trans. hf. Theory, IT-22,6 (Nov. 1976). 644-654.

Digital Library

Google Scholar

[7]

Dolev, D., Even, S., and Karp. R.M. On the security of ping-pong protocols. hf. Control 55. (1982). 57-68.

Google Scholar

[8]

Dolev. D., and Yao, A.C. On the security of public key protocols, In Proceedings of the 22nd FOCS, 1981, 350-357. Also in IEEE Tmns. In/. Theory, IT-29,1983, 198-208.

Digital Library

Google Scholar

[9]

Even, S. A protocol for signing contracts. Tech. Rep. 231, Computer Science Dept., Technion, Haifa, Israel, Jan. 1982. Also presented at Crypt0 81.

Google Scholar

[10]

Even, S., and Goldreich, 0. On the security of multi-party ping-pong protocols. In Proceedings of fhe 24th FOCS, 1983, 34-39.

Digital Library

Google Scholar

[11]

Even, S., Goldreich, O., and Lempel, A. A randomized protocol for signing contracts. Tech. Rep. 233, Computer Science Dept. Technion, Haifa. Israel, Feb. 1982. An extended abstract appears in Advances in Cryptology: Proceedings of Crypt0 82, D. Chaum, et al. Eds., Plenum Press, New York, 1983, pp. 205-210.

Google Scholar

[12]

Even, S., and Yacovi, Y. Relations among public key signature systems Tech. Rep. 175, Computer Science Dept., Technion. Haifa. Israel, Mar. 1980.

Google Scholar

[13]

Fischer, M., Micali, S., and Rackoff, C. An oblivious transfer equivalent to factoring. Presented at EuroCrypt 84.

Google Scholar

[14]

Goldreich, 0. A protocol for sending certified mail, Tech, Rep, 239, Computer Science Dept., Technion. Haifa, Israel, Apr. 1982.

Google Scholar

[15]

Goldreich. 0. On concurrent identification protocols. Tech. Rep. MIT/LCS/TM-250, Massachusetts Institute of Technology, Cambridge, Dec. 1983. Also presented at EuroCrypt 84.

Google Scholar

[16]

Goldreich, 0. Sending certified mail using oblivious transfer and a threshold scheme. Tech. Rep. 325, Science Dept., Technion, Haifa, Israel, July 1984. This is a revised version of Appendix H in On the security of cryptographic protocols and cryptosystems. DSc. thesis, Computer Science Dept., Technion. Haifa, Israel, 1983.

Google Scholar

[17]

Goldreich, 0. A simple protocol for signing contracts. In Advances in Cryptology: Proceedings ofCypt083. D. Chaum, Ed., Plenum Press, New York, 1984, pp. 133-136.

Crossref

Google Scholar

[18]

Goldreich, O., Goldwasser, S. and Micali, S. How to construct random functions. In Proceedings of the 25fh FOCS, 1984, 464-479.

Google Scholar

[19]

Goldwasser, S., and Micali. S. Probabilistic encryption and how to play mental poker, keeping secret all partial information. In Proceedings of fhe 14th STOC. 1982. 365-377. Also in 1. Comput. Syst. Sci. 28, 2 (1984). 270-299.

Digital Library

Google Scholar

[20]

Goldwasser, S. Micali, S., and Rackoff, C. The knowledge complexity of theorem-proving procedures. In Proceedings of thei 7fh SfOC, to appear.

Google Scholar

[21]

Goldwasser, S. Micali, S., and Rivest. R.L. A paradoxical signature scheme. In Proceedings of the 25th FOCS, 1984, 441-448.

Google Scholar

[22]

Hastad, J., and Shamir, A. The cryptographic security of truncated linearly related variables. In Proceedings of the 27th STOC, 1985, to appear.

Digital Library

Google Scholar

[23]

Luby. M., Micali, S. and Rackoff, C. How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin. In Proceedings of the 24th FOCS, 1983, 11-21.

Digital Library

Google Scholar

[24]

Merkle. R.C. Secure communication over insecure channel. Comman. ACM 21,4 (Apr. 19781, 294-299.

Digital Library

Google Scholar

[25]

National Bureau of Standards, Data Encryption Standard, Federal Information Processing Standards, Publ. 46. 1977.

Google Scholar

[26]

Rabin, M.O. Digitalized signatures and public key functions as intractable as factoring. Tech. Rep. MIT/LCS/TR-212, Massachusetts Institute of Technology, Cambridge, 1979.

Digital Library

Google Scholar

[27]

Rabin, M.O. How to exchange secrets by oblivious transfer. unpublished manuscript, 1981.

Google Scholar

[28]

Rabin, M.O. Transaction protection by beacons. Tech. Rep. TR-29- 81, Aiken Computation Laboratory, Harvard Univ., Cambridge, Mass., 1981.

Google Scholar

[29]

Rackoff, C., and Luby. M. One-one pseudo-random function generation and DES, in preparation.

Google Scholar

[30]

Rivest, R.L. Shamir, A., and Adlernan. L. A method for obtaining digital signature and public key cryptosystems. Commun. ACM 21, 2 (Feb. 1978), 120-126.

Digital Library

Google Scholar

[31]

Shamir, A. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612-613.

Digital Library

Google Scholar

[32]

Tedrick, T. Fair exchange of secrets. In Proceedings of Crypfo84, to appear.

Digital Library

Google Scholar

[33]

Yao, AC. Protocols for secure computation. In Proceedings of the 23rd FOCS, 1982,160-164.

Crossref

Google Scholar

Cited By

View all

LI HSHI RKE WJIA Q(2024)Quantum protocol for secure multiparty XOR with application to secure communication in metropolitan area networksSCIENTIA SINICA Physica, Mechanica & Astronomica10.1360/SSPMA-2023-027354:3(230312)Online publication date: 6-Feb-2024
https://doi.org/10.1360/SSPMA-2023-0273
Farràs ORibes-González J(2024)One-Out-of-q OT CombinersIEEE Transactions on Information Theory10.1109/TIT.2023.334029470:4(2984-2998)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3340294
Chenli CTang WLee HJung T(2024)Fair$^{2}$2Trade: Digital Trading Platform Ensuring Exchange and Distribution FairnessIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.336219621:5(4827-4842)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/TDSC.2024.3362196
Show More Cited By

Recommendations

A fair protocol for signing contracts

Two parties, A and B, want to sign a contract C over a communication network. To do so, they must simultaneously exchange their commitments to C. Since simultaneous exchange is usually impossible in practice, protocols are needed to approximate ...
Resolve-Impossibility for a Contract-Signing Protocol
CSFW '06: Proceedings of the 19th IEEE workshop on Computer Security Foundations

A multi-party contract signing protocol allows a set of participants to exchange messages with each other with a view to arriving in a state in which each of them has a preagreed contract text signed by all the others. Such a protocol was introduced by ...
Efficient Fair Contract Signing Protocol from Bilinear Pairings
ISECS '08: Proceedings of the 2008 International Symposium on Electronic Commerce and Security

This paper presents a new fair contract signing protocol between two distrusted parties, which is based on a signature scheme, a verifiable and recoverable encrypted signature (VRES) from bilinear pairings. The protocol employs an off-line trusted third ...

Reviews

Reviewer: Graham K. Jenkins

The increasing acceptance of electronic mail as a business tool has revealed a few problems which have not been manifested in its nonelectronic counterpart. Thus, the signing of a contract between two parties necessitates the electronic exchange of signatures between those parties. The authors of this paper have developed a procedure by which this may be reliably accomplished. An Oblivious Transfer protocol is outlined for this purpose, and this in turn employs a Partial Secrets Exchange subprotocol, employing any appropriate Public Key Encryption system. A similar procedure may be applied to the receipt of certified mail; acknowledgment is generated if and only if the receiver has received an entire message. A further protocol is outlined for the electronic flipping of a coin (where the parties are not co-located and must communicate through some sort of network). The approach is thorough, and a comprehensive set of references is included. The paper will be invaluable for anyone concerned with cryptosystems and their applications.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 28, Issue 6

June 1985

86 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/3812

Editor:
Peter J. Denning
NASA Ames Reasearch enter, Moffett Field, CA

Issue’s Table of Contents

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 June 1985

Published in CACM Volume 28, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

935
Total Citations
View Citations
3,632
Total Downloads

Downloads (Last 12 months)588
Downloads (Last 6 weeks)86

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

LI HSHI RKE WJIA Q(2024)Quantum protocol for secure multiparty XOR with application to secure communication in metropolitan area networksSCIENTIA SINICA Physica, Mechanica & Astronomica10.1360/SSPMA-2023-027354:3(230312)Online publication date: 6-Feb-2024
https://doi.org/10.1360/SSPMA-2023-0273
Farràs ORibes-González J(2024)One-Out-of-q OT CombinersIEEE Transactions on Information Theory10.1109/TIT.2023.334029470:4(2984-2998)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3340294
Chenli CTang WLee HJung T(2024)Fair$^{2}$2Trade: Digital Trading Platform Ensuring Exchange and Distribution FairnessIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.336219621:5(4827-4842)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/TDSC.2024.3362196
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
Chenli CTang WMukherjee SJung T(2024)SCAFT: A Scalable Crowd-Assisted Fair Trading Protocol2024 IEEE International Conference on Blockchain (Blockchain)10.1109/Blockchain62396.2024.00065(442-449)Online publication date: 19-Aug-2024
https://doi.org/10.1109/Blockchain62396.2024.00065
Makhdoom IAbolhasan MLipman JShariati NFranklin DPiccardi M(2024)Securing Personally Identifiable Information: A Survey of SOTA Techniques, and a Way ForwardIEEE Access10.1109/ACCESS.2024.344701712(116740-116770)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3447017
Stroh LPeat JKroneberg MPuthoor IAndersson E(2024)Quantum Rabin oblivious transfer using two pure statesPhysical Review Research10.1103/PhysRevResearch.6.0430046:4Online publication date: 2-Oct-2024
https://doi.org/10.1103/PhysRevResearch.6.043004
Li HShi RJia Q(2024)Quantum secure multiparty computing XOR protocol based on single photons and its application in quantum secure communications for intelligence agentsPhysica Scripta10.1088/1402-4896/ad59d899:8(085101)Online publication date: 1-Jul-2024
https://doi.org/10.1088/1402-4896/ad59d8
Tran ALuong THuynh V(2024)A comprehensive survey and taxonomy on privacy-preserving deep learningNeurocomputing10.1016/j.neucom.2024.127345576:COnline publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1016/j.neucom.2024.127345
Feng JZhang JZhang WHan G(2024)Detecting malicious encrypted traffic with privacy set intersection in cloud-assisted industrial internetJournal of Information Security and Applications10.1016/j.jisa.2024.10383185(103831)Online publication date: Sep-2024
https://doi.org/10.1016/j.jisa.2024.103831
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

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

A fair protocol for signing contracts

Resolve-Impossibility for a Contract-Signing Protocol

Efficient Fair Contract Signing Protocol from Bilinear Pairings

Reviews

Access critical reviews of Computing literature here