Shimon Even
Oded Goldreich
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.
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 6 Diffie, W., and Hellman, M.E. New directions in cryptography, IEEE Trans. hf. Theory, IT-22,6 (Nov. 1976). 644-654.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 24 Merkle. R.C. Secure communication over insecure channel. Comman. ACM 21,4 (Apr. 19781, 294-299. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 31 Shamir, A. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612-613. Google ScholarDigital Library
- 32 Tedrick, T. Fair exchange of secrets. In Proceedings of Crypfo84, to appear. Google ScholarDigital Library
- 33 Yao, AC. Protocols for secure computation. In Proceedings of the 23rd FOCS, 1982,160-164.Google ScholarCross Ref
Index Terms
- A randomized protocol for signing contracts
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 FoundationsA 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 SecurityThis 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
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