Post Quantum Signatures and Scaling Bitcoin

Brandon Black raises a significant point regarding the security of STARKs, particularly focusing on the FRI (Fast Reed-Solomon Interactive) commitment scheme, in the face of potential quantum computational threats. He notes that while STARKs are conjectured to be secure against quantum adversaries due to their reliance on hash functions as the primary primitive within an error-correcting code framework, there currently exists no formal security proof to support this claim. This absence of a formal argument or proof presents a notable gap in the existing literature and research around quantum-resistant cryptographic systems.

The concern extends to the broader implications for cryptographic practices, especially those integral to the Bitcoin signature model. In the evolving post-quantum (PQ) landscape, the demand for robust security arguments and proofs becomes even more critical. Black suggests that in anticipation of future changes to Bitcoin's signature model, or any critical security infrastructure threatened by quantum computing capabilities, a stronger security rationale should be developed. This perspective underscores the need for comprehensive research and development efforts aimed at validating and reinforcing the assumed quantum resistance of cryptographic schemes like STARKs, ensuring they can withstand the challenges posed by quantum computing advancements.