Drawing network protocols

Here is my simple solution using the method shown here:

\documentclass[a4paper,11pt]{article}
\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{matrix,shapes,arrows,positioning,chains, calc}
\begin{document}

\begin{tikzpicture}
\matrix (m)[matrix of nodes, column  sep=2cm,row  sep=8mm, nodes={draw=none, anchor=center,text depth=0pt} ]{
Prover & & Verifier\\[-4mm]
Choose a random number & & \\[-7mm]
$r \in \{0,1\}^{*}.$ & & \\
 & Send $r$ & \\
& & Choose a random number  \\[-7mm]
& &$s \in \{0,1\}^{*}.$\\
 & Send $s$ & \\
};

\draw[shorten <=-1.5cm,shorten >=-1.5cm] (m-1-1.south east)--(m-1-1.south west);
\draw[shorten <=-1.5cm,shorten >=-1.5cm] (m-1-3.south east)--(m-1-3.south west);
\draw[shorten <=-1cm,shorten >=-1cm,-latex] (m-4-2.south west)--(m-4-2.south east);
\draw[shorten <=-1cm,shorten >=-1cm,-latex] (m-7-2.south east)--(m-7-2.south west);
\end{tikzpicture}
\end{document}

EDIT The graphical result is:

Did you look at MSC (Message Sequence Charts) package in CTAN? I've never used but some of our students did it.

EDIT Your example could be done with some code like this

\documentclass[border=2mm]{standalone}
\usepackage{msc}
\begin{document}
\begin{msc}{Example}
\declinst{prover}{}{Prover}
\declinst{verifier}{}{Verifier}
\action*{%
\begin{minipage}{3cm}\centering 
Choose a random number\\
$r\in\{0,1\}^*$
\end{minipage}%
}{prover}
\nextlevel[4]
\mess{Send $r$}{prover}{verifier}
\nextlevel
\action*{%
\begin{minipage}{3cm}\centering
Choose a random number\\
$r\in\{0,1\}^*$
\end{minipage}}{verifier}
\nextlevel[4]
\mess{Send $s$}{verifier}{prover}
\end{msc}
\end{document}

and the result (with xelatex because msc uses pstricks) is

The apperance is not so flexible because msc diagrams are normalized by ITU (International Telecomunication Union) and the package respects the format.