Socialist millionaire

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In cryptography, the socialist millionaire problem[1] is one in which two millionaires want to determine if their wealth is equal, without disclosing any information about their riches to each other. It is a variant of the Millionaire's Problem[2][3] whereby two millionaires wish to compare their riches to determine who has the most wealth, without disclosing any information about their riches to each other.

It is often used as a cryptographic protocol that allows two parties to verify the identity of the remote party through the use of a shared secret, avoiding a man-in-the-middle attack without the inconvenience of manually comparing public key fingerprints through an outside channel. In effect a relatively weak password/passphrase in natural language can be used.

Motivation[edit]

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

A passive attacker, simply spying on the messages Alice and Bob exchange learns nothing about x and y, not even whether x = y.

Even if one of the parties is dishonest, and deviates from the protocol, he or she cannot learn anything more than if x = y.

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.

Therefore, the protocol can be used to authenticate whether two parties have the same secret information. Popular instant message cryptography package Off-the-Record Messaging uses the Socialist Millionaire protocol for authentication, in which the secrets x and y contain information about both parties' long-term authentication public keys, as well as information entered by the users themselves.

Procedure[edit]

Let Alice and Bob fix a prime number p. All operations are performed modulo p, or in other words, in the multiplicative group (\mathbb{Z}/p\mathbb{Z})^*.

For any element h of this multiplicative group, and any integers a,b, let \langle h|a,b\rangle denote the secure multiparty computation procedure returning h^{ab} to each party, whereby:

  • Alice calculates h^a and sends it to Bob, who raises it to the power b.
  • Bob calculates h^b and sends it to Alice, who raises it to the power a.

When h is a primitive root, this procedure is the Diffie-Hellman key exchange and is insecure against man-in-the-middle attacks.

The Socialist millionaire protocol only has a few steps that are not part of the above procedure, and the security of each relies on the difficulty of the discrete logarithm problem, just as the above does. All sent values also include zero-knowledge proofs that they were generated according to protocol.

A prime p and a generator (primitive root) h of (\mathbb{Z}/p\mathbb{Z})^* are agreed on before the protocol, and in practice are generally fixed in a given implementation. For example, in Off-the-Record Messaging p is a specific fixed 1536-bit prime.

Part of the security also relies on random secrets. However, as written below, the protocol is vulnerable to poisoning if Alice or Bob chooses any of a,\alpha,b or \beta to be zero. To solve this problem, each party must check during the Diffie-Hellman exchanges that none of the h^a,h^b,h^\alpha or h^\beta that they receive is equal to one. It is also necessary to check that p \neq q and p' \neq q'.

Alice Multiparty Bob
Message x
Random a,\alpha,r
Public p,h Message y
Random b,\beta,s

Secure g=\langle h|a,b\rangle

Secure \gamma=\langle h|\alpha,\beta\rangle
p=\gamma^r Insecure exchange p,q q=\gamma^s

Let t=pq^{-1}
p'=h^rg^x Insecure exchange p',q' q'=h^sg^y

Secure c=\langle p'q'^{-1}|\alpha,\beta\rangle
Each tests whether c equals t.

Note that: t=pq^{-1}=\gamma^r\gamma^{-s}=\gamma^{r-s}=h^{\alpha\beta(r-s)} and therefore c=(p'q'^{-1})^{\alpha\beta}=(h^rg^xh^{-s}g^{-y})^{\alpha\beta}
=(h^{r-s}g^{x-y})^{\alpha\beta}= (h^{r-s}h^{ab(x-y)})^{\alpha\beta}=h^{\alpha\beta(r-s)}h^{\alpha\beta ab(x-y)}=th^{\alpha\beta ab(x-y)}.

Because of the random values stored in secret by the other party, neither party can force c and t to be equal unless x equals y, in which case h^{\alpha\beta ab(x-y)}=h^0=1. This proves correctness.

See also[edit]

References[edit]

  1. ^ Markus Jakobsson, Moti Yung (1996). "Advances in Cryptology - CRYPTO '96, volume 1109 of Lecture Notes in Computer Science". Berlin. pp. 186–200. doi:10.1007/3-540-68697-5_15.  |chapter= ignored (help)
  2. ^ Andrew Yao (1982). "Proc. 23rd IEEE Symposium on Foundations of Computer Science (FOCS '82)". pp. 160–164. doi:10.1109/SFCS.1982.88.  |chapter= ignored (help)
  3. ^ Andrew Yao (1986). "Proc. 27th IEEE Symposium on Foundations of Computer Science (FOCS '86)". pp. 162–167. doi:10.1109/SFCS.1986.25.  |chapter= ignored (help)

External links[edit]