Abstract
We introduce and construct timed commitment schemes, an extension to the standard notion of commitments in which a potential forced opening phase permits the receiver to recover (with e.ort) the committed value without the help of the committer. An important application of our timed-commitment scheme is contract signing: two mutually suspicious parties wish to exchange signatures on a contract. We show a two-party protocol that allows them to exchange RSA or Rabin signatures. The protocol is strongly fair: if one party quits the protocol early, then the two parties must invest comparable amounts of time to retrieve the signatures. This statement holds even if one party has many more machines than the other. Other applications, including honesty preserving auctions and collective coin-flipping, are discussed.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
L. Adleman, and K. Kompella, “Using smoothness to achieve parallelism”, proc. of STOC 1988, pp. 528–538.
N. Asokan, V. Shoup and M. Waidner, “Optimistic fair exchange of digital signatures”, in proc. Eurocrypt’98, pp. 591–606, 1998.
G. Ateniese, “Efficient protocols for verifiable encryption and fair exchange of digital signatures”, in proc. of the 6th ACM CCS, 1999.
M. Bellare and S. Goldwasser, “Verifiable Partial Key Escrow”, in proc. of ACM CCS, pp. 78–91, 1997.
M. Bellare and S. Goldwasser, “Encapsulated key escrow”. MIT Laboratory for Computer Science Technical Report 688, April 1996.
M. Bellare and P. Rogaway, “The Exact Security of Digital Signatures-How to Sign with RSA and Rabin”, EUROCRYPT 1996, pp. 399–416
M. Ben-Or, O. Goldreich, S. Micali and R. L. Rivest, “A Fair Protocol for Signing Contracts”, IEEE Transactions on Information Theory 36/1 (1990) 40–46
M. Blum, “How to Exchange (Secret) Keys”, STOC 1983: 440–447 and ACM TOCS 1(2): 175–193 (1983)
L. Blum, M. Blum and M. Shub, A Simple Unpredictable Pseudo-Random Number Generator. SIAM J. Comput. 15(2): 364–383 (1986).
J. Y. Cai, R. J. Lipton, R. Sedgwick, A. C. Yao, “Towards uncheatable benchmarks, Structures in Complexity”, in proc. Structures in Complexity, pp. 2–11, 1993.
J. Camenisch, M. Michels, “Proving in Zero-Knowledge that a Number Is the Product of Two Safe Primes”, EUROCRYPT 1999, pp. 107–122.
R. Canetti, O. Goldreich, S. Goldwasser and S. Micali. “Resettable Zero-Knowledge”, ECCC Report TR99-042, Oct 27, 1999 and STOC 2000.
D. Chaum, and T. Pederson, “Wallet databases with observers”, in Proceedings of Crypto’ 92, 1992, pp. 89–105.
R. Cleve, “Limits on the Security of Coin Flips when Half the Processors Are Faulty”, in proc. STOC 1986, pp. 364–369.
R. Cleve, “Controlled gradual disclosure schemes for random bits and their applications”, in proc. Crypto’89, 1990, pp. 573–588.
R. Cleve, R. Impagliazzo, “Martingales, collective coin flipping and discrete control processes”, manuscript, 1993. Available: http://www.cpsc.ucalgary.ca/cleve/papers.html
I. Damgård, “Concurrent Zero-Knowledge in the auxilary string model”, in proc. EUROCRYPT’ 2000.
I. Damgård, “Practical and Provably Secure Release of a Secret and Exchange of Signatures”, J. of Cryptology 8(4): 201–222 (1995)
D. Dolev, C. Dwork and M. Naor, “Non-malleable Cryptography”, Preliminary version: Proc. 21st STOC, 1991. Full version: to appear, Siam J. on Computing. Available: http://www.wisdom.weizmann.ac.il/naor
C. Dwork and M. Naor, “Pricing via Processing-or-Combatting Junk Mail”, Advances in Cryptology-CRYPTO’92, pp. 139–147.
C. Dwork and M. Naor, “An Efficient Existentially Unforgeable Signature Scheme and Its Applications”, J. of Cryptology 11, 1998, pp. 187–208
C. Dwork and M. Naor, “Zaps and their applications”, manuscript.
C. Dwork, M. Naor and A. Sahai, “Concurrent Zero-Knowledge”, STOC, 1998.
S. Even, O. Goldreich and A. Lempel, “A Randomized Protocol for Signing Contracts”, CACM 28(6): 637–647 (1985).
A. Fiat and A. Shamir, “How to Prove Yourself: Practical Solutions to Identification and Signature Problems”, CRYPTO’86, pp. 186–194.
J. A. Garay, M. Jakobsson and P. D. MacKenzie: “Abuse-Free Optimistic Contract Signing”, CRYPTO 1999, pp. 449–466.
O. Goldreich and H. Krawczyk. “On the Composition of Zero Knowledge Proof Systems”, SIAM J. on Computing, Vol. 25, No. 1, pp. 169–192, 1996.
J. Kilian, E. Petrank and C. Rackoff, “Lower Bounds for Zero Knowledge on the Internet”, FOCS 1998, pp. 484–492.
M. Luby, S. Micali and C. Rackoff, “How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin”, FOCS 1983, pp. 11–21
A. Menezes, P. van Oorschot and S. Vanstone, “Handbook of Applied Cryptography” CRC Press, 1996.
M. Naor, B. Pinkas and R. Sumner, “Privacy Preserving Auctions and Mechanism Design”, Proc. of the 1st ACM conference on E-Commerce, November 1999, pp. 129–139.
B. Pfitzmann, M. Waidner, “Optimal Efficiency of Optimistic Contract Signing”, PODC 1998: 113–122
M. O. Rabin, “Transaction Protection by Beacons”, JCSS 27(2): 256–267 (1983)
R. Richardson and J. Kilian, “On the Concurrent Composition of Zero-Knowledge Proofs”, EUROCRYPT’ 99, pp. 415–431, 1999.
R. Rivest, A. Shamir and D. Wagner, “Time lock puzzles and timed release cryptography”, Technical report, MIT/LCS/TR-684
A. Rosen, “A note on the round-complexity of concurrent zero-knowledge”, these proceedings.
V. Shmatikov and J. C. Mitchell, “Analysis of Abuse-Free Contract Signing”, in proc. of 4th Annual Conference on Financial Cryptography, 2000.
J. P. Sorenson, “A Sublinear-Time Parallel Algorithm for Integer Modular Exponentiation”, manuscript.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boneh, D., Naor, M. (2000). Timed Commitments. In: Bellare, M. (eds) Advances in Cryptology — CRYPTO 2000. CRYPTO 2000. Lecture Notes in Computer Science, vol 1880. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44598-6_15
Download citation
DOI: https://doi.org/10.1007/3-540-44598-6_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67907-3
Online ISBN: 978-3-540-44598-2
eBook Packages: Springer Book Archive