Zero-Knowledge Proofs and Putting

[Shindig]

One of the classes I'm teaching this semester is a math course for freshmen, and the lecture tomorrow introduces Zero-Knowledge proofs. It's a pretty simple concept: how you can convince someone you know something without giving them any information about it. For example, there's a way to convince someone you have solved a Sudoku puzzle without giving them any information that would help them solve it (thus spoiling it for them), but with a very (very) small chance that you were lucky and fooled them into thinking you'd solved it. So this naturally got me thinking about putting and the reading parts therein -- speed, line, break, etc. During a round of golf played under the rules, I can't ask a fellow competitor to read a putt for me and tell me how it breaks. But I was wondering if something similar exists in golf: is there a way my fellow competitor could convince me before I attempt it that he or she knows how to correctly play this putt without conveying any information that would aid me in the shot (and thus cause problems for us, rules-wise)? Obviously, we'd never implement such a protocol, especially on any golf course where we weren't the only two people playing (pace of play is important -- the Sudoku protocol described above takes quite some time if you ever implement it). Just an idle theoretical wondering. Hence why it's in the Geek Zone (which I think is the right place for this)... Alternate conversation topic for this thread: do other people end up with thoughts like this? Not necessarily Zero-Knowledge Proof specific.

[turtleback]

One of the classes I'm teaching this semester is a math course for freshmen, and the lecture tomorrow introduces Zero-Knowledge proofs. It's a pretty simple concept: how you can convince someone you know something without giving them any information about it. For example, there's a way to convince someone you have solved a Sudoku puzzle without giving them any information that would help them solve it (thus spoiling it for them), but with a very (very) small chance that you were lucky and fooled them into thinking you'd solved it.

So this naturally got me thinking about putting and the reading parts therein -- speed, line, break, etc. During a round of golf played under the rules, I can't ask a fellow competitor to read a putt for me and tell me how it breaks. But I was wondering if something similar exists in golf: is there a way my fellow competitor could convince me before I attempt it that he or she knows how to correctly play this putt without conveying any information that would aid me in the shot (and thus cause problems for us, rules-wise)?

Obviously, we'd never implement such a protocol, especially on any golf course where we weren't the only two people playing (pace of play is important -- the Sudoku protocol described above takes quite some time if you ever implement it). Just an idle theoretical wondering. Hence why it's in the Geek Zone (which I think is the right place for this)...

Alternate conversation topic for this thread: do other people end up with thoughts like this? Not necessarily Zero-Knowledge Proof specific.

I'm having a bit of trouble getting my head wrapped around this.  Could you give us a non-golf example of a zero knowledge proof?  Or point to one already out there on some site?

[iacas]

I'm having a bit of trouble getting my head wrapped around this.  Could you give us a non-golf example of a zero knowledge proof?  Or point to one already out there on some site?

I second this.

[billchao]

Now that the smart people have chimed in, I don't feel as bad admitting that I have absolutely no idea what you're talking about, @Shindig . :-) I'm pretty good at Sudoku, BTW, and I have no idea how I would go about telling someone how I solved a certain puzzle without revealing anything about it. It would all just and up being general Sudoku advice and techniques that probably wouldn't help them very much if that were stuck in the first place.

[Shindig]

I'm having a bit of trouble getting my head wrapped around this.  Could you give us a non-golf example of a zero knowledge proof?  Or point to one already out there on some site?

Sure. The classic example is a cave with two entrances/exits, but a locked door in the middle. It requires saying a password, but is far enough into the cave that you can't hear it from the outside when spoken. It's the only thing joining the two parts of the caves. To prove to you that I know the password, I can have you wait outside while I walk in one entrance and out the other. You didn't get to hear me say the password, but you know that I know it (otherwise, I couldn't have exited the other door to the cave). The Sudoku example is decently explained here: http://blog.computationalcomplexity.org/2006/08/zero-knowledge-sudoku.html , but the notation is a little weird. I'll try to translate (although re-reading this after finishing, I think mine might be too close to that link. I certainly wouldn't accept what I typed out here as a fairly described homework solution compared to that link)... the goal of the translation, at least, was to try to write it in a less math fashion. You've solved a Sudoku, I want to know that the solution exists without having it spoiled. So you take your solution to the other room, take a blank 9x9 grid, and prepare to copy it over. But first, you randomly permute the numbers 1..9. I don't know what permutation you chose. Let's say the third number in your random permutation is '7'. So you replace each '3' in the original Sudoku with a '7', and so on. Someone viewing the full solution would be able to see that it looks just like any solved Sudoku, although with the numbers switched. But if I saw it, I'd be able to infer the random permutation: I'd look at the "givens" in the Sudoku and be able to figure out many (if not all) of what the substitution is. Then I could see where those numbers appear in blank spaces I hadn't solved yet. I'd be able to get information about the solution, so it wouldn't be a Zero-Knowledge Proof. So instead, you walk in with your solved copy (with the numbers substituted) and a sharpie. Once you're back, but before I can see what you wrote, I'm going to make one of 28 pronouncements. At this point, you can't change your Sudoku permuted solution, except to black out squares with your sharpie. My pronouncement choices: * Show me row i (for some i between 1 and 9) * Show me column j (for some j between 1 and 9) * Show me box k (for some k between 1 and 9) * Show me the givens. You black out everything with the sharpie except what I called for. I can confirm that everything still showing complies -- either the row/column/box fits the rules (every # 1-9) or the givens match up (if two 3s were given, I can confirm they're the same number). If you really solved the Sudoku, you pass this test. If you lied, you fail this test 1/28 of the time at least (assuming I pick the test randomly). We can repeat this, new permutation and everything, and if you keep passing, I can calculate the probability you lied but, through luck, got an answer through (27/28 to the power of # iterations). After a while, I'm convinced to some threshold. ... so that's what I'm wondering if something like it exists for the putting green. Not as exciting as the Monty Hall problem a few months ago (which I also covered with my students, although that inclusion was in the curriculum long before it came up on TST), but it's the sort of thing that crosses my mind. By the way, @billchao I don't necessarily suggest using this to convince someone (beyond one or two rounds of it for the entertainment value) that you've solved a Sudoku.

[iacas]

But I was wondering if something similar exists in golf: is there a way my fellow competitor could convince me before I attempt it that he or she knows how to correctly play this putt without conveying any information that would aid me in the shot (and thus cause problems for us, rules-wise)?

He could tell you he took an AimPoint class.

J/K… but I still am not sure I see what the point is. If it's a mental exercise, then okay, I get that. But… if it's more, to what end? Why would someone else care about your putt? Unless the guy had laser mapped the green and taken a recent sampling of the green speed, he can't be SUPER sure of the read if you define "sure" as within half an inch for any putt outside of about five feet.

[Shindig]

It was a thought that popped into my head yesterday and I wondered if other people end up with similar thoughts. Just a silly thing, where I was thinking about this and golf's rules about advice and information. This might be one of the most absurd things I've posted on the internet in recent memory...

[Abu3baid]

It was a thought that popped into my head yesterday and I wondered if other people end up with similar thoughts. Just a silly thing, where I was thinking about this and golf's rules about advice and information. This might be one of the most absurd things I've posted on the internet in recent memory...

Maybe true, but I learned about zero-knowledge proofs.. I will have to ask my dad about it.

[turtleback]

Sure. The classic example is a cave with two entrances/exits, but a locked door in the middle. It requires saying a password, but is far enough into the cave that you can't hear it from the outside when spoken. It's the only thing joining the two parts of the caves. To prove to you that I know the password, I can have you wait outside while I walk in one entrance and out the other. You didn't get to hear me say the password, but you know that I know it (otherwise, I couldn't have exited the other door to the cave).

The Sudoku example is decently explained here: http://blog.computationalcomplexity.org/2006/08/zero-knowledge-sudoku.html , but the notation is a little weird. I'll try to translate (although re-reading this after finishing, I think mine might be too close to that link. I certainly wouldn't accept what I typed out here as a fairly described homework solution compared to that link)... the goal of the translation, at least, was to try to write it in a less math fashion.

You've solved a Sudoku, I want to know that the solution exists without having it spoiled. So you take your solution to the other room, take a blank 9x9 grid, and prepare to copy it over. But first, you randomly permute the numbers 1..9. I don't know what permutation you chose. Let's say the third number in your random permutation is '7'. So you replace each '3' in the original Sudoku with a '7', and so on. Someone viewing the full solution would be able to see that it looks just like any solved Sudoku, although with the numbers switched.

But if I saw it, I'd be able to infer the random permutation: I'd look at the "givens" in the Sudoku and be able to figure out many (if not all) of what the substitution is. Then I could see where those numbers appear in blank spaces I hadn't solved yet. I'd be able to get information about the solution, so it wouldn't be a Zero-Knowledge Proof. So instead, you walk in with your solved copy (with the numbers substituted) and a sharpie. Once you're back, but before I can see what you wrote, I'm going to make one of 28 pronouncements. At this point, you can't change your Sudoku permuted solution, except to black out squares with your sharpie. My pronouncement choices:

* Show me row i (for some i between 1 and 9)

* Show me column j (for some j between 1 and 9)

* Show me box k (for some k between 1 and 9)

* Show me the givens.

You black out everything with the sharpie except what I called for. I can confirm that everything still showing complies -- either the row/column/box fits the rules (every # 1-9) or the givens match up (if two 3s were given, I can confirm they're the same number). If you really solved the Sudoku, you pass this test. If you lied, you fail this test 1/28 of the time at least (assuming I pick the test randomly).

We can repeat this, new permutation and everything, and if you keep passing, I can calculate the probability you lied but, through luck, got an answer through (27/28 to the power of # iterations). After a while, I'm convinced to some threshold.

... so that's what I'm wondering if something like it exists for the putting green. Not as exciting as the Monty Hall problem a few months ago (which I also covered with my students, although that inclusion was in the curriculum long before it came up on TST), but it's the sort of thing that crosses my mind.

By the way, @billchao I don't necessarily suggest using this to convince someone (beyond one or two rounds of it for the entertainment value) that you've solved a Sudoku.

Interesting, thank for the explanation.

I had a class as a freshman math major that sounds similar to the class you are teaching called Introduction to Higher Math.  We used a great book (whose name I have been furiously been trying to remember and verify) that looked at a lot of unusual math stuff.  It analyzed the "fifteen" puzzle where you slide the little squares around a frame with one square missing.  We did a bunch on duality and the pigeonhole principle.  Some graph theory (Traveling Salesman, and Highway Inspector), Coloring conjectures/theorems, AC current and imaginary numbers, cryptography, etc.  It was really a hodge podge and we did not go into each topic that deeply but it was really interesting and was also a great illustration how math ends up in unlikely places.

It was one of my favorite math classes.

[Shindig]

Interesting, thank for the explanation.   I had a class as a freshman math major that sounds similar to the class you are teaching called Introduction to Higher Math.  We used a great book (whose name I have been furiously been trying to remember and verify) that looked at a lot of unusual math stuff.  It analyzed the "fifteen" puzzle where you slide the little squares around a frame with one square missing.  We did a bunch on duality and the pigeonhole principle.  Some graph theory (Traveling Salesman, and Highway Inspector), Coloring conjectures/theorems, AC current and imaginary numbers, cryptography, etc.  It was really a hodge podge and we did not go into each topic that deeply but it was really interesting and was also a great illustration how math ends up in unlikely places. It was one of my favorite math classes.

Yep. Did units on metalogic, graph theory, number theory, probability, combinatorics, and some other miscellaneous topics. It's one of my favorites as an instructor too.

[turtleback]

Yep. Did units on metalogic, graph theory, number theory, probability, combinatorics, and some other miscellaneous topics. It's one of my favorites as an instructor too.

When I taught JHS math I always wanted to teach an elective of the math kids exposing them to some things to show them what math really was, since most of them think it is just arithmetic.  TPTB would never let me but I still manages to sneak some of that stuff into my regular classes.

My scope was limited because they are young and their mental processes are not that well developed, but I still managed to do some cool things with them.  I had a little Fibonacci unit where we started with the classic rabbit breeding problem that is one way to give rise to them and culminated in using the Fibonaccis to construct a logarithmic spiral.  I would also do a little on 4-color (try to draw a map that requires 5 colors).  And for the last day of school I'd give them a variation on the Bridges of Koenigsburg problem.