Jump to content

Socialist millionaire problem: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Micah (talk | contribs)
46 edits
clarifying information about the problem
Micah (talk | contribs)
46 edits
add references
Line 1: Line 1:
{{crypto-stub}}
{{crypto-stub}}


The '''Socialist Millionaire Problem'''<ref name=socialist-millionaire-problem>{{cite conference
⚫
The '''Socialist Millionaire''' Problem, or Tiercé problem, 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 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.
| author = [[M. Jakobsson]], [[M. Yung]]
| title = Proving without knowing: On oblivious, agnostic and blindfolded provers.
| booktitle = Advancecs in Cryptology - CRYPTO '96, volume 1109 of Lecture Notes in Computer Science
| pages = 186-200
| date = 1996
| location = Berlin
⚫
}}</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 = [[A. Yao]]
| title = Protocols for secure communications
| booktitle = Proc. 23rd IEEE Symposium on Foundations of Computer Science (FOCS '82)
| pages = 160-164
| date = 1982
}}</ref><ref name=how-to-generate-secrets>{{cite conference
| author [[A. Yao]]
| title = How to generate and exchange secrets
| booktitle = Proc. 27th IEEE Symposium on Foundations of Computer Science (FOCS '86)
| pages = 162-167
| date = 1986
}}</ref> 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. [[Brute force attack]]s are avoided by demanding user input on both sides prior to the check itself.
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. [[Brute force attack]]s are avoided by demanding user input on both sides prior to the check itself.
Line 41: Line 60:
If everything is done correctly, then R<sub>ab</sub> should hold the value of (P<sub>a</sub> / P<sub>b</sub>) times (g<sub>2</sub><sup>a<sub>3</sub>b<sub>3</sub></sup>)<sup>(x - y)</sup>, which means that the test at the end of the protocol will only succeed if x equals y. Further, since g<sub>2</sub><sup>a<sub>3</sub>b<sub>3</sub></sup> is a random number not known to any party, if x is not equal to y, no other information is revealed.
If everything is done correctly, then R<sub>ab</sub> should hold the value of (P<sub>a</sub> / P<sub>b</sub>) times (g<sub>2</sub><sup>a<sub>3</sub>b<sub>3</sub></sup>)<sup>(x - y)</sup>, which means that the test at the end of the protocol will only succeed if x equals y. Further, since g<sub>2</sub><sup>a<sub>3</sub>b<sub>3</sub></sup> is a random number not known to any party, if x is not equal to y, no other information is revealed.

==References==
<references/>


== See also ==
== See also ==

Revision as of 23:41, 10 September 2008

Stub icon

This cryptography-related article is a stub. You can help Wikipedia by expanding it.

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. Brute force attacks are avoided by demanding user input on both sides prior to the check itself.

This protocol is used as part of Off-the-Record Messaging.

Example

While data messages are being exchanged, either Alice or Bob may run Socialist Milllionaire Protocol (SMP) to detect impersonation or man-in-the-middle attacks. All exponentiations are done modulo a particular 1536-bit prime, and g1 is a generator of that group. All sent values include zero-knowledge proofs that they were generated according to this protocol, as indicated in the detailed description below.

Suppose Alice and Bob have secret information x and y respectively, and they wish to know whether x equals y. The Socialist Millionaires' Protocol allows them to compare x and y without revealing any information other than whether x and y are equal. For OTR, the secrets contain information about both parties' long-term authentication public keys, as well as information entered by the users themselves. If x equals y, this means that Alice and Bob entered the same secret information, and so must be the same entities who established that secret to begin with.

Assuming that Alice begins the exchange: 

* Alice: 
	 1. Picks random exponents a2 and a3
	 2. Sends Bob g2a = g1a2 and g3a = g1a3
* Bob:
	 1. Picks random exponents b2 and b3
	 2. Computes g2b = g1b2 and g3b = g1b3
	 3. Computes g2 = g2ab2 and g3 = g3ab3
	 4. Picks random exponent r
	 5. Computes Pb = g3r and Qb = g1r g2y
	 6. Sends Alice g2b, g3b, Pb and Qb
* Alice:
	 1. Computes g2 = g2ba2 and g3 = g3ba3
	 2. Picks random exponent s
	 3. Computes Pa = g3s and Qa = g1s g2x
	 4. Computes Ra = (Qa / Qb)a3
	 5. Sends Bob Pa, Qa and Ra
* Bob:
	 1. Computes Rb = (Qa / Qb)b3
	 2. Computes Rab = Rab3
	 3. Checks whether Rab equals (Pa / Pb)
	 4. Sends Alice Rb
* Alice:
	 1. Computes Rab = Rba3
	 2. Checks whether Rab equals (Pa / Pb)

If everything is done correctly, then Rab should hold the value of (Pa / Pb) times (g2a3b3)(x - y), which means that the test at the end of the protocol will only succeed if x equals y. Further, since g2a3b3 is a random number not known to any party, if x is not equal to y, no other information is revealed.

References

  1. ^ M. Jakobsson, M. Yung (1996). "Proving without knowing: On oblivious, agnostic and blindfolded provers.". Advancecs in Cryptology - CRYPTO '96, volume 1109 of Lecture Notes in Computer Science. Berlin. pp. 186–200. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
  2. ^ A. Yao (1982). "Protocols for secure communications". Proc. 23rd IEEE Symposium on Foundations of Computer Science (FOCS '82). pp. 160–164. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
  3. ^ "How to generate and exchange secrets". Proc. 27th IEEE Symposium on Foundations of Computer Science (FOCS '86). 1986. pp. 162–167. {{cite conference}}: Text "author A. Yao" ignored (help)

See also

Retrieved from "https://en.wikipedia.org/w/index.php?title=Socialist_millionaire_problem&oldid=237604220"