# Cryptographic Zero Knowledge Proof Question
**URL:** https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550
**Category:** Factual Questions
**Created:** [July 15, 2008, 6:36am UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550 "2008-07-15T06:36:22Z")
**Posts on this page:** 20
**Page:** 3
### Author:  [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)
#### Post date: [July 17, 2008, 4:06pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/41 "2008-07-17T16:06:09Z")
Using just hashing (like MD5), I can’t think of any solutions beyond doing something silly like rehashing in a loop enough times to make it infeasible to brute force–repeating more times the smaller the seed value is. But, of course that’s a stupid way to do it. It needs to take several decades to brute force something to make it a strong enough method, so if there’s only 100 possible seeds and both of you know that, the fastest you could even process your hash would be 1/100th of several decades (like three months.) Yeah, it would take your rival a couple decades to brute force it, but it’s not really a solution unless you’re real patient.
---
### Author:  [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)
#### Post date: [July 17, 2008, 4:21pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/42 "2008-07-17T16:21:40Z")
[QUOTE=Sinaijon]
But if that’s the case, then when Bob is given Alices hash result h(g(x)), all he has to do is run his hash function(g(h(x)) for all numbers between 1-100. The one that matches will give him Alice’s number. Its the same as my example, with f(x) = h(g(x)) = g(h(x)).
[/QUOTE]
h(g(x)) is a poor way to write what **Shalmanese** means. Think of it instead as:
h(h(x . aSalt) . bSalt) = result = h(h(x . bSalt) . aSalt)
Since Alice doesn’t know what bSalt is and Bob doesn’t know what aSalt is, they can both know “result” without compromising the security of their x.
---
### Author:  [@Chronos](https://boards.straightdope.com/u/Chronos)
#### Post date: [July 17, 2008, 4:34pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/43 "2008-07-17T16:34:46Z")
> [@](#):
>
> as this the article, by any chance? It seems, from the preview, to be about a related, but slightly different, problem, though I haven’t found any closer matches yet.
Sorry, I should have been more clear. The article I was remembering was on the classical version of the problem-- It was probably before the advent of quantum cryptography.
---
### Author:  [@Kinbote](https://boards.straightdope.com/u/Kinbote)
#### Post date: [July 17, 2008, 4:58pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/44 "2008-07-17T16:58:36Z")
[QUOTE=Sinaijon]
But Bob has both the encrypted result and S. So he just runs ‘S’ through all his public keys (there is only 100) until he finds one that matches the encrypted result he originally got from alice. He would then know Alice’s number.
Basically, he finds ‘x’ such that Pub[sub]x/sub = Pub[sub]a/sub
[/QUOTE]
Ah, yeah, I think you’re right. Bob doesn’t have S, but does have 100 candidate Ses. One of which will encrypt to Pub[sub]a/sub.
Dang.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [July 17, 2008, 6:04pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/45 "2008-07-17T18:04:10Z")
Ah. Thinking of salts as strict concatenation is a bit distracting, and the property sought for in the hash function seems a bit narrower than necessary, so I’ll rewrite out what seems to be an appropriately general skeleton for a **Shalmanese** -type protocol:
We have some binary function f(secret, salt) and a binary relation p(y, z) [possibly, but not necessarily, the equality predicate] such that p(f(f(x, a), b), f(f(x’, b), a)) iff x = x’ [or at least, there is high correlation], but determining x from f(x, a) is infeasible, even when the number of possibilities for x is low. Every person N publishes f(secret(N), salt(N)). When Alice wants to compare her number against Bob’s, Alice sends Bob f(secret(Alice), salt(Alice)) and waits for him to send back f(f(secret(Alice), salt(Alice)), salt(Bob)). She then checks if this is in the relation p with f(f(secret(Bob), salt(Bob)), salt(Alice)), which she can compute using Bob’s published information. The result tells her whether or not to believe her secret matches Bob’s.
---
### Author:  [@Sinaijon](https://boards.straightdope.com/u/Sinaijon)
#### Post date: [July 17, 2008, 6:16pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/46 "2008-07-17T18:16:31Z")
[QUOTE=Sage Rat]
h(h(x . aSalt) . bSalt) = result = h(h(x . bSalt) . aSalt)
[/QUOTE]
It still doesn’t work out. aSalt would have to be a substring of bSalt, or bSalt would have to be a substring of aSalt for it to work out. And if that’s the case, then Bob can also figure out Alice’s salt, and from there, her number.
Bob knows the following:
bSalt = ‘BobSalt’
bx = Bob’s number ‘55’
h(bx.bSalt) = knownValueB (he calculates this)
He doesn’t know:
ax = Alice’s number
aSalt = Alice’s Salt
but he does know
h(ax.aSalt) = knownValueA because Alice gives this to him.
So… In order for the hashes to be equal, the inputs need to be equal (otherwise, we’d have false positives), so then it follows that:
h(ax.aSalt).bSalt) = h(bx.bSalt).aSalt
substituting in what Bob knows
knownValueA.‘BobSalt’ = knownValueB.aSalt
From that, it’s obvious to Bob what Alice’s salt must be. (He knows the full string on the left. All the characters on the left that do not belong to knownValueB are then Alice’s salt). He can hash 1-100 to get her number, and compare the results to knownValueA to figure out here number.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [July 17, 2008, 6:27pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/47 "2008-07-17T18:27:13Z")
In response to the post above, I think you’d find it helpful to _not_ think of the use of the salt as simple string-concatenation for input to a unary hash function. Accordingly, see the post above yours. Also, your argument covers the case where Alice and Bob’s number match so that the hashes (with opposite salting orders) match; in this case, it’s not a problem that each is able to figure out the other’s number, as they are meant to discover that theirs match anyway. [They will also discover each other’s salt on your analysis, but, well, it’s just useless salt]
---
### Author:  [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)
#### Post date: [July 18, 2008, 12:33am UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/48 "2008-07-18T00:33:48Z")
[QUOTE=Sinaijon]
knownValueA.‘BobSalt’ = knownValueB.aSalt
[/QUOTE]
You’ve forgotten to hash. This should be
h(knownValueA.‘BobSalt’) = h(knownValueB.aSalt)
The difficulty of finding a just such a function is immense. My guess would be that your odds would be better to find a function h() which is something like:
h(x, h(x, aSalt) . bSalt) = 0
h(x, h(x, bSalt) . aSalt) = 0
h(y, h(x, aSalt) . bSalt) != 0 – (where y!=x)
But it would still be plenty difficult to find such a function that didn’t preserve enough information about x to make it non-trivial to mathematically determine it.
---
### Author:  [@Sinaijon](https://boards.straightdope.com/u/Sinaijon)
#### Post date: [July 18, 2008, 2:32pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/49 "2008-07-18T14:32:53Z")
[QUOTE=Sage Rat]
You’ve forgotten to hash. This should be
h(knownValueA.‘BobSalt’) = h(knownValueB.aSalt)
[/QUOTE]
My presumption was that for the hash, if the output was the same, than the input must be as well. If different inputs can lead to the same output, you have the possibility of false positives.
---
### Author:  [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)
#### Post date: [July 18, 2008, 5:51pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/50 "2008-07-18T17:51:42Z")
How about this:
Alice and Bob share the same secret S and know about a function pair e(k,b) and d(k, b) that operate on a bit string b and key k such that d(k, e(k,b)) = b. Alice picks a large random bit string b[sub]A[/sub] and sends Bob e(S, b[sub]A[/sub]), and Bob picks a large random bit string b[sub]B[/sub] and sends Alice e(S, b[sub]B[/sub]). Since they both know S, Alice can calculate b[sub]B[/sub] and Bob can calculate b[sub]A[/sub]. They then each calculate b[sub]A,B[/sub] which is the xor of b[sub]A[/sub] and b[sub]B[/sub]. Finally, Alice sends Bob an agreed-upon portion of b[sub]A,B[/sub], Bob sends Alice a different portion of b[sub]A,B[/sub], and there exists some portion of b[sub]A,B[/sub] that was not transmitted so that Eve, who was listening in on the whole set of transmissions, can’t reconstruct b[sub]A,B[/sub].
---
### Author:  [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)
#### Post date: [July 18, 2008, 6:04pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/51 "2008-07-18T18:04:42Z")
Oh, I meant to say, I think this also prevents Martin from intercepting the transmissions of each and substituting his own bistreams, since he doesn’t know S, and also would not be able to calculate b[sub]A,B[/sub]. Finally, Alice and Bob can then use the untransmitted bits in b[sub]A,B[/sub] as a session key with some symmetric encryption technique to then converse.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [July 18, 2008, 8:04pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/52 "2008-07-18T20:04:24Z")
Fine, but… how does this address the problem the OP wanted solved, of Alice and Bob having separate secrets and wanting to know if they coincide?
For that matter, for whatever problem you are solving, why do they bother sending each other bits of b[sub]A|B[/sub] at the end? They both already know all the bits of it (you did stipulate that they started out with the same secret S).
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [July 18, 2008, 8:10pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/53 "2008-07-18T20:10:57Z")
[QUOTE=Indistinguishable]
For that matter, for whatever problem you are solving, why do they bother sending each other bits of b[sub]A|B[/sub] at the end? They both already know all the bits of it (you did stipulate that they started out with the same secret S).
[/QUOTE]
Oh, I suppose that’s a confirmation step to foil interceptive Martin. At any rate, I still don’t see how this is targeted to the OP’s problem.
---
### Author:  [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)
#### Post date: [July 18, 2008, 8:12pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/54 "2008-07-18T20:12:10Z")
Alice and Bob have already decided which parts they will be transmitting to each other. So, when Alice gives Bob her portion of b[sub]A,B[/sub], if all of those bits matches the corresponding bits in his calculation of b[sub]A,B[/sub], then he can be pretty sure that his S matches hers. The same thing in the other direction.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [July 18, 2008, 8:13pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/55 "2008-07-18T20:13:42Z")
Ignore this post for a second; parsing above reply.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [July 18, 2008, 8:20pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/56 "2008-07-18T20:20:57Z")
Well, you’d need further stipulations on your d and e to be able to confidently infer from d(S[sub]B[/sub], e(S[sub]A[/sub], b[sub]A[/sub])) XOR b[sub]B[/sub] = d(S[sub]A[/sub], e(S[sub]B[/sub], b[sub]B[/sub])) XOR b[sub]A[/sub] that S[sub]A[/sub] = S[sub]B[/sub]. It doesn’t follow from the requirements you’ve given.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [July 18, 2008, 8:31pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/57 "2008-07-18T20:31:15Z")
[QUOTE=Indistinguishable]
Well, you’d need further stipulations on your d and e to be able to confidently infer from d(S[sub]B[/sub], e(S[sub]A[/sub], b[sub]A[/sub])) XOR b[sub]B[/sub] = d(S[sub]A[/sub], e(S[sub]B[/sub], b[sub]B[/sub])) XOR b[sub]A[/sub] that S[sub]A[/sub] = S[sub]B[/sub]. It doesn’t follow from the requirements you’ve given.
[/QUOTE]
If we take d and e to be XORing functions, for example, then d(S[sub]B[/sub], e(S[sub]A[/sub], b[sub]A[/sub])) XOR b[sub]B[/sub] = d(S[sub]A[/sub], e(S[sub]B[/sub], b[sub]B[/sub])) XOR b[sub]A[/sub] will _always_ hold, regardless of what S[sub]A[/sub] and S[sub]B[/sub] are (and whether or not they match).
---
### Author:  [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)
#### Post date: [July 18, 2008, 8:38pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/58 "2008-07-18T20:38:40Z")
d and e won’t be xoring functions, they’d be something like modulo powers or discrete logarithms, or some other asymmetrical transformation.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [July 18, 2008, 8:40pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/59 "2008-07-18T20:40:41Z")
[QUOTE=Punoqllads]
d and e won’t be xoring functions, they’d be something like modulo powers or discrete logarithms, or some other asymmetrical transformation.
[/QUOTE]
Right, well, you haven’t stated what properties you’re asking for of them. The requirements stated in your post were not enough to support it. We can arbitrarily impose the requirement that d(S[sub]B[/sub], e(S[sub]A[/sub], b[sub]A[/sub])) XOR b[sub]B[/sub] = d(S[sub]A[/sub], e(S[sub]B[/sub], b[sub]B[/sub])) XOR b[sub]A[/sub] should allow us to infer S[sub]A[/sub] = S[sub]B[/sub] with high confidence, but this is pulled out of a hat; do you have an actual example of functions with this property, or reason to believe such functions exist?
(Of course, you also haven’t stated any requirements to prevent information-leakage, either; e might just as well be concatenation and d might just as well be the corresponding truncation, for all the details you’ve given)
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [July 18, 2008, 8:45pm UTC](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550/60 "2008-07-18T20:45:49Z")
Basically, you’ve restated the skeleton of post [#45](http://boards.straightdope.com/sdmb/showpost.php?p=10012943&postcount=45), specializing p to be the equality predicate, and slightly generalizing so that decoding d and encoding e need not be the same function f.
Rewriting the post with that appropriate generalization:
We have some binary functions e(secret, salt) and d(secret, salt), as well as a binary relation p(y, z) [possibly, but not necessarily, the equality predicate], such that p(d(e(x, a), b), d(e(x’, b), a)) iff x = x’ [or at least, there is high correlation], but determining x from e(x, a) is infeasible, even when the number of possibilities for x is low. Every person N publishes e(secret(N), salt(N)). When Alice wants to compare her number against Bob’s, Alice asks him to send her d(e(secret(Alice), salt(Alice)), salt(Bob)), which he can compute using her published information. She then checks if this is in the relation p with d(e(secret(Bob), salt(Bob)), salt(Alice)), which she can compute using Bob’s published information. The result tells her whether or not to believe her secret matches Bob’s.
The $64,000 question is, do such d, e, and p exist, and, if so, what are they?
[Previous page](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550.md?page=2)
[Next page](https://boards.straightdope.com/t/cryptographic-zero-knowledge-proof-question/456550.md?page=4)