
\documentstyle{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{Created=Wed Mar 08 12:54:50 2000}
%TCIDATA{LastRevised=Wed Mar 08 13:39:15 2000}

\begin{document}


CS647 Lecture 12 - Fri 11 Feb 2000
\bigskip

\subsection{Random test}

The goal is to test whether two random strings are equal.
{\bf A} has the string $x\in \{0,1\}^{n}$ and computes $A=\oplus
_{i=1}^{n}(R_{i,x_{i}}\oplus S_{i,x_{i}})$ and {\bf B} has the string $y\in
\{0,1\}^{n}$ and computes $B=\oplus _{i=1}^{n}(R_{i,y_{i}}\oplus
S_{i,y_{i}}) $. The xors are computed bitwise, so that, for instance, $%
R_{i,x_{i}}\oplus S_{i,x_{i}}\in \{0,1\}^{n}$, and $A,B\in \{0,1\}^{n}$ as
well.

\smallskip

{\bf A} sends the $R_{i,x_{i}}$ in $i=1,...,n$ steps. At step $i$, {\bf A}
picks $R_{i,0},R_{i,1}\in _{R}\{0,1\}^{n}$ and sends one of them to {\bf B}
via ${2}\choose{1}$-OT.

\[
\begin{array}{lllll}
R_{i,0} & \rightarrow &  & \leftarrow & y_{i} \\ 
&  & {2}\choose{1}-OT &  &  \\ 
R_{i,1} & \rightarrow &  & \rightarrow & R_{i,y_{i}}
\end{array}
\]

This allows Bob to get one of the two $R^{\prime }$s and {\em not} the other
one. It is a primitive on $n$ bits, an we can repeatedly use the 1- bit
primitive to build it (this is particular to this situation, because Alice
cannot achieve anything by cheating on individual bits). At step $i$, for $%
j=1,...,n$, {\bf A} picks $R_{i,0}^{j},R_{i,1}^{j}\in _{R}\{{0,1\}}$ and
sends one of them to {\bf B} via ${2}\choose{1}$-OT.

\[
\begin{array}{lllll}
R_{i,0}^{j} & \rightarrow &  & \leftarrow & y_{i} \\ 
&  & {2}\choose{1}-OT &  &  \\ 
R_{i,1}^{j} & \rightarrow &  & \rightarrow & R_{i,y_{i}}^{j}
\end{array}
\]

Then, after the $i=1,...,n$ steps, do the same process (also for $n$ bits)
in the other direction. 
\[
\begin{array}{lllll}
x_{i} & \rightarrow &  & \leftarrow & S_{i,0} \\ 
&  & {2}\choose{1}-OT &  &  \\ 
S_{i,x_{i}} & \leftarrow &  & \leftarrow & S_{i,1}
\end{array}
\]

Then $X=Y\Rightarrow A=B$. If $X\neq Y$ then, somewhere in the calculation, 
{\bf A} uses $R_{i0}$, and {\bf B} uses $R_{i1}$ (and Bob does not know
other value, $R_{i0}$). So $A$ and $B$ are randomized. Moreover, they are
independently distributed: $\Pr [A=B]=\left( \frac{1}{2}\right) ^{|A|}=\frac{%
1}{2^{n}}$.

\begin{itemize}
\item  Remark: If {\bf B} knew {\em one} bit on both sides and if $A$ and $B$
were different on only that bit, then {\bf B} could deduce it.

\item  Application: {\bf A} has the string $x$ and {\bf B} has the string $y$%
. They want to compute $f(x,y)$ without one learning the other's string.
\end{itemize}

\subsection{Equivalence between Rabin's OT and ${2}\choose{1}$-OT}

\subsubsection{Rabin's OT}

\[
\begin{array}{lllll}
&  &  & \rightarrow & b\,\,\,with\,\,\, prob =\frac{1}{2} \\ 
b & \rightarrow & R-OT &  &  \\ 
&  &  & \rightarrow & ? \,\,\,with\,\,\, prob =\frac{1}{2}
\end{array}
\]

\subsubsection{One-out-of-two OT}

\[
\begin{array}{lllll}
b_{0} & \rightarrow &  & \leftarrow & c \\ 
&  & {2}\choose{1}-OT &  &  \\ 
b_{1} & \rightarrow &  & \rightarrow & b_{c}
\end{array}
\]

\subsubsection{Rabin's OT from one-out-of-two OT}

\[
\begin{array}{lll}
b\rightarrow & \left( 
\begin{array}{ccc}
\begin{array}{l}
a,b^{\prime }\in _{R}\{{0,1\}} \\ 
b_{a}=b \\ 
b_{\bar{a}}=b^{\prime }
\end{array}
&  & c\in _{R}\{{0,1\}} \\ 
\begin{array}{l}
b_{0}\rightarrow \\ 
b_{1}\rightarrow
\end{array}
& \left[ {2}\choose{1}-OT\right] & 
\begin{array}{l}
\leftarrow c \\ 
\rightarrow b_{c}
\end{array}
\\ 
a & \longrightarrow & 
\end{array}
\right) & \rightarrow b_{c}
\end{array}
\]

With probability $\frac{1}{2}$, we have that $a=c$, so that $b_{c}=b$.
Otherwise (when $a\neq c$), we have $b_{c}=b^{\prime }$, a random bit.
Sending $a$ at the end tells {\bf B} if it received $b$ or $?$.

\subsubsection{One-out-of-two OT from Rabin's OT}

\[
\begin{array}{lll}
\begin{array}{l}
b_{0}\rightarrow \\ 
b_{1}\rightarrow
\end{array}
& \left( 
\begin{array}{ccc}
\begin{array}{l}
r_{1},...r_{n}\in _{R}\{{0,1\}} \\ 
r_{i}\rightarrow 
\end{array}
& \left[ R-OT\right] & 
\begin{array}{l}
\rightarrow r_{i}\quad prob=\frac{1}{2} \\ 
\rightarrow ?\quad prob=\frac{1}{2}
\end{array}
\\ 
& \leftarrow I_{0,}I_{1} & 
\begin{array}{l}
I_{0}=\{{i_{1},...,i_{n/3}\}} \\ 
I_{1}=\{{j_{1},...,j_{n/3}\}}
\end{array}
\\ 
\begin{array}{l}
\hat{b}_{0}=b_{0}\oplus (\oplus _{i\in I_{0}}r_{i}) \\ 
\hat{b}_{1}=b_{1}\oplus (\oplus _{i\in I_{1}}r_{i})
\end{array}
& \hat{b}_{0},\hat{b}_{1}\rightarrow & b_{c}=\hat{b}_{c}\oplus (\oplus
_{i\in I_{c}}r_{i})
\end{array}
\right) & 
\begin{array}{l}
\leftarrow c \\ 
\rightarrow b_{c}
\end{array}
\end{array}
\]

The number of $r_{i}$ going from Alice to Bob is around $n/2$. Each $r_{i}$
is a Bernoulli variable, so from the Law of large numbers, the number of $%
r_{i}$ has a good probability to be between $n/3$ and $2n/3$. Suppose $k$
out of $n$ of the $r_{i}$ were received by Bob. Then $\Pr [k\leq n/3]=\Pr
[k\geq 2n/3]\leq e^{-(1/6)^{2}n}$ (can take out the factor 2 because of the
symetry).

After the $R-OT$'s, Bob creates two sets of indices $I_{0}$ and $I_{1}$such
that $I_{0}\cap I_{1}=\emptyset $, and such that all bits indexed by the
elements of $I_{c}$ where received (in the $I_{\bar{c}}$, there is at least
one index such that the corresponding bit that was not received, except with
probability exponentially small, as shown above). Alice cannot tell $I_{0}$
and $I_{1}$ appart, so she does not know what $c$ is. She computes $\hat{b}%
_{0}=b_{0}\oplus (\oplus _{i\in I_{0}}r_{i})$ and $\hat{b}_{1}=b_{1}\oplus
(\oplus _{i\in I_{1}}r_{i})$, and sends $\hat{b}_{0}$ and $\hat{b}_{1}$to
Bob. He finally finds $b_{c}=\hat{b}_{c}\oplus (\oplus _{i\in I_{c}}r_{i})$
and cannot deduce $b_{\bar{c}}$ since the $r_{i}$'s corresponding
to the indices in $I_{\bar{c}}$ are not known to him.

However, it is possible that the reduction fails. When {\bf B} is able to
construct $I_{0}$ and $I_{1}$ incorrectly, such that all the bits
corresponding to both sets of indices are known, then both $b_{0}$ and $b_{1}
$ will become known to Bob. As above, this happens with probability
exponentially small.

\end{document}
