Falcon Post-Quantum Signature Scheme Proposal

Signature aggregation, as distinguished from batch verification, plays a pivotal role in the integration of Schnorr signatures with Bitcoin, primarily due to its reliance on a linear homomorphic algebraic structure. This characteristic is fundamental to enabling constructs like MuSig, which significantly enhances the efficiency and scalability of signature verifications by aggregating multiple signatures into a single one. However, such an algebraic structure is notably absent in the realm of post-quantum (PQ) signature schemes, whether they are standardized or belong to more exotic classifications.

In light of the challenges presented by the transition to post-quantum cryptography, Layer 2 (L2) Zero-Knowledge (ZK) rollups emerge as a potent solution for maintaining efficiency in signature verification processes. By facilitating the verification of numerous user signatures off-chain and subsequently proving the outcome through a single succinct proof on Layer 1 (L1), L2 ZK rollups effectively streamline the verification process in a manner reminiscent of signature aggregation. A specific example within this context is LaBRADOR, a lattice-based SNARK proposed as a viable option for Bitcoin-oriented ZK rollups to circumvent the limitations posed by the absence of native signature aggregation capabilities in PQ environments.

Explorations into Bitcoin-compatible ZK rollup solutions, such as Citrea, underscore the ongoing efforts to adapt to the constraints of post-quantum cryptography while preserving the efficiencies currently enjoyed with Schnorr-like signature schemes. This research trajectory acknowledges the substantial time investment required to identify and develop post-quantum signature schemes that offer comparable benefits to those provided by Schnorr signatures. Given the historical timeline observed from the development of RSA to the adoption of Schnorr signatures, it is anticipated that achieving a similar breakthrough for a post-quantum analogue could span several years of dedicated research and development. This outlook underscores the necessity of leveraging L2 ZK constructions as an interim strategy to bridge the gap between current cryptographic practices and the eventual realization of post-quantum signature technologies.