BUFF properties for FALCON without increasing the signature size

[Rune Fiedler]

Dear all,

as shown in [CDFFJ21], FALCON does not achieve the BUFF properties
exclusive ownership, message-bound signatures, and non-resignability,
all of which give extra guarantees in the presence of maliciously
generated (public) keys. Previously, the FALCON team has expressed their
intention to implement the generic BUFF transform [CDFFJ21] to achieve
the desired BUFF properties [FALCON22], at the cost of increasing the
signature size by one hash digest (64 bytes, i.e., 1280 bytes to 1344
bytes for security level V).

In our recent work [DFF24], we show that FALCON can achieve the BUFF
properties without increasing the signature size: When the signing
procedure hashes the message with a random salt, we additionally include
the public key in the computation, H(r|pk|m) instead of H(r|m); and
likewise for verification. The idea for this transformation originates
from [PS05] (hence called "PS-3-transform" in our paper) and is a part
of the BUFF transform (which additionally appends this digest to the
signature).

We give our proofs in the Random Oracle Model and (partially) lift them
to the Quantum Random Oracle Model. Unforgeability of the transformed
scheme tightly reduces to unforgeability of the original scheme.

With these new results, we suggest to standardize FALCON with the
PS-3-transform applied over FALCON with the BUFF transform applied. This
way, we can have the extra security of the BUFF properties without the
penalty of extended signature sizes.

Best regards,
Samed, Rune, and Marc

[CDFFJ21] https://eprint.iacr.org/2020/1525
[DFF24] https://eprint.iacr.org/2024/710
[FALCON22]
https://csrc.nist.gov/csrc/media/Presentations/2022/falcon-update/images-media/session-1-prest-falcon-pqc2022.pdf
[PS05] https://doi.org/10.1007/11496137_10