3 % $Id: crypto.dtx,v 1.2 2003/09/05 16:13:14 mdw Exp $
5 % Typesetting crypto papers
7 % (c) 2001 Mark Wooding
9 %----- Revision history -----------------------------------------------------
11 % $Log: crypto.dtx,v $
12 % Revision 1.2 2003/09/05 16:13:14 mdw
13 % Various minor fettlings. Fix paragraph formatting after programs. More
16 % Revision 1.1 2002/02/03 20:49:03 mdw
17 % Checkin for new build system.
22 % \begin{meta-comment} <general public licence>
24 %% crypto package -- useful macros for typesetting crypto papers
25 %% Copyright (c) 2001 Mark Wooding
27 %% This program is free software; you can redistribute it and/or modify
28 %% it under the terms of the GNU General Public License as published by
29 %% the Free Software Foundation; either version 2 of the License, or
30 %% (at your option) any later version.
32 %% This program is distributed in the hope that it will be useful,
33 %% but WITHOUT ANY WARRANTY; without even the implied warranty of
34 %% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
35 %% GNU General Public License for more details.
37 %% You should have received a copy of the GNU General Public License
38 %% along with this program; if not, write to the Free Software Foundation,
39 %% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
42 % \begin{meta-comment} <Package preambles>
43 %<+package>\NeedsTeXFormat{LaTeX2e}
44 %<+package>\ProvidesPackage{crypto}
45 %<+package> [2001/09/16 1.0 Crypto typesetting]
50 %% {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
51 %% 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
52 %% Digits \0\1\2\3\4\5\6\7\8\9
53 %% Exclamation \! Double quote \" Hash (number) \#
54 %% Dollar \$ Percent \% Ampersand \&
55 %% Acute accent \' Left paren \( Right paren \)
56 %% Asterisk \* Plus \+ Comma \,
57 %% Minus \- Point \. Solidus \/
58 %% Colon \: Semicolon \; Less than \<
59 %% Equals \= Greater than \> Question mark \?
60 %% Commercial at \@ Left bracket \[ Backslash \\
61 %% Right bracket \] Circumflex \^ Underscore \_
62 %% Grave accent \` Left brace \{ Vertical bar \|
63 %% Right brace \} Tilde \~}
66 % \begin{meta-comment}
70 \describespackage{crypto}
76 %^^A-------------------------------------------------------------------------
77 % \section{User guide}
79 % \subsection{Algorithm typesetting}
81 % A lot of provable-security papers need to be able to typeset algorithms
82 % describing adversaries, schemes, oracle behaviour, etc. There is a
83 % (relatively) standard format for doing this which we support.
85 % \DescribeEnv{program}
86 % The \env{program} environment provides handy notation for describing
87 % algorithms formally. It gives a \env{tabbing} environment, so that things
88 % can be laid out nicely, and allows fragments of algorithms to be laid out
89 % in columns or rows, with separating rules.
92 % Within the \env{program} environment, the |\next| command stops typesetting
93 % the current column, typesets a vertical separator rule, and starts a new
94 % column. Adjacent columns are spaced out evenly across the page, with equal
95 % space around the rules rules and at the current margins. This means that
96 % the rules don't line up, but it still seems to provide a pleasing effect.
98 % \DescribeMacro\newline
99 % The |\newline| macro begins a new row of algorithm typesetting. A page
100 % break is possible at a |\newline|.
103 % A number of standard keywords are available, as shown in
104 % table~\ref{tab:kw}. The typsetting of these is done by the |\kw| command,
105 % which usually sets its argument in text bold face, but can be redefined.
106 % The standard definition uses |\xspace| so that you don't need to remember
107 % to say \verb*+\ + after a keyword command.
110 % \def\row#1{\texttt{\string#1} & #1 \\}
111 % \begin{tabular}{ll}
112 % \textbf{Command} & \textbf{Keyword} \\
132 % \caption{Keywords available for algorithm typesetting}
137 % Within a \env{program} environment, the |\ind| command shunts the indent
138 % level 1\,em to the right.
140 % \DescribeMacro\gets
141 % \DescribeMacro\getsr
143 % Assignment can be represented using the standard command |\gets|, which
144 % typesets a left-pointing arrow `$\gets$'. Random sampling -- the selection
145 % of a random element from a set or probability distribution -- can be
146 % represented using the new command |\getsr|, which typesets an arrow with a
147 % little `R' above it `$\getsr$'. Random membership -- showing that
148 % something is a random variable with some distribution -- can be represented
149 % using the |\inr| command, which just typesets an $\in$ sign with a
150 % subscript `R': `$\inr$'.
152 % Should one wish, one can use a different character than `R' to denote
153 % randomness. Some authors use `\$', for example. I know of one
154 % (cheapskate?) author who has used `\rlap/c'. Redefining the |\random|
155 % command lets you do this. For example, you can say
156 % |\newcommand{\random}{\$}| should you so wish.
159 % Long identifiers can be typeset using the |\id| command. giving the
160 % identifier name as an argument. The |\id| command is only valid in maths
161 % mode. As currently set up, |\id| sets its argument in \emph{text} italics;
162 % this seems to look better in documents which use a PostScript body face and
163 % Computer Modern for maths.
166 % It's handy to be able to glue a bit of (possibly fancy) maths typesetting
167 % to an identifier, e.g., to construct $\Xid{H'}{list}$, or
168 % $\Xid{\mathcal{E}}{CTR$\$$}^F$. This is done using
169 % \syntax{"\\Xid{"<maths>"}{"<text>"}"}. The two bits are joined by a text
172 % \DescribeMacro\cookie
173 % Sometimes textual names are used for special `symbols', which have meaning
174 % to algorithms, e.g., the symbols $\cookie{find}$ and $\cookie{guess}$ in
175 % the standard indistinguishability game. These can be typeset using the
178 % \subsection{Other stuff}
180 % \DescribeMacro\Thing
181 % In the quantifiable-security world, there are standard symbols for
182 % advantage, success probability, insecurity, etc. The generic `style hook'
183 % for these is \syntax{"\\Thing{"<name>"}{"<notion>"}{"scheme"}"}, which
184 % typesets $\Thing{name}{notion}{scheme}$. It helps a lot if you have the
185 % \package{amstext} package loaded.
187 % \DescribeMacro\Succ
189 % \DescribeMacro\InSec
190 % \DescribeMacro\Expt
191 % \DescribeMacro\Game
193 % Some standard `things' are provided: "\\Succ{"<notion>"}{"<scheme>"}",
194 % "\\Adv{"<notion>"}{"<scheme>"}", "\\InSec{"<notion>"}",
195 % "\\Expt{"<notion>"}{"<scheme>"}", and "\\Game{"<notion>"}{"<scheme>"}".
199 % In proofs which proceed by varying the rules of the game played by the
200 % adversary and bounding the probability of it noticing at each step, game
201 % names are usually typeset as $\G n$ for small numbers $n$. The command
202 % \syntax{"\\G{"<n>"}"} command does this typesetting. There's an optional
203 % argument, which is a symbol to write instead of `G'.
205 % \DescribeMacro\Func
206 % \DescribeMacro\Perm
207 % When dealing with finite PRFs and PRPs, we need to talk about the set of
208 % \emph{all} functions (or permutations) over particular sets, usually
209 % $n$-vectors of bits. The macros \syntax{"\\Func{"<l>"}{"<L>"}"} and
210 % \syntax{"\\Perm{"<L>"}"} typeset $\Func{l}{L}$ and $\Perm{L}$ respectively,
211 % and are intended to denote the sets of all functions $F\colon \{0, 1\}^l
212 % \to \{0, 1\}^L$ and all permutations $\Pi\colon \{0, 1\}^L \to \{0, 1\}^L$
215 % \DescribeMacro\PKCS
216 % Finally, the |\PKCS| macro typesets `\PKCS{$n$}', allowing you to name RSA
217 % Security Inc.'s Public Key Cryptography Standards in a relatively nice way.
222 %^^A-------------------------------------------------------------------------
223 % \section{Implementation}
225 % We need David Carlisle's handy \package{xspace} package and the AMS |\text|
230 \RequirePackage{amstext}
231 \RequirePackage{xspace}
234 % \subsection{Algorithm typsetting}
236 % \begin{macro}{\cookie}
240 % First, some style issues. Note the |\xspace| at the end of |\kw|.
243 \def\cookie#1{\text{\normalfont\sffamily\/#1\/}}
244 \def\kw#1{\text{\normalfont\bfseries\/#1\/}\xspace}
245 \def\id#1{\text{\normalfont\itshape\/#1\/}}
252 % \begin{macro}{\getsr}
253 % \begin{macro}{\inr}
255 % The symbols for random selection and membership are fairly easy. The `R'
256 % over $\getsr$ is actually in scriptscript style, because that seems to look
260 \providecommand\random{R}
261 \def\inr{\mathrel{\in_{\random}}}
262 \def\getsr{\mathrel{\mathop{\gets}\limits^{\scriptscriptstyle\random}}}
268 % \begin{macro}{\Xid}
270 % The compound identifiers set by |\Xid| are easy.
273 \def\Xid#1#2{\id{$#1$-#2}}
278 % Now for the various keywords. These are trivial, but useful.
281 \def\RETURN{\kw{return}}
285 \def\REPEAT{\kw{repeat}}
286 \def\WHILE{\kw{while}}
287 \def\UNTIL{\kw{until}}
288 \def\FOREVER{\kw{forever}}
291 \def\FOREACH{\kw{for\,each}}
295 \def\ABORT{\kw{abort}}
296 \def\PARSE{\kw{parse}}
298 \def\NEW{\ifmmode\mathop{\kw{new}}\else\kw{new}\fi}
300 \def\OUTPUT{\kw{output}}
304 % \begin{environment}{program}
305 % \begin{macro}{\next}
306 % \begin{macro}{\newline}
307 % \begin{macro}{\ind}
309 % Now for the \env{program} environment and its associated twiddling. This
310 % is actually a little fiddly.
312 % At the beginning, if we're in vertical mode -- i.e., there was a paragraph
313 % break before the start of the environment -- then remember this, because it
314 % affects the typesetting at the end. Set up |\next| and |\newline| in terms
315 % of the underlying machinery, and start a row of algorithm.
320 \@tempswatrue\ifvmode\@tempswafalse\fi%
321 \def\next{\program@end\vrule\program@begin}%
322 \def\newline{\program@endline\medskip\program@startline}%
323 \def\ind{\quad\=\+\kill}%
324 \ifdim\topsep<\parskip\topsep\parskip\fi%
325 \ifdim\@topsepadd<\z@\@topsepadd\z@\fi%
326 \begingroup\trivlist%
327 \advance\@topsep-\parskip\advance\@topsepadd-\parskip\item%
332 % Ending the environment is easy-ish. We stop the current row and leave a
333 % gap, matching the one that |\poem@startline| adds automatically. If we
334 % were initially in horizontal mode, then don't indent the next paragraph,
335 % and ignore spaces after the |\end{program}| command.
339 \program@endline\endtrivlist\endgroup%
340 \if@tempswa\@endparenv\fi\@ignoretrue%
344 % Now for the guts of all of this. First of all, we turn to the typesetting
345 % of a column, which is just hfil glue, a \env{minipage} with zero width and
346 % a \env{tabbing} environment. The first tab is already set 1\,em in from
347 % the margin. We use \env{minipage} to set up the list parameters correctly
348 % and manage the initial and final spacing. The zero width is OK because
349 % \env{tabbing} sets a list of hboxes rather than using outer horizontal
350 % mode, so the |\hsize| is irrelevant.
359 \parskip\z@\parsep\z@%
364 % This is rather messy. The |\item| from the \env{trivlist} messes up the
365 % spacing. We remove the box, and fix |\prevdepth| to ensure that there's no
372 \setbox\z@\lastbox\unskip\unskip\unskip\setbox\z@\lastbox\unskip%
375 \@startfield\strut\ignorespaces%
379 % Ending a program has no discernable subtlety.
390 % Finally, the row setting is fairly easy. We have to ensure that we obey
391 % the prevailing list parameters.
394 \def\program@startline{%
395 \moveright\@totalleftmargin%
396 \hb@xt@\linewidth\bgroup%
399 \def\program@endline{%
410 % \subsection{Other stuff}
412 % \begin{macro}{\Thing}
413 % \begin{macro}{\Succ}
414 % \begin{macro}{\Adv}
415 % \begin{macro}{\InSec}
416 % \begin{macro}{\Expt}
417 % \begin{macro}{\Game}
419 % Typesetting |\Thing| is easy. This acts as a style hook for the rest of
423 \def\Thing#1#2#3{\text{\normalfont\bfseries#1}^{\text{\normalfont#2}}_{#3}}
426 % And now here they are.
429 \def\Succ{\Thing{Succ}}
430 \def\Adv{\Thing{Adv}}
431 \def\InSec#1{\Thing{InSec}{#1}{}}
432 \def\Expt{\Thing{Expt}}
433 \def\Game{\Thing{Game}}
445 % The name of a game is typeset simply as
448 \newcommand\G[2][G]{\mathbf{#1}_{#2}}
453 % \begin{macro}{\Func}
454 % \begin{macro}{\Perm}
456 % The finite sets of functions and permutations are just a style choice. We
457 % choose to buck the standard trends and use caligraphic letters.
460 \def\Func#1#2{\mathcal{F}^{#1,#2}}
461 \def\Perm#1{\mathcal{P}^{#1}}
467 % \begin{macro}{\PKCS}
469 % Finally, I find that \PKCS{$n$} looks best typeset like this:
472 \def\PKCS#1{PKCS\,\##1}
477 % \vskip\parskip\vbox{ ^^A The best way I could find of keeping this lot
478 % ^^A together, I'm afraid.
479 % That's all there is. Byebye.
486 % \hfill Mark Wooding, \today