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.


1 Answer 1


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.


Your Answer

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

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