Zero Knowledge Proof (with Avi Wigderson) - Numberphile

Featuring Avi Wigderson from the Institute for Advanced Study, Princeton.
More info and links below ↓↓↓

NUMBERPHILE


Video by Brady Haran
and Pete McPartlan

[EnigmacTheFirst]

Finished watching and I still have zero knowledge

[deidara_]

This video feels like a zero-knowledge proof of zero-knowledge proofs.

[ResandOuies]

would be nice to see an example of translating of statement and proof to a map with coloring

[Tom-efmz]

Even for Numberphile, this video is just absolutely insane.

[toniokettner]

the guy proving the existence of zero knowledge proofs was like: lemme prove that i have a proof that you can prove that you have a proof you don't want to tell

[ReaperUnreal]

Somehow this 30 minute video gave me better understanding about zero-knowledge proofs than 2 hour-long lectures on the subject I had a few years ago.

[jonaszurba]

please do a follow up on how to convert logical statements into a 3 colourable map

[steveau]

Professor Wigderson is one of the nicest, kindest people - he once took an email from me - a novice - and was gracious and generous with his time.

[AlexTaradov]

I agree with others, we need a followup video with a practical example. This is interesting, but too abstract.

[kristiandamholt]

18:20 "Any formal mathematical statement can be converted into a map. And, I should stress, this conversion is efficient. There is a SIMPLE ALGORITHM KNOWN TO ALL..."
18:55 "Very simple, efficient, known to everybody"
Just had to laugh at these.

[martimlobao]

It would be extremely helpful to see how to convert even a trivial statement into a map, as well as how to convert a 3-coloring of that map into a proof of that statement. Or at least a link to some paper where that process is explained, searching online returns no clear explanation.

[nbjornestol]

Congratulations to Avi for winning the Abel Prize!

[wizard]

Long story short: it's not a proof. It's evidence that a person *probably* knows a proof. NP-complete problems have a forward direction which is easy, and a reverse direction which is very difficult. The zero-knowledge "proof" is showing that you can do the reverse operation as many times as you like. Statistically you could be guessing the answer by chance but you repeatedly do this to increase confidence that you know how to do the reverse procedure, and therefore have a proof.

[vincentpelletier]

I have been staring at this video for 30 minutes, and I have an urge to not erase anything for some reason.

[GregHillPoet]

Proof of the four-color map theorem can be zero-knowledge verified using a three-color map.

[asenna]

I don't think I've ever understood any concept less in my life, but I still really enjoyed listening to Avi, and it's always interesting to see these complex mathematical ideas, even if they make my head hurt.

[ericb]

To summarize:
1) you can show a map can be 3 colouring without revealing information about the colouring
2) you can transform any statement into a map
3) if that statement is true, you can do a 3-colouring on that resulting map
C) you can do zero knowledge proofs for any statement

[_abdul]

I Once accidentally Proved The Collatz Conjecture in my dream. Now I know why I don't know anything about it.

[jonathanlevy]

Plot twist, I didn't know what an envelope is so you teach me something

[antonmiserez]

''Fermat's Last Theorem follows as a corollary" is the perfect answer to "[...]a truly marvelous proof of this, which this margin is too narrow to contain." Fermat would be proud