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 screenshot of wikipedia


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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