# 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. Commented Dec 2, 2013 at 13:40

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? Commented Dec 3, 2013 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. Commented Dec 3, 2013 at 7:26