Can two traitors safely reveal themselves to each other?

Question

Suppose Alice is a traitor and suspects Bob might also be a traitor. If Bob is a traitor, she would like to conspire with him together, if not she doesn't want to reveal that she is a traitor. Is there a protocol Alice and Bob can engage in that would reveal that they are either:

1. Both traitors
2. Not both traitors

With a trusted third party, this would be be easy. Both Alice and Bob reveal their traitor/non-traitor status to the TTP and if both are traitors the TTP tells them so, if only one or none of them are traitors the TTP just says they are not both traitors.

But is there a way without a trusted third party?

I did some research and found this might be an example of a fair exchange and thus be technically impossible without a TTP. Most of the info I can find on fair exchange is over my head though and I thought this situation might be unique in that it involves agreement on potentially the same information, the protocol equivalent of an AND operation. And of course there is that feeling of "it's such a simple problem, how could it be impossible?" so I had to ask.

Answer 1

But is there a way without a trusted third party?

Sure, one of the simpler solutions is probably to use Yao's Garbled Circuit Protocol to compute the AND gate. Note that actually using the original protocol will do here because the modern speed-ups are only important for large numbers of ANDs and malicious security would also be somewhat useless as a dishonest party can just lie and claim 1 to learn the other party's input bit.

So here's the basic protocol:

Setup Phase (executed only by Bob):

1. Pick $6$ random 128-bit keys and call them $k_A^0,k_A^1,k_B^0,k_B^1,k_\land^0,k_\land^1$.
2. Define the encryption scheme $E_{k,k'}(m)=(r,F_k(r\|0)\oplus F_{k'}(r\|0)\oplus m,F_k(r\|1)\oplus F_{k'}(r\|1)\oplus 0^{128})$ where $F_k(m)$ is a single AES-128 block cipher encryption call and $r$ is a freshly randomly chosen 127-bit value. The corresponding decryption function returns an error whenever the XOR of the third entry with the re-computed AES evaluations doesn't yield 128 zeroes.
3. Compute the "garbled table", that is compute $T_{11}=E_{k_A^1,k_B^1}(k_\land^1)$ and $T_{xy} = E_{k_A^x,k_B^y}(k_\land^0)$ for $x,y\in\{0,1\}$ with $x\land y=0$.
4. Randomly permute the four table entries, call the result $T_0,\ldots, T_3$, eg using a Fisher-Yates shuffle fed by a cryptographic RNG.
5. Compute $H_0=H(r\|k^0_\land)$ and $H_1=H(r\|k^1_\land)$ using your favourite cryptographic hash function, e.g. SHA-256 and some 128-bit random string $r$.
6. Send $T_0,\ldots, T_3,H_0,H_1$ to Alice.

Input Phase (executed between both):

1. Bob sends $k^x_B$ to Alice where $x$ is his input bit.
2. Bob also picks a random Diffie-Hellman key (e.g. for P-256), call it $t$ and sends the public element $T=[t]G$ to Alice.
3. Alice picks her own Diffie-Hellman key, call it $k$, and computes $K_c=[k]G, K_{1-c}=T-K_c$ for her secret protocol input bit $c$ and sends over $K_0$ to Bob.
4. Bob computes $K_1=T-K_0$ and chooses two new DH keys $r_0,r_1$ with $R_0=[r_0]G, R_1=[r_1]G$ and sends over to Alice $E_0=(R_0,H([r_0]K_0)\oplus k_A^0), E_1=(R_1,H([r_1]K_1)\oplus k_A^1)$ using your favourite hash function, e.g. SHA-256
5. Alice selects $E_c=(L,R)$ from the two received ciphertexts corresponding to her input bit $c$ and computes $k_A^c=R\oplus H([k]L)$

Note: The last 4 steps are my adaption of the oblivious transfer protocol of Naor and Pinkas from "Efficient Oblivious Transfer Protocols" (2001).

Computation (executed by Alice)

Alice now tries to decrypt all 4 entries of the garbled table $T_0,T_3$ using $k_A^c$ and $k_B^x$. Only one decryption should succeed recovering $k_\land$.

Output Exchange (executed between Alice and Bob)

1. Alice sends $k_\land$ to Bob, Bob now knows the result of the AND gate computation by virtue of comparing the value with $k_\land^0$ and $k_\land^1$
2. Bob sends $r$ to Alice who can then also recover the evaluation bit by re-computing $H_0,H_1$ and checking which hash matches.