Paper 2005/418

Generic On-Line/Off-Line Threshold Signatures

Chris Crutchfield, David Molnar, David Turner, and David Wagner


We propose on-line/off-line threshold signature schemes, in which the bulk of signature computation can take place ``off-line" during lulls in service requests. Such precomputation can help systems using threshold signatures quickly respond to requests. For example, tests of the Pond distributed file system showed that computation of a threshold RSA signature consumes roughly 86% of the time required to service writes to small files. Because a large number of writes in file systems are for small files, threshold signatures form a performance bottleneck in Pond and similar systems. We apply the ``hash-sign-switch" paradigm of Shamir and Tauman and the distributed key generation protocol of Gennaro et al. to convert any existing secure threshold digital signature scheme into a threshold on-line/off-line signature scheme. Our construction is fully distributed and requires no trusted dealers. We show that the straightforward attempt at proving security of the resulting construction runs into a subtlety that does not arise for Shamir and Tauman's construction. We resolve the subtlety and prove our signature scheme secure against a static adversary in the partially synchronous communication model under the one-more-discrete-logarithm assumption. The on-line phase of our scheme is efficient: computing a signature takes one round of communication and a few modular multiplications in the common case.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
On-lineOff-lineSignature SchemesThreshold Cryptography
Contact author(s)
turnerdx @ gmail com
2006-11-06: revised
2005-11-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chris Crutchfield and David Molnar and David Turner and David Wagner},
      title = {Generic On-Line/Off-Line Threshold Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2005/418},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.