infra: Expunge revision history clutter.

[mdwtools] / crypto.dtx

% \begin{meta-comment}
%
% $Id: crypto.dtx,v 1.2 2003/09/05 16:13:14 mdw Exp $
%
% Typesetting crypto papers
%
% (c) 2001 Mark Wooding
%
% \end{meta-comment}
%
% \begin{meta-comment} <general public licence>
%%
%% crypto package -- useful macros for typesetting crypto papers
%% Copyright (c) 2001 Mark Wooding
%%
%% This program is free software; you can redistribute it and/or modify
%% it under the terms of the GNU General Public License as published by
%% the Free Software Foundation; either version 2 of the License, or
%% (at your option) any later version.
%% 
%% This program is distributed in the hope that it will be useful,
%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%% GNU General Public License for more details.
%% 
%% You should have received a copy of the GNU General Public License
%% along with this program; if not, write to the Free Software Foundation,
%% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
% \end{meta-comment}
%
% \begin{meta-comment} <Package preambles>
%<+package>\NeedsTeXFormat{LaTeX2e}
%<+package>\ProvidesPackage{crypto}
%<+package>                [2001/09/16 1.0 Crypto typesetting]
% \end{meta-comment}
%
% \CheckSum{245}
%% \CharacterTable
%%  {Upper-case    \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z
%%   Lower-case    \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z
%%   Digits        \0\1\2\3\4\5\6\7\8\9
%%   Exclamation   \!     Double quote  \"     Hash (number) \#
%%   Dollar        \$     Percent       \%     Ampersand     \&
%%   Acute accent  \'     Left paren    \(     Right paren   \)
%%   Asterisk      \*     Plus          \+     Comma         \,
%%   Minus         \-     Point         \.     Solidus       \/
%%   Colon         \:     Semicolon     \;     Less than     \<
%%   Equals        \=     Greater than  \>     Question mark \?
%%   Commercial at \@     Left bracket  \[     Backslash     \\
%%   Right bracket \]     Circumflex    \^     Underscore    \_
%%   Grave accent  \`     Left brace    \{     Vertical bar  \|
%%   Right brace   \}     Tilde         \~}
%%
%
% \begin{meta-comment}
%
%<*driver>
\input{mdwtools}
\describespackage{crypto}
\mdwdoc
%</driver>
%
% \end{meta-comment}
%
%^^A-------------------------------------------------------------------------
% \section{User guide}
%
% \subsection{Algorithm typesetting}
%
% A lot of provable-security papers need to be able to typeset algorithms
% describing adversaries, schemes, oracle behaviour, etc.  There is a
% (relatively) standard format for doing this which we support.
%
% \DescribeEnv{program}
% The \env{program} environment provides handy notation for describing
% algorithms formally.  It gives a \env{tabbing} environment, so that things
% can be laid out nicely, and allows fragments of algorithms to be laid out
% in columns or rows, with separating rules.
%
% \DescribeMacro\next
% Within the \env{program} environment, the |\next| command stops typesetting
% the current column, typesets a vertical separator rule, and starts a new
% column.  Adjacent columns are spaced out evenly across the page, with equal
% space around the rules rules and at the current margins.  This means that
% the rules don't line up, but it still seems to provide a pleasing effect.
%
% \DescribeMacro\newline
% The |\newline| macro begins a new row of algorithm typesetting.  A page
% break is possible at a |\newline|.
%
% \DescribeMacro\kw
% A number of standard keywords are available, as shown in
% table~\ref{tab:kw}.  The typsetting of these is done by the |\kw| command,
% which usually sets its argument in text bold face, but can be redefined.
% The standard definition uses |\xspace| so that you don't need to remember
% to say \verb*+\ + after a keyword command.
% \begin{table}
%   \centering
%   \def\row#1{\texttt{\string#1} & #1 \\}
%   \begin{tabular}{ll}
%     \textbf{Command} & \textbf{Keyword} \\
%     \row\RETURN
%     \row\IF
%     \row\THEN
%     \row\ELSE
%     \row\REPEAT
%     \row\WHILE
%     \row\UNTIL
%     \row\FOREVER
%     \row\DO
%     \row\FOR
%     \row\FOREACH
%     \row\FROM
%     \row\IN
%     \row\TO
%     \row\ABORT
%     \row\PARSE
%     \row\NEW
%     \row\AS
%   \end{tabular}
%   \caption{Keywords available for algorithm typesetting}
%   \label{tab:kw}
% \end{table}
%
% \DescribeMacro\ind
% Within a \env{program} environment, the |\ind| command shunts the indent
% level 1\,em to the right.
%
% \DescribeMacro\gets
% \DescribeMacro\getsr
% \DescribeMacro\inr
% Assignment can be represented using the standard command |\gets|, which
% typesets a left-pointing arrow `$\gets$'.  Random sampling -- the selection
% of a random element from a set or probability distribution -- can be
% represented using the new command |\getsr|, which typesets an arrow with a
% little `R' above it `$\getsr$'.  Random membership -- showing that
% something is a random variable with some distribution -- can be represented
% using the |\inr| command, which just typesets an $\in$ sign with a
% subscript `R': `$\inr$'.
%
% \DescribeMacro\id
% Long identifiers can be typeset using the |\id| command. giving the
% identifier name as an argument.  The |\id| command is only valid in maths
% mode.  As currently set up, |\id| sets its argument in \emph{text} italics;
% this seems to look better in documents which use a PostScript body face and
% Computer Modern for maths.
%
% \DescribeMacro\Xid
% It's handy to be able to glue a bit of (possibly fancy) maths typesetting
% to an identifier, e.g., to construct $\Xid{H'}{list}$, or
% $\Xid{\mathcal{E}}{CTR$\$$}^F$.  This is done using
% \syntax{"\\Xid{"<maths>"}{"<text>"}"}.  The two bits are joined by a text
% hyphen `-'.
%
% \DescribeMacro\cookie
% Sometimes textual names are used for special `symbols', which have meaning
% to algorithms, e.g., the symbols $\cookie{find}$ and $\cookie{guess}$ in
% the standard indistinguishability game.  These can be typeset using the
% |\cookie| command.
%
% \subsection{Other stuff}
%
% \DescribeMacro\Thing
% In the quantifiable-security world, there are standard symbols for
% advantage, success probability, insecurity, etc.  The generic `style hook'
% for these is \syntax{"\\Thing{"<name>"}{"<notion>"}{"scheme"}"}, which
% typesets $\Thing{name}{notion}{scheme}$.  It helps a lot if you have the
% \package{amstext} package loaded.
%
% \DescribeMacro\Succ
% \DescribeMacro\Adv
% \DescribeMacro\InSec
% \DescribeMacro\Expt
% \DescribeMacro\Game
% \begin{synshorts}
% Some standard `things' are provided: "\\Succ{"<notion>"}{"<scheme>"}",
% "\\Adv{"<notion>"}{"<scheme>"}", "\\InSec{"<notion>"}", 
% "\\Expt{"<notion>"}{"<scheme>"}", and "\\Game{"<notion>"}{"<scheme>"}".
% \end{synshorts}
%
% \DescribeMacro\G
% In proofs which proceed by varying the rules of the game played by the
% adversary and bounding the probability of it noticing at each step, game
% names are usually typeset as $\G n$ for small numbers $n$.  The command
% \syntax{"\\G{"<n>"}"} command does this typesetting.  There's an optional
% argument, which is a symbol to write instead of `G'.
%
% \DescribeMacro\Func
% \DescribeMacro\Perm
% When dealing with finite PRFs and PRPs, we need to talk about the set of
% \emph{all} functions (or permutations) over particular sets, usually
% $n$-vectors of bits.  The macros \syntax{"\\Func{"<l>"}{"<L>"}"} and
% \syntax{"\\Perm{"<L>"}"} typeset $\Func{l}{L}$ and $\Perm{L}$ respectively,
% and are intended to denote the sets of all functions $F\colon \{0, 1\}^l
% \to \{0, 1\}^L$ and all permutations $\Pi\colon \{0, 1\}^L \to \{0, 1\}^L$
% respectively. 
%
% \DescribeMacro\PKCS
% Finally, the |\PKCS| macro typesets `\PKCS{$n$}', allowing you to name RSA
% Security Inc.'s Public Key Cryptography Standards in a relatively nice way.
% 
% \implementation
%
%
%^^A-------------------------------------------------------------------------
% \section{Implementation}
%
% We need David Carlisle's handy \package{xspace} package and the AMS |\text|
% command.
%
%    \begin{macrocode}
%<*package>
\RequirePackage{amstext}
\RequirePackage{xspace}
%    \end{macrocode}

% \subsection{Algorithm typsetting}
%
% \begin{macro}{\cookie}
% \begin{macro}{\kw}
% \begin{macro}{\id}
%
% First, some style issues.  Note the |\xspace| at the end of |\kw|.
%
%    \begin{macrocode}
\def\cookie#1{\text{\normalfont\sffamily\/#1\/}}
\def\kw#1{\text{\normalfont\bfseries\/#1\/}\xspace}
\def\id#1{\text{\normalfont\itshape\/#1\/}}
%    \end{macrocode}
%
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\getsr}
% \begin{macro}{\inr}
%
% The symbols for random selection and membership are fairly easy.  The `R'
% over $\getsr$ is actually in scriptscript style, because that seems to look
% nicer.
%
%    \begin{macrocode}
\def\inr{\mathrel{\in_R}}
\def\getsr{\mathrel{\mathop{\gets}\limits^{\scriptscriptstyle R}}}
%    \end{macrocode}
%
% \end{macro}
% \end{macro}
%
% \begin{macro}{\Xid}
%
% The compound identifiers set by |\Xid| are easy.
%
%    \begin{macrocode}
\def\Xid#1#2{\id{$#1$-#2}}
%    \end{macrocode}
%
% \end{macro}
%
% Now for the various keywords.  These are trivial, but useful.
%
%    \begin{macrocode}
\def\RETURN{\kw{return}}
\def\IF{\kw{if}}
\def\THEN{\kw{then}}
\def\ELSE{\kw{else}}
\def\REPEAT{\kw{repeat}}
\def\WHILE{\kw{while}}
\def\UNTIL{\kw{until}}
\def\FOREVER{\kw{forever}}
\def\DO{\kw{do}}
\def\FOR{\kw{for}}
\def\FOREACH{\kw{for\,each}}
\def\FROM{\kw{from}}
\def\IN{\kw{in}}
\def\TO{\kw{to}}
\def\ABORT{\kw{abort}}
\def\PARSE{\kw{parse}}
\def\AS{\kw{as}}
\def\NEW{\ifmmode\mathop{\kw{new}}\else\kw{new}\fi}
%    \end{macrocode}
%
% \begin{environment}{program}
% \begin{macro}{\next}
% \begin{macro}{\newline}
% \begin{macro}{\ind}
%
% Now for the \env{program} environment and its associated twiddling.  This
% is actually a little fiddly.
%
% At the beginning, if we're in vertical mode -- i.e., there was a paragraph
% break before the start of the environment -- then remember this, because it
% affects the typesetting at the end.  Set up |\next| and |\newline| in terms
% of the underlying machinery, and start a row of algorithm.
%
%    \begin{macrocode}
\def\program{%
  \normalfont%
  \@tempswatrue\ifvmode\@tempswafalse\fi%
  \def\next{\program@end\vrule\program@begin}%
  \def\newline{\program@endline\medskip\program@startline}%
  \def\ind{\quad\=\+\kill}%
  \ifdim\topsep<\parskip\topsep\parskip\fi%
  \ifdim\@topsepadd<\z@\@topsepadd\z@\fi%
  \begingroup\trivlist%
  \advance\@topsep-\parskip\advance\@topsepadd-\parskip\item%
  \program@startline%
}
%    \end{macrocode}
%
% Ending the environment is easy-ish.  We stop the current row and leave a
% gap, matching the one that |\poem@startline| adds automatically.  If we
% were initially in horizontal mode, then don't indent the next paragraph,
% and ignore spaces after the |\end{program}| command.
%
%    \begin{macrocode}
\def\endprogram{%
  \program@endline\endtrivlist\endgroup%
  \if@tempswa\@endparenv\fi\@ignoretrue%
}
%    \end{macrocode}
%
% Now for the guts of all of this.  First of all, we turn to the typesetting
% of a column, which is just hfil glue, a \env{minipage} with zero width and
% a \env{tabbing} environment.  The first tab is already set 1\,em in from
% the margin.  We use \env{minipage} to set up the list parameters correctly
% and manage the initial and final spacing.  The zero width is OK because
% \env{tabbing} sets a list of hboxes rather than using outer horizontal
% mode, so the |\hsize| is irrelevant.
%
%    \begin{macrocode}
\def\program@begin{%
  \begingroup%
  \hfil%
  \minipage[t]\z@%
    \topsep\z@%
    \itemsep\z@%
    \parskip\z@\parsep\z@%
    \partopsep\z@%
    \tabbing%
%    \end{macrocode}
%
% This is rather messy.  The |\item| from the \env{trivlist} messes up the
% spacing.  We remove the box, and fix |\prevdepth| to ensure that there's no
% glue at the top.
%
%    \begin{macrocode}
      \quad\=dummy\\%
      \@stopfield%
      \begingroup%
        \setbox\z@\lastbox\unskip\unskip\unskip\setbox\z@\lastbox\unskip%
      \endgroup%
      \prevdepth-\@m\p@%
      \@startfield\strut\ignorespaces%
}
%    \end{macrocode}
%
% Ending a program has no discernable subtlety.
%
%    \begin{macrocode}
\def\program@end{%
    \endtabbing%
  \endminipage%
  \hfil%
  \endgroup%
}
%    \end{macrocode}
%
% Finally, the row setting is fairly easy.  We have to ensure that we obey
% the prevailing list parameters.
%
%    \begin{macrocode}
\def\program@startline{%
  \moveright\@totalleftmargin%
  \hb@xt@\linewidth\bgroup%
    \program@begin%
}
\def\program@endline{%
    \program@end%
  \egroup%
}
%    \end{macrocode}
%
% \end{macro}
% \end{macro}
% \end{macro}
% \end{environment}
%
% \subsection{Other stuff}
%
% \begin{macro}{\Thing}
% \begin{macro}{\Succ}
% \begin{macro}{\Adv}
% \begin{macro}{\InSec}
% \begin{macro}{\Expt}
% \begin{macro}{\Game}
%
% Typesetting |\Thing| is easy.  This acts as a style hook for the rest of
% these things.
%
%    \begin{macrocode}
\def\Thing#1#2#3{\text{\normalfont\bfseries#1}^{\text{\normalfont#2}}_{#3}}
%    \end{macrocode}
%
% And now here they are.
%
%    \begin{macrocode}
\def\Succ{\Thing{Succ}}
\def\Adv{\Thing{Adv}}
\def\InSec#1{\Thing{InSec}{#1}{}}
\def\Expt{\Thing{Expt}}
\def\Game{\Thing{Game}}
%    \end{macrocode}
%
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\G}
%
% The name of a game is typeset simply as
%
%    \begin{macrocode}
\newcommand\G[2][G]{\mathbf{#1}_{#2}}
%    \end{macrocode}
%
% \end{macro}
%
% \begin{macro}{\Func}
% \begin{macro}{\Perm}
%
% The finite sets of functions and permutations are just a style choice.  We
% choose to buck the standard trends and use caligraphic letters.
%
%    \begin{macrocode}
\def\Func#1#2{\mathcal{F}^{#1,#2}}
\def\Perm#1{\mathcal{P}^{#1}}
%    \end{macrocode}
%
% \end{macro}
% \end{macro}
%
% \begin{macro}{\PKCS}
%
% Finally, I find that \PKCS{$n$} looks best typeset like this:
%
%    \begin{macrocode}
\def\PKCS#1{PKCS\,\##1}
%    \end{macrocode}
%
% \end{macro}
%
% \vskip\parskip\vbox{ ^^A The best way I could find of keeping this lot
%                      ^^A together, I'm afraid.
% That's all there is.  Byebye.
%
%    \begin{macrocode}
%</package>
%    \end{macrocode}
% \nopagebreak
%
% \hfill Mark Wooding, \today
% }
% \Finale
%
\endinput