- Socialist millionaire
The Socialist Millionaire Problemcite conference
author =M. Jakobsson ,M. Yung
title = Proving without knowing: On oblivious, agnostic and blindfolded provers.
booktitle = Advances in Cryptology - CRYPTO '96, volume 1109 of Lecture Notes in Computer Science
pages = 186-200
date = 1996
location = Berlin] , 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 Problemcite 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] cite conference
authorA. 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] 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.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 attack s. 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
See also
*
Off-the-Record Messaging External links
* [http://www.cypherpunks.ca/otr/Protocol-v2-3.1.0.html Description of the OTR-Messaging Protocol version 2]
Wikimedia Foundation. 2010.
