Jump to content

Socialist millionaire problem: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
 
(40 intermediate revisions by 21 users not shown)
Line 1: Line 1:
{{short description|Cryptographic problem}}
In [[cryptography]], the '''socialist millionaire problem'''<ref name=socialist-millionaire-problem>{{cite conference
In [[cryptography]], the '''socialist millionaire problem'''<ref name=socialist-millionaire-problem>{{cite conference
| author = [[Markus Jakobsson]], [[Moti Yung]]
| author = [[Markus Jakobsson]], [[Moti Yung]]
| title = Proving without knowing: On oblivious, agnostic and blindfolded provers.
| title = Proving without knowing: On oblivious, agnostic and blindfolded provers.
| booktitle = Advances in Cryptology - CRYPTO '96, volume 1109 of Lecture Notes in Computer Science
| book-title = Advances in Cryptology CRYPTO '96, volume 1109 of Lecture Notes in Computer Science
| pages = 186–200
| pages = 186–200
| year = 1996
| year = 1996
Line 8: Line 9:
| doi = 10.1007/3-540-68697-5_15
| doi = 10.1007/3-540-68697-5_15
| url = http://cseweb.ucsd.edu/users/markus/proving.ps
| url = http://cseweb.ucsd.edu/users/markus/proving.ps
| doi-access = free
}}</ref> 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]]<ref name=millionaires-problem>{{cite conference
}}</ref> 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]]<ref name=millionaires-problem>{{cite conference
| author = [[Andrew Yao]]
| author = [[Andrew Yao]]
| title = Protocols for secure communications
| title = Protocols for secure communications
| booktitle = Proc. 23rd IEEE Symposium on Foundations of Computer Science (FOCS '82)
| book-title = Proc. 23rd IEEE Symposium on Foundations of Computer Science (FOCS '82)
| pages = 160–164
| pages = 160–164
| year = 1982
| year = 1982
Line 19: Line 21:
| author = [[Andrew Yao]]
| author = [[Andrew Yao]]
| title = How to generate and exchange secrets
| title = How to generate and exchange secrets
| booktitle = Proc. 27th IEEE Symposium on Foundations of Computer Science (FOCS '86)
| book-title = Proc. 27th IEEE Symposium on Foundations of Computer Science (FOCS '86)
| pages = 162–167
| pages = 162–167
| year = 1986
| year = 1986
Line 29: Line 31:


== Motivation ==
== Motivation ==

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


Line 36: Line 37:
Even if one of the parties is dishonest and deviates from the protocol, that person cannot learn anything more than if <math>x = y</math>.
Even if one of the parties is dishonest and deviates from the protocol, that person cannot learn anything more than if <math>x = y</math>.


An active attacker capable of arbitrarily interfering with Alice and Bob's communication (a [[man-in-the-middle attack|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.
An active attacker capable of arbitrarily interfering with Alice and Bob's communication ([[man-in-the-middle attack]]) 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 <math>x</math> and <math>y</math> contain information about both parties' long-term authentication public keys as well as information entered by the users themselves.
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 <math>x</math> and <math>y</math> contain information about both parties' long-term authentication public keys as well as information entered by the users themselves.


== Off-the-Record Messaging protocol ==
== Procedure ==
{{Main|Off-the-Record Messaging}}
[[File:SMP - Socialist Millionaire Protocol.png|thumb|State Machine Process for the Socialist Millionaire Protocol (SMP) implemented by GoldBug.sf.net Instant Messenger (http://goldbug.sf.net) and Spot-On Applikation (http://spot-on.sf.net).]]
[[File:SMP - Socialist Millionaire Protocol.png|thumb|State machine of a socialist millionaire protocol (SMP) implementation.]]
Let Alice and Bob fix a [[prime number]], <math>p</math>. All operations are performed modulo <math>p</math>, or in other words, in the [[multiplicative group]], <math>(\mathbb{Z}/p\mathbb{Z})^*</math>.


The protocol is based on [[group theory]].
For any element, <math>h</math>, of this multiplicative group, and any integers <math>a,b</math>, let <math>\langle h|a,b\rangle</math> denote the [[secure multiparty computation]] procedure returning <math>h^{ab}</math> to each party, whereby:
* Alice calculates <math>h^a</math> and sends it to Bob, who then calculates <math>h^{ab}</math>.
* Bob calculates <math>h^b</math> and sends it to Alice, who then calculates <math>h^{ba}</math>.
When <math>h</math> is a primitive root, this procedure is the [[Diffie-Hellman]] key exchange and is insecure against [[man-in-the-middle]] attacks.


A group of prime [[Order (group theory)|order]] <math>p</math> and a generator <math>h</math> are agreed upon ''a priori'', and in practice are generally fixed in a given implementation. For example, in the Off-the-Record Messaging protocol, <math>p</math> is a specific fixed 1,536-bit prime. <math>h</math> is then a generator of a prime-order subgroup of <math>(\mathbb{Z}/p\mathbb{Z})^*</math>, and all operations are performed modulo <math>p</math>, or in other words, in a subgroup of the [[multiplicative group]], <math>(\mathbb{Z}/p\mathbb{Z})^*</math>.
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.


By <math>\langle h|a,\,b\rangle</math>, denote the [[secure multiparty computation]], [[Diffie–Hellman–Merkle key exchange#Generalization to finite cyclic groups|Diffie–Hellman–Merkle key exchange]], which, for the integers, <math>a</math>, <math>b</math>, returns <math>h^{ab}</math> to each party:
A prime, <math>p</math>, and a generator (primitive root), <math>h</math>, of <math>(\mathbb{Z}/p\mathbb{Z})^*</math> are agreed on before the protocol, and in practice are generally fixed in a given implementation. For example, in the [[Off-the-Record Messaging]] protocol, <math>p</math> is a specific fixed 1536-bit prime.
* Alice calculates <math>h^a</math> and sends it to Bob, who then calculates <math>\left(h^a\right)^b \equiv h^{ab}</math>.
* Bob calculates <math>h^b</math> and sends it to Alice, who then calculates <math>\left(h^b\right)^a \equiv h^{ba}</math>.
<math>h^{ab} \equiv h^{ba}</math> as multiplication in <math>(\mathbb{Z}/p\mathbb{Z})^*</math> is associative. Note that this procedure is insecure against [[man-in-the-middle]] attacks.


The socialist millionaire protocol<ref name=socialist-millionaire-protocol>{{cite journal
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 <math>a</math>, <math>b</math>, or <math>\beta</math> to be zero. To solve this problem, each party must check during the [[Diffie-Hellman]] exchanges that none of the <math>h^a, h^b, h^\alpha,</math> or <math>h^\beta</math> that they receive is equal to 1. It is also necessary to check that <math>P_a \neq P_b</math> and <math>Q_a \neq Q_b</math>.
| author = Fabrice Boudot, Berry Schoenmakers, Jacques Traoré
| title = A Fair and Efficient Solution to the Socialist Millionaires' Problem
| journal = Discrete Applied Mathematics
| volume = 111
| number = 1
| pages = 23–36
| year = 2001
| doi = 10.1016/S0166-218X(00)00342-5
| url = https://www.win.tue.nl/~berry/papers/dam.pdf
}}</ref> 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.

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 <math>a</math>, <math>b</math>, <math>\alpha</math>, or <math>\beta</math> to be zero. To solve this problem, each party must check during the [[Diffie-Hellman]] exchanges that none of the <math>h^a</math>, <math>h^b</math>, <math>h^\alpha</math>, or <math>h^\beta</math> that they receive is equal to 1. It is also necessary to check that <math>P_a \neq P_b</math> and <math>Q_a \neq Q_b</math>.


{| class="wikitable" style="text-align:center;"
{| class="wikitable" style="text-align:center;"
Line 77: Line 90:
|-
|-
| 4
| 4
| Test <math>h^a \neq g</math>, <math>h^\alpha \neq \gamma</math>
| Test <math>h^b \neq 1</math>, <math>h^\beta \neq 1</math>
|
|
| Test <math>h^b \neq g</math>, <math>h^\beta \neq \gamma</math>
| Test <math>h^a \neq 1</math>, <math>h^\alpha \neq 1</math>
|-
|-
| 5
| 5
| Insecure send <math>P_a = \gamma^r</math>
| <math>\begin{align}
P_a &= \gamma^r \\
|
Q_a &= h^r g^x
| Insecure send <math>P_b = \gamma^s</math>
\end{align}</math>
|
| <math>\begin{align}
P_b &= \gamma^s \\
Q_b &= h^s g^y
\end{align}</math>
|-
|-
| 6
| 6
| Insecure send <math>Q_a = h^r g^x</math>
|
|
| Insecure send <math>Q_b = h^s g^y</math>
| Insecure exchange <math>P_a, Q_a, P_b, Q_b</math>
|
|-
|-
| 7
| 7
| Test <math>P_a \neq P_b</math>, <math>Q_a \neq Q_b</math>
|
|
| Test <math>P_a \neq P_b</math>, <math>Q_a \neq Q_b</math>
| Secure <math>c = \left\langle\left. Q_aQ_b^{-1} \right| \alpha, \beta \right\rangle</math>
|
|-
|-
| 8
| 8
| Test <math>P_a \neq P_b</math>, <math>Q_a \neq Q_b</math>
|
|
| Secure <math>c = \left\langle Q_aQ_b^{-1}|\alpha, \beta \right\rangle</math>
| Test <math>P_a \neq P_b</math>, <math>Q_a \neq Q_b</math>
|
|-
|-
| 9
| 9
| Test <math>c = P_aP_b^{-1}</math>
| Test <math>c = P_a{P_b}^{-1}</math>
|
|
| Test <math>c = P_aP_b^{-1}</math>
| Test <math>c = P_a{P_b}^{-1}</math>
|}
|}



Note that:
Note that:
:<math>\begin{align}
:<math>\begin{align}
PQ^{-1} &= \gamma^r \gamma^{-s} = \gamma^{r - s} \\
P_a{P_b}^{-1} &= \gamma^r \gamma^{-s} = \gamma^{r - s} \\
&= h^{\alpha\beta(r - s)}
&= h^{\alpha\beta(r - s)}
\end{align}</math>
\end{align}</math>


and therefore
and therefore
:<math>\begin{align}
:<math>\begin{align}
c &= \left(Q_aQ_b^{-1}\right)^{\alpha\beta} \\
c &= \left(Q_aQ_b^{-1}\right)^{\alpha\beta} \\
&= \left(h^r g^x h^{-s} g^{-y}\right)^{\alpha\beta}
&= \left(h^r g^x h^{-s} g^{-y}\right)^{\alpha\beta}
= \left(h^{r - s} g^{x - y}\right)^{\alpha\beta} \\
= \left(h^{r - s} g^{x - y}\right)^{\alpha\beta} \\
&= \left(h^{r - s} h^{ab(x - y)}\right)^{\alpha\beta}
&= \left(h^{r - s} h^{ab(x - y)}\right)^{\alpha\beta}
= h^{\alpha\beta(r - s)} h^{\alpha\beta ab(x - y)} \\
= h^{\alpha\beta(r - s)} h^{\alpha\beta ab(x - y)} \\
&= P_aP_b^{-1} h^{\alpha\beta ab(x - y)}
&= \left(P_a{P_b}^{-1}\right) h^{\alpha\beta ab(x - y)}
\end{align}</math>.
\end{align}</math>.


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


==See also==
==See also==
* [[Off-the-Record Messaging]]
* [[Zero-knowledge proof]]
* [[Zero-knowledge proof]]


==References==
==References==
{{reflist}}
<references/>


==External links==
==External links==
* [http://www.cypherpunks.ca/otr/Protocol-v2-3.1.0.html Description of the OTR-Messaging Protocol version 2]
* [http://www.cypherpunks.ca/otr/Protocol-v2-3.1.0.html Description of the OTR-Messaging Protocol version 2]
* [http://twistedoakstudios.com/blog/Post3724_explain-it-like-im-five-the-socialist-millionaire-problem-and-secure-multi-party-computation The Socialist Millionaire Problem - Explain it like I'm Five]
* {{Webarchive|url=https://web.archive.org/web/20221225214935/http://twistedoakstudios.com/blog/Post3724_explain-it-like-im-five-the-socialist-millionaire-problem-and-secure-multi-party-computation|date=December 25, 2022|title=Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation}}
* [http://goldbug.sf.net Goldbug Messenger, which uses an implementation the Socialist Millionaire Protocol]
* [http://goldbug.sf.net Goldbug Messenger, which uses an implementation the Socialist Millionaire Protocol]


[[Category:Cryptographic protocols]]
[[Category:Theory of cryptography]]

Latest revision as of 20:35, 24 July 2024

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 and , respectively. Alice and Bob wish to learn if 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 and , not even whether .

Even if one of the parties is dishonest and deviates from the protocol, that person cannot learn anything more than if .

An active attacker capable of arbitrarily interfering with Alice and Bob's communication (man-in-the-middle attack) 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 and contain information about both parties' long-term authentication public keys as well as information entered by the users themselves.

Off-the-Record Messaging protocol

[edit]
State machine of a socialist millionaire protocol (SMP) implementation.

The protocol is based on group theory.

A group of prime order and a generator are agreed upon a priori, and in practice are generally fixed in a given implementation. For example, in the Off-the-Record Messaging protocol, is a specific fixed 1,536-bit prime. is then a generator of a prime-order subgroup of , and all operations are performed modulo , or in other words, in a subgroup of the multiplicative group, .

By , denote the secure multiparty computation, Diffie–Hellman–Merkle key exchange, which, for the integers, , , returns to each party:

  • Alice calculates and sends it to Bob, who then calculates .
  • Bob calculates and sends it to Alice, who then calculates .

as multiplication in is associative. Note that this procedure is insecure against man-in-the-middle attacks.

The socialist millionaire protocol[4] 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.

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 , , , or to be zero. To solve this problem, each party must check during the Diffie-Hellman exchanges that none of the , , , or that they receive is equal to 1. It is also necessary to check that and .

Alice Multiparty Bob
1 Message
Random
Public Message
Random
2 Secure
3 Secure
4 Test , Test ,
5
6 Insecure exchange
7 Secure
8 Test , Test ,
9 Test Test

Note that:

and therefore

.

Because of the random values stored in secret by the other party, neither party can force and to be equal unless equals , in which case . This proves correctness.

See also

[edit]

References

[edit]
  1. ^ Markus Jakobsson, Moti Yung (1996). "Proving without knowing: On oblivious, agnostic and blindfolded provers.". 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.
  2. ^ Andrew Yao (1982). "Protocols for secure communications" (PDF). Proc. 23rd IEEE Symposium on Foundations of Computer Science (FOCS '82). pp. 160–164. doi:10.1109/SFCS.1982.88.
  3. ^ Andrew Yao (1986). "How to generate and exchange secrets" (PDF). Proc. 27th IEEE Symposium on Foundations of Computer Science (FOCS '86). pp. 162–167. doi:10.1109/SFCS.1986.25.
  4. ^ Fabrice Boudot, Berry Schoenmakers, Jacques Traoré (2001). "A Fair and Efficient Solution to the Socialist Millionaires' Problem" (PDF). Discrete Applied Mathematics. 111 (1): 23–36. doi:10.1016/S0166-218X(00)00342-5.{{cite journal}}: CS1 maint: multiple names: authors list (link)
[edit]