Viewing a single comment thread. View all comments

zorblax wrote (edited )

But once she starts narrowing them down to exclude other cities on the same continent or in the same country, it would be obvious to Bob where Alice lives, since the random points she picks would start converging in one area where there is only one city. So, that is one case where the second method would not work in protecting each party's anonymity.

Yes, but the point isn't to prevent the other person from knowing your location, the point is to only reveal your location if the other person probably lives there too. If you start to converge as more rounds are played, that's good -- you need it to converge so you eventually get an answer.

Additionally, with very wide bounds you don't actually get a compacted region, you get a washer-shaped zone of possibility. For the first 2 rounds it would be practically impossible to figure out.

Let's say Eve pretends to be Bob, and tells Alice the first bit of Bob's city hash is 0 (Eve is making this part up - she doesn't actually know what Bob's hash is). Alice disconnects. This tells Eve that the first bit of Alice's city hash is not 0, which leaves only 1.

I thought of that, but I don't think it's that big of a deal.

I just came up with a better one that has none of these drawbacks: Alice and Bob agree on a salt, and both hash their locations with the salt(using some intentionally slow hasing function, like 1 minute per hash) and sign that data. They then send the detatched signature to each other. If they have the same location, the signature will verify on their hashed location, if not, it will not, with no information leakage.

It could still be broken by brute force, but not as easily. You could improve it by involving Carol, who compares the two hashes and only exchanges the signatures if they are the same, but that would mean trusting Carol to not always give Eve your signature for brute-forcing.

This is a very difficult problem to solve because it's basically a two-way zero-knowledge proof, where there are a very small number of possible objects. I don't know if you'll get better than a guessing game.

2

sudo OP wrote

I don't think that new idea is much better, unless CryptoNight is unbearably slow (not slow as in computeHash(); sleep(10);, I mean slow as in it takes a lot of processor time to compute the hash - and if it's that slow, how could Alice and Bob compute their hashes in a timely fashion in the first place?) Even if they have to agree on a salt first, all Eve would have to do is create a table of hashes from big city names + salt, then try to verify each one with the detached signature until it clicks. Then she'd know where Alice lives. Or, if Eve already computed a table of hashes of city names with a given salt (say the salt is "StalinsMoustache"), then Eve could suggest to Alice that they use "StalinsMoustache" as the salt. Alice would agree, and Eve's work would be reduced significantly. Or, if Alice is aware of this trick, and Bob suggests a salt to her, she says, "No, Bob, I think you might really be Eve, and you're just suggesting that salt because you have a pre-computed hash table of city names using that salt, and you'll try to brute-force it using my signature once I give it to you. I'm picking the salt." To which Bob replies, "Well, you could really be Eve impersonating Alice, and you could be trying to trick me with a salt you made up beforehand and computed a hash table from. So, I can't trust you to pick the salt." If neither can trust the other to pick a salt, then they wouldn't be able to do this exchange. (Maybe they could have some third party randomly generate the salt, but that's just shifting the trust again.)

It seems to me like your first idea is still the best one that's been suggested.

2

zorblax wrote

Use Diffie-Hellman to determine the salt. Unique for any pair of people.

And yes, the hash function would have to be very very slow to make brute-force hard.

1

sudo OP wrote

Diffie-Hellman would only work if you've already met the other person in real life before (so you know that they actually exist). If Eve is pretending to be Bob online, but Bob doesn't actually exist in real life, doing a Diffie-Hellman exchange won't help Alice. It would only work if Alice knew Bob in real life, but thinks the person she's talking to online isn't really Bob, but Eve.

I guess your first idea (bit-by-bit revealing of the hash) is the best we can do.

1

zorblax wrote

That's a problem of the protocol, not the primitive itself. If Eve can impersonate Bob then the entire thing is basically public to her anyway, no matter what you do.

1