I can prove I’ve solved this Sudoku without revealing it

Video Description

Support us on Patreon: http://patreon.com/polylog I can convince you that I’ve solved a sudoku without giving you any information about my solution. We discuss how to do this using what cryptographers call a zero-knowledge proof, and how the same tricks can be used for almost any other problem you can think of. Blog post: https://vasekrozhon.wordpress.com/2025/03/17/zero-knowledge-proofs/ Code for the animations: https://github.com/polylog-cs/zero-knowledge-proofs/ Richard Hladík: Script editor, video editor, animator. Site: https://rihl.uralyx.cz/ Tomáš Sláma: Script editor, video editor, animator. Channel: https://www.youtube.com/@YTomS Václav Rozhoň: Writer, animator, the verifier. Blog: https://vasekrozhon.wordpress.com/ Václav Volhejn: Narrator, animator, script editor, the prover. Channel: https://www.youtube.com/@vvolhejn Thank you to our beta testers: Matěj, Honza, Filip. Thank you to Gabor Hollbeck for helping with the video equipment. Animations: Motion Canvas, a TypeScript library https://motioncanvas.io/ Color palette: Solarized https://ethanschoonover.com/solarized/ Music: Astrisx, Cases to Rest, Thannoid, and ZigZag Heart by Blue Dot Sessions Mario Speedrun: https://www.youtube.com/watch?v=LmgguleEH3k 0:00 Intro 0:50 Interactive proofs 2:28 Graph coloring 3:22 A simple protocol 6:31 Building the full protocol 10:24 Commitment schemes 12:37 Reducing sudoku to coloring 14:28 General reduction 17:04 Discussion 19:09 Outro