%Lecture of Jan.,25, 2000
%Li Ma (9745151)
\documentclass[12pt]{article}


\usepackage[dvips]{graphics, color}
\usepackage{epsfig}


\input{ProgMacs}
\input{MathMacs}
\input{ThmMacs}
\newcommand{\comment}[1]{}                       

\begin{document}
\section{BC with equality}
%\section{Lecture 7}
%\subsection{bit commitment}
% $1. OWP~+~HCP~\rightarrow ~BC$\\
% $2. OWF~+~HCP~\rightarrow ~PRBG$\\
% $3. PRBG~\rightarrow ~BC$\\
% 
%We did 1. and 2. in the last lecture and now we are going to do 3..
%Let $g:\{0,1\}^n \rightarrow \{0,1\}^{3n}$ be a Pseudo-Random bit 
%generator.
%\begin{itemize}
%\item Bob picks a random $r \in_R \{0,1\}^{3n}$, and sends it to Alice,
%\item to commit to b=0, Alice sends $g(x)$ for random $x\in_R \{0,1\}^{n}$;~
% to commit to b=1, Alice sends $g(x)\bigoplus r$ for random $x\in_R \{0,1\}^{n}$,
%\item to unveil Alice sends $b,x.$
%\end{itemize}

%``{\bf Concealing}'': follows from Pseudo-Rrandomness of $g$.

%``{\bf Binding}'':
%To cheat Alice needs $x_0,~x_1,$ s.t. $g(x_0)=w=g(x_1)\bigoplus r.$
%This means $g(x_0)\bigoplus g(x_1)=r.$

%Since x $\in \{0,1\}^n,$ then g(x) has at most $2^n$ possible values, hence
%$g(x_0)\oplus g(x_1)$ has at most $2^{2n}$ possible values. 
%Therefore, Prob of cheating: $$Prob~(\exists~ x_0, ~x_1,~s.t.~
% g(x_0)\oplus g(x_1)=r) ~\leq 2^{2n}/2^{3n}=1/2^n.$$
% 
\subsection{Comparing equality of two committed inputs}
\begin{example}\label{example1} bit 
commitment based on {\rm GNI}.
\begin{eqnarray*}  
& {\rm GNI}:(G_1, G_2)\in {\rm GNI} & \\                        
       P & &  V\\
&\hspace{1cm} \stackrel{ZK((G_1, G_2)\in {\rm GNI})}{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}}\,>  & \\    
commit(b_1), & & \\               
G\approx G_{b_1}  & & \\ 
&\hspace{1cm} \stackrel{G }{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}}\,>  & \\    
commit(b_2), & & \\               
G'\approx G_{b_2}  & & \\  
&\hspace{1cm} \stackrel{G' }{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}}\,>  & \\   
&\hspace{1cm} \stackrel{G=\pi(G')}{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}}\,>  & \\                            
%                        & & check \; G = \pi(G'),\\
                        & & if \; G = \pi(G') \; then \; accept \; b_1 = b_2.\\
\end{eqnarray*}   
\end{example}
\begin{example}
bit commitment based on {\rm QNR}.                          
\begin{eqnarray*} 
& y\in {\rm QNR}_n[+1]&   \\                                
       P & &  V\\
&\hspace{1cm} \stackrel{ZK(y\in {\rm QNR}_n[+1])}{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}}\,>  & \\
commit(b_1), & & \\               
z_1\equiv y^{b_1}*r^2 \; mod  \;n, & & \\ 
r \in_R Z^*_n, & & \\
&\hspace{1cm} \stackrel{z_1 }{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}} \,>& \\    
commit(b_2), & & \\               
z_2 \equiv y^{b_2}*r'^2  \;mod \; n,& & \\  
r' \in_R Z^*_n, & & \\
&\hspace{1cm} \stackrel{z_2}{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}}\,>  & \\
&\hspace{1cm} \stackrel{v:= r r' y^{b_{1}}}{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}}\,>  & \\    
                        & & if \;  z_1z_2  = v^{2}  \; then \; accept \; b_1 = b_2.\\
\end{eqnarray*} 
\end{example}
To prove $ b_1\neq b_2$ P sends $\sqrt{yz_1z_2}$. 
\subsection{Computation on boolean circuits using committed inputs}
We shall use the previous two examples to do computations on boolean
circuits.
Prover commits to three bits: $b_1,~ b_2,~ b_3 \in \{0,1\}$, s.t.
B: $b_1\wedge b_2 =b_3.$ There are only four possible situations of B (see
Table T), i.e.
B (three bits) must belong to one of the 
following situation $T_j$ (three bits).
$${\bf Table }~ T$$
$$T_1: 0\wedge 0=0$$
$$T_2: 0\wedge 1=0$$
$$T_3: 1\wedge 0=0$$
$$T_4: 1\wedge 1=1$$
We design the protocol by using the "Cut and Choose" technique in order to 
prove that $B \in T$. P permutes the Table T then commit to ($\pi(T)$) to V.
\begin{eqnarray*}                          
       P & &  V\\
&\hspace{1cm} \stackrel{commit(\pi(T))}{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}}\,>  & \\ 
                        & & c\in_R\{0,1\}, \\   
& \hspace{-1cm} <\,\stackrel{c}{{\linethickness{0.5mm}\put(-10,3)
                        {\line(1,0){75}}}}  & \\
if \;c=0, & & \\                        
&\hspace{1cm} \stackrel{\pi,~unveil(\pi(T))}{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}}\,>  & \\ 
if \; c=1, & & \\                          
&\hspace{1cm} \stackrel{ZK(B=T_i)}{{\linethickness{0.5mm}\put(-30,3)
                        {\line(1,0){75}}}}\,>  & \\ 
\end{eqnarray*}
Note: 

1. $\pi$ is a permutation of Table T.

2. Using example \ref{example1}, P can show to V that the three committed bits B: $b_1, b_2$ and $b_3$ 
   are equal to the three committed bits of $T_i$ respectly.
   
\bigskip         
If $b_1\wedge b_2=b_3,$ Pr[accept]=1,

If $b_1\wedge b_2\neq b_3,$ Pr[accept]$\leq 1/2^k,$ where k=$\#$ of rounds.

We can use this method for any logical gate: $\wedge, \vee, -,\oplus.$

\subsection{Rudich's Trick}
Now we are going to talk about a general way to obtain a bit 
commitment where we can prove equality based on any bit commitment. Here 
``Rudich's Trick'' is the way to show two committed bits are equal. 

Suppose $b=b'$, where $b, b'\in \{0,1\}$,
let $u_i,x_{i}$ be random bits and $v_i, y_i$ be defined according
to $u_i\oplus v_i=b,~ x_i\oplus y_i=b',~ i=1, \cdots 2n$.
We shall use 4n committed bits to commit one bit.
$$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Alice ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Bob $$
\begin{eqnarray*}
 commit(b) : & \hspace{2cm}& commit(b') : \\
\alpha_1: \, C(u_1),C(v_1) & \hspace{2cm} & C(x_1),C(y_1) \, :\beta_1\\
\alpha_2: \, C(u_2),C(v_2) & \hspace{2cm} & C(x_2),C(y_2)  \, :\beta_2\\
                     \vdots& \hspace{2cm} &\vdots \\
\alpha_{2n}: \, C(u_{2n}),C(v_{2n}) & \hspace{2cm} & C(x_{2n}),C(y_{2n}) \, :\beta_{2n} \\
\end{eqnarray*}
where $\alpha_i$ and $\beta_i$ are two committed bits and C denotes commit.
\begin{itemize}
\item {Bob imposes two random permutations $\pi_{\alpha}, 
\pi_{\beta}$ to Alice who permutes $\alpha_i$ using $\pi_{\alpha}$ and $\beta_i$ 
using $\pi_{\beta}.$ 
\begin{eqnarray*} 
C(u_9),C(v_9) &  \hspace{2cm} & C(x_2),C(y_2) \\
C(u_n),C(v_n) &  \hspace{2cm} & C(x_7),C(y_7) \\
                     \vdots& \hspace{2cm} &\vdots \\
C(u_3),C(v_3) &  \hspace{2cm} & C(x_6),C(y_6) \\
\end{eqnarray*} 
}
\pagebreak
\item {Regardless of b, $u_i,x_i$ and $v_i,y_i$ are either identical 
or opposite. Alice will claim for the first half of the lines whether they are ``='' or ``$\neq$''.
\begin{eqnarray*} 
C(u_9),C(v_9) & \hspace{1cm} = \hspace{1cm}& C(x_2),C(y_2) \\
C(u_n),C(v_n) & \hspace{1cm} \neq \hspace{1cm}& C(x_7),C(y_7) \\
                     \vdots& \hspace{2cm} &\vdots \\
C(u_{41}),C(v_{41}) & \hspace{1cm} =\hspace{1cm}& C(x_{63}),C(y_{63}) \\
\hline\\
C(u_{99}),C(v_{99}) & \hspace{1cm}   \hspace{1cm}& C(x_{n-9}),C(y_{n-9}) \\
C(u_{2n}),C(v_{2n}) & \hspace{1cm}   \hspace{1cm}& C(x_{55}),C(y_{55}) \\
                     \vdots& \hspace{2cm} &\vdots \\
C(u_3),C(v_3) & \hspace{1cm}  \hspace{1cm}& C(x_6),C(y_6) \\
\end{eqnarray*} 
for example: 
\begin{eqnarray*}
 b=b'=0 & \hspace{2cm} & b=b'=1 \\
 0\oplus 0=0\oplus 0~:~u_i=x_i,~v_i=y_i,&\hspace{2cm}&0\oplus 1=0\oplus 1:~u_i=x_i,~v_i=y_i, \\
 0\oplus 0=1\oplus 1~:~u_i\neq x_i,~v_i\neq y_i,&\hspace{2cm}&1\oplus 0=0\oplus 1:~u_i\neq x_i,~v_i\neq y_i. \\
\end{eqnarray*}
}
\item {For each line Bob randomly chooses to see the both left sides or both 
right sides, but not both sides, then Alice unveils them to Bob.
\begin{eqnarray*} 
C(u_9),U(v_9) &\hspace{1cm}=\hspace{1cm}& C(x_2),U(y_2) \\
U(u_n),C(v_n) &\hspace{1cm}\neq \hspace{1cm}& U(x_7),C(y_7) \\
                     \vdots& \hspace{2cm} &\vdots \\
C(u_{41}),U(v_{41}) & \hspace{1cm} =\hspace{1cm}& C(x_{63}),U(y_{63}) \\
\hline\\
C(u_{99}),C(v_{99}) & \hspace{1cm}   \hspace{1cm}& C(x_{n-9}),C(y_{n-9}) \\
C(u_{2n}),C(v_{2n}) & \hspace{1cm}   \hspace{1cm}& C(x_{55}),C(y_{55}) \\
                     \vdots& \hspace{2cm} &\vdots \\
C(u_3),C(v_3) & \hspace{1cm}  \hspace{1cm}& C(x_6),C(y_6) \\
\end{eqnarray*} 
where U denotes unveil.
}
\end{itemize}

If Alice wants to cheat, suppose b=1, b'=0 and Alice cliams that 
$\alpha_i=\beta_i$, for example:
\begin{eqnarray*}
b=1& & b'=0 \\
\alpha_i:~ 0 \oplus 1 &=&1 \oplus 1 ~:\beta_i\\
\end{eqnarray*}

With 1/2 probability, Bob will request to see the left sides and Alice unveils
to him that $(u_i=0) \neq (x_i=1)$, then Bob rejects.

With 1/2 probability, Bob will request to see the right sides and Alice unveils
to him that $v_i=1=y_i$, then Bob accepts.
So if $b\neq b'$, 1/2 probability Bob will be cheated.

Therefore,

If b=b', Pr[accept]=1,

If $b\neq b'$, Pr[accept]$\leq (1/2)^n$, at each line, if $b\neq b'$,
regardless of Alice's answer, the probability Bob finds out that 
Alice is cheating is 1/2.

After a test is conclusive, Alice can construct a new valid commitment
to represent both $b$ and $b'$ using the untouched commitments:

\begin{eqnarray*} 
 commit(b,b') : \\
C(u_{99}),C(v_{99})\\
C(u_{2n}),C(v_{2n})\\
\vdots\\
C(u_3),C(v_3)\\
C(x_{n-9}),C(y_{n-9})\\
C(x_{55}),C(y_{55})\\
\vdots \\
C(x_6),C(y_6)
\end{eqnarray*} 

\end{document}

