Original upload date: Sun, 16 Mar 2025 01:00:00 GMT
Archive date: Fri, 21 Mar 2025 10:15:21 GMT
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 cryptographer
...
s 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
