Zero-knowledge proofs, encoding Sudoku and Mario speedruns without semantic leak

We published our video on zero-knowledge proofs! Surprisingly, making this video took a lot of work. Zero-knowledge proofs for coloring are one of those algorithms that, in hindsight, seem beautifully simple and clean. But that’s just an illusion—there’s actually a lot going on behind the scenes. We struggled with deciding how in-depth to go and which applications to discuss. In the end, the video covers a bit of everything, and I hope different viewers will find something that sparks their curiosity. If that’s the case, you should definitely check out some slower, more in-depth sources; zero-knowledge proofs are realistically too difficult to understand them from 20 minutes of a video. For example, the following book on cryptography is a classic: https://www.wisdom.weizmann.ac.il/~oded/foc.html Here’s a list of topics that did not make it in the video. 1. How to reduce satisfiability to coloring? We pointed out that almost everything can be reduced to 3-coloring. This is closely c ... Read full article.