Pushing the limits of one-time signatures

Bicakci K.

2nd International Conference on Security of Information and Networks, SIN'09, Famagusta, Cyprus (Gkry), 6 - 10 October 2009, pp.249-257 identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1145/1626195.1626258
  • City: Famagusta
  • Country: Cyprus (Gkry)
  • Page Numbers: pp.249-257
  • Keywords: Authentication, Digital signatures, Hash collisions, One-time signatures, Wireless sensor networks
  • Istanbul Technical University Affiliated: No


Computational and security advantages of one-time signatures come together with their length restrictions. In most applications, one-time signature should be accompanied with one-time public key(s) to enable multiple signing with a single certified public key. This is why most of the time decreasing the size of one-time signature at a cost of larger public key is not what we desire. In this paper, we show the most efficient one-time signature construction proposed so far in the sense that the total length of a signature and a public key is minimized. Requiring heavier offline computation while keeping the online computation cost both for signing and verification not changed, our improvement is a significant result especially for wireless sensor networks. This is because limited battery power puts stringent limitations on message sizes however heavy offline computation is acceptable and can be performed prior to the deployment of the sensor network. Copyright 2009 ACM.