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.

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

CATALANO, Dario;DI RAIMONDO, MARIO;
2008-01-01

Abstract

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.
2008
978-3-540-78439-5
File in questo prodotto:
File Dimensione Formato  
Off-Line On-Line Signatures: Theoretical aspects and Experimental Results (proceedings PDF).pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Dimensione 607.76 kB
Formato Adobe PDF
607.76 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/78831
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 32
  • ???jsp.display-item.citation.isi??? 27
social impact