Quantum Secure Signing Algorithm with a 256 bit signature & key. Am I missing anything? Can I remove tradeoff?

Question

So I was looking at Lamport signatures and trying to figure out if there is a way to reduce the key size and signature. I stumbled across something that is tiny (125 times smaller signatures and 500 times smaller public key) and almost as secure but it has a catch.

So, I realized that Lamport Signatures get their security from requiring the user to pre-commit to 512 different values, you then show half your secret keys to sign. The security comes from the fact that an attacker only has odds of any randomly picked number being the correct signature of roughly 1/2^256

What if instead, you started with a random 512 bit number A, hashed A getting 512 bit B, then hashed it again to get 512 bit C. Now you use C as your public key. And when you want to sign a message, like Lamport signatures, if a bit is 0, then you pull a bit from A, if 1 then pull a bit from B. The difference being that with Lamport you need an entire hash not just a bit(little bit more secure.. but not worth the space, double the key in my system and you probably have more security).

Then catch is that you now need to reveal A, which can be used to calculate B and C. This proves that you did indeed use those hashes to sign. The problem is that you've just revealed your private key and anyone else can sign on your behalf. So the only way this works is if you use two phases: commit phase where you hand over the signature and message. Then a verifying phase where you send over your private key to verify that it was indeed you signing it.

In most cases, multiphases is fine. After all, Lamport is essentially multiphase.. send public key, send signature.

Using a long hash chain you could come up with a many-use private key where you just pop off the last hash (which is actually three hashes) to use it.

Am I missing anything? Any thoughts on how to remove the commit phase or construct something that gets similar security uses a similar idea?

Still not going to work for my cryptocurrency since I can't have multi-phase signatures but might help some people out there or help with brainstorming a shorter public key & signature scheme that would work.

Answer 1

In most cases, multiphases is fine. After all, Lamport is essentially multiphase.. send public key, send signature.

Not quite - with Lamport (or any other signature scheme), after seeing the public key and the signature, an attacker still cannot forge a signature; with your technique, he can. Almost all uses of signatures rely on this property, and so your technique cannot be considered a general replacement.

If what you have meets the requirements of your problem space, that's fine. Just realize that it really is a niche solution...

Actually, if you're happy with the limitations of your method, it can be simplified somewhat: to "sign" a message $M$, pick a random string $R$, and transmit $H(R, M)$ and $M$. Then, in phase 2, transmit $R$. This uses one fewer hash (and the hash can be of shorter length, as we're not giving away half the bits in the commit phase).