How many messages would it take until the success probability of a forger becomes $1/2$? $1/4$?

  • $\begingroup$ It might be worth adding a link / description of Sphincs(+) for context. $\endgroup$ – puzzlepalace Sep 17 '18 at 2:06

For all SPHINCS-like constructions, security is slightly more complicated to analyze than for say a hash function. For SPHINCS we do not only have two dimensions as for hash functions where we got the effort an attacker spends and the corresponding probability. For SPHINCS there is a third dimension, namely an 'attack effort' - 'probability' pair occurs only with a certain probability. This latter probability slowly increases with every signature an adversary sees. However, parameters are selected such that the probability that an 'attack effort' - 'probability' pair occurs times the inverse of the effort needed to achieve probability 1/2 under this pair is below a targeted value (this is what is considered the full attack complexity). E.g., for SPHINCS-256 this target value is $2^{128}$ considering quantum adversaries. This is not entirely true, as I said that the probability of occurrence increases with each signature. Hence, for every target value, there is a threshold for which it will be passed. Therefore one has to decide for how many signatures that target must not be passed. For SPHINCS-256 the target holds for $q = 2^{50}$ signatures. For SPHINCS+ the target holds for $q = 2^{64}$ signatures. If a user does more than $q$ signatures the attack complexity starts to decrease. Actually, the SPHINCS and SPHINCS+ specification/paper give formulas for the bit-security. You can answer your question yourself as follows:

In the case of SPHINCS-like constructions, a bit security of $b$ bits corresponds approximately to a success probability of $2^{-b}$. Just fix $b$ accordingly and solve for the number of signatures $q_{sign}$ in the formula.

| improve this answer | |

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.