Yao's Millionaires' problem
Yao's Millionaires' problem is a secure multi-party computation problem introduced in 1982 by computer scientist and computational theorist Andrew Yao. The problem discusses two millionaires, Alice and Bob, who are interested in knowing which of them is richer without revealing their actual wealth. This problem is analogous to a more general problem where there are two numbers formula_1 and formula_2 and the goal is to determine whether the inequality formula_3 is true or false without revealing the actual values of formula_1 and formula_2. The Millionaires' problem is an important problem in cryptography, the solution  of which is used in e-commerce and data mining. Commercial applications sometimes have to compare numbers that are confidential and whose security is important. Many solutions have been introduced for the problem. The first solution, presented by Yao, is exponential in time and space. Protocols and proof. The protocol of Hsiao-Ying Lin and Wen-Guey Tzeng. Let formula_6 be a binary string of length "n". Denote 0-encoding of "s" as formula_7 and 1-encoding of "s" as formula_8 Then, the protocol is based on the following claim: The protocol leverages this idea into a practical solution to  Yao's Millionaires' problem by performing a private set intersection between formula_10 and formula_11. The protocol of Ioannidis and Ananth. The protocol uses a variant of oblivious transfer, called 1-2 oblivious transfer. In that transfer one bit is transferred in the following way: a sender has two bits formula_14 and formula_15. The receiver chooses formula_16, and the sender sends formula_17 with the oblivious transfer protocol such that To describe the protocol, Alice's number is indicated as formula_1, Bob's number as formula_2, and it is assumed that the length of their binary representation is less than formula_22 for  some formula_23. The protocol takes the following steps. Proof. Correctness. Bob calculates the final result from formula_80, and the result depends on formula_81. "K", and therefore "c" as well, can be split into 3 parts. The left part doesn't affect the result. The right part has all the important information, and in the middle is a sequence of zeros that separates those two parts. The length of each partition of "c" is linked to the security scheme. For every "i", only one of formula_82 has non-zero right part, and it is formula_83 if formula_44, and formula_85 otherwise. In  addition, if formula_86, and formula_87 has a non-zero right part, then formula_88 has also a non-zero right part, and the two leftmost bits of this right part will be the same as the one of formula_89. As a result, the right part of "c" is a function of the entries Bob transferred correspond to the unique bits in "a" and "b", and the only bits in the right part in "c" that are not random are the two leftmost, exactly the bits that determines the result of formula_90, where "i" is the highest-order bit in which "a  and b" differ. In the end, if formula_90, then those two leftmost bits will be 11, and Bob will answer that formula_3. If the bits are 10, then formula_93, and he will answer formula_79. If formula_95, then there will be no right part in "c", and in this case the two leftmost bits in "c" will be 11, and will indicate the result. Security. The information Bob sends to Alice is secure because it is sent through oblivious transfer, which is secure. Bob gets 3 numbers from Alice: Complexity. The complexity of the protocol is formula_99. Alice constructs "d"-length number  for each bit of "a", and Bob calculates XOR "d" times of "d"-length numbers. The complexity of those operations is formula_99. The communication part takes also formula_99. Therefore, the complexity of the protocol is formula_102