Tuesday, February 4, 2014

Presenting Algorithms/Protocols in a neat way using Latex

Latex is a very useful tool for scientific writings. It has many cool features to present our writings in a neat manner. I use the TeX Live version of Latex on Ubuntu and I am going to describe how to present algorithms/protocols which contains different steps using the algorithm and algorithmic packages of Latex.

If these two packages do not come with the default installation, you need to install algorithm.sty and algorithmic.sty files to your local installation or you can just place them in the folder where you have the latex file you are currently writing.

First let me show an example output of the latex script which uses the above two packages:

As shown above, algorithm and algorithmic packages take care of all the details such as putting a border around the algorithm/protocol, including a topic for that, numbering the steps with precise alignment and breaking the steps even across several lines without affecting the alignment and numbering.

Following is the Latex script to get an output as above:

1. First you need to include the two packages with \usepackage command as shown below:
\documentclass[a4paper,11pt]{article}
\usepackage{algorithm}
\usepackage{algorithmic}

2. Then you can use the actual script which produces above output using the two packages as shown below:
\begin{algorithm}[H]
\floatname{algorithm}{Attack}
\renewcommand{\thealgorithm}{}
\caption{Steps that Mallory follows to obtain key K}
\label{protocol1}
\begin{algorithmic}[1]
\STATE $M$ : Eavesdrops the protocol 1 above and gets $X$ from step 1 and initiates the same protocol with $B$, by substituting $X$ for $K$ above.
\STATE $M\rightarrow{B}$ : $P = E_{B}(S_{M}(X)) = E_{B}(S_{M}(E_{B}(S_{A}(K))))$
\STATE $B$ : $V_{M}(D_{B}(P)) = V_{A}(D_{B}(E_{B}(S_{A}(X)))) = X$
\STATE $B\rightarrow{M}$ : $Q = E_{M}(S_{B}(X)) = E_{M}(S_{B}(E_{B}(S_{A}(K))))$\\
Since the same key pair is used for both encryption and signing, $S_{B}(E_{B}(message)) = message$\\
Therefore, $Q = E_{M}(S_{A}(K))$
\STATE $M$ : $D_{M}(Q) = S_{A}(K)$
\STATE $M$ : Since the same key pair is used for both encryption and signing, $E_{A}(S_{A}(K)) = K$. Mallory can obtain the key $K$ in this way and decrypt all the subsequent messages encrypted with key $K$.
\end{algorithmic}
\end{algorithm} 

[H] in line one specifies to include this algorithm in the current position itself without floating to somewhere else in the document.

Line 2 customizes the name used to categorize these set of steps: you can name it as 'Algorithm', 'Protocol' etc. Here I have used the name 'Attack', since this describes an attack scenario.

Line 3 also customizes a default command in the package by specifying not to number this particular piece of writing. In a research paper, when you have several protocol/algorithm listings, you might need to number them as you want. This command allows to customize that numbering in the way you want, by specifying whether to use Roman numbers, Arabic numbers or letters.

Line 6 specifies style of numbering you need to number the steps of the protocol/algorithm. You also can opt out numbering by leaving the brackets blank.

As shown in Lines 7 and below, each different step in the protocol needs to be preceded by the command \STATE to differentiation and numbering of each step in the protocol.

That covers all the features need to obtain an output shown at the beginning of the post. Hope this helps.