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.

$\endgroup$
  • 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 '17 at 13:27
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...

$\endgroup$
  • $\begingroup$ $W-OTS+$ is also more secure than $W-OTS$ in case of $SHA-256$ $\endgroup$ – Infinity Nov 21 '17 at 15:20
  • $\begingroup$ It will be huge favor\ if you tell what other versions of $W-OTS$ exist $\endgroup$ – Infinity Nov 21 '17 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 '17 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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