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.
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.
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.
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.
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.
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.
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]
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.
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.
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].
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.
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).
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.
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.
Ignore this post for a second; parsing above reply.
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.
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).
d and e won’t be xoring functions, they’d be something like modulo powers or discrete logarithms, or some other asymmetrical transformation.
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)
Basically, you’ve restated the skeleton of post #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?