The notion of offline/online digital signature scheme was introduced by Even, Goldreich and Micali. Informally such signatures schemes are used to reduce the time required to compute a signature using some kind of preprocessing. Even, Goldreich and Micali show how to realize offline/online digital signature schemes by combining regular digital signatures with efficient onetime signatures. Later, Shamir and Tauman presented an alternative construction (which produces shorter signatures) obtained by combining regular signatures with chameleon hash functions. In this paper, we study offline/online digital signature schemes both from a theoretic and a practical perspective. More precisely, our contribution is threefold. First, we unify the Shamir–Tauman and Even et al. approaches by showing that they can be seen as different instantiations of the same paradigm. We do this by showing that the onetime signatures needed in the Even et al. approach only need to satisfy a weak notion of security. We then show that chameleon hashing is basically a onetime signature which satisfies such a weaker security notion. As a byproduct of this result, we study the relationship between onetime signatures and chameleon hashing, and we prove that a special type of chameleon hashing (which we call doubletrapdoor) is actually a fully secure onetime signature. Next, we consider the task of building, in a generic fashion, threshold variants of known schemes: Crutchfield et al. proposed a generic way to construct a threshold offline/online signature scheme given a threshold regular one. They applied known threshold techniques to the Shamir–Tauman construction using a specific chameleon hash function. Their solution introduces additional computational assumptions which turn out to be implied by the socalled onemore discrete logarithm assumption. Here, we propose two generic constructions that can be based on any threshold signature scheme, combined with a specific (doubletrapdoor) chameleon hash function. Our constructions are efficient and can be proven secure in the standard model using only the traditional discrete logarithm assumption. Finally, we ran experimental tests to measure the difference between the real efficiency of the two known constructions for nonthreshold offline/online signatures. Interestingly, we show that, using some optimizations, the two approaches are comparable in efficiency and signature length.
The notion of offline/online digital signature scheme was introduced by Even, Goldreich and Micali. Informally such signatures schemes are used to reduce the time required to compute a signature using some kind of preprocessing. Even, Goldreich and Micali show how to realize offline/online digital signature schemes by combining regular digital signatures with efficient onetime signatures. Later, Shamir and Tauman presented an alternative construction (which produces shorter signatures) obtained by combining regular signatures with chameleon hash functions. In this paper, we study offline/online digital signature schemes both from a theoretic and a practical perspective. More precisely, our contribution is threefold. First, we unify the ShamirTauman and Even et al. approaches by showing that they can be seen as different instantiations of the same paradigm. We do this by showing that the onetime signatures needed in the Even et al. approach only need to satisfy a weak notion of security. We then show that chameleon hashing is basically a onetime signature which satisfies such a weaker security notion. As a byproduct of this result, we study the relationship between onetime signatures and chameleon hashing, and we prove that a special type of chameleon hashing (which we call doubletrapdoor) is actually a fully secure onetime signature. Next, we consider the task of building, in a generic fashion, threshold variants of known schemes: Crutchfield et al. proposed a generic way to construct a threshold offline/online signature scheme given a threshold regular one. They applied known threshold techniques to the ShamirTauman construction using a specific chameleon hash function. Their solution introduces additional computational assumptions which turn out to be implied by the socalled onemore discrete logarithm assumption. Here, we propose two generic constructions that can be based on any threshold signature scheme, combined with a specific (doubletrapdoor) chameleon hash function. Our constructions are efficient and can be proven secure in the standard model using only the traditional discrete logarithm assumption. Finally, we ran experimental tests to measure the difference between the real efficiency of the two known constructions for nonthreshold offline/online signatures. Interestingly, we show that, using some optimizations, the two approaches are comparable in efficiency and signature length.
Offline/online signatures revisited: A general unifying paradigm, efficient threshold variants and experimental results
CATALANO, Dario;DI RAIMONDO, MARIO;
20130101
Abstract
The notion of offline/online digital signature scheme was introduced by Even, Goldreich and Micali. Informally such signatures schemes are used to reduce the time required to compute a signature using some kind of preprocessing. Even, Goldreich and Micali show how to realize offline/online digital signature schemes by combining regular digital signatures with efficient onetime signatures. Later, Shamir and Tauman presented an alternative construction (which produces shorter signatures) obtained by combining regular signatures with chameleon hash functions. In this paper, we study offline/online digital signature schemes both from a theoretic and a practical perspective. More precisely, our contribution is threefold. First, we unify the Shamir–Tauman and Even et al. approaches by showing that they can be seen as different instantiations of the same paradigm. We do this by showing that the onetime signatures needed in the Even et al. approach only need to satisfy a weak notion of security. We then show that chameleon hashing is basically a onetime signature which satisfies such a weaker security notion. As a byproduct of this result, we study the relationship between onetime signatures and chameleon hashing, and we prove that a special type of chameleon hashing (which we call doubletrapdoor) is actually a fully secure onetime signature. Next, we consider the task of building, in a generic fashion, threshold variants of known schemes: Crutchfield et al. proposed a generic way to construct a threshold offline/online signature scheme given a threshold regular one. They applied known threshold techniques to the Shamir–Tauman construction using a specific chameleon hash function. Their solution introduces additional computational assumptions which turn out to be implied by the socalled onemore discrete logarithm assumption. Here, we propose two generic constructions that can be based on any threshold signature scheme, combined with a specific (doubletrapdoor) chameleon hash function. Our constructions are efficient and can be proven secure in the standard model using only the traditional discrete logarithm assumption. Finally, we ran experimental tests to measure the difference between the real efficiency of the two known constructions for nonthreshold offline/online signatures. Interestingly, we show that, using some optimizations, the two approaches are comparable in efficiency and signature length.File  Dimensione  Formato  

OffLine OnLine Signatures revisited: a general unifying paradigm, efficient threshold variants and experimental results (journal PDF).pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Dimensione
423.77 kB
Formato
Adobe PDF

423.77 kB  Adobe PDF  Visualizza/Apri 
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.