On the Security of the Winternitz One-Time Signature Scheme
The authors show that the Winternitz one-time signature scheme is existentially unforgeable under adaptive chosen message attacks when instantiated with a family of pseudo random functions. Compared to previous results, which require a collision resistant hash function, the result provides significantly smaller signatures at the same security level. They also consider security in the strong sense and show that the Winternitz one-time signature scheme is strongly unforgeable assuming additional properties of the pseudo random function. In this paper they formally define several key-based security notions for function families and investigate their relation to pseudorandomness.