1
$\begingroup$

LMS is a hash-based digital signature scheme. It is a standard alongside of XMSS, which has it's bit-security stated in the paper(about 200bit-security for standard parameters). LMS security assumption is based on ROM of hash functions. Does it mean the bit-security for LMS is equal to the bit-security of hash functions in QROM?

$\endgroup$
1
$\begingroup$

Does it mean the bit-security for LMS is equal to the bit-security of hash functions in QROM?

Well, Edward Eaton examines this in a multitarget setting (that is, where the adversary has been given a number of public keys (and valid signatures for those keys), and aims to produce a forgery for any one of them); his conclusion (Theorem 2, section 4.2) is that:

Theorem 2. Let A be an adversary attacking the security of the full LMS scheme in the multi-user setting. If A makes at most q queries, then the probability they break the existential unforgeability of any of the instances of LMS is at most $$580q/2^{n/2}$$

Given that Grover's algorithm requires $\pi /2 \cdot 2^{n/2}$ queries (counting the compute and the uncompute operations as two separate queries), this implies that the security is no worse than $log_2(580 / (\pi/2)) \approx 8.5$ bits worse than the security of the underlying hash function against Grover's algorithm.

$\endgroup$
4
  • $\begingroup$ if I am not mistaken, LMS only allows SHA256 as a hashfunction, while XMSS can do either SHA2 or SHAKE? What is the bit security of these, in presence of the quantum computers? How does one calculate this bit security? $\endgroup$
    – namaewa
    Mar 2 at 21:42
  • $\begingroup$ @namaewa: well, if they act like a random Oracle, then the bit security would be the same (however, Eaton's analysis depends on some precise details of LMS, and so it is likely different by a constant factor). However, XMSS uses (for $n=256$) SHAKE-128; that has preimage resistance of only 128 bits (against a classical internal collision attack); I'm not certain to what extend this attack would be improved with a Quantum Computer. $\endgroup$
    – poncho
    Mar 2 at 22:37
  • $\begingroup$ so XMSS seems to have a weaker security assumption than LMS, I read in their paper that for n=32, w=16 and SHA256 it provides 196bit security. So LMS security for the same parameters would be 256? $\endgroup$
    – namaewa
    Mar 2 at 22:53
  • $\begingroup$ @namaewa: XMSS and LMS are analyzed in different security models, and so the resulting strengths are not directly comparable. If you were to ask about best known-attacks, LMS and the SHA-256 version of XMSS would be close (with XMSS getting a bit of an edge for multitarget attacks which assume a truly huge number of target public keys) $\endgroup$
    – poncho
    Mar 2 at 22:58

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.