Actually, the skeleton naturally generalizes a bit more, once one thinks of allowing asymmetries:
We have some binary functions e1, e2, d1, and d2, as well as a binary relation p(y, z) [possibly, but not necessarily, the equality predicate], such that p(d1(e1(x, a), b), d2(e2(x’, b), a)) iff x = x’ [or at least, there is high correlation], but determining x from e1(x, a) and e2(x, a) is infeasible, even when the number of possibilities for x is low. Every person N publishes e1(secret(N), salt(N)) and e2(secret(N), salt(N)). When Alice wants to compare her number against Bob’s, Alice asks him to send her d1(e1(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 d2(e2(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 remains as above, mutatis mutandis.
Whoops, I forgot to take account of the XOR step at the end of your protocol. Also, tightening up the information-leakage requirements. Alright, this is the last skeleton, I promise:
We have some binary functions e1, e2, ternary functions d1 and d2, as well as a binary relation p(y, z) [possibly, but not necessarily, the equality predicate], such that p(d1(e1(x, a), x’, b), d2(e2(x’, b), x, a)) iff x = x’ [or at least, there is high correlation], but determining x from e1(x, a) and e2(x, a) (and a few calls to d1(z, x, a) and d2(z, x, a) with the z of one’s choice) is infeasible, even when the number of possibilities for x is low. Every person N publishes e1(secret(N), salt(N)) and e2(secret(N), salt(N)). When Alice wants to compare her number against Bob’s, Alice asks him to send her d1(e1(secret(Alice), salt(Alice)), secret(Bob), salt(Bob)), which he can compute using her published information. She then checks if this is in the relation p with d2(e2(secret(Bob), salt(Bob)), secret(Alice), 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.
I think I can show a simple example: suppose Alice and Bob both work at Really Smart Cryptologists, Inc. The secret that they share is that the number 119 is evenly divisible by 7 and 17. Using their proprietary (but well-known) Really Sneaky Algorithm, they know that for any number n that is relatively prime to the least common multiple of 7-1 and 17-1 (48) they can compute a number m where n * m is congurent to 1 modulo 48. Once they have those two numbers, for any number b which is between 1 and 118, b[sup]n[sup]m[/sup][/sup] modulo 119 = b.
Later in the week, Alice calls up Bob. Bob doesn’t know for sure that it’s Alice, and Alice can’t be sure that her call wasn’t intercepted. So they set up a suitable challenge to prove that each party knows the secret of the number 119. First they decide on an encoding number. At random they pick the number 5, and both agree that it’s a suitable encoding number. Using a handy formula invented by a guy named Euclid, they can each individually calculate that the appropriate decoding number would then be 29, because 5 * 29 is congruent to 1 modulo 48, which in turn means that for any number b, b[sup]5[sup]29[/sup][/sup] modulo 119 = b.
Next, they agree that once they calculate the xor of their random 7-bit strings, Bob will give Alice the bottom 2 bits and Alice will give Bob the high 2 bits. Alice decides to use the bitstring 1010011 = 83 and Bob decides to use the bitstring 0111001 = 57. Alice calculates that 83[sup]5[/sup] modulo 119 is 104 and then sends 104 to Bob. Bob calculates that 57[sup]5[/sup] modulo 119 is 92 and then sends 92 to Alice. Bob calculates that 104[sup]29[/sup] modulo 119 is 83, getting the bitstring 1010011, and Alice calculates that 92[sup]29[/sup] modulo 119 is 57, getting the bitstring 0111001.
Finally, since they each have the two bitstrings, they can each calculate the xor of them, namely 1101010. Then Alice sends Bob the 2 bits she promised, ‘11’, and Bob sends Alice the two bits he promised, ‘10’. Since Bob can see that Alice’s 2 bits match the top 2 bits of 1101010 and Alice can see that Bob’s 2 bits match the bottom 2 bits, they can know that, due to the difficulty of factoring the number 119, they can be sure that they’re talking to each other, not some impostor.
Quite good. But, I would say, it doesn’t quite handle the general case where Alice has an arbitrary secret number, Bob has an arbitrary secret number, and they want to see if they match, as Alice and Bob might not know the prime factorization of their secret numbers from the start [also, their secret number might not be the product of two primes, but that’s more nitpicky and probably glossoverable]. Also, I’m a little concerned about the possibility for false positives; is it rigorously reasonable to conclude that their secret numbers match, given that the test comes out happy? Running through the protocol using differing secret numbers, it’s not clear to me; of course, intuition says “What are the chances that things would come out that way if their secret numbers differed?”, but I’d like to see intuition solidified.
Actually, I’m not sure the secret you were saying they discovered they shared was that they both used the same product of two primes (e.g., 119). I suppose the secret they discovered they shared was that they both knew the prime factorization of this number (e.g., 7 * 17); basically, this allowed them to confirm each other’s identity, in the face of having already met and set up a shared secret to use for such confirmation in the future. But then this sort of thing seems even further from what the OP would want. Could you clarify how to use this protocol to handle something like the following challenge?
Alice and Bob have never met before
Each is assigned a random number which they know and the other doesn’t
They are to determine whether their numbers match; however, if their numbers don’t match, they should not learn any more information about what each other’s numbers are
I suppose you could do something like “Alice takes her secret random number and converts it mechanically into two primes; so does Bob. They then run through the protocol above and if things turn out happy at the end, they probably had the same secret random number. Otherwise, they didn’t.” Is that the idea?
Okay, I now see where the method breaks down. If it’s mechanically generated from random numbers, then for a small enough set of random numbers, you can calculate all of the values p * q and know all of the factorizations. Back to the drawing board…
Okay, I’m making another stab at this. I think that discrete logarithms might be the right way to go about it. Assume that all parties (Alice, Bob, Eve, Martin – heck, even Trent) have some known large prime p to work with. Alice and Bob pick their random bit strings b[sub]A[/sub] and b[sub]B[/sub] as normal, calculate their respective e[sub]i[/sub] = e(S,b[sub]i[/sub]) = S[sup]b[sub]i[/sub][/sup] modulo p, and exchange the results with each other. Then Bob calculates e[sub]A[/sub][sup]b[sub]B[/sub][/sup] modulo p and Alice calculates e[sub]B[/sub][sup]b[sub]A[/sub][/sup] modulo p. At this point, if they have the same secret S, they should have the same number, so if they share subsets of the bits of the result with each other, they should be able to confirm that they have the same S.
Since calculating discrete logarithms is a known hard problem, I believe that even if the number of available secrets S is small, Eve (who has again been listening in the entire time) would have to do a brute force search. While this algorithm would not prevent Martin from sending bits back and forth, I believe that Alice and Bob could avoid transmitting certain bits across their connection and then use some of the untransmitted bits as a session key.
I don’t have enough of a mathematical background to be certain of these beliefs, so I would be appreciative if the more mathematically inclined could weigh in.
Basically, Bob calculates (S[sub]A[/sub][sup]b[sub]A[/sub][/sup])[sup]b[sub]B[/sub][/sup] mod p and compares it to Alice’s calculation of (S[sub]B[/sub][sup]b[sub]B[/sub][/sup])[sup]b[sub]A[/sub][/sup] mod p. But the exponents just multiply and multiplication is commutative; so they’ll think their secrets match as long as their secrets, when raised to some randomly chosen power, are equal modulo p. But I see little reason why this is a reasonable inference; many different numbers can have equal b[sub]A[/sub]b[sub]B[/sub]-th powers modulo p.
Yes, but I believe that it requires a lot of computing power to come up with some number N such that you know the discrete logarithm modulo p for every base in the set of available secrets, and even if you did, the bit validation portion would trip you up. The bit validation would consist of Alice telling Bob, “send me bit i” and Bob sending back that bit, and then telling Alice, “send me bit j” and Alice sending him that bit. Repeat until both Bob and Alice trust that the other person knows the number.
I’m not sure I understand you. All the bit validation process ensures is that S[sub]A[/sub][sup]b[sub]A[/sub]b[sub]B[/sub][/sup] = S[sub]B[/sub][sup]b[sub]A[/sub]b[sub]B[/sub][/sup] (mod p). How does one move from this to concluding that S[sub]A[/sub] = S[sub]B[/sub]? Is it actually the assumption that, if this works out many times, they are probably equal? I suppose that’s reasonable enough, though it’s amenable to manipulation. For example, suppose Alice’s secret is 1, Bob’s secret is p - 1, and Bob cheats by always choosing b[sub]B[/sub] to be even; then they’ll always get a hit as though their secrets match, even though they don’t.
But I guess Bob can always fuck up the protocol by just lying, so we can’t hope to get past such worries that maybe the “Do they match?” question is answered incorrectly because of such manipulation. So perhaps we should only worry about the protocol giving the right answer when run fairly, and only care about manipulation insofar as it can lead to information-leakage. In which case, my only concern is to shore up the intuition that the inference from “Equal powers of secrets modulo p, where the power is the product of two random numbers” to “Equal secrets” is justified.
Sure, except in Diffie-Hellman key exchange, everyone knows the publicly shared base S from the start; the intent is to establish a new shared secret between the two parties in the exchange, which turns out to be S[sup]b[sub]A[/sub]b[sub]B[/sub][/sup] mod p. In the OP’s challenge, both parties may or may not share the same secret S, and the intent is to determine whether or not they do, without revealing any further information about it.
So for a given prime number p used as a modulus, there is a set of integers that are good generators, where for an element of that set, g, for all integers in the range [1, p-1] g[sup]i[/sup] is congruent to g[sup]j[/sup] modulo p if and only if i = j. For example, for the case where p = 11, the set of good generators G = {2, 6, 7, 8}. No doubt there is literature out there for picking generators of maximum length for a given prime modulus.
Note that for any number n, n[sup]p-1[/sup] will always be congruent to 1 modulo p, and nsup/2[/sup] will always be congruent to either 1 or (p-1) modulo p. There could be some protocol to ensure that b[sub]A[/sub] * b[sub]B[/sub] will never be congruent to (p-1)/2 or p-1 modulo p.
That should prevent some false positives from showing up, but that doesn’t prevent all of them. For instance, when p = 569, powers of both 6 and 11 create sequences of maximal length, but 6^71 is congruent to 11^71 modulo 569. There might be some literature for picking good values of p.
Well, it’s not good generators in your sense which we want (exponentiation with a fixed base is an injective function of its exponent). We want that exponentiation with a fixed exponent should be an injective function of the base; i.e., that g[sup]i[/sup] is congruent to h[sup]i[/sup] modulo p if and only if g = h. This will happen if, say, i is coprime to p - 1.
[That this is what we actually want is illustrated by your concluding example]
Hrm, I notice that for my example of p = 569, (p-1)/2 = 284, which is a multiple of 71. I have a hunch that using primes p where (p-1)/2 is also prime makes for happier exponentiation, but I’ve pretty much reached the limit of my math knowledge.
Yes, so-called “safe primes”. Though it hasn’t been proved that arbitrarily large ones exist. But, then, lots of reasonable conjectures haven’t been proved in this area…
