Abstract
In this paper we show how to achieve timed fair exchange of digital signatures of standard type. Timed fair exchange (in particular, contract signing) has been considered before, but only for Rabin and RSA signatures of a special kind. Our construction follows the gradual release paradigm, and works on a new “time” structure that we call a mirrored time-line. Using this structure, we design a protocol for the timed fair exchange by two parties of arbitrary values (values lying on their respective mirrored time-lines). We then apply the blinding techniques of Garay and Jakobsson to turn this protocol into a protocol for the timed fair exchange of standard signatures.
The length of these mirrored time-lines makes another problem apparent, which is making sure that the underlying sequence has a period large enough so that cycling is not observed. We also show how to construct these structures so that, under reasonable assumptions, this is indeed the case.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asokan, N., Shoup, V., Waidner, M.: Fair exchange of digital signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 591–606. Springer, Heidelberg (1998)
Bao, F.: An efficient verifiable encryption scheme for encryption of discrete logarithms. In: Schneier, B., Quisquater, J.-J. (eds.) CARDIS 1998. LNCS, vol. 1820. Springer, Heidelberg (2000)
Bleichenbacher, D.: On the distribution of DSA session keys (2000) (manuscript)
Blum, M.: Coin flipping by telephone: A protocol for solving impossible problems. In: Advances in Cryptology—CRYPTO 1981, pp. 11–15. ECE Report 82-04 (1982)
Blum, M.: How to exchange (secret) keys. ACM Transactions on Computer Systems 1(2), 175–193 (1983)
Blum, L., Blum, M., Shub, M.: A simple unpredictable pseudo-random number generator. SIAM Journal on Computing 15(2), 364–383 (1986)
Brickell, E., Chaum, D., Damgård, I., van de Graaf, J.: Gradual and verifiable release of a secret (extended abstract). In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 156–166. Springer, Heidelberg (1988)
Burmester, M., Desmedt, Y., Seberry, J.: Equitable Key Escrow with Limited Time Span. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 380–391. Springer, Heidelberg (1998)
Bellare, M., Goldwasser, S.: Encapsulated key escrow. In MIT/LCS/TR-688 (1996)
Bellare, M., Goldwasser, S.: Verifiable partial key escrow. In: Proc. ACM CCS, pp. 78–91 (1997)
Boneh, D., Naor, M.: Timed commitments (extended abstract). In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (2000)
Boudot, F.: Efficient proofs that a committed number lies in an interval. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 431–444. Springer, Heidelberg (2000)
Barić, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 480–494. Springer, Heidelberg (1997)
Boudot, F., Traoré, J.: Efficient publicly verifiable secret sharing schemes with fast or delayed recovery. In: Varadharajan, V., Mu, Y. (eds.) ICICS 1999. LNCS, vol. 1726, pp. 87–102. Springer, Heidelberg (1999)
Chaum, D.: Blind signatures for untraceable payments. In: Advances in Cryptology: Proceedings of Crypto 1982, pp. 199–203. Plenum Press, New York (1983)
Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
Chaum, D., Evertse, J., van de Graaf, J.: An improved protocol for demonstrating possession of discrete logarithms and some generalizations. In: Price, W.L., Chaum, D. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 127–141. Springer, Heidelberg (1988)
Chan, A., Frankel, Y., Thiounis, Y.: Easy come – easy go divisible cash. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 561–575. Springer, Heidelberg (1998)
Camenisch, J., Michels, M.: Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 106–121. Springer, Heidelberg (1999)
Camenisch, J., Michels, M.: Separability and efficiency for generic group signature schemes (extended abstract). In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 414–430. Springer, Heidelberg (1999)
Chaum, D., Pedersen, T.: Wallet databases with observers (extended abstract). In: Brickell, E.F. (ed.) CRYPTO 1992 [CRY92], pp. 89–105. Springer, Heidelberg (1993)
McCurley, K.S., Ziegler, C.D. (eds.): Advances in Cryptology 1981 - 1997. LNCS, vol. 740. Springer, Heidelberg (1999)
Damgård, I.B.: Practical and provably secure release of a secret and exchange of signatures. J. of Crypt. 8(4), 201–222 (1995)
Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992 [CRY92], pp. 139–147. Springer, Heidelberg (1993)
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)
Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Friedlander, J.B., Pomerance, C., Shparlinski, I.E.: Period of the power generator and small values of Carmichael’s function. Math. Comp. 70, 1591–1605 (2001)
Friedlander, J.B., Pomerance, C., Shparlinski, I.E.: Small values of the Carmichael function and cryptographic applications. In: Progress in Computer Science and Applied Logic, vol. 20, pp. 25–32, Birkhäuser Verlag, Basel, Switzerland (2001)
Goldreich, O.: A simple protocol for signing contracts. In: Advances in Cryptology—CRYPTO 1983, pp. 133–136 (1983)
Garay, J., Jakobsson, M.: Timed Release of Standard Digital Signatures. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 168–182. Springer, Heidelberg (2003)
Garay, J., Jakobsson, M., MacKenzie, P.: Abuse-free Optimistic Contract Signing. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 449–466. Springer, Heidelberg (1999)
Galbraith, S., Mao, W., Paterson, K.: A cautionary note regarding cryptographic protocols based on composite integers. In: HPL-2001-284 (2001)
Goldschlag, D., Stubblebine, S.: Publicly Verifiable Lotteries: Applications of Delaying Functions. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 214–226. Springer, Heidelberg (1998)
Hardy, G.H., Littlewood, J.E.: Some problems in “Partitio Numerorum” III: On the expression of a number as a sum of primes. Acta Math. 44, 1–70 (1923)
Mao, W.: Guaranteed correct sharing of integer factorization with off-line shareholders. In: Imai, H., Zheng, Y. (eds.) PKC 1998. LNCS, vol. 1431, pp. 27–42. Springer, Heidelberg (1998)
Mao, W.: Timed-Release Cryptography. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 342–357. Springer, Heidelberg (2001)
Martin, G., Pomerance, C.: The normal order of iterates of the Carmichael λ-function (in progress)
May, T.: Timed-release crypto (1993), http://www.hks.net/cpunks/cpunks-0/1460.html
Pomerance, C., Sorenson, J.: Counting the integers factorable via cyclotomic methods. J. Algorithms 19, 250–265 (1995)
Rivest, R., Shamir, A., Wagner, D.: Time-lock puzzles and timedrelease crypto. In: MIT/LCS/TR-684 (1996)
Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)
Shamir, A.: Partial key escrow: A new approach to software key escrow. In: Key Escrow Conference (1995)
Syverson, P.: Weakly Secret Bit Commitment: Applications to Lotteries and Fair Exchange. In: Proceedings of the 1998 IEEE Computer Security Foundations Workshop (CSFW11), Rockport Massachusetts (June 1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Garay, J.A., Pomerance, C. (2003). Timed Fair Exchange of Standard Signatures. In: Wright, R.N. (eds) Financial Cryptography. FC 2003. Lecture Notes in Computer Science, vol 2742. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45126-6_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-45126-6_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40663-1
Online ISBN: 978-3-540-45126-6
eBook Packages: Springer Book Archive