\documentclass{article}

\usepackage[underline=false]{pgf-umlsd}
\usepackage{tikz}

% From http://tex.stackexchange.com/questions/164707/how-to-use-greek-letters-in-pgf-umlsd-or-generally-terms-starting-with
\renewcommand{\mess}[4][0]{
  \stepcounter{seqlevel}
  \path
  (#2)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess from) {};
  \addtocounter{seqlevel}{#1}
  \path
  (#4)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess to) {};
  \draw[->,>=angle 60] (mess from) -- (mess to) node[midway, above]
  {#3};
  \node (\detokenize{#3} from) at (mess from) {};
  \node (\detokenize{#3} to) at (mess to) {};
}
% From http://tex.stackexchange.com/questions/98525/pgf-umlsd-and-externalize
\newcommand{\sdinit}{%
	\pgfdeclarelayer{umlsd@background}%
	\pgfdeclarelayer{umlsd@threadlayer}%
	\pgfsetlayers{umlsd@background,umlsd@threadlayer,main}%
}
\newcommand{\sdbegin}{%
	\setlength{\unitlength}{1cm}%
	\tikzstyle{sequence}=[coordinate]%
	\tikzstyle{inststyle}=[rectangle, draw, anchor=west, minimum
	height=0.8cm, minimum width=1.6cm, fill=white, 
	drop shadow={opacity=1,fill=black}]%
	\ifpgfumlsdroundedcorners%
		\tikzstyle{inststyle}+=[rounded corners=3mm]%
	\fi%
	\tikzstyle{blockstyle}=[anchor=north west]%
	\tikzstyle{blockcommentstyle}=[anchor=north west, font=\small]%
	\tikzstyle{dot}=[inner sep=0pt,fill=black,circle,minimum size=0.2pt]%
	\global\def\unitfactor{0.6}%
	\global\def\threadbias{center}%
	% reset counters
	\setcounter{preinst}{0}%
	\setcounter{instnum}{0}%
	\setcounter{threadnum}{0}%
	\setcounter{seqlevel}{0}%
	\setcounter{callevel}{0}%
	\setcounter{callselflevel}{0}%
	\setcounter{blocklevel}{0}%
	% origin
	\node[coordinate] (inst0) {};%
}
\newcommand{\sdend}{%
	\begin{pgfonlayer}{umlsd@background}%
		\ifnum\value{instnum}>0%
			\foreach \t [evaluate=\t] in {1,...,\theinstnum}{%
				\draw[dotted] (inst\t) -- ++(0,-\theseqlevel*\unitfactor-2.2*\unitfactor);%
			}%
		\fi%
		\ifnum\value{threadnum}>0%
			\foreach \t [evaluate=\t] in {1,...,\thethreadnum}{%
				\path (thread\t)+(0,-\theseqlevel*\unitfactor-0.1*\unitfactor) node (threadend) {};%
				\tikzstyle{threadstyle}+=[threadcolor\t]%
				\drawthread{thread\t}{threadend}%
			}%
		\fi%
	\end{pgfonlayer}%
}

\usepackage{amsmath}
\usepackage{amsfonts}

\begin{document}

\begin{figure}
	\centering
	\sdinit{}
	\begin{tikzpicture}
		% Define symbols and names for the parties
		\sdbegin{}
		\newinst{A}{$\hat{A}$}
		\newinst[5]{B}{$\hat{B}$} % Increase "5" to widen
		
		% Message from Alice to Bob, with precomputations
		\postlevel
		\mess{A}{$\hat{A}, \hat{B}, g^x, \text{Sig}_{\hat{A}}(g^x, \hat{B})$}{B}
		\node[anchor=east] at (mess from) {$x \xleftarrow{\$} \mathbb{Z}_p^*$};
		
		% Message from Bob to Alice, with computations by both sides
		\postlevel
		\mess{B}{$\hat{B}, \hat{A}, g^y, \text{Sig}_{\hat{B}}(g^y, g^x, \hat{A})$}{A}
		\node[anchor=west] at (mess from) {\shortstack[r]{
				$y \xleftarrow{\$} \mathbb{Z}_p^*$ \\
				$k \leftarrow (g^x)^y$}};
		\node[anchor=east] at (mess to) {$k \leftarrow (g^y)^x$};
		
		\sdend{}
	\end{tikzpicture}
	\caption{The MQV key exchange}
	\label{fig:mqv}
\end{figure}

\end{document}
