Validating a shared secret between two parties, one bit at a time

Question

1. What is the following protocol known as?
2. 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

1. Alice tells Bob the first bit of the secret.
2. 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.
3. 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.

Answer 1

Assuming that you can run this protocol multiple times, it is completely insecure. Say we are an attacker trying to deduce Alice's secret and that the secret has length $n$. We can then extract Alice's secret using at most $(n+n^2)/2$ times. Let's call the secret as $s$ and let $s_i$ denote the $i$th bit of $s$.

Our attack hinges on two key observations: 1. For odd $i$, Alice will just send us $s_i$, if we know the prefix $s_1\|\dots\|s_{i-1}$ and execute the protocol honestly using an $s'$ with the same prefix. 2. For even $i$, Bob needs to send the bit. If Bob sends the correct bit, Alice's answer will always be $s_{i+1}$ and therefore identical for multiple executions. If Bob sends the wrong bit, Alice's answer is random and thus will differ between two executions with probability $1/2$.

So for $1\le i \le n$ our attack proceeds as follows:

• If $i$ is odd, choose a random secret $s'$ such that $s'_1\|\dots\|s'_{i-1} = s_1\|\dots\|s_{i-1}$ and perform the protocol honestly. Note that by the correctness of the protocol Alice's message in round $i$ of this execution will be $s_i$. Thus at the end of this execution we have learned $s_{i}$ with probability $1$.
• If $i$ is even, choose a random secret $s'$ such that $s'_1\|\dots\|s'_{i} = s_1\|\dots\|s_{i-1}\|0$. Using this $s'$ run at most $n$ executions of the protocol. Let $\bar{s}_j$ denote the bit sent by Alice in round $i+1$ of the $j$th execution. If there are ever $j,j' \in \{1,\dots,n\}$ such that $\bar{s}_j \neq \bar{s}_{j'}$ we can abort and deduce that $s_i=1$. Otherwise, if $\bar{s}_j = \bar{s}_{j'}$ for all $j,j' \in \{1,\dots,n\}$, then we can deduce with probability $1-2^{-n}$ that $s_i=0$ and $s_{i+1}=\bar{s}_j$. So overall, we have learned at least $s_{i}$ with probability at least $1-2^{-n}$.

After at most $(n + n^2)/2$ executions we have thus revealed $s$ with probability at least $(1-2^{-n})^{n/2} > 1-2^{-n/2}$.