What is the smallest hash-based OTS in terms of the sum of the public key and signature which provides 256 bits of security?
1
-
$\begingroup$ Possibly related question on Winternitz One-Time Signature. $\endgroup$– fgrieu ♦Jan 1, 2018 at 9:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
In theory, there is another scheme bei Bleichenbacher and Maurer which is slightly more efficient but according to current knowledge requires collision resistance and hence needs a bigger hash function output length.
-
$\begingroup$ 256-bit post-quantum security sounds reasonable. $\endgroup$– MelabJan 4, 2018 at 22:08
-
$\begingroup$ In which world? Already 128bit quantum security seems sometimes close to overkill. Something like 256 classical / 128 post-quantum is already super conservative. $\endgroup$– mephistoJan 5, 2018 at 21:39
-
$\begingroup$ We had 256 classical security, so why not have 256 post-quantum security? $\endgroup$– MelabJan 6, 2018 at 6:49
-
$\begingroup$ 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. $\endgroup$– mephistoJan 6, 2018 at 8:46
-
$\begingroup$ And in practice we also use classical 128 bit security all over the place and consider it fine. Or did you see anyone asking you to use 26268 bit RSA keys? Or 512 bit hash functions? The latter are standardized as NIST asked for it but no one is using it. $\endgroup$– mephistoJan 6, 2018 at 8:51