Talk:Socialist millionaire problem

Rename variables

There is currently a clash with p (the prime) and p the calculated value.

I think changing the calculated value p -> m and q -> n would make sense.

A concern then would be that h, m, and n are too similar, in which case I recommend changing h -> g (the generator). This would also be consistent with the diffie-hellman page and the Primitive_root_modulo_n page where primitive roots are denoted as g.

Lastly, g and gamma are already there and might be changed to d and delta ?

Cciollaro (talk) 03:17, 8 July 2014 (UTC)

Clarify what an attacker can do

An active attacker, capable of arbitrarily interfering with Alice and Bob's communication (a man-in-the-middle) cannot learn more than a passive attacker, and cannot affect the outcome of the protocol other than to make it fail.

What does make it fail mean here?

Alice and Bob wish to learn if x = y without allowing either party to learn anything else about the other's secret value.

It would help to be clear on what the outcomes for Alice and Bob are. They initiate this procedure and get a result. What are the possible results? Is it binary, just equals or not equals, or is there also a "unable to determine" result they can discern? If it's binary, then failure is presumably causing them to get the not equals response, because it's the equals response that they will respond to by sharing secrets. 70.116.69.206 (talk) 19:00, 1 April 2013 (UTC)

Counter Example

The statement ending with "This proves correctness." is a bit misleading, what in fact it proves is that x equals y is one solution to $h^{\alpha \beta ab(x-y)}\equiv _{P}1$; however since $h$ is a generator mod $P$, (x-y)=0 is not the only solution. As illistrated below:

Alice Multiparty Bob Message $x=3$ Random $a=6,\alpha =9,r=11$ Public $P=23,h=5$ Message $y=14$ Random $b=15,\beta =17,s=20$ Secure $g=\langle h|a,b\rangle =2$ Secure $\gamma =\langle h|\alpha ,\beta \rangle =14$ $p=\gamma ^{r}=22$ Insecure exchange $p,q$ $q=\gamma ^{s}=2$ Let $t=pq^{-1}=22*12=11$ $p'=h^{r}g^{x}=15$ Insecure exchange $p',q'$ $q'=h^{s}g^{y}=4$ Secure $c=\langle p'q'^{-1}|\alpha ,\beta \rangle =11$ Each tests whether $c=11$ equals $t=11$, which passes. Even though $x=3$ does not equal $y=14$.

$(h^{a}=8\neq 1),(h^{b}=19\neq 1),(h^{\alpha }=11\neq 1),(h^{\beta }=15\neq 1),(p=22\neq q=2),(p'=15\neq q'=4)$
199.34.4.20 (talk) 19:57, 17 November 2014 (UTC)

Infact all a Mallory in the middle need do is choose ${\dot {b}},{\dot {\beta }}$ such that $h^{{\dot {b}}{\dot {\beta }}}\equiv 1$, then regardless of Alice and Bob's Choices of $a,b,\alpha ,\beta ,r,s$ Mallory's messages ${\dot {x}},{\dot {y}}$ would appear to be the same as $x,y$ respectively.
199.34.4.20 (talk) 22:10, 17 November 2014 (UTC)

update above counter example to match the current page's terminology

	Alice	Multiparty	Bob
1	Message $x=3$ Random $a=6,\alpha =9,r=11$	Public $p=23,h=5$	Message $y=14$ Random $b=15,\beta =17,s=20$
2	Test $h^{b}=19\neq 1$	Secure $g=\langle h|a,b\rangle =2$	Test $h^{a}=8\neq 1$
3	Test $h^{\beta }=15\neq 1$	Secure $\gamma =\langle h|\alpha ,\beta \rangle =14$	Test $h^{\alpha }=11\neq 1$
4	${\begin{aligned}P_{a}&=\gamma ^{r}=22\\Q_{a}&=h^{r}g^{x}=15\end{aligned}}$		${\begin{aligned}P_{b}&=\gamma ^{s}=2\\Q_{b}&=h^{s}g^{y}=4\end{aligned}}$
5		Insecure exchange $P_{a},Q_{a},P_{b},Q_{b}$
6		Secure $c=\left\langle \left.Q_{a}Q_{b}^{-1}\right|\alpha ,\beta \right\rangle =11$
7	Test ${\begin{aligned}(P_{a}=22)&\neq (P_{b}=2)\\(Q_{a}=15)&\neq (Q_{b}=4)\end{aligned}}$		Test ${\begin{aligned}(P_{a}=22)&\neq (P_{b}=2)\\(Q_{a}=15)&\neq (Q_{b}=4)\end{aligned}}$
8	Test $c=(P_{a}P_{b}^{-1}=22*12=11)$		Test $c=(P_{a}P_{b}^{-1}=22*12=11)$
both Alice and Bob compare step 6 results to step 8 and see that 11 matches; however this is a false positive because Alice's message 3 does not match Bob's mesage 14.

Notes:

• the counter example above comes from $h^{\alpha (x-y)}=1$ since

${\begin{aligned}\\&\alpha \beta ab(x-y)\\&=9*17*6*15*(3-14)\\&=(6*(3-14))*(9*17*15)\\&=(2*11)*(3*-1*9*17*15)\\&and\\&(5^{(2*11)})^{(3*-1*9*17*15)}\\&=1^{(3*-1*9*17*15)}\end{aligned}}$

• The newly rewritten final statment "Because of the random values stored in secret by the other party, neither party can force $c$ and $P_{a}P_{b}^{-1}$ to be equal unless $x$ equals $y$, in which case $h^{\alpha \beta ab(x-y)}=h^{0}=1$. This proves correctness", is now just a blatant misunderstanding of the mathematics behind this algorithm. Any of the following will force a false positive given $x\neq y$:
  • $h=1$
  • $h^{a}=1$
  • $h^{b}=1$
  • $h^{\alpha }=1$
  • $h^{\beta }=1$
  • $h^{(x-y)}=1$
  • $h^{a\alpha }=1$
  • $h^{ab}=1$
  • $h^{a\beta }=1$
  • $h^{a(x-y)}=1$
  • $h^{b\alpha }=1$
  • $h^{b\beta }=1$
  • $h^{b(x-y)}=1$
  • $h^{\alpha \beta }=1$
  • $h^{\alpha (x-y)}=1$
  • $h^{\beta (x-y)}=1$
  • $h^{ab\alpha }=1$
  • $h^{ab\beta }=1$
  • $h^{ab(x-y)}=1$
  • ... well you get where I'm going here, use the commutative property of the exponents to get $h^{blah}=1$ then $(h^{blah})^{rest}=(1)^{rest}=1$, where the existance of $h^{blah\neq 0}=1$ is guaranteed due to the properties of $h$ being a generator

199.34.4.20 (talk) 22:36, 29 March 2016 (UTC)

I believe you're applying the modulo too early. Here I reproduce your list along with my understanding of why your arguments don't apply.

Given $x\neq y$:

• $h=1$ — Not possible because the unit is not a generator.
• $h^{a}=1$ — Not possible because of testing. This rules out an exponent equaling zero or a multiple of the group order.
• $h^{b}=1$ — Ditto
• $h^{\alpha }=1$ — Ditto
• $h^{\beta }=1$ — Ditto
• $h^{(x-y)}=1$ — This is exactly what you're looking for, so doesn't pose a problem.
• $h^{a\alpha }=1$ — The product can only be equal to zero if one of the factors already is. It can only equal a multiple of the prime order of the group if either factor already is. Both cases are ruled out by earlier testing.
• $h^{ab}=1$ — Ditto
• $h^{a\beta }=1$ — Ditto
• $h^{b\alpha }=1$ — Ditto
• $h^{b\beta }=1$ — Ditto
• $h^{\alpha \beta }=1$ — Ditto
• $h^{ab\alpha }=1$ — Ditto
• $h^{ab\beta }=1$ — Ditto
• $h^{a(x-y)}=1$ — Since $a\neq 0{\pmod {p}}$ this is only possible when $(x-y)=0{\pmod {p}}$ which is what you're looking for.
• $h^{b(x-y)}=1$ — Ditto
• $h^{\alpha (x-y)}=1$ — Ditto
• $h^{\beta (x-y)}=1$ — Ditto
• $h^{ab(x-y)}=1$ — Ditto

This still leaves the possibility that the difference between $x$ and $y$ is any multiple of the group order $p$, I'm not sure whether/how that is handled in the protocol.

--2A02:1810:2586:B400:24A6:D6B8:F671:DD2B (talk) 16:37, 11 May 2020 (UTC)

Ideally, there should be additional tests to ensure that $\alpha$, $\beta$, $a$ and $b$ are coprime to $p-1$, but AFAIK, this is not possible with the partial knowledge, as the integer factorization of $p-1$ is not known in general. But checking that $\gamma ^{(p-1)/d}\neq 1$ for the smallest prime factors $d$ of $p-1$ and ditto for $g$ and restricting the size of $x$ and $y$ could avoid the issue.

With your counter-example, the issue comes from the fact that $a$ is divisible by 2 (thus is not coprime to $p-1$) and that $y$ is too large in the context of your counter-example ($x-y$ has a large prime factor common with $p$: 11). With that, $2\times 11$ is divisible by $p-1$, which yields the issue. Vincent Lefèvre (talk) 01:30, 25 December 2018 (UTC)

Clarify initial state

Article currently says "Let Alice and Bob fix a prime number p". Does "fix" mean that they agree upon the number? How? Out of band? Through previous communications? Is this "fix" subject to attack? For example can a Man In The Middle convince Alice that P=7 while convincing Bob that P=5? Have Alice and Bob verified each other's identities, and if so, how? Article needs more detail about the initial state, assumptions, and what if anything has come before. 68.110.104.114 (talk) 18:25, 20 November 2014 (UTC)

Yes "fix" does mean that they both agree upon a number to use beforehand, usually way out of band and static for all communications as is in the case of OTR which uses a well-known nothing up my sleeve number defined as group 5 in RFC 3526

FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
670C354E 4ABC9804 F1746C08 CA237327 FFFFFFFF FFFFFFFF

and $h=2$ 199.34.4.20 (talk) 19:30, 4 April 2016 (UTC)

Poorly writte

Article uses variable it never introduces, namely alpha and beta. In general, the article feels like it was written as a blob of cut & paste errors.