% File              : template.tex
% Version           : $Revision: 1.2 $
% Last-modified     : $Date: 2005/01/04 11:38:53 $
% Last-modifier     : FJ

\documentclass{splib}

\begin{document}
% main environment
\begin{protocol}%
% name
{Schnorr's Protocol}%
% authors
{C. P. Schnorr}%
% date of the first publication
{1991}%
% editor name
{}%
% date of submission
{}%
% date of last change, empty or = date of submission
{}

\begin{abstract}
The Schnorr protocol is described by R. Cramer,
  I. Damg{\aa}rd and B. Schoenmakers in~\cite{BRICS-EP-94-CDS_PPKS}.
\end{abstract}

\begin{core}
\begin{declarations}
\dcl{A, B}{principal}
\dcl{Na, Nb}{fresh number}
\dcl{Sa}{private key}
\dcl{Pa = exp(g,Sa)}{public key}

\end{declarations}

\bigskip{}
\code{A chooses Na and computes a = exp(g,Na)  }
\begin{messages}
\msg{1} {A}{B}{ a }
\end{messages}

\code{B chooses Nb}
\begin{messages}
\msg{2} {B}{A}{ Nb }
\end{messages}

\code{A computes r = Na + Nb $\times$ Sa }
\begin{messages}
\msg{3} {A}{B}{ r }
\end{messages}

\code{B checks that exp(g, r) = a $\times$ exp(Pa,Nb)}
\end{core}


\begin{explanation}
A zero-knowledge protocol is designed for convincing the
  verifier of   the validity of a given statement, without releasing any
  knowledge beyond  the validity of the statement. This concept was introduced
  in~\cite{cj98-01-15}. An overview can be found in~\cite{Gol01}.
  We present the Schnorr protocol which is described by R. Cramer,
  I. Damg{\aa}rd and B. Schoenmakers in~\cite{BRICS-EP-94-CDS_PPKS} and which
  uses this method.

The \code{+}, \code{$\times$} and \code{exp} symbols denote respectively
addition, multiplication and modular exponentiation.
 
Details of the computation done by \code{B} at the last step of the
protocol: %to check the identity of \code{A}:

\begin{tabular}{ll@{\hspace{-3mm}}l}
\hspace{-2mm}
& \code{a $\times$ exp(Pa,Nb)} & \\
= & \code{exp(g,Na) $\times$ exp(exp(g,Sa),Nb)} & \\
= & \code{exp(g,Na) $\times$ exp(g,Sa $\times$ Nb)}&\\
= & \code{exp(g,Na + Sa $\times$ Nb)}&\\
= & \code{exp(g, r)} & ~\\
\end{tabular}
\end{explanation}

\begin{property}
 \code{A} wants to prove his identity to  \code{B} by showing him that he knows \code{Sa} without
revealing it.
\end{property}

\begin{references}
\cite{BRICS-EP-94-CDS_PPKS}
\end{references}


\end{protocol}
\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:

