Security Now #1034: Introduction to Zero-Knowledge Proofs – Taking Down Quantum Factorization

Date: July 16, 2025
Hosts: Steve Gibson & Leo Laporte

Episode Overview

This lively episode delivers a two-part masterclass: first, a deep and highly entertaining takedown of so-called "quantum factorization breakthroughs"—with Steve enthusiastically debunking the hype—and then a thoughtful, accessible introduction to the concept and applications of Zero-Knowledge Proofs (ZKPs). Along the way, listener questions spark nuanced discussions on software code-signing, messaging app security, browser fingerprinting, and more. The whole show is punctuated with Steve’s dry wit and Leo’s curious skepticism, making advanced topics engaging for all listeners.

Key Discussion Points & Insights

1. Quantum Factorization—Much Ado About Nothing

• Takedown of Quantum Hype

  • Steve discusses a new paper by renowned cryptographer Peter Gutmann that sharply criticizes recent celebrated achievements in quantum computing's ability to factor large numbers.
  • Peter’s paper ("Replication of quantum factorization records with an 8 bit home computer, an abacus and a dog") lampoons the "quantum breakthroughs" as either misleading, trivial, or outright fraud.

• Major Arguments & Evidence

  • Most quantum "factorizations" use highly contrived, artificial numbers that are easy to solve by other means.
  • Actual hard problems, like real RSA factorization with randomly chosen primes, remain untouched.
  • Many so-called records simply verify known factors or use preprocessing that reduces the “quantum” portion to a trivial step, or swap the hard part for an easily solvable form.

• Memorable Quotes

  • "None of it is true. It has never worked. It's all... deliberately contrived tests." – Steve Gibson [03:37]
  • "A VIC 20 above an Abacus, an Abacus above a dog, and a dog above a quantum factorization physics experiment." – Steve Gibson, paraphrasing Gutmann [54:16]
  • "Not even to factor the six bit number 35..." – Steve Gibson [56:56]
  • "He just drives a stake through the heart of quantum computing by the time we're done." – Steve Gibson [29:01]

• Notable Laughter/Exasperation

  • Steve recounts that Gutmann “matched” all reported quantum feats with a VIC-20 computer, an abacus, or even by training his dog to bark, poking fun at the misplaced hype.
  • Leo: "So this is amazing. How did we get fooled by this?" [46:15]

• Key Timestamped Moments

  • [16:32] — Introduction of Gutmann's paper and credentials.
  • [28:58] — Explanation of “physics experiments” and the use of “force decks”/contrived test numbers.
  • [39:39] — Discussion of “stunt factorizations” (reverse-engineering problems to fit known answers).
  • [46:15–49:11] — The dog 'Scribble' factors small numbers (i.e., barks three times to factor 15 and 21).
  • [54:16] — Humorous ranking of computation power.

2. Security News & Listener Feedback

a. Notepad++ Code-Signing Controversy [61:18]

• Frequent updates to Notepad++ prompt the developer to suggest users install a self-signed root certificate to suppress antivirus warnings, which Steve strongly discourages.
• Steve’s Critique: Installing random root certificates undermines the entire trust system and can create terrible habits, even though the AV/code signing ecosystem is currently broken for small open source developers.
• Notable Quote: "Just about the last thing I want is for my own machines CA root stores to be filling up with random certificates from the authors of freeware that I wish to use." [76:45]

b. Messaging Apps: WhatsApp vs Signal

• Signal encrypts message storage on-device and encryption keys are stored in the protected keychain, protecting data if the phone is backed up and preventing easy exfiltration even by spyware.
• WhatsApp, prioritizing usability and portability, keeps messages decrypted for backups and transfers, causing security concerns.
• Listener’s Explanation: “Single has chosen privacy over portability…and stores the encryption key on the keychain. WhatsApp has chosen to keep the messages decrypted so that they can be recovered from backup…” – Chris (listener) [92:50]
• WhatsApp’s claim of server-side vulnerability mitigation prompts questions about end-to-end encryption integrity; Steve and listeners remain skeptical.

c. Browser Fingerprinting

• Steve walks through the EFF’s Cover Your Tracks tool (successor to Panopticlick), revealing that even with privacy add-ons, browser configurations are uniquely fingerprintable.
• "Our fingerprinting, tracking, today's tracking technology has become serious. It's become that serious that…even with uBlock Origin and Privacy Badger, my browser is still unique among a quarter-million tested." [122:19]
• Advice: The more “unique” your setup is (plugins, screen size, fonts), the more trackable you are; paradoxically, aggressive anti-tracking measures can make you more unique.
• [107:05–124:24] — Steve steps through each measuring parameter, demystifying browser fingerprinting with humor and detail.

d. Crypto ATMs and Regulatory Moves in New Zealand

• Listener notes New Zealand is moving to ban crypto ATMs to combat laundering and fraud, echoing global regulatory trends.

e. Other Feedback

• Zotification of proper code-signing for open source/freeware, Let's Encrypt now providing certificates for IPs, difficulties with AV vendors, and privacy/anonymity challenges on Linux vs Windows.

3. Main Topic: Introduction to Zero-Knowledge Proofs (ZKPs)

a. Motivation & Use Cases

• Modern privacy concerns—like age verification—can benefit from zero-knowledge proof concepts, where one party proves they know or can do something without revealing any actual information beyond that.
• Google’s new open-source ZKP-based age verification gets a brief mention as a real-world illustration.

Steve:

"The goal is to… verify someone's age is 18 while revealing absolutely nothing about them other than proving the assertion that they're 18. So it turns out there's a whole field of math…proving an assertion while revealing nothing." [06:01]

b. ZKP Characters & Definitions

• ZKP literature uses standard character names: Peggy (Prover), Victor (Verifier), alongside the classic Alice, Bob, Eve, Mallory, etc.
• Formal: "A zero knowledge proof is a protocol by which one party, the prover, can convince another party, the verifier, that some given statement is true without conveying to the verifier any information beyond the mere fact of that statement's truth." [135:46]

c. Physical ZKP Examples—Engaging Mini-Stories

i. The Where’s Wally (Waldo) Example [142:13]

• Peggy wants to prove she knows where Wally is hidden in a dense cartoon with zero knowledge transfer. She uses a second, larger opaque sheet with a “keyhole” to privately reveal only Wally—never his location—convincing Victor without revealing anything more.
• Key insight: Victor learns only that Peggy knows a solution, but nothing about it, nor can he prove it to another person.

ii. The Locked Boxes/Matching Purchases Example [146:24]

• Two competitors, each under NDA, want to know if they bought the same number of widgets without revealing how many. Using slotted, lockable boxes and keyed access, they achieve a yes/no answer with zero knowledge leakage about the actual numbers.

iii. The Ali Baba's Cave / Magic Door Statistical Example [146:24]

• Peggy claims to know a secret word that opens a magic door in a ring-shaped cave. Victor repeatedly tests Peggy by requesting she emerge from different exits unseen. Statistical accumulation of correct responses (by chance, 1 in 2, then 1 in 4, then 1 in 8, etc.) quickly makes “faking it” infeasible, reliably proving knowledge without revealing the word or enabling third-party verification.

d. ZKP Properties and Uses:

• Formal Requirements:

  • Completeness: If the statement's true, the verifier will be convinced by an honest prover.
  • Soundness: If the statement is false, a cheating prover can't convince an honest verifier except with negligible probability.
  • Zero Knowledge: The verifier learns nothing except the truth of the assertion.

• Applications: ZKPs are critical in authentication, privacy-preserving credentials, cryptocurrency, and may (with more infrastructure) underpin future age verification regimes.

• Steve:

  "The property of... soundness—if the assertion is false, it's not possible for a prover to fool the verifier into believing it's true…But it's the third property, zero knowledge, that the verifier is unable to learn anything other than the truth of the assertion. That's where the magic happens..." [168:52]

e. Audience Engagement

• Steve recommends involving children in the ZKP thought experiments for fun and learning, as these are intuitive in their physical form if you skip the heavy math.

Notable Quotes & Moments

• "Ignorance is not bliss." – Steve Gibson [03:13]
• "A VIC 20 above an Abacus, an Abacus above a dog, and a dog above a quantum factorization physics experiment." [54:16]
• "All this noise about how quantum computing is zipping right along and quantum factorization is BS, Steve explains." – Leo (Intro) [00:00]
• "This one's not a propeller-head episode… get your kids in for the discussion of zero knowledge proofs." – Steve Gibson [07:42]

Important Timestamps

• Quantum Factorization Takedown: [16:32]–[58:00]
• Browser Fingerprinting Demonstration: [107:05]–[124:24]
• Zero-Knowledge Proofs Segment: [133:06]–[170:42]
• Physical/Intuitive ZKP Examples: [142:13–168:49]

Summary

This episode is a must-listen for anyone interested in cryptography, computer security, or privacy technology. Steve Gibson brings clarity and critical thinking to the quantum computing “threat”—thoroughly debunking exaggerated claims that quantum factorization is on the verge of defeating today’s cryptography. He then brings the concept of Zero-Knowledge Proofs down to earth, masterfully explaining their theory and real-world potential through fun, intuitive examples.

For professionals, skeptics, and the “crypto-curious” alike, this episode is both an education and a delight.