# Yao's millionaire problem

In 1982, Andrew Yao proposed the millionaire problem[1], which discussed how could two millionaires determine who is richer while keeping their actual wealth private.

# 1 secure multiparty computation

Secure multiparty computation(SMC), or secure computation, secure function evaluation(SFE) is an abstract of this kind of problems. SMC asks for protocols that enable several parties collaboratively compute a function without exposing their input.

More specifically, a set of parties, $$P_1, P_2, ...,P_n$$, each of whom has a input $$x_i, 1\leq i \leq n$$, they want to evaluate $$y=f(x_1, x_2, ..., x_n)$$ while keeping $$x_i$$ in private. Yao's millionaire problem is SMC with comparison as $$f$$.

# 2 Lin-Tzeng protocol

Lots of solutions have been proposed in literature to solve the millionaire problem. We only discusses the homomorphic encryption based solution proposed by Lin and Tzeng[2].

The sketch of Lin-Tzeng protocol[2] is, firstly encoding $$x,y$$(the millionaires' wealth) such that $$S_x\cap S_y\neq \emptyset \Leftrightarrow x>y$$, then the problem is how to determine the private set intersection of $$S_x,S_y$$, which is solved by a homomorphic encryption based subprotocol.

## 2.1 0-encoding and 1-encoding

For $$s=s_ns_{n-1}...s_0\in \{0,1\}^n$$, 0-encoding of $$s$$ is the set $$S_s^0=\{s_ns_{n-1}...s_{i+1}1|s_i=0, 1\leq i\leq n\}$$, invert the least significant bit of all prefix of $$s$$ tailing 0. And 1-encoding of $$s$$ is $$S_s^1=\{s_ns_{n-1}...s_{i}|s_i=1, 1\leq i\leq n\}$$, all prefix of $$s$$ tailing 1. After encoding, $$x\gt y$$ if and only if $$S_x^1\cap S_y^0\neq \emptyset$$(we skip the proof here which is trivial).

## 2.2 multiplicative homomorphism

Homomorphism is a property provided by cryptosystems, within which, the operation on plaintext can be mapped into another operation on ciphertext, $$E(x\times y)=E(x)\cdot E(y)$$, so that we can outsource computation to an untrusted third party(cloud maybe). For instance, within textbook RSA, $$E(xy)=(xy)^e\ mod\ N=x^e y^e\ mod\ N=E(x)E(y)$$. We can let the cloud do the multiplication while keeping the input and output in private.

Additive homomorphism is quite the same. If a cryptosystem simultaneously provides additive and multiplicative homomorphism, we say it is fully homomorphic which is complete for all computable functions theoretically.

## 2.3 the protocol

1. Alice sends a matrix $$T_{2\times n}$$ to Bob, where $$T[x_i,i]=E(1), T[\bar{x_i},i]=E(r_i)$$($$r_i$$ is random).

2. On receiving $$T_{2\times n}$$, Bob computes $$c_t=T[t_n,n]\cdot T[t_{n-1},n-1]...\cdot T[t_i, i]$$ for each $$t=t_nt_{n-1}...t_i\in S_y^0$$, and chooses another $$n-|S_y^0|$$ random ciphertext forming a new set $$\{c_1,c_2,...,c_n\}$$ which will be sent back to Alice after random permutation.

3. Alice decrypts all $$c_i$$, checks whether some of them are $$1$$ which indicates $$x\gt y$$ and tells Bob the result.

If Bob responds $$\{c_t\}$$ directly without filling another $$n-|S_y^0|$$ random ciphertext, $$\#0s$$ of $$y$$ is leaked.

Multiplicative homomorphic cipher in the protocol can be replaced by an additive homomorphic cipher, and use $$E(0)$$ other than $$E(1)$$ simultaneously.

## 2.4 correctness and security

Because of multiplicative homomorphism, if $$D(c_t)=1$$, then $$T[t_n,n],T[t_{n-1},n-1],...T[t_i, i]$$ are all ciphertext of $$1$$ with high probability, which means $$x_n=t_n,x_{n-1}=t_{n-1},...,x_i=t_i$$.

All messages observed by outside attackers are encrypted. Bob cannot differentiate $$E(1)$$ and $$E(r_i)$$ such that he gets no idea of $$x$$. With $$\{c_t\}$$, Alice also gains no information of $$y$$ if she follows the protocol.

# References

[1] A.C. Yao, Protocols for secure computations, in: Foundations of Computer Science, 1982, Sfcs’08. 23rd Annual Symposium on, IEEE, 1982: pp. 160–164.

[2] H.-Y. Lin, W.-G. Tzeng, An efficient solution to the millionaires’ problem based on homomorphic encryption, in: International Conference on Applied Cryptography and Network Security, Springer, 2005: pp. 456–466.

Tags: cryptography.