Quantum Advances, Hybrid Signatures and SNARKs to the Rescue with Dan Boneh

Dan Boneh discusses the implications of Google's recent quantum algorithm announcement and expresses concerns about the risks of hastily transitioning to post-quantum cryptography. He emphasizes the uncertainty surrounding the timeline for quantum computers, suggesting that while estimates range from 2035 to 2040, the 2040 mark is more realistic. Companies like Google and Cloudflare aim for a 2029 deadline for transitioning to post-quantum security, but Boneh warns that this aggressive timeline could lead to significant mistakes, particularly in the context of digital signatures.

Boneh advocates for a cautious approach, recommending that organizations wait for hardware security module (HSM) providers to support post-quantum signatures rather than compromising security by moving keys to less secure environments. He highlights the complexity of the transition process and the need for industries to identify and replace outdated encryption code. He argues that rushing the transition could pose greater risks than the threats posed by quantum computers themselves.

In discussing post-quantum systems, Boneh favors algebraic signatures over hash-based ones, citing their structural advantages and potential for innovation. He notes that algebraic systems, especially those based on lattice structures, offer features like adapter signatures and distributed key generation, which could enhance security. The conversation highlights two leading quantum computing architectures: superconducting qubits and neutral atoms. Superconducting qubits, used by companies like Google and IBM, require complex cooling systems and have local connectivity, limiting interactions to nearby qubits. In contrast, neutral atoms represent a newer approach that utilizes lasers and optics, allowing for better connectivity and flexibility in algorithms, although they are approximately 1000 times slower than superconducting qubits.

Challenges in building quantum computers primarily revolve around managing errors due to environmental interactions with atoms. Three main approaches to error reduction are discussed: improving the accuracy of physical qubits, employing quantum error correction techniques, and shortening computation durations to minimize errors. Recent achievements, such as the Willow experiment demonstrating successful quantum error correction, indicate significant progress in the field. The conversation emphasizes that longer computations lead to more accumulated errors, and simplifying algorithms can reduce computation length and the number of qubits needed for error correction.

The discussion shifts to the Google paper's zero-knowledge (ZK) proof, which demonstrates the algorithm's functionality without revealing its details. The interaction between classical and quantum computers is crucial, as classical systems program the optical apparatus for quantum gates. The proprietary nature of some discoveries in quantum computing raises concerns about transparency and potential advantages in quantum technology. The conversation also highlights the implications of timing in elliptic curve computations for Bitcoin, warning that vulnerabilities could arise if transactions are submitted to the mempool without post-quantum mechanisms in place.

Hybrid signatures, which combine ECDSA with lattice-based signatures, are introduced as a means to enhance security. This approach requires an attacker to compromise both signature types, ensuring that before quantum computers become prevalent, the security level remains robust. The discussion also covers the status of isogenes in post-quantum security, with new candidates like SKYSIGN and HAK mentioned, emphasizing the need for further cryptanalysis before deployment.

AI's impact on security is explored, particularly its ability to generate proofs for new cryptographic schemes and enhance formal methods. The role of AI in zero-knowledge applications is highlighted, with examples of AI tools being effective in bug detection and proof generation. The conversation delves into various applications of ZK, including the ability to prove compliance of source code while keeping it secret. The need for new cryptographic primitives, such as obfuscation and witness encryption, is emphasized, with practical applications in Bitcoin and Ethereum.

The conversation introduces universal witness encryption, which enables encryption to arbitrary polynomial time statements, and discusses the challenges of creating a witness encryption scheme that allows decryption only if a SNARK verifier accepts a certain proof. Dan shares his focus on cryptography for blockchains, particularly addressing cryptographic challenges in this space, including encrypted mempools that allow transactions to be submitted in encrypted form.

Researchers discuss the myriad open problems in blockchain technology, likening it to a child in a toy store. They note that new questions are emerging in areas previously considered settled, such as batch and threshold decryption. The idea of traceable threshold decryption is introduced, allowing for accountability if a secret key is exposed. The conversation concludes with a nod to ongoing research efforts, including a recent result by Goyal and Gauraswamy, and the potential for applying their techniques to improve SNARKs from other codes.