[swid]

He’s talking about zero knowledge proofs - it’s a neat use of graph coloring where you send an encrypted proof that a graph can be colored with three colors and no neighbors with the same color. The verifier makes a challenge to prove two nodes don’t have the same color, and the prover provides a key to decrypted just those two nodes. This process is repeated a number of times (with new colored graphs) until the verifier approaches certainty that the prover will always be able to show all nodes have neighbors with different colors.

This coloring problem is NP complete and somehow the thing the prover is proving is encoded in the graph structure. At the end of the day, the only thing the verifier is sure of is that the prover can make the three colored graph, 1 bit that corresponds to the thing the verifier wants to know (eg - does the prover have a token that can show they are over 18).

[evgen]

For simple yes/no questions ("Is over 18?", "Is US resident?") then you should look back to David Chaum's blind signatures and the work that came out of that back in the 90s. The math is super-simple to understand and there are a ton of even easier metaphors with envelopes and carbon paper that you can use to explain to your grandmother. Once you get someone to grok blind signatures it is easy to lead them to zero-knowledge proofs.