Since the signatures all generate the public keys, those can be derived from sig and proven by pre-commited XOR of every pub key compared with XOR of every signature end hash.

  • $\begingroup$ Are you asking if a hash function that XORs other hash functions retains cryptographic security? $\endgroup$ – forest Apr 9 '19 at 0:58
  • $\begingroup$ yes sort of, does it? the question is asked in the context of Winternitz hash signature since I had the idea that it could shrink pub key size by 32x. $\endgroup$ – phi Apr 9 '19 at 12:31

If I understand you correctly, you're proposing that we have a number of one-time-signatures (which, with the corresponding messages, hash to the corresponding public keys), and then we produce the xor of all the public keys. Then, the receiver would validate all those signatures together (by computing the corresponding public keys, xor them together, and seeing if the result is the published xor).

If so, it doesn't work; an adversary could put together a forgery, that is, a series of messages and signatures that would evaluate to that same xor. How he would do so is straight-forward; he would generate a series of messages and random signatures; he would then find the corresponding public keys. Then, he would find a subset of those public keys that would xor to the published value - this can be done by solving a set of linear equations. That subset would be the forgery.

  • $\begingroup$ W-OTS has a public key of 32*256 bit, quite large. I was thinking those could be reduced to just 256 bit, by XORing them together. At loss of security but it seemed to me it would still be like finding a needle in a haysack. $\endgroup$ – phi Apr 9 '19 at 6:37
  • $\begingroup$ What are the linear equations? $\endgroup$ – phi Apr 9 '19 at 6:37
  • $\begingroup$ If a hash function is secure, and it is computationally hard to find a pre-image for a specific output, is it not also hard to find 32 pre-images whose hashes combine, with XOR, to a specific output? $\endgroup$ – phi Apr 9 '19 at 9:39
  • $\begingroup$ @phi: so, the attacker is bounded to using only 32 pre-images (rather than an arbitrary number); that's not quite as trivial, but still considerably simpler than finding a hash preimage. Why don't you just hash the 32 public keys together? $\endgroup$ – poncho Apr 9 '19 at 11:20
  • $\begingroup$ an attacker still has to find pre-image to hashes, even if XOR combination of 32 hashes, sounds similar in hardness to if the 32 public keys were hashed, but hash would work as well as XOR. $\endgroup$ – phi Apr 9 '19 at 11:23

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.