Off-Line/On-Line Signatures: Theoretical Aspects and Experimental Results

This paper presents some theoretical and experimental results about off-line/on-line digital signatures. The goal of this type of schemes is to reduce the time used to compute a signature using some kind of preprocessing. They were introduced by Even, Goldreich and Micali and constructed by combining regular digital signatures with efficient one-time signatures. Later Shamir and Tauman presented an alternative construction (which produces shorter signatures) by combining regular signatures with chameleon hash functions.

We first unify the Shamir-Tauman and Even

et al.

approaches by showing that they can be considered different instantiations of the same paradigm. We do this by showing that the one-time signatures needed in the Even

et al.

approach only need to satisfy a weak notion of security. We then show that chameleon hashing are in effect a type of one-time signatures which satisfy this weaker security notion.

In the process we study the relationship between one-time signatures and chameleon hashing, and we prove that a special type of chameleon hashing (which we call

two-trapdoor

) is a fully secure one-time signature.

Finally we ran experimental tests using OpenSSL libraries to test the difference between the two approaches. In our implementation we make extensive use of the observation that off-line/on-line digital signatures do not require collision-resistant hash functions to compress the message, but can be safely implemented with universal one-way hashing in both the off-line and the on-line step. The main application of this observation is that both the steps can be applied to shorter digests. This has particular relevance if block-ciphers or hash functions based one-time signatures are used since these are very sensitive to the length of the message. Interestingly, we show that (mostly due to the above observation about hashing), the two approaches are comparable in efficiency and signature length.