Falcon Post-Quantum Signature Scheme Proposal

In a recent discussion on the Bitcoin Development Mailing List, concerns were raised about the complexity and potential challenges of implementing Falcon, one of the NIST Post-Quantum Cryptography (PQC) schemes. The difficulty primarily stems from the need for software emulation of floating point arithmetic—a process that is not only intricate but also susceptible to errors that could lead to forgery attacks. Additionally, the scheme requires handling discrete Gaussian sampling, further complicating its implementation.

The conversation also highlighted the debate over the suitability of Falcon for bitcoin-like applications, given its signature overhead. Despite these concerns, there's an argument for the necessity of having a conservative stateless signing scheme as a fallback option. This is particularly relevant for authenticating the Unspent Transaction Output (UTXO) set in the face of potential Cryptographically Relevant Quantum Computing (CRQC) developments. While the large signature size of Falcon is acknowledged, suggestions have been made that this could be addressed by using smaller parameter sets or adopting variants like SPHINCS+ that, although losing NIST compatibility, offer advantages in certain contexts.

A significant point of discussion was the adaptability of different architectures to post-quantum signature schemes. For instances where managing state is feasible, XMSS signatures were recommended for their compactness, efficiency, and ease of implementation across various platforms. This approach not only facilitates quicker and simpler signature processes but also naturally discourages address reuse due to the unbalanced nature of XMSS, adding a layer of security and privacy. The dialogue included a reference to a technical resource discussing stateful post-quantum signatures with static backups, accessible at this link, which provides further insight into the practical aspects of implementing these advanced cryptographic solutions in real-world applications.