1. Protocols and Proof

1.1. The Protocol of Hsiao-Ying Lin and Wen-Guey Tzeng^[1]

Let ${\displaystyle s=s_n{s}_{n-1}\dots s_1\in \{0,1{\}}^n}$ be a binary string of length n.

Denote 0-encoding of s as ${\displaystyle S_s^0=\{s_n{s}_{n-1}\dots s_{i+1}1|s_i=0;1\le i\le n\}}$ and 1-encoding of s as ${\displaystyle S_s^1=\{s_n{s}_{n-1}\dots s_i|s_i=1;1\le i\le n\}.}$

Then, the protocol is based on the following claim: Assume a and b are binary strings of length n-bits. Then, ${\displaystyle a>b}$ if the sets ${\displaystyle S_a^1}$ and ${\displaystyle S_b^0}$ have a common element (where here a and b are the binary encodings of the corresponding integers).

The protocol leverages this idea into a practical solution to Yao's Millionaires' problem by performing a private set intersection between ${\displaystyle S_a^1}$ and ${\displaystyle S_b^0}$.

1.2. The Protocol of Loannidis & Ananth^[2]

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 ${\displaystyle S_0}$ and ${\displaystyle S_1}$. The receiver chooses ${\displaystyle i\in \{0,1\}}$ and the sender sends ${\displaystyle S_i}$ with the oblivious transfer protocol such that

1. the receiver doesn't get any information about ${\displaystyle S_{(1-i)}}$,
2. the value of ${\displaystyle i}$ is not exposed to the sender.

To describe the protocol, Alice's number is indicated as ${\displaystyle a}$ and Bob's number as ${\displaystyle b}$ and assume that the length of their binary representation is less than ${\displaystyle d}$ for some ${\displaystyle d\in N}$. The protocol takes the following steps.

1. Alice creates a matrix ${\displaystyle K}$ of size ${\displaystyle d\times 2}$ of ${\displaystyle k}$-bit numbers, where ${\displaystyle k}$ is the length of the key in the oblivious transfer protocol. In addition, she chooses two random numbers ${\displaystyle u}$ and ${\displaystyle v}$ where ${\displaystyle 0\le u<2k}$ and ${\displaystyle v\le k}$.
2. ${\displaystyle K_{ijl}}$ will be the ${\displaystyle l}$-th bit of the number which appears in cell ${\displaystyle K_{ij}}$ (where ${\displaystyle l=0}$ indicates the least significant bit). In addition, ${\displaystyle a_i}$ is denoted as the ${\displaystyle i}$-th bit of Alice's number ${\displaystyle a}$. For every ${\displaystyle i}$, ${\displaystyle 1\le i\le d}$ Alice does the following actions.
   1. For every bit ${\displaystyle j\ge v}$ she sets ${\displaystyle K_{i1j}}$ and ${\displaystyle K_{i2j}}$ to random bits.
   2. If ${\displaystyle a_i=1}$ let ${\displaystyle l=1}$ otherwise let ${\displaystyle l=2}$ and for every ${\displaystyle j,0\le j\le 2\cdot i-1}$ set ${\displaystyle K_{ilj}}$ to a random bit.
   3. For ${\displaystyle m=2\cdot i}$ set ${\displaystyle K_{il(m+1)}=1}$ and ${\displaystyle K_{ilm}}$ to ${\displaystyle a_i}$.
   4. For every ${\displaystyle i,1\le i<d}$, ${\displaystyle S_i}$ will be a random ${\displaystyle k}$-bit number and ${\displaystyle S_d}$ will be another number of ${\displaystyle k}$ bits where all bits except the last two are random and the last two are calculated as ${\displaystyle S_{d(k-1)}=1\oplus \underset{j=1}{\overset{d-1}{⨁}}{S}_{j(k-1)}\oplus \underset{j=1}{\overset{d}{⨁}}{K}_{j1(k-1)}}$ and ${\displaystyle S_{d(k-2)}=1\oplus \underset{j=1}{\overset{d-1}{⨁}}{S}_{j(k-2)}\oplus \underset{j=1}{\overset{d}{⨁}}{K}_{j1(k-2)}}$, where ${\displaystyle ⨁}$ is the bitwise XOR operation.
   5. For ${\displaystyle l=1,2}$ set ${\displaystyle K_{ij}^{\prime }=rot(K_{il}\oplus S_i,u)}$. Where ${\displaystyle rot(x,t)}$ indicates the bitwise rotation of ${\displaystyle x}$ to the left by ${\displaystyle t}$ bits.
3. For every ${\displaystyle i}$, ${\displaystyle 0\le i\le d}$ Bob transfers ${\displaystyle K_{il}^{\prime }}$ with the oblivious transfer protocol where ${\displaystyle l=b_i+1}$ and ${\displaystyle b_i}$ is the ${\displaystyle i}$-th bit of ${\displaystyle b}$.
4. Alice sends to Bob ${\displaystyle N=rot(\underset{j=1}{\overset{d}{⨁}}{S}_j,u)}$.
5. Bob calculates the bitwise XOR of all the numbers he got in step 3 and ${\displaystyle N}$ from step 4. Bob scans the result from left to right until he finds a large sequence of zero bits. Let ${\displaystyle c}$ be the bit to the right of that sequence (${\displaystyle c}$ is non zero). If the bit to the right of ${\displaystyle c}$ equals 1 then ${\displaystyle a\ge b}$. otherwise ${\displaystyle a<b}$.

1.3. Proof

Correctness

Bob calculates the final result from ${\displaystyle N\oplus \underset{i=1}{\overset{d}{⨁}}{K}_{i(b_i+1)}^{\prime }=rol(\underset{i=1}{\overset{d}{⨁}}{K}_{i(b_i+1)},u)}$ and the result depends on ${\displaystyle c=\underset{i=1}{\overset{d}{⨁}}{K}_{i(b_i+1)}}$. 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 there is a sequence of zeros what separate those two parts. The length of each partition of c is linked to the security scheme.

For every i, only one of ${\displaystyle K_{i1},K_{i2}}$ has non zero right part and it is ${\displaystyle K_{i1}}$ if ${\displaystyle a_i=1}$ and ${\displaystyle K_{i2}}$ otherwise. In addition, if ${\displaystyle i>j}$ and ${\displaystyle K_{il}}$ has a non zero right part then ${\displaystyle K_{il}\oplus K_{jl}}$ has also a non zero right part and the two leftmost bits of this right part will be the same as the one of ${\displaystyle A_{il}}$. 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 which are not random are the two leftmost, Exactly the bits which determines the result of ${\displaystyle a_i>b_i}$ where i is the highest order bit in which a and b differ. In the end, if ${\displaystyle a_i>b_i}$ then those two leftmost bits will be 11 and Bob will answer that ${\displaystyle a\ge b}$. If the bits are 10 then ${\displaystyle a_i<b_i}$ and he will answer a<b. If a=b 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,

1. ${\displaystyle rol(K_{i(1+b_i)}\oplus S_i,u)}$ for every ${\displaystyle i}$ Bob receives one such number and ${\displaystyle S_i}$ is random so no secure information is transformed,
2. N, This is an XOR of random numbers and therefore reveals no information. The relevant information is revealed only after calculating c and,
3. c, The same goes for c. The left part of c is random and the right part is random as well except from the two leftmost bits. Deducing any information from those bits requires guessing some other values and the chance of guessing them correct is very low.

1.4. Complexity

The complexity of the protocol is ${\displaystyle O(d^2)}$. 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 ${\displaystyle O(d^2)}$. The communication part takes also ${\displaystyle O(d^2)}$. Therefore, the complexity of the protocol is ${\displaystyle O(d^2).}$