Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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
up vote 3 down vote accepted

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.

share|improve this answer
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
I understand now. Thank you! – George V. Williams Dec 3 '13 at 21:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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