Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 know a protocol for bit commitment using regular OT (Bob has 1/2
chance of learning the bit Alice transferred to him) which goes like this:

Alice chooses a bit $b$
For $i=0$ to $i=n^2$
$\;\;\;$Alice chooses $x_{ij}$ for $1\leq j\leq n^2$ randomly so that $(\sum_jx_{ij}) \equiv b \pmod 2$
$\;\;\;$Alice and Bob do an oblivious transfer $OT(x_{ij}=y_{ij})$ for every $j$

Alice sends to Bob committed bit $b$ and all of the $x_{ij}$.
If $(\sum_jx_{ij}) \not\equiv b \pmod 2$ for one $i$, Bob rejects. Otherwise, he accepts.

So this protocol uses $n^2$ iterations of OT. I'm trying to find a protocol that would use instead $n$
iterations of $\binom{1}{2}-OT$ (1-out-of-2 oblivious transfer) with exponential security in $n$. I'm thinking
about using $xor$'s and random bits but the only way I can think about has linear security (I think) ...

Alice chooses $b$ and $2n$ random bits $\{b_1,b_2,\dots,b_{2n}\}$
such that $b_1\oplus b_2=b$, $b_3\oplus b_4=b$, $\dots,b_{2n-1}\oplus b_{2n}=b$.
Bob chooses bits $c_1,\dots, c_n$.
Alice and Bob do a $\binom{1}{2}-OT$ for every $\{b_1,b_2,c_1\},\{b_3,b_4,c_2\},\dots,\{b_{2n-1},b_{2n},c_n\}$.

Alice sends to Bob committed bit $b$ and all of the $b_i\in b_{2n}$.
Bob checks if $b_1\oplus b_2=b$, $b_3\oplus b_4=b$, $\dots,b_{2n-1}\oplus b_{2n}=b$.
If it fails once, he rejects, otherwise he accepts.

I would like some of your inputs to know if I'm heading in the right direction.

share|improve this question
up vote 0 down vote accepted

It turned out that the protocol I designed was good.

Bob can't cheat because its impossible for him to discover $b$ because at every $\binom{1}{2}-OT$ iterations, Bob can only discover $b_i$ or $b_{i+1}$ for $i\geq1$ and $i=2k-1$ such that $1\leq k\leq\frac{n}{2}$ ($i$ is uneven).

Alice has an exponentially small chance to cheat without getting caught because if she would like to do so, Alice would have to lie on the reveal phase for every row for one of the $b_i$ or $b_{i+1}$, hoping that Bob discovered the other one. (She doesn't know which one Bob discovered). If Bob finds out that one of the bit isn't the one he discovered during the oblivious transfer or that one row doesn't equal the others, Bob rejects.

share|improve this answer

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.