53 The Millionaire’s Problem

The Millionaire’s Problem, introduced by Andy Yao in 1982, began the study of privacy-preserving multiparty computation.

Alice and Bob want to know who is the richer without revealing how much they are actually worth. Alice is worth I million dollars; Bob is worth J million dollars. They want to determine whether or not I ≥ J, but at the end of the protocol, neither should have learned any more about the other person’s wealth than is implied by the truth value of the predicate I ≥ J.

For simplicity, we assume that I and J are both in the set {1,2,…,10}. Let N be a security parameter, and assume that Alice has public and private RSA keys (e,n) and (d,n), respectively, where n = , and | |≈| |≈. A protocol that intuitively works is shown in Figure 53.1.¹

Alice Bob 1. Choose random x such that |x| = N. Let C = E(e,n)(x). Let m = C - J + 1 mod n. 2. Y i = D(d,n)(m + i - 1), i [1,10]. [Note: Y J = x. ]         Choose random prime p s.t. |p| = and |Zi - Zj|≥ 2 for i≠j, where Zi = (Y i mod p), i [1,10].         Wi = (Zi + (i > I)) mod p, i [1,10]. 3. result = (WJ ≡ x (mod p)). Figure 53.1: Solution to Yao’s Millionaire’s problem.

In step 1, Bob sends Alice a random-looking number m. The number m + J - 1 is the encryption of Bob’s secret x. Alice decrypts the numbers m,m + 1,…,m + 9 to get corresponding Y ₁,…,Y ₁₀. The number Y _J is Bob’s secret x, but Alice doesn’t know which it is since all of the Y _i’s “look” random. She then reduces them all mod a random prime p, resulting in Z₁,…,Z₁₀. Note that Z_J = x mod p and the other Z_i’s look random. Finally, she adds 1 (modp) to each of the numbers Z_i for which i is greater than her own wealth I. If she adds 1 to Z_J, this means that J > I; if not J ≤ I. Bob can tell with is the case from the numbers that Alice sends him in step 2. Namely, if W_J ≡ x (mod p), this means that 1 was not added, so I ≥ J. Otherwise, I < J.

Clearly, all that Alice learns from Bob is a set of random-looking numbers m,…,m + 9, one of which corresponds to Bob’s wealth J, but she has no way of telling which, since any number in Z* _n is the RSA encryption of some plaintext message. Bob on the other hand receives p and W₁,…,W₁₀ from Alice in step 2. However, he does not know any Z_i for i≠J since he cannot the corresponding numbers m + i- 1. He also cannot recover Y _i from W_i because of the information loss implicit in the “mod p” operation. Thus, he also learns nothing about Alice’s wealth I except for the value of the predicate I ≥ J.

We remark that this protocol works only in the semi-honest model in which both Alice and Bob follow their protocol, but both will try to infer whatever they can about the other’s secrets after the fact.

54 Ideal versus Real Protocol Security Model

How to define security in a multiparty protocol is far from obvious. For example, in the millionaire’s problem, there is no way to prevent either Alice or Bob from lying about their wealth, nor is it possible to prevent either of them voluntarily giving up secrecy by broadcasting their wealth. Thus, we can’t hope to find a protocol that will prevent all kinds of cheating. What we do instead is to compare a given “real” protocol with a corresponding very simple “ideal” protocol involving a trusted party. The idea is that the real protocol should simulate the ideal protocol, much the same as the simulator of a zero knowledge proof system simulates the real interaction between prover and verifier. The real protocol is deemed to be secure if any bad things that can happen in the real protocol are also possible in the ideal protocol.

For example, the ideal protocol for the millionaire’s problem has just two steps: In step 1, Alice and Bob send their secrets I and J, respectively, to the trusted party across a private, secure channel. In step 2, the trusted party computes the value of the predicate I ≥ J and sends the result back to both Alice and Bob. The goal of the real protocol is that Alice and Bob don’t learn any more than they could learn in the ideal protocol.

55 Functionality

But what is it that an ideal multiparty protocol computes? Suppose there are m parties to the protocol, P₁,…,P_m. Each P_i has a private input x_i and receives a private output y_i. We say that F is a (multi-party) functionality if F is a random process that maps m inputs to m outputs. As a special case, we say that F is deterministic if the m outputs are uniquely determined by the m inputs.

The millionaire’s problem can be expressed simply as the problem of securely computing the (deterministic) functionality F(I,J) = ((I ≥ J),(I ≥ J)) in the semi-honest model.

56 Security Parameters for Multiparty Protocols

There is no simple choice of the “right” security model for multiparty computations. As with other aspects of cryptography, different kinds of threats are deemed significant in different situations. We list below some of the parameters that are important in the literature on secure multiparty computation.

Channels:

 

• Reliable but not private.
• Private channel.

Computational limitations:

 

• Adversary assume to be a probabilistic polynomial time Turing machine.
• Adversary has unbounded computational power.

Choice of corrupted parties:

 

• Adversary may dynamically corrupt parties as the computation progresses.
• Non-adaptive: Adversary chooses dishonest parties before the protocol begins (but corrupted parties are not known to the honest parties).

Adversary actions:

 

• Malicious adversary: Actively disrupts the protocol.
• Semi-honest: Follows the protocol but gathers information (which it may share with other corrupted parties).

Protocol disruption:

 

• Adversary may prematurely terminate the protocol.
• No premature abort.

Bounds on corruption:

The number of dishonest parties may be bounded, e.g., < n∕2 or < n∕3.

57 Oblivious Transfer

OT₁^k, 1-out-of-k oblivious transfer, is the functionality

where σ₁,…,σ_k {0,1} and i {1,…,k}. Here, the first party (Alice) has k secret bits σ₁,…,σ_k. Bob has a secret index i. At the end of the protocol, Bob learns only σ_i and Alice learns nothing (λ). In particular, Alice does not know which of her bits was learned by Bob, and Bob does not learn σ_j for any j≠i.

Oblivious transfer is central to many of the constructions for secure multiparty computation. We give a protocol for OT₁^k in the semi-honest model. Our construction assumes an enhanced trapdoor permutation {f_α : D_α → D_α}_αI. (See appendix of Volume 2 for technical information on exactly what it means to be enhanced.) Roughly speaking, given a security parameter 1ⁿ and a random string r, there is an algorithm G(1ⁿ,r) that returns a pair (α,t), where α is the index of a trapdoor permutation f_α and t is a trapdoor. (Think of RSA key generation, where we randomly generate a public and private key pair.) Moreover, there is a feasible algorithm for computing f_α(x) given α and x, and there is a feasible algorithm for computing f_α^-1(y) given t and y. We also assume that b is a hard-core predicate for f_α.

Our construction is shown in Figure 57.1. The idea behind the protocol is that Bob sends Alice a k-tuple (y₁,…,y_k) of numbers. All y_j are random except for y_i; y_i is the encryption of a random number x_i. Alice decrypts them all to get z₁,…,z_k, XOR’s the associated hard-core predicate b(z_j) with each of her secrets σ_j, and sends the encrypted secrets (c₁,…,c_k) to Bob. Because y_i is the encryption of x_i, then z_i = x_i, so Bob is able to compute b(z_i) and decrypt c_i to obtain σ_i. He doesn’t learn the other secrets since for j≠i, he knows only x_j = f_α(z_i). He cannot predict b(z_i) given x_j with more than an negligible advantage since b is hard-core for f_α.

Common input: Security parameter 1n.         Alice Bob Private input: (σ1,…,σk). Private input: i.         1. Choose random r. Compute (α,t) = G(1n,r). 2. Choose random x1,…,xk Dα. Let yj = 3. For j {1,…,k}:   zj = fα-1(yj) .   cj = σj ⊕ b(zj).   (Note: zi = xi and ci = σi ⊕ b(xi).) 4. Output ci ⊕ b(xi). Figure 57.1: An OT1k oblivious transfer protocol.