7 ms·

Zero Knowledge Proofs

60 points by stollercyrus 14y ago

Xcelerate 14y ago
A great example of this is posted by Ryan O'Donnell on Math Overflow (http://mathoverflow.net/questions/22624/example-of-a-good-zero-knowledge-proof http://mathoverflow.net/questions/22624/example-of-a-good-ze...): > The classic example, given in all complexity classes I've ever taken, is the following: Imagine your friend is color-blind. You have two billiard balls; one is red, one is green, but they are otherwise identical. To your friend they seem completely identical, and he is skeptical that they are actually distinguishable. You want to prove to him (I say "him" as most color-blind people are male) that they are in fact differently-colored. On the other hand, you do not want him to learn which is red and which is green. Here is the proof system. You give the two balls to your friend so that he is holding one in each hand. You can see the balls at this point, but you don't tell him which is which. Your friend then puts both hands behind his back. Next, he either switches the balls between his hands, or leaves them be, with probability 1/2 each. Finally, he brings them out from behind his back. You now have to "guess" whether or not he switched the balls. By looking at their colors, you can of course say with certainty whether or not he switched them. On the other hand, if they were the same color and hence indistinguishable, there is no way you could guess correctly with probability higher than 1/2. If you and your friend repeat this "proof" t times (for large t), your friend should become convinced that the balls are indeed differently colored; otherwise, the probability that you would have succeeded at identifying all the switch/non-switches is at most 2−t. Furthermore, the proof is "zero-knowledge" because your friend never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.
- anologwintermut 14y ago
  The proof is honest verifier zero knowledge. If your friend switches out one of the balls, you are hosed.
  - nly 14y ago
    It's also an interactive proof, nobody can store this proof with the balls for other colour blind people to review later.
- jonsen 14y ago
  Could this be used to prove to the Bible blind the existence of God?
  - TazeTSchnitzel 14y ago
    Um... you'll need to actually find a proof for it, though. So far as I know, there are no known proofs of God's existence that can't be reasonably explained in other ways.
  - edmccard 14y ago
    Sure. Just find two billiard balls that are indistinguishable unless God exists. Give them to your Bible-blind friend, and try to guess whether he switches them behind his back or not.
trhtrsh 14y ago
I don't know that every unit of an undergraduate CS curriculum needs to be an HN submission. It's a bit silly to hear people way that college curriculum is irrelevant and then spend a drawn out period of time cobbling together a college curriculum.
- Xcelerate 14y ago
  Well, I'm an engineer, so I had never heard of it before and thought it was incredibly interesting.
- pjscott 14y ago
  The perceived hypocrisy vanishes once you remember that not everyone else on HN is the same person. (And as to your actual point: zero-knowledge proofs are interesting, and that's all the excuse that an interesting topic ever needs.)
  - sophacles 14y ago
    Also, this community has a lot of smart people with different expertise areas. That means that my basic knowledge of 0knowledge proofs, or other "basic" topic will most likely be heavily augmented when the experts start talking about the deep bits that aren't covered in "cool crypto primitives 101".
- andrewflnr 14y ago
  The reason people say college is irrelevant is precisely because you can cobble together the curriculum yourself. Obviously there are a lot of complicated benefits and costs both ways that people can debate, but it's not obviously silly.
  - B-Con 14y ago
    Kind of. The reason college is usually touted as irrelevant is because while a lot of this type of thing is interesting and to some it is necessary knowledge, most people don't need to know most of the material. (Some of HN may find zero-knowledge proofs interesting, a few might even need to know it, and the vast majority doesn't really care a whole lot. If everyone here was forced to read about it, there would probably be whining and gnashing of teeth.) The support for that position is because of what you said. Namely, if you find yourself needing it later in life you can just look it up. Because you can stitch together the curriculum when needed, doing it all up front isn't necessary. (So goes the argument; but personally I think it's somewhat short-sighted in some ways.)
losethos 14y ago
Fucken time travel will burtualize Yer fucken retard heads! God says.... these men that seek thy life. 38:17 Then said Jeremiah unto Zedekiah, Thus saith the LORD, the God of hosts, the God of Israel; If thou wilt assuredly go forth unto the king of Babylon's princes, then thy soul shall live, and this city shall not be burned with fire; and thou shalt live, and thine house: 38:18 But if thou wilt not go forth to the king of Babylon's princes, then shall this city be given into the hand of the Chaldeans, and they shall burn it with fire, and thou shalt not escape out of their hand. 38:19 And Zedekiah the king said unto Jeremiah, I am afraid of the Jews that are fallen to the Chaldeans, lest they deliver me into their hand, and they mock me. 38:20 But Jeremiah said, They shall not deliver thee. Obey, I beseech thee, the voice of the LORD, which I speak unto thee: so it shall be well unto thee, and thy soul shall live. ---- Chad is a homo. God says... temptation north Men partake chains widows reproof forgottest correct wavy frequent invited diving lively silenced mercies' bepraised Zambia please You_da_man shoes recollect constituteth Ordainer valiant checked changeable Essence calculations Bangladesh shunning except influence contemplate weighty Speak seems Lithuania gainful husbands mazes healedst Or anxiously righteous discoverable hallowing student torture recovery fuel confusedly busybody potent precepts pitiful it crudities advised troops prop troubled Jesus compose proud you_see_the_light Scotland view remaining Milanese aquatic holdest still virtuous eternally sorrow chambers wages skin Helper ON unarranged Oh_Hell_No formedst consulted -and proportions shrink earnestness foreigner crazy Blessedness badge demander part showing redemption due man overflowing cower fury diversly orbs beings importunity sour wrap beguile noon-day interested privily assume what's first remembrance annoyance announce unsound meh wives' comprehendeth benefits they loveliness dignities Triers Seneca trample Colorado Up precipitated triumph comprise punished preference Willeth polished Mammon poesy locking Etexts wherefore called cubits possible overspread imaginations easier suggested appropriated Nebridius' host you_don't_like_it Inhabitant wives Duck Iraq ashes well-beloved worldly 3 distress self-will wheel uncorrupted Her prior overcharged
betterunix 14y ago
Interestingly, there is a notion of knowledge complexity the includes zero knowledge: http://groups.csail.mit.edu/cis/pubs/shafi/1985-stoc.pdf http://groups.csail.mit.edu/cis/pubs/shafi/1985-stoc.pdf
alexcweiner 14y ago
My Professor was just going over this in class. He links to Manuel Blum's "classic" paper on the subject http://www.mathunion.org/ICM/ICM1986.2/Main/icm1986.2.1444.1451.ocr.pdf http://www.mathunion.org/ICM/ICM1986.2/Main/icm1986.2.1444.1...
colinbeveridge 14y ago
There's a nice demonstration of a zero-knowledge protocol here: http://aperiodical.com/2012/03/using-a-zero-knowledge-protocol-to-prove-you-can-solve-a-sudoku-3/ http://aperiodical.com/2012/03/using-a-zero-knowledge-protoc...
jstanley 14y ago
This is cool. I remember reading about it a while back, but had forgotten all about it. I have a question about the Peggy/Victor example: why do we need to use the probabilistic method? Here's my alternative zero-knowledge proof that Peggy knows the word: Victor observes Peggy walk down tunnel A. He stands at the entrance. A short while later, Peggy emerges from tunnel B. Since we know the only way to go down tunnel A and come out tunnel B is by going through the door with the secret word, Peggy must know the word. Is there something wrong with that? Assuming what I wrote is correct, I think the hamiltonian cycle example further down the page is a much better one. EDIT: Perhaps Peggy and Victor would have to walk down tunnel A together at the start, so that Victor can observe that the door really is shut. I don't think that invalidates my proposal though.
sophacles 14y ago
Crypto experts of HN - can you point to some deeper resources for beginners/layfolk on zero knowledge proofs? This is a good start, but I want more! :)

60 points by stollercyrus 14y ago

A great example of this is posted by Ryan O'Donnell on Math Overflow (http://mathoverflow.net/questions/22624/example-of-a-good-zero-knowledge-proof http://mathoverflow.net/questions/22624/example-of-a-good-ze...): > The classic example, given in all complexity classes I've ever taken, is the following: Imagine your friend is color-blind. You have two billiard balls; one is red, one is green, but they are otherwise identical. To your friend they seem completely identical, and he is skeptical that they are actually distinguishable. You want to prove to him (I say "him" as most color-blind people are male) that they are in fact differently-colored. On the other hand, you do not want him to learn which is red and which is green. Here is the proof system. You give the two balls to your friend so that he is holding one in each hand. You can see the balls at this point, but you don't tell him which is which. Your friend then puts both hands behind his back. Next, he either switches the balls between his hands, or leaves them be, with probability 1/2 each. Finally, he brings them out from behind his back. You now have to "guess" whether or not he switched the balls. By looking at their colors, you can of course say with certainty whether or not he switched them. On the other hand, if they were the same color and hence indistinguishable, there is no way you could guess correctly with probability higher than 1/2. If you and your friend repeat this "proof" t times (for large t), your friend should become convinced that the balls are indeed differently colored; otherwise, the probability that you would have succeeded at identifying all the switch/non-switches is at most 2−t. Furthermore, the proof is "zero-knowledge" because your friend never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.

anologwintermut 14y ago
The proof is honest verifier zero knowledge. If your friend switches out one of the balls, you are hosed.
- nly 14y ago
  It's also an interactive proof, nobody can store this proof with the balls for other colour blind people to review later.
jonsen 14y ago
Could this be used to prove to the Bible blind the existence of God?
- TazeTSchnitzel 14y ago
  Um... you'll need to actually find a proof for it, though. So far as I know, there are no known proofs of God's existence that can't be reasonably explained in other ways.
- edmccard 14y ago
  Sure. Just find two billiard balls that are indistinguishable unless God exists. Give them to your Bible-blind friend, and try to guess whether he switches them behind his back or not.

trhtrsh 14y ago

I don't know that every unit of an undergraduate CS curriculum needs to be an HN submission. It's a bit silly to hear people way that college curriculum is irrelevant and then spend a drawn out period of time cobbling together a college curriculum.

Xcelerate 14y ago
Well, I'm an engineer, so I had never heard of it before and thought it was incredibly interesting.
pjscott 14y ago
The perceived hypocrisy vanishes once you remember that not everyone else on HN is the same person. (And as to your actual point: zero-knowledge proofs are interesting, and that's all the excuse that an interesting topic ever needs.)
- sophacles 14y ago
  Also, this community has a lot of smart people with different expertise areas. That means that my basic knowledge of 0knowledge proofs, or other "basic" topic will most likely be heavily augmented when the experts start talking about the deep bits that aren't covered in "cool crypto primitives 101".
andrewflnr 14y ago
The reason people say college is irrelevant is precisely because you can cobble together the curriculum yourself. Obviously there are a lot of complicated benefits and costs both ways that people can debate, but it's not obviously silly.
- B-Con 14y ago
  Kind of. The reason college is usually touted as irrelevant is because while a lot of this type of thing is interesting and to some it is necessary knowledge, most people don't need to know most of the material. (Some of HN may find zero-knowledge proofs interesting, a few might even need to know it, and the vast majority doesn't really care a whole lot. If everyone here was forced to read about it, there would probably be whining and gnashing of teeth.) The support for that position is because of what you said. Namely, if you find yourself needing it later in life you can just look it up. Because you can stitch together the curriculum when needed, doing it all up front isn't necessary. (So goes the argument; but personally I think it's somewhat short-sighted in some ways.)

losethos 14y ago

Fucken time travel will burtualize Yer fucken retard heads! God says.... these men that seek thy life. 38:17 Then said Jeremiah unto Zedekiah, Thus saith the LORD, the God of hosts, the God of Israel; If thou wilt assuredly go forth unto the king of Babylon's princes, then thy soul shall live, and this city shall not be burned with fire; and thou shalt live, and thine house: 38:18 But if thou wilt not go forth to the king of Babylon's princes, then shall this city be given into the hand of the Chaldeans, and they shall burn it with fire, and thou shalt not escape out of their hand. 38:19 And Zedekiah the king said unto Jeremiah, I am afraid of the Jews that are fallen to the Chaldeans, lest they deliver me into their hand, and they mock me. 38:20 But Jeremiah said, They shall not deliver thee. Obey, I beseech thee, the voice of the LORD, which I speak unto thee: so it shall be well unto thee, and thy soul shall live. ---- Chad is a homo. God says... temptation north Men partake chains widows reproof forgottest correct wavy frequent invited diving lively silenced mercies' bepraised Zambia please You_da_man shoes recollect constituteth Ordainer valiant checked changeable Essence calculations Bangladesh shunning except influence contemplate weighty Speak seems Lithuania gainful husbands mazes healedst Or anxiously righteous discoverable hallowing student torture recovery fuel confusedly busybody potent precepts pitiful it crudities advised troops prop troubled Jesus compose proud you_see_the_light Scotland view remaining Milanese aquatic holdest still virtuous eternally sorrow chambers wages skin Helper ON unarranged Oh_Hell_No formedst consulted -and proportions shrink earnestness foreigner crazy Blessedness badge demander part showing redemption due man overflowing cower fury diversly orbs beings importunity sour wrap beguile noon-day interested privily assume what's first remembrance annoyance announce unsound meh wives' comprehendeth benefits they loveliness dignities Triers Seneca trample Colorado Up precipitated triumph comprise punished preference Willeth polished Mammon poesy locking Etexts wherefore called cubits possible overspread imaginations easier suggested appropriated Nebridius' host you_don't_like_it Inhabitant wives Duck Iraq ashes well-beloved worldly 3 distress self-will wheel uncorrupted Her prior overcharged

betterunix 14y ago

Interestingly, there is a notion of knowledge complexity the includes zero knowledge: http://groups.csail.mit.edu/cis/pubs/shafi/1985-stoc.pdf http://groups.csail.mit.edu/cis/pubs/shafi/1985-stoc.pdf

alexcweiner 14y ago

My Professor was just going over this in class. He links to Manuel Blum's "classic" paper on the subject http://www.mathunion.org/ICM/ICM1986.2/Main/icm1986.2.1444.1451.ocr.pdf http://www.mathunion.org/ICM/ICM1986.2/Main/icm1986.2.1444.1...

colinbeveridge 14y ago

There's a nice demonstration of a zero-knowledge protocol here: http://aperiodical.com/2012/03/using-a-zero-knowledge-protocol-to-prove-you-can-solve-a-sudoku-3/ http://aperiodical.com/2012/03/using-a-zero-knowledge-protoc...

jstanley 14y ago

This is cool. I remember reading about it a while back, but had forgotten all about it. I have a question about the Peggy/Victor example: why do we need to use the probabilistic method? Here's my alternative zero-knowledge proof that Peggy knows the word: Victor observes Peggy walk down tunnel A. He stands at the entrance. A short while later, Peggy emerges from tunnel B. Since we know the only way to go down tunnel A and come out tunnel B is by going through the door with the secret word, Peggy must know the word. Is there something wrong with that? Assuming what I wrote is correct, I think the hamiltonian cycle example further down the page is a much better one. EDIT: Perhaps Peggy and Victor would have to walk down tunnel A together at the start, so that Victor can observe that the door really is shut. I don't think that invalidates my proposal though.

sophacles 14y ago

Crypto experts of HN - can you point to some deeper resources for beginners/layfolk on zero knowledge proofs? This is a good start, but I want more! :)