2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – mikeazo
    Dec 2, 2013 at 13:40

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – George V. Williams
    Dec 3, 2013 at 0:05
  • $\begingroup$ 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. $\endgroup$
    – student
    Dec 3, 2013 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.