Pushing the Limits of One-Time Signatures

Abstract

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.