1
$\begingroup$
  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.

$\endgroup$
3
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ The attack is considerably more efficient if we are able to alternate between Alice and Bob roles... $\endgroup$ – poncho Feb 2 at 15:08
  • $\begingroup$ @poncho That's true. However, if the roles in the protocol are a priori fixed then the adversary would need to be a third party communicating with both Alice and Bob for that to work. And I interpret "They communicate over a secure channel." as an encrypted and authenticated channel which would thwart that attack vector. $\endgroup$ – Maeher Feb 2 at 18:59
  • $\begingroup$ Thank you. What about if they can only run the protocol once? eg. They are standing in the same room and give each other one chance at verification. (secure channel and have authenticated the other party already) $\endgroup$ – AndrewHarvey Feb 2 at 23:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.