Winternitz Signature Scheme Using Nonadjacent Forms

Abstract EN

Hash-based signatures are gaining attention as one of the alternatives that can replace current digital signatures that are not secure against an attack by quantum computers along with lattice-based signatures, multivariate signatures, and code-based signatures.

Up to now, all hash-based signatures have used binary representations to generate signatures.

In this paper, we propose using the nonadjacent form (NAF) when generating signatures in hash-based signatures.

Concretely, we propose a hash-based signature scheme, WSS-N, which is obtained by applying nonadjacent forms (NAF) to the Winternitz signature scheme.

We prove that WSS-N is existentially unforgeable under chosen message attacks in the standard model.

And we show that WSS-N needs less hash function calls compared to the Winternitz signature scheme using the binary representation, WSS-B.

For a specific parameter with a 256-bit security, we can see that WSS-N generates signatures faster than WSS-B by 8%.

Finally, we implement both WSS-N and WSS-B and show that WSS-N generates signatures faster than WSS-B on a desktop computer.