# Smallest 256-bit security hash-based OTS?

What is the smallest hash-based OTS in terms of the sum of the public key and signature which provides 256 bits of security?

I will just assume you mean 256-bit classical security as 256-bit post-quantum would be ridiculous. Then it would most likely be WOTS+ in the multi-target secure version described in this paper. The signature size depends on the value you choose for the Winternitz parameter $w$. For $w=16$ a signature contains 67 hash values (each of which should be 256bits in your case). As public key you can take the hash of all the chain ends (and the public seed) as done in the SPHINCS+ specification. Then your public key is two hashes (512 bit in your case). Key generation in this case costs ~67*16 short hashes and one hash over 67 hash values. Sign and verify for a given message add up to key generation time, i.e., they are both strictly upper bounded by these 67*16 + 1 hashes.
• Because this was already overkill classically. The observable universe has about $2^{265}$ atoms... However, justification for such a high security was a margin to account for possible impacts of cryptanalysis. In the symmetric setting this seems unreasonable as you would just replace the used hash function / block cipher. – mephisto Jan 6 '18 at 8:46