3
$\begingroup$

There are two versions of Winternitz-One time signature scheme, $W-OTS$ and $W-OTS^+$

Security of both is as following

$W-OTS$ is strongly unforgeable under chosen message attacks if $F$ is a collision resistant, undetectable one-way function family

$W-OTS^+$is strongly unforgeable under chosen message attacks if $F$ is a $2nd$-preimage resistant, undetectable one-way function family

My question is which version is more secure $W-OTS$ or $W-OTS^+$?

According to my understanding $W-OTS$ is more secure than $W-OTS^+$ because for attacker it is comparatively easy to find collision resistant as compared to $2nd-$preimage resistant.

If so is it secure to use $2nd-$ preimage resistant Winternitz one time signature scheme?

Ideally scheme should be collision resistant or $2nd-$preimage resistant.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ The security of both cases are in the same category strongly unforgeable under chosen message attacks, with their respective assumption for the inner function. It does not make sense to compare the collision resistance of one function to the preimage resistance of another function - especially if they are actually functions drawn from a family of functions with some security parameters. What might be interesting however, is to have a closer look at the tightness of those security proofs. $\endgroup$
    – tylo
    Nov 20, 2017 at 13:27

1 Answer 1

Reset to default
6
$\begingroup$

W-OTS+ is stronger, as it makes weaker assumptions on the hash function.

Let us take a rather extreme example, let us consider W-OTS and W-OTS+ based on the MD5 hash function.

Now, the proof for W-OTS is quite invalid; it assumes that the hash function is collision resistant, and we know how to generate collisions with MD5.

On the other hand, W-OTS+ based on MD5 would appear to be secure; despite MD5 being "broken", we do not know how to create second preimages to MD5.

BTW: this appears to be more about the proof technique used to prove W-OTS, rather than the actual security; we can create MD5 collisions (invalidating the proof), however we don't know how to use those collisions to actually attack W-OTS-MD5; hence it would appear to be secure (but we can't prove it).

Also, one note: those aren't the only versions of Winternitz signatures in the published literature...

Improve this answer
$\endgroup$
3
  • $\begingroup$ $W-OTS+$ is also more secure than $W-OTS$ in case of $SHA-256$ $\endgroup$
    – Infinity
    Nov 21, 2017 at 15:20
  • $\begingroup$ It will be huge favor\ if you tell what other versions of $W-OTS$ exist $\endgroup$
    – Infinity
    Nov 21, 2017 at 15:21
  • $\begingroup$ Well, there's the OTS scheme in datatracker.ietf.org/doc/draft-mcgrew-hash-sigs (which is about 3 times faster than W-OTS+) $\endgroup$
    – poncho
    Nov 21, 2017 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.