Quantum Computing: What, When, Where, How
1Digest
This podcast explores the implications of quantum computing for cryptography, particularly for blockchains. Experts discuss the potential of quantum computers to break current encryption methods, emphasizing the need for a transition to post-quantum cryptography. The discussion clarifies misconceptions surrounding quantum supremacy and analyzes recent advancements from tech giants like Google and Microsoft. Timelines for the development of cryptographically relevant quantum computers are explored, along with the challenges of predicting them. The podcast delves into the specific risks and costs associated with prematurely adopting post-quantum cryptography, focusing on digital signatures, zero-knowledge proofs (ZKPs), and proof-of-work mechanisms. Different approaches to post-quantum cryptography, including lattice-based and hash-based systems, are compared, considering their performance and security trade-offs. The advantages and disadvantages of various ZKP approaches are analyzed, highlighting the potential of lattice-based ZKPs as a post-quantum solution. The podcast concludes with practical advice for developers, emphasizing the importance of a cautious and well-planned transition, avoiding hasty decisions driven by hype, and prioritizing a thorough cost-benefit analysis before migrating to post-quantum cryptography. The importance of understanding the difference between the privacy and security aspects of ZKPs in the context of post-quantum threats is also stressed.
Outlines
Introduction to Quantum Computing and its Cryptographic Implications & Fundamentals of Quantum Computing
The podcast introduces quantum computing and its potential to break current cryptographic systems, emphasizing the need for blockchain builders to prepare for a post-quantum world. Dan Bene explains quantum computing fundamentals, including superposition and amplitudes, and how quantum computers can perform faster computations relevant to cryptography.
Recent Quantum Computing News, Misconceptions, and Timelines for Transition
The discussion analyzes recent quantum computing news, clarifying misconceptions about quantum supremacy and topological qubits. It explores timelines for the development of cryptographically relevant quantum computers and NIST's plans to deprecate current cryptographic schemes.
Implications for Blockchains and Builders & Post-Quantum Cryptography and Zero-Knowledge Proofs
The podcast examines the implications of quantum computing for blockchains, analyzing the risks and costs of prematurely switching to post-quantum cryptography. It contrasts current elliptic curve-based cryptography with lattice-based cryptography as a post-quantum solution and explores the advantages and disadvantages of different ZKP approaches.
Lattice-Based ZKPs, Jolt, and Practical Considerations for Post-Quantum Migration
New research on lattice-based ZKPs is introduced as a potential alternative to hashing-based approaches for creating post-quantum secure systems like Jolt. The practical challenges of migrating to post-quantum cryptography are discussed, emphasizing the importance of a cost-benefit analysis and avoiding hasty transitions.
Advice for Builders: A Cautious Approach
The podcast concludes with advice for developers on approaching post-quantum cryptography, stressing careful planning and a balanced approach, avoiding decisions driven by hype, and understanding the difference between privacy and security properties of ZKPs.
Keywords
Quantum Computing
Computation leveraging quantum mechanics principles (superposition, entanglement) for potentially exponentially faster solutions to specific problems.
Post-Quantum Cryptography
Cryptographic algorithms secure against both classical and quantum computer attacks (lattice-based, code-based, hash-based).
Shor's Algorithm
Quantum algorithm efficiently solving integer factorization and discrete logarithm problems, threatening public-key cryptosystems.
Zero-Knowledge Proof (ZKP)
Cryptographic proof allowing one party to prove a statement's truth without revealing information beyond its truth (used in blockchains).
NIST Post-Quantum Cryptography Standardization
NIST's process of selecting and standardizing quantum-resistant cryptographic algorithms.
Lattice-Based Cryptography
Post-quantum cryptography based on the hardness of lattice problems; promising for security and potential efficiency.
Hashing-Based Cryptography
Post-quantum cryptography relying on collision resistance in cryptographic hash functions; offers security but may have performance limitations.
Elliptic Curve Cryptography (ECC)
Public-key cryptography based on elliptic curves; widely used but vulnerable to quantum attacks.
Quantum Supremacy
A milestone where a quantum computer solves a problem significantly faster than any classical computer (often contrived).
Q&A
What are the fundamental differences between classical and quantum computing, and why are cryptographers concerned about the latter?
Quantum computing uses quantum mechanics (superposition, entanglement) for potentially exponentially faster computation for specific problems, threatening the security of many widely used cryptographic systems.
What are the timelines for the development of a cryptographically relevant quantum computer, and what should blockchain builders be doing to prepare?
Timelines are uncertain (15-30+ years). Blockchain builders should research and prepare for a transition to post-quantum cryptography, focusing on digital signatures and prioritizing software update systems.
What are the main misconceptions surrounding quantum computing advancements, particularly regarding quantum supremacy?
Quantum supremacy demonstrations often involve contrived tasks, not necessarily implying practical applications or immediate threats to existing cryptographic systems.
How do different approaches to post-quantum cryptography compare in terms of performance and security?
Lattice-based cryptography offers strong security but often larger key sizes and signatures. Hash-based cryptography provides strong security but can have even larger signatures. The choice depends on the application and the trade-off between security and performance.
What are the main differences between elliptic curve-based and lattice-based cryptography in the context of zero-knowledge proofs?
Elliptic curve-based ZKPs currently offer shorter proofs and more efficient folding schemes. Lattice-based ZKPs are a promising post-quantum alternative, but their efficiency is still under development.
What are the key risks associated with rapidly migrating to post-quantum cryptography?
Rushing the transition can introduce new bugs and complexities, especially when integrating with existing systems. A careful cost-benefit analysis is crucial.
What advice would you give to developers considering a transition to post-quantum cryptography?
Prepare, but don't panic. Carefully weigh the costs and benefits of waiting, and avoid hasty decisions driven by hype. A measured approach is key.
Show Notes
with @danboneh @succinctJT @smc90
This episode is all about quantum computing -- what it is, how it works, what's hype vs. reality, and how to prepare for it/ what builders should do.
Specifically, we cover:
- What quantum computing is and isn't, and what people are really talking about when they worry about a quantum computer that can break cryptographic systems that are not secure against quantum attacks.
- When is it happening/ what are the "timelines" for quantum computing becoming a reality -- or rather, when could we have a cryptographically relevant quantum computer -- how many years away are we? and when are the U.S. government's deadlines/ NIST standards for post-quantum cryptography?
- How will different types of cryptography be affected, or not? What are different approaches and tradeoffs?
- Where does quantum computing and post-quantum crypto apply to blockchains -- which by and large rely on signatures, not encryption, so may be more quantum-resistant in many ways (and not in others)...
As always, we tease apart the signal vs. the noise in recent "science-by-press release" corporate quantum-computing milestone announcements. We also help answer questions on when do builders need to plan their switch to a post-quantum crypto world, what pitfalls to avoid there (hint: bugs! software upgrades!). Finally, we briefly cover different approaches to post-quantum crypto; and also dig deeper on zero-knowledge/ succinct-proof systems and how they relate to post-quantum crypto.
Our expert guests, in conversation with Sonal Chokshi, are:
- Dan Boneh, Stanford University professor and applied cryptography expert and pioneer; also Senior Research Advisor to a16z crypto;
- Justin Thaler, research partner at a16z, professor at Georgetown, and longtime expert and pioneer in interactive and ZK proof systems.
SEE ALSO: Post-quantum blockchains by Valeria Nikolaenko
more resources + papers on topics mentioned:
- A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup [see also]
- Proofs, Arguments, and Zero-Knowledge by Justin Thaler
- LatticeFold+: Faster, Simpler, Shorter Lattice-Based Folding for Succinct Proof Systems by Dan Boneh and Binyi Chen
- Neo: Lattice-based folding scheme for CCS over small fields and pay-per-bit commitments by Wilson Nguyen and Srinath Setty
- "Q-Day Clock" from Project Eleven -- public dashboard to visually track timeline for quantum computing to reach cryptographically relevant capabilities and break widely used encryption algorithms
- on hard forks for quantum emergencies
- Quantum analysis of AES, Kyungbae Jang, Anubhab Baksi, Hyunji Kim, Gyeongju Song, Hwajeong Seo, Anupam Chattopadhyay
- The Google Willow Thing by Scott Aaronson
- FAQs on Microsoft’s topological qubit thing by Scott Aaronson
- Microsoft’s claim of a topological qubit faces tough questions, American Physical Society
As a reminder, none of this is investment, business, legal, or tax advice; please see a16z.com/disclosures for more important information including a link to our investments.
Hosted by Simplecast, an AdsWizz company. See pcm.adswizz.com for information about our collection and use of personal data for advertising.
Table of contents
United States
