In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, the socialist millionaire 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.
It is often used as a
cryptographic protocol
A security protocol (cryptographic protocol or encryption protocol) is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods, often as sequences of cryptographic primitives. A protocol describe ...
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
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 (a
man-in-the-middle
In cryptography and computer security, a man-in-the-middle, monster-in-the-middle, machine-in-the-middle, monkey-in-the-middle, meddler-in-the-middle, manipulator-in-the-middle (MITM), person-in-the-middle (PITM) or adversary-in-the-middle (AiTM) ...
) 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
Off-the-Record Messaging (OTR) is a cryptographic protocol that provides encryption for instant messaging conversations. OTR uses a combination of AES symmetric-key algorithm with 128 bits key length, the Diffie–Hellman key exchange with 1536 bi ...
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
![SMP - Socialist Millionaire Protocol](https://upload.wikimedia.org/wikipedia/commons/8/86/SMP_-_Socialist_Millionaire_Protocol.png)
The protocol is based on
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
.
A group of prime
order
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...
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
In mathematics and group theory, the term multiplicative group refers to one of the following concepts:
*the group under multiplication of the invertible elements of a field, ring, or other structure for which one of its operations is referred to ...
,
.
By
, denote the
secure multiparty computation
Secure multi-party computation (also known as secure computation, multi-party computation (MPC) or privacy-preserving computation) is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their ...
,
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
In cryptography and computer security, a man-in-the-middle, monster-in-the-middle, machine-in-the-middle, monkey-in-the-middle, meddler-in-the-middle, manipulator-in-the-middle (MITM), person-in-the-middle (PITM) or adversary-in-the-middle (AiTM) ...
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
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
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
.
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
*
Zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information a ...
References
{{reflist
External links
Description of the OTR-Messaging Protocol version 2The Socialist Millionaire Problem - Explain it like I'm FiveGoldbug Messenger, which uses an implementation the Socialist Millionaire Protocol
Theory of cryptography