- What is the following protocol known as?
- Is it considered secure? Would it work?
Background
Alice and Bob each have a secret.
They wish to determine if they both know the same secret.
If they do share the same secret, they are happy for each other to know this. If they don't share the same secret, they don't want to disclose that secret to the other person.
There is no trusted third party.
They communicate over a secure channel.
Protocol
- Alice tells Bob the first bit of the secret.
- Bob compares this bit to his own secret, if it matches, Bob shares the second bit of his secret with Alice, if it doesn't match, Bob shares a random bit with Alice.
- Alice compares this bit to her own secret, if it matches, Alice shares the third bit of her secret with Bob, if it doesn't match, Alice shares a random bit with Bob.
They each continue step 2 and 3. If at any point, their bits don't match, all subsequent bits they share are random.
If they reach the end and every bit has matched, they know they share the same secret, if at any point a bit didn't match, they know they didn't share the same secret, and keep the rest of the secret safe.
Of course this depends on randomness, so there is a small chance you don't share the same secret, but will come to the conclusion that you do, it's dependent mostly based on the length of the secret, the longer the less likely you run into coincidence that those random bits just happen to match up.
To protect against leaking the start of the message too easily, Alice and Bob could pre-pad their true secret with a shared random pre-secret key.