# What does this step in this protocol for the Yao's Millionaire Problem mean?

I was reading “An Efficient Protocol for Yao’s Millionaires’ Problem” (Ioannidis and Grama 2003). In the proposed protocol in section three, it is written:

(Step 4) For every $i$, $1 \le i \le d$, Bob obliviously transfers $A^\prime_{il}$ where $l = b_i + 1$.

(Some context: $d$ is a security parameter, $A^{\prime}$ is a matrix of size $d \times 2$, and $b_i$ are the bits of Bob's number.)

I understand the definition of 1-2 oblivious transfer, however, I am confused exactly what Bob is obliviously transferring. Is it referring to the bits of $A^\prime_{il}$? If so, the paper explicitly says that only 1-2 transfers are used, so does that mean that $A^\prime_{il}$ is no larger than $2$ bits?

• 1-2 does not mean 1 out of 2 bits it means 1 item out of a set of two items. The items can be any length. – mikeazo Dec 2 '13 at 13:40

## 1 Answer

In here, it is 1-2 oblivious transfer meaning that for each $i$, the receiver gets $A'_{i1}$ or $A'_{i2}$ but the sender does not know which. The length of the elements $A'_{ij}$ is not important as long as you choose a correct oblivious transfer protocol.

• This is the explanation which I originally came up with. I was thrown off by $l = b_i + 1$, since Bob already knows $b_i$ (and by extension, can find $l$). So what does $A^\prime_{il}$ mean? – George V. Williams Dec 3 '13 at 0:05
• It should be that Alice has the matrix $A'$, so Bob knows $b_i$, computes $l$ and uses OT protocol to get one of the values from the corresponding row of the matrix - $A'_{il}$. Alice does not learn which value $A'_{i1}$ or $A'_{i2}$ Bob learned. – student Dec 3 '13 at 7:26