How to compute result in last step of Socialist millionaires problem?

Question

I was trying to understand Socialist millionaires problem and solution in OTR protocol, but I'm stuck at figuring out how and who computes $(Q_{a}Q_b{}^{-1})^{\alpha\beta}$.

If I'm Bob then I received $Q_{a}$, I can compute $Q_{b}^{-1}$ and I know my $\beta$. However I don't know $\alpha$. How is it computed then?

I'm uploading screenshot of wikipedia page, which I'm reffering to, in case it get's modified in future

Answer 1

The answer is that Bob and Alice each calculate $(Q_a Q_b^{-1})^{\alpha \beta}$. Alice computes the quantity $Q_a$, Bob computes $Q_b$, Alice computes $(Q_a Q_b^{-1})^\alpha$ and sends that to Bob, who can compute $c = (Q_a Q_b^{-1})^{\alpha \beta}$.

---

Let's step through the protocol, keeping in mind the OTR reference (assuming that you do the tests, which I'm leaving out because it clutters things more):

$\text{Alice} \rightarrow \text{Bob}$: Alice picks random $a$ and $\alpha$, sends $g_{2a} = h^{a}$ and $g_{3a} = h^{\alpha}$ to Bob.

$\text{Bob} \rightarrow \text{Alice}$: Bob picks random $b$ and $\beta$, computes $g \equiv g_{2a}^{b}$ and $\gamma \equiv g_{3a}^{\beta}$, picks random $s$, sends $P_b \equiv \gamma^s$, $Q_b = h^s g^y$, $g_{2b} = h^b$, and $g_{3b} = h^\beta$ back to Alice. note: At this point, Bob has computed the secure $g$ and $\gamma$.

$\text{Alice} \rightarrow \text{Bob}$: Alice also computes $g = g_{2b}^{a}$ and $\gamma = g_{3b}^{\alpha}$, computes $P_a \equiv \gamma^r$, $Q_a \equiv h^r g^x$, and $R_a = (Q_a Q_b^{-1})^{\alpha}$, sends $P_a, Q_a, R_a$.

$\text{Bob} \rightarrow \text{Alice}$: Bob computes $R_b \equiv (Q_a Q_b^{-1})^{\beta}$, compute $c = R_{ab} = R_a^{\beta}$, check whether $c = P_a P_b^{-1}$, send $R_b$.

$\text{Alice} \rightarrow \text{Bob}$: compute $c = R_{ab} = R_b^{\alpha}$, also check $c = P_a P_b^{-1}$.

Bob can compute $c$ in the fourth step, because Bob computed $Q_b$ in step 2, and received $R_a$ from Alice in step 3.