Changes between Version 62 and Version 63 of Bibliography


Ignore:
Timestamp:
2011-11-29T17:50:08Z (10 years ago)
Author:
zooko
Comment:

demote some older pubs about hash-based sigs

Legend:

Unmodified
Added
Removed
Modified
  • Bibliography

    v62 v63  
    3030and practical signature scheme with minimal security requirements: a pseudorandom and a second preimage resistant (hash) function family. Its signature size is reduced to less than 25% compared to
    3131the best provably secure hash based signature scheme.”
    32 
    33 [http://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/DOTV08.pdf Digital Signatures out of Second-Preimage Resistant Hash Functions] by Dahmen, Okeya, Takagi, Vuillame; This scheme is secure as long as the underlying hash function has ''second-preimage resistance'', which real hash functions are a lot more likely to have than to have a stronger property like ''collision-resistance''.
    34 
    35 [http://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/hashbasedcrypto.pdf Hash-based Digital Signature Schemes] by Buchmann, Dahmen, and Szydlo; A survey of why it might be a good idea.
    36 
    37 [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8AC81C407AA3CBF35093032BD01F3085?doi=10.1.1.95.1374&rep=rep1&type=pdf Merkle Signatures with Virtually Unlimited Signature Capacity] by Buchmann, Dahmen, Klintsevich, Okeya, and Vuillaume; includes treating the parameters as an optimization problem and solving it with various weights or constraints to find various good settings for the parameters. Unfortunately their weights and constraints are different from hours: they thought it was fine to let key generation time take tens of hours! We want key generation time to be as few milliseconds as possible. A good rule of thumb for us would probably be try to reduce the time of whichever of the three operations is the slowest: key-generation, signing, and verification.
    38 
    39 [https://www.minicrypt.cdc.informatik.tu-darmstadt.de/reports/reports/REDBP08.pdf Fast Hash-Based Signatures on Constrained Devices] by Rohde, Eisenbarth, Dahmen, Buchmann, and Paar; a case study of implementing hash-based digital signatures for a 8-bit microcontroller. Their implementation had some trade-offs that we wouldn't want: it is a "key-evolving" design (the signer has to maintain state in order to avoid a security failure), it can only handle a limited number of signatures, and they spent a lot of time in key generation. Hm, they don't say how long key-generation took in this paper—only that it took so long that they had to run it on a PC instead of on their microcontroller. In [Merkle Signatures with Virtually Unlimited Signature Capacity], the key-generation took tens of hours on a PC!!! On the other hand, they do show a digital signature scheme which is faster at signing and verifying and is also arguably safer than RSA or ECDSA on their 8-bit microcontroller.
    4032
    4133=== Elliptic Curve Cryptography ===
     
    121113
    122114[https://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=81263 Cryptanalysis of the Tiger Hash Function] by Mendel and Rijmen
     115
     116[http://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/DOTV08.pdf Digital Signatures out of Second-Preimage Resistant Hash Functions] by Dahmen, Okeya, Takagi, Vuillame; This scheme is secure as long as the underlying hash function has ''second-preimage resistance'', which real hash functions are a lot more likely to have than to have a stronger property like ''collision-resistance''.
     117
     118[http://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/hashbasedcrypto.pdf Hash-based Digital Signature Schemes] by Buchmann, Dahmen, and Szydlo; A survey of why it might be a good idea.
     119
     120[http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8AC81C407AA3CBF35093032BD01F3085?doi=10.1.1.95.1374&rep=rep1&type=pdf Merkle Signatures with Virtually Unlimited Signature Capacity] by Buchmann, Dahmen, Klintsevich, Okeya, and Vuillaume; includes treating the parameters as an optimization problem and solving it with various weights or constraints to find various good settings for the parameters. Unfortunately their weights and constraints are different from hours: they thought it was fine to let key generation time take tens of hours! We want key generation time to be as few milliseconds as possible. A good rule of thumb for us would probably be try to reduce the time of whichever of the three operations is the slowest: key-generation, signing, and verification.
     121
     122[https://www.minicrypt.cdc.informatik.tu-darmstadt.de/reports/reports/REDBP08.pdf Fast Hash-Based Signatures on Constrained Devices] by Rohde, Eisenbarth, Dahmen, Buchmann, and Paar; a case study of implementing hash-based digital signatures for a 8-bit microcontroller. Their implementation had some trade-offs that we wouldn't want: it is a "key-evolving" design (the signer has to maintain state in order to avoid a security failure), it can only handle a limited number of signatures, and they spent a lot of time in key generation. Hm, they don't say how long key-generation took in this paper—only that it took so long that they had to run it on a PC instead of on their microcontroller. In [Merkle Signatures with Virtually Unlimited Signature Capacity], the key-generation took tens of hours on a PC!!! On the other hand, they do show a digital signature scheme which is faster at signing and verifying and is also arguably safer than RSA or ECDSA on their 8-bit microcontroller.
     123