SLH-DSA-SHAKE-128 is NIST "Category 1", but ML-DSA-768 is NIST "Category 3"

[dkg]

Assuming #99 goes through, we'll be standardizing two levels of SLH-DSA: SLH-DSA-SHAKE-128s and SLH-DSA-SHAKE-128f, which FIPS 205 indicates is NIST "category 1", and SLH-DSA-SHAKE-256s, which FIPS 205 indicates is NIST "Category 5".

But the ML-DSA choices are ML-DSA-768 (NIST "category 3") and ML-DSA-1024 (NIST "category 5").

So it looks to me like the weaker/smaller/faster SLH-DSA signatures are weaker than the weaker/smaller-faster ML-DSA . Is that intentional? Am i misreading the FIPS specs? are the NIST categories things we should be concerned about?

[falko-strenzke]

Indeed, this is a mismatch based on the NIST security levels that we intentionally introduced from the beginning: While for SLH-DSA we introduce the 128 bit and 256 bit parameters (previously also the 192 bit), for ML-DSA and ML-KEM we introduce the 192 bit and 256 bit parameters. (Note that here you seem to confuse the ML-KEM parameters "-512", "-768", and "-1024" with the ML-DSA parameters "-44", "-65", an "-87".)

The idea here is (at least in my interpretation of this mismatch) to maintain a security margin for the module-lattice schemes. This is also reflected by pairing the 192 bit module lattice parameters with EC parameters with 128 bit security and the 256 bit module lattice parameters with EC parameters with a security of 192 (or 224) bit.

[falko-strenzke]

@dkg Does my explanation make sense to you? Can we close this issue based on my response?

[dkg]

@wussler presented a table at the 2024 May interim which i thought was compelling for the current choices of algorithm strengths. As far as i'm concerned, we can close this issue.

[wussler]

This is the current security bits PQ/curve matching. Note that the security bits are approximate.

Algorithm	Security bits PQ	Security bits curve
ML-KEM-768 + X25519	192	128
ML-KEM-1024 + X448	256	224
ML-DSA-65 + Ed25519	192	128
ML-DSA-87 + Ed448	256	224
SLH-DSA-SHAKE-128f	128	N/A
SLH-DSA-SHAKE-128s	128	N/A
SLH-DSA-SHAKE-256s	256	N/A

In the current proposal, a safety margin is included for the ML-* algorithms, that are matched with curves with less security bits. The speed tradeoff is minimal, and the size tradeoff is around 1KB per operation.