Would this raise the security margin and allow use of 128-bit signatures for exactly 128-bit (classical) security?
Yes and no - yes, it would raise the security margin somewhat, but not to the full "128 bit classical security level".
As for why it wouldn't raise it to the full 128 bit level, well, for two reasons:
For one, the attacker could take a guess at S0
, and compute TRUNCATE-128(HMAC(S0,i||"0"))
and see if it happens to be the value in the public key; that can happen for two reasons:
His guess for S0
happens to be correct; if S0
is 128 bits, this happens with probability $2^{-128}$
His guess for S0
is wrong, but TRUNCATE-128(HMAC(S0,i||"0"))
just happens to be the correct value anyways; if we model HMAC as a random function, then this happens with probability $2^{-128}$
Hence, the probability of either of these happening is approximately $2^{-127}$, giving us a security level that is slightly less than 128 bits.
- For another, let us assume that the adversary has $M$ public key, messages and signatures (each message being $N$ bits); what he can do is try to guess
S0
for the first bit of each private key; if he succeeds (for any message with a 1
first bit, hence S1
was used), then he can generate that forgery for that public key. If we assume that the goal of the adversary is to generate a forgery for one of the public keys (and he doesn't care which), then the expected work effort is $2^{-128} / (N/2)$ (with the $N/2$ factor being the approximate messages with a 0
first bit); for large $N$ this is obviously a nontrivial decrease in security.
Now, the obvious defense against the first observation is to increase the size of S0
and S1
(which will cause an increase in the size of a signature). And, against the second observation, you need to stir in some per-public-key distinguisher (along with the 'bit position' which your proposal does) somehow into the one-way-function. If you look at the current standard hash based signature methods (LMS, XMSS, Sphincs+), they do that (using various techniques to stir things in - none of them use HMAC).