diff options
author | Karl Berry <karl@freefriends.org> | 2015-03-24 21:18:29 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2015-03-24 21:18:29 +0000 |
commit | 5aeb41ca04c8e1569d208402993903b5f0440be9 (patch) | |
tree | b76fac3b05a66e400a17c83b5e00a653cc692948 /Master | |
parent | 1b9aa95deee3641bd94fd7589b3ebe1e84f87103 (diff) |
cryptocode (24mar15)
git-svn-id: svn://tug.org/texlive/trunk@36612 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master')
-rw-r--r-- | Master/texmf-dist/doc/latex/cryptocode/README | 8 | ||||
-rw-r--r-- | Master/texmf-dist/doc/latex/cryptocode/cryptocode.pdf | bin | 0 -> 810963 bytes | |||
-rw-r--r-- | Master/texmf-dist/doc/latex/cryptocode/cryptocode.tex | 3315 | ||||
-rw-r--r-- | Master/texmf-dist/tex/latex/cryptocode/cryptocode.sty | 1406 | ||||
-rwxr-xr-x | Master/tlpkg/bin/tlpkg-ctan-check | 2 | ||||
-rw-r--r-- | Master/tlpkg/tlpsrc/collection-science.tlpsrc | 1 | ||||
-rw-r--r-- | Master/tlpkg/tlpsrc/cryptocode.tlpsrc | 0 |
7 files changed, 4731 insertions, 1 deletions
diff --git a/Master/texmf-dist/doc/latex/cryptocode/README b/Master/texmf-dist/doc/latex/cryptocode/README new file mode 100644 index 00000000000..fa65b30894b --- /dev/null +++ b/Master/texmf-dist/doc/latex/cryptocode/README @@ -0,0 +1,8 @@ +The cryptocode bundle provides commands and commands for easily typesetting +pseudocode and simple protocols as well as environments for visualizing +game-based proofs and black-box reductions as often used within the cryptographic +community. + +The cryptocode bundle is licensed under the LaTeX Project Public License + + -- Arno Mittelbach <mail@arno-mittelbach.de> 23 Mar 2015
\ No newline at end of file diff --git a/Master/texmf-dist/doc/latex/cryptocode/cryptocode.pdf b/Master/texmf-dist/doc/latex/cryptocode/cryptocode.pdf Binary files differnew file mode 100644 index 00000000000..802ec5b0226 --- /dev/null +++ b/Master/texmf-dist/doc/latex/cryptocode/cryptocode.pdf diff --git a/Master/texmf-dist/doc/latex/cryptocode/cryptocode.tex b/Master/texmf-dist/doc/latex/cryptocode/cryptocode.tex new file mode 100644 index 00000000000..3dd048a2aee --- /dev/null +++ b/Master/texmf-dist/doc/latex/cryptocode/cryptocode.tex @@ -0,0 +1,3315 @@ + %% Copyright 2015 Arno Mittelbach + % + % This work may be distributed and/or modified under the + % conditions of the LaTeX Project Public License, either version 1.3 + % of this license or (at your option) any later version. + % The latest version of this license is in + % http://www.latex-project.org/lppl.txt + % and version 1.3 or later is part of all distributions of LaTeX + % version 2005/12/01 or later. + % + % This work has the LPPL maintenance status `maintained'. + % + % The Current Maintainer of this work is Arno Mittelbach. + % + % This work consists of the files cryptocode.tex and cryptocode.sty + +\documentclass[a4paper]{report} + +% more than one optional parameter +\usepackage[usenames]{xcolor} +\usepackage{hyperref} +\usepackage[ + n, + operators, + advantage, + sets, + adversary, + landau, + probability, + notions, + logic, + ff, + mm, + primitives, + events, + complexity, + asymptotics, + keys]{cryptocode} + + +\usepackage{csquotes} +\usepackage{fullpage} +\usepackage{dashbox} +\usepackage{todonotes} + +\usepackage{url} + + +\usetikzlibrary{shapes.callouts} +\usetikzlibrary{ocgx} + +\usepackage{listings} + +\usepackage{trace} + +\usepackage{makeidx} +\makeindex + + +\author{Arno Mittelbach\\ +\texttt{mail@arno-mittelbach.de}} +\title{\Huge Cryptocode \\ \large\textsc{Typesetting Cryptography}} + +\definecolor{mygreen}{rgb}{0,0.6,0} +\definecolor{mygray}{rgb}{0.5,0.5,0.5} +\definecolor{mymauve}{rgb}{0.58,0,0.82} + +\lstset{language=[LaTeX]TeX, + backgroundcolor=\color{white}, % choose the background color; you must add \usepackage{color} or \usepackage{xcolor} + basicstyle=\footnotesize, % the size of the fonts that are used for the code + breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace + breaklines=true, % sets automatic line breaking + captionpos=b, % sets the caption-position to bottom + commentstyle=\color{mygreen}, % comment style + deletekeywords={...}, % if you want to delete keywords from the given language + escapeinside={\%*}{*)}, % if you want to add LaTeX within your code + extendedchars=true, % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8 + frame=single, % adds a frame around the code + keepspaces=true, % keeps spaces in text, useful for keeping indentation of code (possibly needs columns=flexible) + keywordstyle=\color{blue}, % keyword style + language=Octave, % the language of the code + morekeywords={*,...}, % if you want to add more keywords to the set + numbers=left, % where to put the line-numbers; possible values are (none, left, right) + numbersep=5pt, % how far the line-numbers are from the code + numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers + rulecolor=\color{black}, % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here)) + showspaces=false, % show spaces everywhere adding particular underscores; it overrides 'showstringspaces' + showstringspaces=false, % underline spaces within strings only + showtabs=false, % show tabs within strings adding particular underscores + stepnumber=2, % the step between two line-numbers. If it's 1, each line will be numbered + stringstyle=\color{mymauve}, % string literal style + tabsize=2, % sets default tabsize to 2 spaces + title=\lstname } + +\begin{document} +%\pcfixhyperref + +\maketitle + + + + +\begin{abstract} +\thispagestyle{empty} +The cryptocode package is targeted at cryptographers typesetting their results in \LaTeX. +It provides various predefined commands for different topics in cryptography. +In particular it provides an easy interface to write pseudocode, protocols, game based proofs +and draw black-box reductions. + + +\vspace{2em} +\begin{center} +\fbox{ +\pseudocode{% +\textbf{ Alice} \< \< \textbf{ Bob} \\[0.5\baselineskip][\hline] + \<\< \\[-0.5\baselineskip] +x \sample \ZZ_q \< \< \\ + X \gets g^x \<\< \\ + \< \sendmessageright*{\GG,q,g,X} \< \\ + \<\< y \sample \ZZ_q \\ + \<\< Y \gets g^y \\ + \< \sendmessageleft*{Y} \< \\ + \key_A \gets Y^x \<\< \key_B \gets X^y } +} +\end{center} + + + +\end{abstract} +\newpage + +\pagenumbering{arabic} + +\tableofcontents +\thispagestyle{empty} +\newpage + +\chapter{Cryptocode by Example} + +Cryptocode is a \LaTeX package to ease the writing of cryptographic papers. It provides mechanisms +for writing pseudocode, protocols, game-based proofs and black-box reductions. In addition it comes +with a large number of predefined commands. In this chapter we present the various features of +cryptocode by giving small examples. But first, let's load the package + +\begin{lstlisting} +\usepackage[ + n, + advantage, + operators, + sets, + adversary, + landau, + probability, + notions, + logic, + ff, + mm, + primitives, + events, + complexity, + asymptotics, + keys + ]{cryptocode} +\end{lstlisting} + +Note that all the options refer to a set of commands. That is, without any options cryptocode will provide the mechanisms +for writing pseudocode, protocols, game-based proofs and black-box reductions but not define additional commands, +such as \lstinline$\pk$ or \lstinline$\sk$ (for typesetting public and private/secret keys) which are part of the keys option. +We discuss the various options and associated commands in Chapter~\ref{chap:commands}. + + +\section{Pseudocode} +The cryptocode package tries to make writing pseudocode easy and enjoyable. The +\lstinline$\pseudocode$ command takes a single parameter where you can start writing +code in mathmode using \lstinline{\\} as line breaks. Following is an $\indcpa$ game +definition using various commands from cryptocode to ease writing keys (\lstinline{\pk,\sk}), +sampling (\lstinline{\sample}), and more: +\begin{center} +\fbox{\pseudocode[linenumbering,syntaxhighlight=auto]{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen (\secparam) \\ + (\state,m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c, \state) \\ + return b = b' }} +\end{center} + + +The above code is generated by (the code is actually wrapped in an \lstinline$fbox$). +\begin{lstlisting} +\pseudocode[linenumbering,syntaxhighlight=auto]{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen (\secparam) \\ + (\state,m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c, \state) \\ + return b = b' } +\end{lstlisting} +The pseudocode command thus takes a single mandatory argument (the code) plus an optional argument +which allows you to specify options in a key=value fashion. In the above example we used the linenumbering +option (which not surprisingly adds line numbers to the code) as well as the syntaxhighlighting option which +highlights certain keywords (in the example it is responsible for setting \enquote{return} as \pseudocodeconstant[]{return}). + +It is easy to define a heading for your code. Either specify the header using the option \enquote{head} or use +the \lstinline$\procedure$ command which takes an additional argument to specify the headline. +\begin{center} +\fbox{\procedure[linenumbering]{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen (\secparam) \\ + (\state,m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c, \state) \\ + \pcreturn b = b' }} +\end{center} +\begin{lstlisting} +\procedure[linenumbering]{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen (\secparam) \\ + (\state,m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c, \state) \\ + \pcreturn b = b' } +\end{lstlisting} +Here in the example we have not turned on the automatic syntax highlighting but used the command \lstinline$\pcreturn$ +to highlight the return statement. Besides \lstinline$\pcreturn$ there are a variant of predefined \enquote{PseudocodeConstants} +such as \lstinline$\pcfor$, \lstinline$\pcif$, etc. + +There is a lot more that we will discuss in detail in Chapter~\ref{chap:pseudocode}. Here, for example +is the same code with an overlay explanation and a division of the pseudocode. +\begin{center} +\fbox{ +\begin{pcimage} +\procedure[linenumbering]{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen (\secparam)\pcnode{kgen} \pclb + \pcintertext[dotted]{Setup Completed} + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c, \state) \\ + \pcreturn b = b' } + +\pcdraw{ + \node[rectangle callout,callout absolute pointer=(kgen),fill=orange] + at ([shift={(+3,-1)}]kgen) { + \begin{varwidth}{3cm} + $\kgen(\secparam)$ samples a public key $\pk$ and a private key $\sk$. + \end{varwidth} + }; +} +\end{pcimage} +} +\end{center} + +\begin{lstlisting} +\begin{pcimage} +\procedure[linenumbering]{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen (\secparam)\pcnode{kgen} \pclb + \pcintertext[dotted]{Setup Completed} + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c, \state) \\ + \pcreturn b = b' } + +\pcdraw{ + \node[rectangle callout,callout absolute pointer=(kgen),fill=orange] + at ([shift={(+3,-1)}]kgen) { + \begin{varwidth}{3cm} + $\kgen(\secparam)$ samples a public key $\pk$ and a private key $\sk$. + \end{varwidth} + }; +} +\end{pcimage} +\end{lstlisting} + +\section{Columns} +The \lstinline$\pseudocode$ and \lstinline$\procedure$ commands allow the usage of multiple columns. +You switch to a new column by inserting a \lstinline$\>$. This is similar to using an \lstinline$align$ +environment and placing a tabbing \& character.\footnote{In fact, the \emph{pseudocode} command +is based on amsmath's flalign environment.} +\begin{center} +\fbox{% +\pseudocode{% + \textbf{First} \> \textbf{Second} \> \textbf{Third} \> \textbf{Fourth} \\ + b \sample \bin \> b \sample \bin \> b \sample \bin \> b \sample \bin} +} +\end{center} +\begin{lstlisting} +\pseudocode{% + \textbf{First} \> \textbf{Second} \> \textbf{Third} \> \textbf{Fourth} \\ + b \sample \bin \> b \sample \bin \> b \sample \bin \> b \sample \bin} +\end{lstlisting} +As you can see the first column is left aligned the second right, the third left and so forth. +In order to get only left aligned columns you could thus simply always skip a column by +using \lstinline$\>\>$. You can also use \lstinline$\<$ a shorthand for \lstinline$\>\>$. +\begin{center} +\fbox{% +\pseudocode{% + \textbf{First} \< \textbf{Second} \< \textbf{Third} \< \textbf{Fourth} \\ + b \sample \bin \< b \sample \bin \< b \sample \bin \< b \sample \bin} +} +\end{center} + +\section{Protocols} +Using columns makes it easy to write even complex protocols. Following is a simple +three party protocol +\begin{center} +\fbox{% +\pseudocode{% + \textbf{Alice} \< \< \textbf{Bob} \< \< \textbf{Charlie} \\[][\hline] + \text{work} \< \< \< \< \\ + \< \sendmessageright{top=Work result,topstyle=red} \< \< \< \\ + \< \< \text{work} \< \< \\ + \< \< \< \sendmessageright{top=Work result,bottom=Bottom message} \< \\ + \< \< \< \< \text{work} \\ + \< \sendmessageleftx{8}{\text{A long message for Alice}} \< \\ + \text{finalize} \< \< \< \< } +} +\end{center} +\begin{lstlisting} +\pseudocode{% + \textbf{Alice} \< \< \textbf{Bob} \< \< \textbf{Charlie} \\[][\hline] + \text{work} \< \< \< \< \\ + \< \sendmessageright{top=Work result,topstyle=red} \< \< \< \\ + \< \< \text{work} \< \< \\ + \< \< \< \sendmessageright{top=Work result,bottom=Bottom message} \< \\ + \< \< \< \< \text{work} \\ + \< \sendmessageleftx{8}{\text{A long message for Alice}} \< \\ + \text{finalize} \< \< \< \< } +\end{lstlisting} +The commands \lstinline$\sendmessageright$ and \lstinline$\sendmessageleft$ are very flexible and +allow to style the sending of messages in various ways. Also note the \lstinline$\\[][\hline]$ at the end of the +first line. Here the first optional argument allows us to specify the lineheight (similarly to the behavior in an +align environment). The second optional argument allows us to, for example, draw a horizontal line. + +In multi player protocols such as the one +above the commands \lstinline$\sendmessagerightx$ and \lstinline$\sendmessageleftx$ (note the x at the end) +allow to send messages over multiple columns. In the example, as we were using \lstinline$\<$ the +final message thus spans 8 columns. + +For basic protocols you might also utilize the \lstinline$\sendmessageright*$ and \lstinline$\sendmessageleft*$ +commands which simply take a message which is displayed. +\begin{center} +\fbox{% +\pseudocode{% +\textbf{ Alice} \< \< \textbf{ Bob} \\[0.5\baselineskip][\hline] + \<\< \\[-0.5\baselineskip] +x \sample \ZZ_q \< \< \\ + X \gets g^x \<\< \\ + \< \sendmessageright*{\GG,q,g,X} \< \\ + \<\< y \sample \ZZ_q \\ + \<\< Y \gets g^y \\ + \< \sendmessageleft*{Y} \< \\ + \key_A \gets Y^x \<\< \key_B \gets X^y +} +} +\end{center} +\begin{lstlisting} +\pseudocode{% +\textbf{ Alice} \< \< \textbf{ Bob} \\[0.5\baselineskip][\hline] + \<\< \\[-0.5\baselineskip] +x \sample \ZZ_q \< \< \\ + X \gets g^x \<\< \\ + \< \sendmessageright*{\GG,q,g,X} \< \\ + \<\< y \sample \ZZ_q \\ + \<\< Y \gets g^y \\ + \< \sendmessageleft*{Y} \< \\ + \key_A \gets Y^x \<\< \key_B \gets X^y } +\end{lstlisting} +We will discuss protocols in greater detail in Chapter~\ref{chap:protocols}. + +\section{Game-based Proofs} +Cryptocode supports authors in visualizing game-based proofs. It defines an environment +\lstinline$gameproof$ which allows to wrap a number of game procedures displaying helpful +information as to what changes from game to game, and to what each step is reduced. + +\vspace{2\baselineskip} +\begin{center} +\begin{gameproof} +\gameprocedure[linenumbering,mode=text]{% + Step 1 \\ + Step 2 \\ + Step 3 + } +\gameprocedure[mode=text]{% + Step 1 \\ + \gamechange{Step 2 is different} \\ + Step 3 + } +\addgamehop{1}{2}{hint={\footnotesize some hint}} +\end{gameproof} +\end{center} +\begin{lstlisting} +\begin{gameproof} +\gameprocedure[linenumbering,mode=text]{% + Step 1 \\ + Step 2 \\ + Step 3 + } +\gameprocedure[mode=text]{% + Step 1 \\ + \gamechange{Step 2 is different} \\ + Step 3 + } +\addgamehop{1}{2}{hint={\footnotesize some hint}} +\end{gameproof} +\end{lstlisting} +Note that we made use of the option \enquote{mode=text} in the above example which tells the underlying pseudocode +command to not work in math mode but in plain text mode. We'll discuss how to visualize game-based proofs in Chapter~\ref{chap:gbproofs}. + +\section{Black-box Reductions} +Cryptocode provides a strucured syntax to visualize black-box reductions. Basically cryptocode +provides an environment to draw boxes that may have oracles and that can be communicated with. +Cryptocode makes heavy use of TIKZ (\url{https://www.ctan.org/pkg/pgf}) for this, which gives you +quite some control over how things should look like. Additionally, as you can specify node names +(for example the outer box in the next example is called \enquote{A}) you can easily extend the pictures +by using plain TIKZ commands. +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} \\ + \text{Step 2} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Adversary,minheight=4cm] + \end{bbrbox} + + \bbrmsgto{top=$m$} + \bbrmsgfrom{top=$\sigma$} + \bbrmsgtxt{\pseudocode{% + \text{more work} + }} + \bbrmsgto{top=$m$} + \bbrmsgfrom{top=$\sigma$} + + \bbrqryto{side=$m$} + \bbrqryfrom{side=$b$} + \end{bbrenv} + + \pseudocode{ + \text{finalize} + } + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} + + \begin{bbroracle}{OraA} + \begin{bbrbox}[name=Oracle 1,minheight=1cm] + \end{bbrbox} + \end{bbroracle} + \bbroraclequeryto{top=$m$} + \bbroraclequeryfrom{top=$b$} + + \begin{bbroracle}{OraB} + \begin{bbrbox}[name=Oracle 2,minheight=1cm] + \end{bbrbox} + \end{bbroracle} + \bbroraclequeryto{top=$m$} + \bbroraclequeryfrom{top=$b$} +\end{bbrenv} +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} \\ + \text{Step 2} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Adversary,minheight=4cm] + \end{bbrbox} + + \bbrmsgto{top=$m$} + \bbrmsgfrom{top=$\sigma$} + \bbrmsgtxt{\pseudocode{% + \text{more work} + }} + \bbrmsgto{top=$m$} + \bbrmsgfrom{top=$\sigma$} + + \bbrqryto{side=$m$} + \bbrqryfrom{side=$b$} + \end{bbrenv} + + \pseudocode{ + \text{finalize} + } + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} + + \begin{bbroracle}{OraA} + \begin{bbrbox}[name=Oracle 1,minheight=1cm] + \end{bbrbox} + \end{bbroracle} + \bbroraclequeryto{top=$m$} + \bbroraclequeryfrom{top=$b$} + + \begin{bbroracle}{OraB} + \begin{bbrbox}[name=Oracle 2,minheight=1cm] + \end{bbrbox} + \end{bbroracle} + \bbroraclequeryto{top=$m$} + \bbroraclequeryfrom{top=$b$} +\end{bbrenv} +\end{lstlisting} +We'll discuss the details in Chapter~\ref{chap:bbr}. + +\chapter{Cryptographic Notation} +In this section we'll discuss the various commands for notation that can be loaded via package options. +\begin{lstlisting} +\usepackage[ + n, + advantage, + operators, + sets, + adversary, + landau, + probability, + notions, + logic, + ff, + mm, + primitives, + events, + complexity, + asymptotics, + keys + ]{cryptocode} +\end{lstlisting} + +\textbf{Remark. } The commands defined so far are far from complete and are currently mostly targeted at what I needed in my +papers (especially once you get to cryptographic notions and primitives). So please if you feel that something should be added +drop me an email. + +\section{Security Parameter} +In cryptography we make use of a security parameter which is usually written as $1^n$ or $1^\lambda$. The cryptocode +package, when loading either option \enquote{n} or option \enquote{lambda} will define the commands +\begin{lstlisting} + \secpar + \secparam +\end{lstlisting} +The first command provides the \enquote{letter}, i.e., either $n$ or $\lambda$, whereas \lstinline$\secparam$ points +to $1^\secpar$. + +\section{Advantage Terms} +Load the package option ``advantage'' in order to define the command \lstinline$\advantage$ used to specify advantage terms such as: +\[ +\advantage{prf}{\adv,\prf} = \negl +\] +\begin{lstlisting} + \advantage{prf}{\adv,\prf} = \negl +\end{lstlisting} +Specify an optional third parameter to replace the $(\secpar)$. + +\section{Math Operators} +The \enquote{operators} option provides the following list of commands: + +\begin{center} +\begin{tabular}{l l l l} +\textbf{Command} & \textbf{Description} & \textbf{Result} & \textbf{Example} \\\hline +\lstinline$\sample$ & Sampling from a distribution, or running a randomized procedure & $\sample$ & $b \sample \bin$ \\ +\lstinline$\floor$ & Rounding down & $\floor{42.5}$ & \\ +\lstinline$\ceil$ & Rounding up & $\ceil{41.5}$ & \\ +\lstinline$\Angle$ & Vector product & $\Angle{x,y}$ & \\ +\lstinline$\abs$ & Absolute number & $\abs{42.9}$ & \\ +\lstinline$\norm$ & Norm & $\norm{x}$ & \\ +\lstinline$\concat$ & Verbose concatenation (I usually prefer simply \lstinline$\|$) & $\concat$ & $x \gets a\concat b$ \\ +\lstinline$\emptystring$ & The empty string & $\emptystring$ & $x \gets \emptystring$ +\end{tabular} +\end{center} + +\section{Adversaries} +The \enquote{adversary} option provides the following list of commands: + +\begin{center} +\begin{tabular}{l l l} +\textbf{Command} & \textbf{Description} & \textbf{Result} \\\hline +\lstinline$\adv$ & Adversary & $\adv$ \\ +\lstinline$\bdv$ & Adversary & $\bdv$ \\ +\lstinline$\cdv$ & Adversary & $\cdv$ \\ +\lstinline$\ddv$ & Adversary & $\ddv$ \\ +\lstinline$\mdv$ & Adversary & $\mdv$ \\ +\lstinline$\pdv$ & Adversary & $\pdv$ \\ +\lstinline$\sdv$ & Adversary & $\sdv$ +\end{tabular} +\end{center} + +The style in which an adversary is rendered is controlled via +\begin{lstlisting} +\renewcommand{\pcadvstyle}[1]{\mathcal{#1}} +\end{lstlisting} + + +\section{Landau} +The \enquote{landau} option provides the following list of commands: + +\begin{center} +\begin{tabular}{l l l} +\textbf{Command} & \textbf{Description} & \textbf{Result} \\\hline +\lstinline$\bigO{n^2}$ & Big O notation & $\bigO{n^2}$ \\ +\lstinline$\smallO{n^2}$ & small o notation & $\smallO{n^2}$ \\ +\lstinline$\bigOmega{n^2}$ & Big Omega notation & $\bigOmega{n^2}$ \\ +\lstinline$\bigsmallO{n^2}$ & Big and small O notation & $\bigsmallO{n^2}$ +\end{tabular} +\end{center} + + +\section{Probabilities} +The \enquote{probability} option provides commands for writing probabilities. Use +\begin{lstlisting} +\prob{X=x} +\probsub{x\sample{\bin^n}}{x=5} +\condprob{X=x}{A=b} +\condprobsub{x\sample{\bin^n}}{x=5}{A=b} +\end{lstlisting} +to write basic probabilities, probabilities with explicit probability spaces and conditional probabilities. +\begin{align*} +& \prob{X=x} \\ +& \probsub{x\sample{\bin^n}}{X=x} \\ +& \condprob{X=x}{A=b} \\ +& \condprobsub{x\sample{\bin^n}}{x=5}{A=b} +\end{align*} +You can control the probability symbol (Pr) by redefining +\begin{lstlisting} +\renewcommand{\probname}{Pr} +\end{lstlisting} + +For expectations you can use +\begin{lstlisting} +\expect{X} +\expsub{x,y\sample\set{1,\ldots,6}}{x+y} +\condexp{X+Y}{Y>3} +\condexpsub{x,y\sample\set{1,\ldots,6}}{x+y}{y>3} +\end{lstlisting} +yielding +\begin{align*} +& \expect{X} \\ +& \expsub{x,y\sample\set{1,\ldots,6}}{x+y} \\ +& \condexp{X+Y}{Y>3} \\ +& \condexpsub{x,y\sample\set{1,\ldots,6}}{x+y}{y>3} +\end{align*} +You can control the expactation symbol ($\mathbb{E}$) by redefining +\begin{lstlisting} +\renewcommand{\expectationname}{\ensuremath{\mathbb{E}}} +\end{lstlisting} + +The support $\supp{X}$ of a random variable $X$ can be written as +\begin{lstlisting} +\supp{X} +\end{lstlisting} +where again the name can be controlled via +\begin{lstlisting} +\renewcommand{\supportname}{Supp} +\end{lstlisting} + +For denoting entropy and min-entropy use +\begin{lstlisting} +\entropy{X} +\minentropy{X} +\condminentropy{X}{Y=5} +\end{lstlisting} +This yields +\begin{align*} +& \entropy{X} \\ +& \minentropy{X} \\ +& \condminentropy{X}{Y=5} +\end{align*} + +\section{Sets} +The \enquote{sets} option provides commands for basic mathematical sets. +You can write sets and sequences as +\begin{lstlisting} +\set{1, \ldots, 10} +\sequence{1, \ldots, 10} +\end{lstlisting} +which is typeset as +\begin{align*} +& \set{1, \ldots, 10} \\ +& \sequence{1, \ldots, 10} +\end{align*} + +In addation the following commands are provided +\begin{center} +\begin{tabular}{l l l} +\textbf{Command} & \textbf{Description} & \textbf{Result} \\\hline +\lstinline$\bin$ & The set containing 0 and 1 & $\bin$ \\ +\lstinline$\NN$ & Natural numbers & $\NN$ \\ +\lstinline$\ZZ$ & Integers & $\ZZ$ \\ +\lstinline$\QQ$ & Rational numbers & $\QQ$ \\ +\lstinline$\RR$ & Reals & $\RR$ \\ +\lstinline$\PP$ & & $\PP$ \\ +\lstinline$\FF$ & & $\FF$ \\ +\end{tabular} +\end{center} + +\section{Crypto Notions} +The \enquote{notions} option provides the following list of commands: + +\begin{center} +\begin{tabular}{l l l} +\textbf{Command} & \textbf{Description} & \textbf{Result} \\\hline +\lstinline$\indcpa$ & IND-CPA security for encryption schemes & $\indcpa$ \\ +\lstinline$\indcpa$ & IND-CCA security for encryption schemes & $\indcca$ \\ +\lstinline$\indcpai$ & IND-CCA1 security for encryption schemes & $\indccai$ \\ +\lstinline$\indcpaii$ & IND-CCA2 security for encryption schemes & $\indccaii$ \\ +\lstinline$\priv$ & PRIV security for deterministic public-key encryption schemes & $\priv$ \\ +\lstinline$\ind$ & IND security (for deterministic public-key encryption schemes) & $\ind$ \\ +\lstinline$\prvcda$ & PRV-CDA security (for deterministic public-key encryption schemes)& $\prvcda$ \\ +\lstinline$\prvrcda$ & PRV\$-CDA security (for deterministic public-key encryption schemes) & $\prvrcda$ \\ +\lstinline$\kiae$ & Key independent authenticated encryption & $\kiae$ \\ +\lstinline$\kdae$ & Key dependent authenticated encryption & $\kdae$ \\ +\lstinline$\mle$ & Message locked encryption & $\mle$ \\ +\lstinline$\uce$ & Universal computational extractors & $\uce$ \\ +\end{tabular} +\end{center} + +The style in which notions are displayed can be controlled via redefining +\begin{lstlisting} +\renewcommand{\pcnotionstyle}[1]{\ensuremath{\mathrm{#1}}} +\end{lstlisting} + +\section{Logic} +The \enquote{logic} option provides the following list of commands: + +\begin{center} +\begin{tabular}{l l l} +\textbf{Command} & \textbf{Description} & \textbf{Result} \\\hline +\lstinline$\AND$ & Logical AND & $\AND$ \\ +\lstinline$\OR$ & Logical OR & $\OR$ \\ +\lstinline$\NOT$ & not & $\NOT$ \\ +\lstinline$\xor$ & exclusive or & $\xor$ \\ +\lstinline$\false$ & false & $\false$ \\ +\lstinline$\true$ & true & $\true$ +\end{tabular} +\end{center} + + +% Function Families +\section{Function Families} +The \enquote{ff} option provides the following list of commands: + +\begin{center} +\begin{tabular}{l l l} +\textbf{Command} & \textbf{Description} & \textbf{Result} \\\hline +\lstinline$\kgen$ & Key generation & $\kgen$ \\ +\lstinline$\pgen$ & Parameter generation & $\pgen$ \\ +\lstinline$\eval$ & Evaluation & $\eval$ \\ +\lstinline$\il$ & Input length & $\il$ \\ +\lstinline$\ol$ & Output length & $\ol$ \\ +\lstinline$\kl$ & Key length & $\kl$ \\ +\lstinline$\nl$ & Nonce length & $\nl$ \\ +\lstinline$\rl$ & Randomness length & $\rl$ +\end{tabular} +\end{center} + +The style in which these are displayed can be controlled via redefining +\begin{lstlisting} +\renewcommand{\pcalgostyle}[1]{\ensuremath{\mathsf{#1}}} +\end{lstlisting} + + +% Machine Model +\section{Machine Model} +The \enquote{mm} option provides the following list of commands: + +\begin{center} +\begin{tabular}{l l l} +\textbf{Command} & \textbf{Description} & \textbf{Result} \\\hline +\lstinline$\CRKT$ & A circuit & $\CRKT$ \\ +\lstinline$\TM$ & A Turing machine & $\TM$ \\ +\lstinline$\PROG$ & A program & $\PROG$ \\ +\lstinline$\uTM$ & A universal Turing machine & $\uTM$ \\ +\lstinline$\uC$ & A universal Circuit & $\uC$ \\ +\lstinline$\uP$ & A universal Program & $\uP$ \\ +\lstinline$\tmtime$ & Time (of a TM) & $\tmtime$ \\ +\lstinline$\ppt$ & Probabilistic polynomial time & $\ppt$ +\end{tabular} +\end{center} + +The style in which these are displayed can be controlled via redefining +\begin{lstlisting} +\renewcommand{\pcmachinemodelstyle}[1]{\ensuremath{\mathsf{#1}}} +\end{lstlisting} + +\section{Crypto Primitives} +The \enquote{primitives} option provides the following list of commands: + + +\begin{center} +\begin{tabular}{l l l} +\textbf{Command} & \textbf{Description} & \textbf{Result} \\\hline +\lstinline$\prover$ & Proover & $\prover$ \\ +\lstinline$\verifier$ & Verifier & $\verifier$ \\ +\lstinline$\nizk$ & Non interactie zero knowledge & $\nizk$ \\ +\lstinline$\hash$ & A hash function & $\hash$ \\ +\lstinline$\gash$ & A hash function& $\gash$ \\ +\lstinline$\fash$ & A hash function & $\fash$ \\ +\lstinline$\enc$ & Encryption & $\enc$ \\ +\lstinline$\dec$ & Decryption & $\dec$ \\ +\lstinline$\sig$ & Signing & $\sig$ \\ +\lstinline$\verify$ & Verifying & $\verify$ \\ +\lstinline$\obf$ & Obfuscation & $\obf$ \\ +\lstinline$\iO$ & Indistinguishability obfuscation & $\iO$ \\ +\lstinline$\diO$ & Differing inputs obfuscation & $\diO$ \\ +\lstinline$\mac$ & Message authentication & $\mac$ \\ +\lstinline$\puncture$ & Puncturing & $\puncture$ \\ +\lstinline$\source$ & A source & $\source$ \\ +\lstinline$\predictor$ & A predictor & $\predictor$ \\ +\lstinline$\sam$ & A sampler & $\sam$ \\ +\lstinline$\distinguisher$ & A distinguisher & $\distinguisher$ \\ +\lstinline$\dist$ & A distinguisher& $\dist$ \\ +\lstinline$\simulator$ & A simulator & $\simulator$ \\ +\lstinline$\ext$ & An extractor & $\ext$ +\end{tabular} +\end{center} + +The style in which these are displayed can be controlled via redefining +\begin{lstlisting} +\renewcommand{\pcalgostyle}[1]{\ensuremath{\mathsf{#1}}} +\end{lstlisting} + +\section{Events} +The \enquote{events} option provides the following list of commands. + +To classify an event use +\begin{lstlisting} +\event{Event} +\nevent{Event} +\end{lstlisting} +where the second is meant as the negation. These are typset as +\begin{align*} +&\event{Event}\\ +&\nevent{Event} +\end{align*} + +For bad events, use \lstinline$\bad$ ($\bad$). + +\section{Complexity} +The \enquote{complexity} option provides the following list of commands: + +\begin{center} +\begin{tabular}{l l l} +\textbf{Command} & \textbf{Result} \\\hline +\lstinline$\npol$ & $\npol$ \\ +\lstinline$\conpol$ & $\conpol$ \\ +\lstinline$\pol$ & $\pol$ \\ +\lstinline$\bpp$ & $\bpp$ \\ +\lstinline$\ppoly$ & $\ppoly$ \\ +\lstinline$\NC{1}$ & $\NC1$ \\ +\lstinline$\AC{1}$ & $\AC1$ \\ +\lstinline$\TC{1}$ & $\TC1$ \\ +\lstinline$\AM$ & $\AM$ \\ +\lstinline$\coAM$ & $\coAM$ +\end{tabular} +\end{center} + +The style in which these are displayed can be controlled via redefining +\begin{lstlisting} +\renewcommand{\pccomplexitystyle}[1]{\ensuremath{\mathsf{#1}}} +\end{lstlisting} + +\section{Asymptotics} +The \enquote{asymptotics} option provides the following list of commands: + +\begin{center} +\begin{tabular}{l l p{7.5cm}} +\textbf{Command} & \textbf{Description} & \textbf{Result} \\\hline +\lstinline$\negl$ & A negligible function & $\negl$ (takes an optional argument \lstinline$\negl[a]$ ($\negl[a]$). Write \lstinline$\negl[]$ for $\negl[]$.) \\ +\lstinline$\poly$ & A polynomial & $\poly$ (takes an optional argument \lstinline$\poly[a]$ ($\poly[a]$). Write \lstinline$\poly[]$ for $\poly[]$.) \\ +\lstinline$\pp$ & some polynomial $^\pp$ & $\pp$ \\ +\lstinline$\qq$ & some polynomial $^\qq$ & $\qq$ \\ +\end{tabular} +\end{center} + +The style in which these are displayed can be controlled via redefining +\begin{lstlisting} +\renewcommand{\pcpolynomialstyle}[1]{\ensuremath{\mathrm{#1}}} +\end{lstlisting} + +\section{Keys} +The \enquote{keys} option provides the following list of commands: + + +\begin{center} +\begin{tabular}{l l l} +\textbf{Command} & \textbf{Description} & \textbf{Result} \\\hline +\lstinline$\pk$ &public key & $\npol$ \\ +\lstinline$\vk$ & verification key& $\vk$ \\ +\lstinline$\sk$ & secret key& $\sk$ \\ +\lstinline$\key$ & a plain key& $\key$ \\ +\lstinline$\hk$ & hash key& $\hk$ \\ +\lstinline$\gk$ &gash key & $\gk$ \\ +\lstinline$\fk$ & function key & $\fk$ +\end{tabular} +\end{center} + +The style in which these are displayed can be controlled via redefining +\begin{lstlisting} +\renewcommand{\pckeystyle}[1]{\ensuremath{\mathsf{#1}}} +\end{lstlisting} + + +\chapter{Pseudocode} +\label{chap:pseudocode} + +In this chapter we discuss how to write pseudocode with the cryptocode library. + +\section{Basics} + +The cryptocode package provides the command \emph{pseudocode} in order to write simple cryptostyle algorithms. +Consider the following definition of an IND-CPA game +\begin{center} +\fbox{% +\pseudocode{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen (\secparam) \\ + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +} +\end{center} +which is generated as +\begin{lstlisting} +\pseudocode{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen (\secparam) \\ + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +\end{lstlisting} +As you can see the pseudocode command provides a math based environment where you can simply start typing your pseudocode +separating lines by \lstinline$\\$. + + +\paragraph{Boxed appearance} +Although most examples here appear centered and boxed this is not directly part of the pseudocode package but due to the examples being +typeset as +\begin{lstlisting} +\begin{center} +\fbox{% +Code +} +\end{center} +\end{lstlisting} + + +\subsection{Customizing Pseudocode} +Besides the mandatory argument the \lstinline{\pseudocode} command can take an optional argument which consists of a list of key=value pairs +separated by commas (,). +\begin{lstlisting} +\pseudocode[options]{body} +\end{lstlisting} +The following keys are available: +\begin{description} +\item[head] +A header for the code +\item[width] +An exact width. If no width is specified, cryptocode tries to automatically compute the correct width. +\item[lnstart] +The starting line number when using line numbering. +\item[lnstartright] +The starting line number for right aligned line numberswhen using line numbering. +\item[linenumbering] +Enables line numbering. +\item[syntaxhighlight] +When set to \enquote{auto} cryptocode will attempt to automatically hightlight keywords such as \enquote{for}, \enquote{foreach} +and \enquote{return} +\item[keywords] +Provide a comma separated list of keywords for automatic syntax highlighting. +\item[addkeywords] +Provide additional keywords for automatic syntax highlighting. +\item[mode] +When set to text pseudocode will not start in math mode but in text mode. +\item[xshift] +Allows horizontal shifting +\end{description} +The following code +\begin{lstlisting} +\pseudocode[linenumbering,syntaxhighlight=auto,head=Header]{ return null } +\end{lstlisting} +creates +\begin{center} +\fbox{\pseudocode[linenumbering,syntaxhighlight=auto,head=Header]{ return null }} +\end{center} + + + +\subsection{Indentation} +\index{indentation} +\index{pcind} +\index{t} + +In order to indent code use \lstinline$\pcind$ or short \lstinline$\t$. You can also usecustomized spacing such as \lstinline$\quad$ or \lstinline$\hspace$ +when using the pseudocode command in math mode. +\begin{center} +\fbox{% +\pseudocode{% + \pcfor i = 1..10 \pcdo \\ + \pcind T[i] \sample \bin^n \\ + \pcfor i = 1..10 \pcdo \\ + \t T[i] \sample \bin^n } +} +\end{center} +which is generated as +\begin{lstlisting} +\pseudocode{% + \pcfor i = 1..10 \pcdo \\ + \pcind T[i] \sample \bin^n \\ + \pcfor i = 1..10 \pcdo \\ + \t T[i] \sample \bin^n } +\end{lstlisting} +You can specify multiple levels via the optional first argument +\begin{lstlisting} +\pcind[level] +\end{lstlisting} +\begin{center} +\fbox{% +\pseudocode{% + \pcfor i = 1..10 \pcdo \\ + \pcind T[i] \sample \bin^n \\ + \pcind\pcind T[i] \sample \bin^n \\ + \pcind[3] T[i] \sample \bin^n \\ + \pcind[4] T[i] \sample \bin^n \\ + \pcind[5] T[i] \sample \bin^n } +} +\end{center} +\begin{lstlisting} +\pseudocode{% + \pcfor i = 1..10 \pcdo \\ + \pcind T[i] \sample \bin^n \\ + \pcind\pcind T[i] \sample \bin^n \\ + \pcind[3] T[i] \sample \bin^n \\ + \pcind[4] T[i] \sample \bin^n \\ + \pcind[5] T[i] \sample \bin^n } +\end{lstlisting} + +\index{pcindentname} +You can customize the indentation shortcut by redefining +\begin{lstlisting} +\renewcommand{\pcindentname}{t} +\end{lstlisting} + +\subsection{Textmode} +\index{text mode} + +By default pseudocode enables \LaTeX' math mode. You can change this behavior and tell the pseudocode command to interpret the content +in text mode by setting the option \enquote{mode=text}. +\begin{center} +\fbox{\pseudocode[mode=text]{% +This is \\ +\t simply text}} +\end{center} +\begin{lstlisting} +\pseudocode[mode=text]{% +This is \\ +\t simply text} +\end{lstlisting} + +\subsection{Syntax Highlighting} + +\index{pccontinue} +\index{pccomment} +\index{pcdo} +\index{pcdone} +\index{pcelse} +\index{pcfi} +\index{pcforeach} +\index{pcglobvar} +\index{pcif} +\index{pcin} +\index{pcnew} +\index{pcnull} +\index{pcparse} +\index{pcrepeat} +\index{pcreturn} +\index{pcthen} +\index{pctrue} +\index{pcwhile} + + +In the above examples we have used commands \lstinline$\pcreturn$ and \lstinline$\pcfor$ to highlight certain keywords. +Besides the \emph{pcreturn}, \emph{pcfor} and \emph{pcdo} (where the pc stands for pseudocode) that were used in the above +examples the package defines the following set of constants: + +\begin{center} +\begin{tabular}{lll} + \textbf{name} & \textbf{usage} & \textbf{outcome} \\ + pccontinue & \lstinline$\pccontinue$ & \pccontinue \\ + pccomment & \lstinline$\pccomment{comment}$ & \pccomment{comment} \\ + pcdo & \lstinline$\pcdo$ & \pcdo \\ + pcdone & \lstinline$\pcdone$ & \pcdone \\ + pcfalse & \lstinline$\pcfalse$ & \pcfalse \\ + pcelse & \lstinline$\pcelse$ & \pcelse \\ + pcfi & \lstinline$\pcfi$ & \pcfi \\ + pcfor & \lstinline$\pcfor$ & \pcfor \\ + pcforeach & \lstinline$\pcforeach$ & \pcforeach \\ + pcglobvar & \lstinline$\pcglobvar$ & \pcglobvar \\ + pcif & \lstinline$\pcif$ & \pcif \\ + pcin & \lstinline$\pcin$ & \pcin \\ + pcnew & \lstinline$\pcnew$ & \pcnew \\ + pcnull & \lstinline$\pcnull$ & \pcnull \\ + pcparse & \lstinline$\pcparse$ & \pcparse \\ + pcrepeat & \lstinline$\pcrepeat{10}$ & \pcrepeat{10} \\ + pcuntil & \lstinline$\pcuntil$ & \pcuntil \\ + pcreturn & \lstinline$\pcreturn$ & \pcreturn \\ + pcthen & \lstinline$\pcthen$ & \pcthen \\ + pctrue & \lstinline$\pctrue$ & \pctrue \\ + pcwhile & \lstinline$\pcwhile$ & \pcwhile +\end{tabular} +\end{center} +Note that \lstinline{\pcdo}, \lstinline{\pcin} and \lstinline{\pcthen} have a leading space. This is due to their usual usage scenarios +such as +\begin{center} +\pseudocode{\pcfor i \pcin \{1,\ldots,10\}} +\end{center} +Furthermore all constants have a trailing space. This can be removed by adding the optional parameter [] such as +\begin{center} +\pseudocode{\pcfor i \pcin[] \{1,\ldots,10\}} +\end{center} +\begin{lstlisting} +\pseudocode{\pcfor i \pcin[] \{1,\ldots,10\}} +\end{lstlisting} + +\index{pseudocodeconstant} +In order to change the font you can overwrite the command \lstinline{\pseudocodeconstant} which is defined as +\begin{lstlisting} +\newcommand{\pseudocodeconstant}[2][\ ]{\ensuremath{\mathbf{#2}}#1} +\end{lstlisting} + +\subsubsection{Automatic Syntax Highlighting} +The pseudocode command comes with an experimental feature to automatically highlight keywords. This can be activated via +the option \enquote{syntaxhighlight=auto}. The preset list of keywords it looks for are +\begin{lstlisting} +for ,foreach ,return ,{ do }, in ,new ,if ,null ,null,true ,true,until ,{ to },false ,false,{ then },repeat ,else ,done ,done,fi +\end{lstlisting} +Note that the keywords are matched with spaces and note the grouping for trailing spaces. That is, the \enquote{ do } keyword won't match within the string \enquote{don't}. +Via the option \enquote{keywords} you can provide a custom list of keywords. +Thus the following bubblesort variant (taken from \url{http://en.wikipedia.org/wiki/Bubble_sort}) +\begin{center} +\fbox{\procedure[syntaxhighlight=auto]{Bubblesort(A : list of items)}{ + n \gets \mathsf{length}(A) \\ + repeat \\ + \t s \gets false \\ + \t for i = 1 to n-1 do \\ + \t\t \pccomment{if this pair is out of order} \\ + \t\t if A[i-1] > A[i] then \\ + \t\t\t \pccomment{swap them and remember something changed} \\ + \t\t\t \mathsf{swap}( A[i-1], A[i] ) \\ + \t\t\t s \gets true \\ + until \neg s } +} +\end{center} +can be typeset as +\begin{lstlisting} +\procedure[syntaxhighlight=auto]{Bubblesort(A : list of items)}{ + n \gets \mathsf{length}(A) \\ + repeat \\ + \t s \gets false \\ + \t for i = 1 to n-1 do \\ + \t\t \pccomment{if this pair is out of order} \\ + \t\t if A[i-1] > A[i] then \\ + \t\t\t \pccomment{swap them and remember something changed} \\ + \t\t\t \mathsf{swap}( A[i-1], A[i] ) \\ + \t\t\t s \gets true \\ + until \neg s } +\end{lstlisting} + +You can also define additional keywords using the \enquote{addkeywords} option. This would allow ous to specify length and swap in the above example. +We can also overwrite how a single keyword is set by defining the command \lstinline$dohighlightKEYWORD$. Thus to set swap and length in \lstinline$\mathsf$ +we could define +\begin{lstlisting} +\newcommand{\dohighlightswap}[1]{\mathsf{#1}} +\newcommand{\dohighlightlengt}[1]{\mathsf{#1}} +\end{lstlisting} +and then +\begin{lstlisting} +\procedure[syntaxhighlight=auto,addkeywords={swap,length}]{Bubblesort(A : list of items)}{ + n \gets length(A) \\ + repeat \\ + \t s \gets false \\ + \t for i = 1 to n-1 do \\ + \t\t \pccomment{if this pair is out of order} \\ + \t\t if A[i-1] > A[i] then \\ + \t\t\t \pccomment{swap them and remember something changed} \\ + \t\t\t swap( A[i-1], A[i] ) \\ + \t\t\t s \gets true \\ + until \neg s } +\end{lstlisting} + +\subsection{Predefined Headings} +\index{procedure} +\index{mainprocedure} +\index{circuit} +\index{program} + +Besides the \lstinline{\pseudocode} command the commands \lstinline{\procedure}, \lstinline{\mainprocedure}, \lstinline{\circuit} and \lstinline{\program} +provide easy access to generate code with common headers. They all take two mandatory arguments and an optional argument. +\begin{lstlisting} +\procedure[options]{Header}{Body} +\end{lstlisting} + +\subsubsection{Examples} +\begin{center} +\fbox{% +\procedure{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen(\secparam) \\ + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +} +\end{center} +which is generated as +\begin{lstlisting} +\procedure{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen(\secparam) \\ + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +\end{lstlisting} + +And the same with \lstinline{\mainprocedure}, \lstinline{\circuit}, \lstinline{\program} and \lstinline{\algorithm}: + +\begin{center} +\begin{pcvstack} +\begin{pchstack} +\mainprocedure{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen(\secparam) \\ + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +\hspace{2cm} +\circuit{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen(\secparam) \\ + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +\end{pchstack} + +\vspace{0.5cm} + +\begin{pchstack} +\program{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen(\secparam) \\ + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +\hspace{2cm} +\algorithm{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen(\secparam) \\ + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +\end{pchstack} +\end{pcvstack} +\end{center} + + +The prefixes (Main, Circ, etc.) can be controlled via the commands: + +\begin{center} +\begin{tabular}{ll} +\textbf{Command} & \textbf{Default} \\ +\lstinline$\pcmainname$ & \lstinline$\textsc{Main }$ \\ +\lstinline$\pcalgorithmname$ & \lstinline$\textsc{Algo. }$\\ +\lstinline$\pccircuitname$ & \lstinline$\textsc{Circ. }$\\ +\lstinline$\pcprogramname$ & \lstinline$\textsc{Prog. }$\\ +\lstinline$\pcprotocolname$ & \lstinline$\textsc{Protocol }$ +\end{tabular} +\end{center} + + +\section{Line Numbering} +\index{line numbering} +\index{pcln} +\index{pclnr} +\index{pcrln} +The pseudocode command allows to insert line numbers into pseudocode. You can either manually control linenumbering or simply turn on the option +\enquote{linenumbering}. +\begin{center} +\fbox{% +\procedure[linenumbering]{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen\secparam) \\ + \label{tmp:line:label} (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +} +\end{center} +is generated by +\begin{lstlisting} +\procedure[linenumbering]{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen\secparam) \\ + \label{tmp:line:label} (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +\end{lstlisting} +Note how you can use labels such as \lstinline$\label{tmp:line:label}$ which now points to \ref{tmp:line:label}. + +\subsection{Manually Inserting Linenumbers} +In order to manually insert line numbers use the command \lstinline$\pcln$. +\begin{center} +\fbox{% +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen\secparam) \\ + \pcln\label{tmp:line:label2} (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } +} +\end{center} +is generated by +\begin{lstlisting} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen\secparam) \\ + \pcln\label{tmp:line:label2} (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } +\end{lstlisting} +Note that the label \emph{tmp:line:label2} now points to line number \ref{tmp:line:label2}. + + + +\subsection{Start Values} +You can specify the start value (-1) of the counter by setting the option \enquote{lnstart}. +\begin{lstlisting} +\procedure[lnstart=10,linenumbering]{Header}{Body} +\end{lstlisting} +\begin{center} +\fbox{% +\procedure[lnstart=10,linenumbering]{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen\secparam) \\ + (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +} +\end{center} + +\subsection{Separators} +\index{pclnseparator} +The commands \lstinline$\pclnseparator$ defines the separator between the pseudocode and the line numbering. By +default the left separator is set to (:) colon. Also see Section~\ref{sec:protocol:separator}. + + +\section{Subprocedures} +\index{subprocedure} +The pseudocode package allows the typesetting of sub procedures such as + +\begin{center} +\procedure[linenumbering]{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen(\secparam) \\ + (m_0,m_1) \sample \begin{subprocedure}% + \dbox{\procedure{$\adv(\secparam, \pk, c)$}{% + \text{Step 1} \\ + \text{Step 2} \\ + \pcreturn m_0, m_1 }} + \end{subprocedure} \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } + \end{center} + +To create a subprocedure use the \emph{subprocedure} environment. The above example is generated via + \begin{lstlisting} +\procedure[linenumbering]{$\indcpa_\enc^\adv$}{% + b \sample \bin \\ + (\pk,\sk) \sample \kgen(\secparam) \\ + (m_0,m_1) \sample \begin{subprocedure}% + \dbox{\procedure{$\adv(\secparam, \pk, c)$}{% + \text{Step 1} \\ + \text{Step 2} \\ + \pcreturn m_0, m_1 }} + \end{subprocedure} \\ + c \sample \enc(\pk,m_b) \\ + b' \sample \adv(\secparam, \pk, c) \\ + \pcreturn b = b' } +\end{lstlisting} +Here the dbox command (from the dashbox package) is used to generate a dashed box around the sub procedure. + +\subsection{Numbering in Subprocedures} +Subprocedures as normal pseudocode allow you to create line numbers. By default the line numbering starts with 1 in a subprocedure while +ensuring that the outer numbering remains intact. Also note that the linenumbering on the outer procedure in the above example is inherited +by the subprocedure. For more control, either use manual numbering or set the option \enquote{linenumbering=off} on the subprocedure. + +\begin{center} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \begin{subprocedure}% + \dbox{\procedure{$\adv(\secparam, \pk, c)$}{% + \pcln \text{Step 1} \\ + \pcln \text{Step 2} \\ + \pcln \pcreturn m_0, m_1 }} + \end{subprocedure} \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } + \end{center} + \begin{lstlisting} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \begin{subprocedure}% + \dbox{\procedure{$\adv(\secparam, \pk, c)$}{% + \pcln \text{Step 1} \\ + \pcln \text{Step 2} \\ + \pcln \pcreturn m_0, m_1 }} + \end{subprocedure} \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } +\end{lstlisting} + + +\section{Stacking Procedures} +You can stack procedures horizontally or vertically using the environments ``pchstack'' and ``pcvstack''. +\begin{lstlisting} +\begin{pchstack}[center] body \end{pchstack} +\begin{pcvstack}[center] body \end{pcvstack} +\end{lstlisting} + +The following example displays two procedures next to one another. As a spacing between two horizontally outlined procedures +use \lstinline{\pchspace} which takes an optional length as a parameter. + +\begin{pchstack}[center] +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \adv^O(\secparam, \pk) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } + +\pchspace + + \procedure{Oracle $O$}{% + \pcln \text{line 1} \\ + \pcln \text{line 2} +} +\end{pchstack} + +\begin{lstlisting} +\begin{pchstack}[center] +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \adv^O(\secparam, \pk) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } + +\pchspace + + \procedure{Oracle $O$}{% + \pcln \text{line 1} \\ + \pcln \text{line 2} +} +\end{pchstack} +\end{lstlisting} + + +Similarly you can stack two procedures vertically using the \enquote{pcvstack} environment. As a spacing between two vertically stacked procedures +use \lstinline{\pcvspace} which takes an optional length as a parameter. + + +\begin{pcvstack}[center] +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \adv^O(\secparam, \pk) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } + +\pcvspace + + \procedure{Oracle $O$}{% + \pcln \text{line 1} \\ + \pcln \text{line 2} +} +\end{pcvstack} + + +\begin{lstlisting} +\begin{pcvstack}[center] +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \adv^O(\secparam, \pk) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } + +\pcvspace + + \procedure{Oracle $O$}{% + \pcln \text{line 1} \\ + \pcln \text{line 2} +} +\end{pcvstack} +\end{lstlisting} + + +Horizontal and vertical stacking can be combined +\begin{pchstack}[center] +\begin{pcvstack} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \adv^{O,H_1,H_2}(\secparam, \pk) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } + +\pcvspace + +\begin{pchstack} + \procedure{Oracle $O$}{% + \pcln \text{line 1} \\ + \pcln \text{line 2} +} + + \procedure{Oracle $H_1$}{% + \pcln \text{line 1} \\ + \pcln \text{line 2} +} + + \procedure{Oracle $H_2$}{% + \pcln \text{line 1} \\ + \pcln \text{line 2} +} +\end{pchstack} +\end{pcvstack} + +\pchspace + +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \adv^O(\secparam, \pk) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } + +\end{pchstack} + + +\begin{lstlisting} +\begin{pchstack}[center] +\begin{pcvstack} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \adv^{O,H_1,H_2}(\secparam, \pk) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } + +\pcvspace + +\begin{pchstack} + \procedure{Oracle $O$}{% + \pcln \text{line 1} \\ + \pcln \text{line 2} +} + + \procedure{Oracle $H_1$}{% + \pcln \text{line 1} \\ + \pcln \text{line 2} +} + + \procedure{Oracle $H_2$}{% + \pcln \text{line 1} \\ + \pcln \text{line 2} +} +\end{pchstack} +\end{pcvstack} + +\pchspace + +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \adv^O(\secparam, \pk) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } + +\end{pchstack} +\end{lstlisting} + +\section{Divisions and Linebreaks} +\index{linebreaks} +\index{hline} +Within the pseudocode command you generate linebreaks as $\\$. In order to specify the linewidth you can add an optional argument +\begin{lstlisting} +\\[height] +\end{lstlisting} +Furthermore, you can add, for example a horizontal line by using the second optional argument and write +\begin{lstlisting} +\\[][\hline] +\end{lstlisting} + +\begin{center} +\fbox{ +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\[2\baselineskip][\hline\hline] + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \adv^O(\secparam, \pk) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } +} +\end{center} + +\begin{lstlisting} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\[2\baselineskip][\hline\hline] + \pcln (\pk,\sk) \sample \kgen(\secparam) \\ + \pcln (m_0,m_1) \sample \adv^O(\secparam, \pk) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c) \\ + \pcln \pcreturn b = b' } +\end{lstlisting} + + +\section{Fancy Code} + +Consider the \indcpa\ game. Here we have a single adversary $\adv$ that is called twice, first to output two messages then +given the ciphertext of one of the messages to \enquote{guess} which one was encrypted. Often this is not visualized. +Sometimes an additional state $\state$ is passed as we have in the following example on the left. On the right, +we visualize the same thing in a bit more fancy way. + +\begin{center} + +\pchstack{ + +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen (\secparam) \\ + \pcln (\state,m_0,m_1) \sample \adv(\secparam, \pk, c) \pcnode{start} \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c, \state) \pcnode{end} \\ + \pcln \pcreturn b = b' } + + +\pchspace[1cm] + +\begin{pcimage} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen (\secparam) \\ + \pcln (m_0,m_1) \sample \adv(\secparam, \pk, c) \pcnode{start} \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c, \state) \pcnode{end} \\ + \pcln \pcreturn b = b' } + +\pcdraw{ + \path[->] (start) edge[bend left=50] node[right]{$\state$} (start|-end); +} +\end{pcimage} + +} +\end{center} + +The image on the right is generated by: +\begin{lstlisting} +\begin{pcimage} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen (\secparam) \\ + \pcln (m_0,m_1) \sample \adv(\secparam, \pk, c) \pcnode{start} \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c, \state) \pcnode{end} \\ + \pcln \pcreturn b = b' } + +\pcdraw{ + \path[->] (start) edge[bend left=50] node[right]{$\state$} (start|-end); +} +\end{pcimage} +\end{lstlisting} + +In order to achieve the above effect cryptocode utilizes TIKZ underneath. The +\lstinline$pcnode$ command generates TIKZ nodes and additionally we wrapped the +pseudocode (or procedure) command in an \lstinline$\begin{pcimage}\end{pcimage}$ environment +which allows us to utilize these nodes later, for example using the \lstinline$\pcdraw$ +command. We can achieve a similar effect without an additional pcimage environment as + +\begin{lstlisting} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen (\secparam) \\ + \pcln (m_0,m_1) \sample \adv(\secparam, \pk, c) \pcnode{start} \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c, \state) \pcnode{end}[draw={ + \path[->] (start) edge[bend left=50] node[right]{$\state$} (start|-end); + }] \\ + \pcln \pcreturn b = b' } +\end{lstlisting} + +\subsection{Example: Explain your Code} +As an exmaple of what you can do with this, let us put an explanation to a line of the code. + +\begin{center} +\begin{pcimage} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen (\secparam)\pcnode{kgen} \\ + \pcln (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c, \state) \\ + \pcln \pcreturn b = b' } + +\pcdraw{ + \node[rectangle callout,callout absolute pointer=(kgen),fill=orange] + at ([shift={(+3,+1)}]kgen) { + \begin{varwidth}{3cm} + $\kgen(\secparam)$ samples a public key $\pk$ and a private key $\sk$. + \end{varwidth} + }; +} +\end{pcimage} +\end{center} + +\begin{lstlisting} +\begin{center} +\begin{pcimage} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \kgen (\secparam)\pcnode{kgen} \\ + \pcln (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c, \state) \\ + \pcln \pcreturn b = b' } + +\pcdraw{ + \node[rectangle callout,callout absolute pointer=(kgen),fill=orange] + at ([shift={(+3,+1)}]kgen) { + \begin{varwidth}{3cm} + $\kgen(\secparam)$ samples a public key $\pk$ and a private key $\sk$. + \end{varwidth} + }; +} +\end{pcimage} +\end{center} +\end{lstlisting} + +Using the \emph{ocgx} package (\url{https://www.ctan.org/pkg/ocgx}) we could even make the +$\kgen$ command clickable: + +\begin{center} +\begin{pcimage} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \switchocg{kgen}{\kgen (\secparam)}\pcnode{kgen} \\ + \pcln (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c, \state) \\ + \pcln \pcreturn b = b' } + +\pcdraw{ + \begin{scope}[ocg={ref=kgen,status=invisible,name=Key Generation Explanation}] + \node[rectangle callout,callout absolute pointer=(kgen),fill=orange] + at ([shift={(+3,+1)}]kgen) { + \begin{varwidth}{3cm} + $\kgen(\secparam)$ samples a public key $\pk$ and a private key $\sk$. + \end{varwidth} + }; + \end{scope} +} +\end{pcimage} +\end{center} + +(Click on $\kgen$ to see the magic.) + +\begin{lstlisting} +\begin{center} +\begin{pcimage} +\procedure{$\indcpa_\enc^\adv$}{% + \pcln b \sample \bin \\ + \pcln (\pk,\sk) \sample \switchocg{kgen}{\kgen (\secparam)}\pcnode{kgen} \\ + \pcln (m_0,m_1) \sample \adv(\secparam, \pk, c) \\ + \pcln c \sample \enc(\pk,m_b) \\ + \pcln b' \sample \adv(\secparam, \pk, c, \state) \\ + \pcln \pcreturn b = b' } + +\pcdraw{ + \begin{scope}[ocg={ref=kgen,status=invisible,name=Key Generation Explanation}] + \node[rectangle callout,callout absolute pointer=(kgen),fill=orange] + at ([shift={(+3,+1)}]kgen) { + \begin{varwidth}{3cm} + $\kgen(\secparam)$ samples a public key $\pk$ and a private key $\sk$. + \end{varwidth} + }; + \end{scope} +} +\end{pcimage} +\end{center} +\end{lstlisting} + + +\chapter{Tabbing Mode} +\label{chap:tabbing} +\index{Tabbing Mode} +\index{mintabmode} +In the following chapter we discuss how to create multiple columns within a \lstinline$pseudocode$ command. +Within a \lstinline$pseudocode$ command you can switch to a new column by inserting a \lstinline$\>$. +This is similar to using an \lstinline$align$ environment and placing a tabbing \& character. Also, +similarly to using \lstinline$align$ you need to ensure that the number of \lstinline$\>$ are identical +on each line. +\begin{center} +\fbox{% +\pseudocode{% + \textbf{First} \> \textbf{Second} \> \textbf{Third} \> \textbf{Fourth} \\ + b \sample \bin \> b \sample \bin \> b \sample \bin \> b \sample \bin} +} +\end{center} +\begin{lstlisting} +\pseudocode{% + \textbf{First} \> \textbf{Second} \> \textbf{Third} \> \textbf{Fourth} \\ + b \sample \bin \> b \sample \bin \> b \sample \bin \> b \sample \bin} +\end{lstlisting} +As you can see the first column is left aligned the second right, the third left and so forth. +In order to get only left aligned columns you could thus simply always skip a column by +using \lstinline$\>\>$. You can also use \lstinline$\<$ a shorthand for \lstinline$\>\>$. +\begin{center} +\fbox{% +\pseudocode{% + \textbf{First} \< \textbf{Second} \< \textbf{Third} \< \textbf{Fourth} \\ + b \sample \bin \< b \sample \bin \< b \sample \bin \< b \sample \bin} +} +\end{center} +\begin{lstlisting} +\pseudocode{% + \textbf{First} \< \textbf{Second} \< \textbf{Third} \< \textbf{Fourth} \\ + b \sample \bin \< b \sample \bin \< b \sample \bin \< b \sample \bin} +\end{lstlisting} + +This is basically all you need to know in order to go on to writing protocols with the +cryptocode package. So unless you want to know a bit more about tabbing (switching columns) +and learn some of the internals, feel free to proceed to Chapter~\ref{chap:protocols}. + + +\section{Tabbing in Detail} +At the heart of the pseudocode package is an align (or rather a flalign*) environment which allows you to use basic math writing. Usually an align (or flalign) environment uses \& as tabbing characters. The pseudocode comes in two modes the first of which changes the default align behavior. That is, it automatically adds a tabbing character to the beginning and end of each line and changes the tabbing character to \lstinline$\>$. This mode is called mintabmode and is active by default. + +In mintabmode in order to make use of extra columns in the align environment (which we will use shortly in order to write protocols) you can use \lstinline$\>$ as you would use \& normally. But, don't forget that there is an alignment tab already placed at the beginning and end of each line. So the following example +\begin{center} +\fbox{% +\pseudocode{% + \textbf{Alice} \> \> \textbf{Bob} \\ + b \sample \bin \> \> \\ + \> \xrightarrow{\text{send over } b} \> \\ + \> \> \text{do something}} +} +\end{center} +is generated by +\begin{lstlisting} +\pseudocode{% + \textbf{Alice} \> \> \textbf{Bob} \\ + b \sample \bin \> \> \\ + \> \xrightarrow{\text{send over } b} \> \\ + \> \> \text{do something}} +\end{lstlisting} + +In Chapter~\ref{chap:protocols} we'll discuss how to write protocols in detail. +The next two sections are rather technical, so feel free to skip them. + + +\subsection{Overriding The Tabbing Character} +\index{pctabname} +If you don't like \lstinline$\>$ as the tabbing character you can choose a custom command by overwriting \lstinline$\pctabname$. +For example +\begin{lstlisting} +\renewcommand{\pctabname}{\myTab} + +\pseudocode{% + \textbf{Alice} \myTab \myTab \textbf{Bob} \\ + b \sample \bin \myTab \myTab \\ + \myTab \xrightarrow{\text{send over } b} \myTab \\ + \myTab \myTab \text{do something}} +\end{lstlisting} + +\subsection{Custom Line Spacing and Horizontal Rules} +\index{pclb} +As explained underlying the pseudocode command is an flalign environment. This would allow the use +of \lstinline$\\[spacing]$ to specifiy the spacing between two lines or of \lstinline$[\\\hline]$ +to insert a horizontal rule. In order to achieve the same effect within the pseudocode command you +can use \lstinline$\\{[spacing][\hline]}$. You can also use \lstinline$\pclb$ to get a line break which +does not insert the additional alignment characters. + +\chapter{Protocols} +\label{chap:protocols} + +The pseudocode package can also be used to write protocols such as +\begin{center} +\fbox{% +\protocol{My Protocol}{% + \textbf{Alice} \> \> \textbf{Bob} \\ + b \sample \bin \> \> \\ + \> \xrightarrow{\text{send over } b} \> \\ + \> \> \text{do something} \\ + \> \xleftarrow{\text{send over sth. else}} \> \\ + \text{finalize} \> \>} + } +\end{center} +which uses the tabbing feature of align and is generated as +\begin{lstlisting} +\protocol{My Protocol}{% + \textbf{Alice} \> \> \textbf{Bob} \\ + b \sample \bin \> \> \\ + \> \xrightarrow{\text{send over } b} \> \\ + \> \> \text{do something} \\ + \> \xleftarrow{\text{send over sth. else}} \> \\ + \text{finalize} \> \>} +} +\end{lstlisting} +In order to get nicer message arrows use the commands \lstinline$\sendmessageright*{message}$ and \lstinline$\sendmessageleft*{message}$. +Both take an additional optional argument specifying the length of the arrow and both are run +in math mode. +\begin{lstlisting} +\sendmessageright*[3.5cm]{message} +\sendmessageleft*[3.5cm]{message} +\end{lstlisting} + + +\begin{center} +\fbox{% +\protocol{My Protocol}{% + \textbf{Alice} \> \> \textbf{Bob} \\ + b \sample \bin \> \> \\ + \> \sendmessageright*{\text{send over } b} \> \\ + \> \> \text{do something} \\ + \> \sendmessageleft*{\text{send over sth. else}} \> \\ + \text{finalize} \> \> } + } +\end{center} +\begin{lstlisting} +\protocol{My Protocol}{% + \textbf{Alice} \> \> \textbf{Bob} \\ + b \sample \bin \> \> \\ + \> \sendmessageright*{\text{send over } b} \> \\ + \> \> \text{do something} \\ + \> \sendmessageleft*{\text{send over sth. else}} \> \\ + \text{finalize} \> \> } +\end{lstlisting} + +Besides the starred version there is also the unstarred version which allows more flexibility. Note that a crucial difference between +the starred and unstarred versions are that \lstinline$\sendmessageleft*{message}$ wraps an aligned environment around the message. +\begin{center} +\protocol{My Protocol}{% + \textbf{Alice} \> \> \textbf{Bob} \\ + b \sample \bin \> \> \\ + \> \sendmessageright{centercol=3,top=send over $b$,bottom=Text below,topstyle={draw,solid,yshift=0.25cm},style={dashed}} \> \\ + \> \> \text{do something} \\ + \> \sendmessageleft{length=8cm,top=send over sth. else} \> \\ + \text{finalize} \> \> } +\end{center} +\begin{lstlisting} +\protocol{My Protocol}{% + \textbf{Alice} \> \> \textbf{Bob} \\ + b \sample \bin \> \> \\ + \> \sendmessageright{centercol=3,top=send over $b$,bottom=Text below,topstyle={draw,solid,yshift=0.25cm},style={dashed}} \> \\ + \> \> \text{do something} \\ + \> \sendmessageleft{length=8cm,top=send over sth. else} \> \\ + \text{finalize} \> \> } +\end{lstlisting} +The unstarred commands take key-value pairs. The following keys are available: +\begin{description} +\item[top] +The content to display on top of the arrow. +\item[bottom] +The content to display below the arrow. +\item[left] +The content to display on the left of the arrow. +\item[right] +The content to display on the right of the arrow. +\item[topstyle] +The TIKZ style to be used for the top node. +\item[bottomstyle] +The TIKZ style to be used for the bottom node. +\item[rightstyle] +The TIKZ style to be used for the right node. +\item[leftstyle] +The TIKZ style to be used for the left node. +\item[length] +The length of the arrow. +\item[style] +The style of the arrow. +\item[width] +The width of the column +\item[centercol] +Can be used to ensure that the message is displayed in the center. This should be set to the +column index. In the above example, the message column is the third column (note that there is +a column left of alice that is automatically inserted.). +\end{description} + + +\section{Tabbing} +When typesetting protocols you might find that using two tabs instead of a single tab usually provides +a better result as this ensures that all columns are left aligned. +For this you can use \lstinline$\<$ instead of \lstinline$\>$ (see Chapter~\ref{chap:tabbing}). + +Following is once more the example from before but now with double tapping. +\begin{center} +\fbox{% +\protocol{My Protocol}{% + \textbf{Alice} \< \< \textbf{Bob} \\ + b \sample \bin \< \< \\ + \< \sendmessageright*{\text{send over } b} \< \\ + \< \< \text{do something} \\ + \< \sendmessageleft*{\text{send over sth. else}} \< \\ + \text{finalize} \< \< } + } +\end{center} + +\section{Multiline Messages} +Using the send message commands you can easily generate multiline messages as the command +wraps an \emph{aligned} environment around the message. +\begin{center} +\fbox{% +\protocol{My Protocol}{% + \textbf{Alice} \< \< \textbf{Bob} \\ + b \sample \bin \< \< \\ + \< \sendmessageright*{\text{send over } b\\ \text{second line}} \< \\ + \< \< \text{do something} \\ + \< \sendmessageleft*{&\text{left aligned}\\ &\text{multiline message}} \< \\ + \text{finalize} \< \<} + } +\end{center} +\begin{lstlisting} +\protocol{My Protocol}{% + \textbf{Alice} \< \< \textbf{Bob} \\ + b \sample \bin \< \< \\ + \< \sendmessageright*{\text{send over } b\\ \text{second line}} \< \\ + \< \< \text{do something} \\ + \< \sendmessageleft*{&\text{left aligned}\\ &\text{multiline message}} \< \\ + \text{finalize} \< \<} +\end{lstlisting} + + + +\subsection{Multiplayer Protocols} + +You are not limited to two players. In order to send messages skipping players use \lstinline$\sendmessagerightx$ and \lstinline$\sendmessageleftx$. +\begin{lstlisting} +\sendmessagerightx[width]{columnspan}{Text} +\sendmessageleftx[width]{columnspan}{Text} +\end{lstlisting} + +\begin{center} +\fbox{% +\protocol{Multiparty Protocol}{% + \textbf{Alice} \< \< \textbf{Bob} \< \< \textbf{Charlie} \\ + \text{work} \< \< \< \< \\ + \< \sendmessageright{top=Work result} \< \< \< \\ + \< \< \text{work} \< \< \\ + \< \< \< \sendmessageright{top=Work result,bottom=Bottom message} \< \\ + \< \< \< \< \text{work} \\ + \< \sendmessageleftx[7cm]{8}{\text{A long message for Alice}} \< \\ + \text{finalize} \< \< \< \< } +} +\end{center} + +\begin{lstlisting} +\begin{center} +\protocol{Multiparty Protocol}{% + \textbf{Alice} \< \< \textbf{Bob} \< \< \textbf{Charlie} \\ + \text{work} \< \< \< \< \\ + \< \sendmessageright{top=Work result} \< \< \< \\ + \< \< \text{work} \< \< \\ + \< \< \< \sendmessageright{top=Work result,bottom=Bottom message} \< \\ + \< \< \< \< \text{work} \\ + \< \sendmessageleftx[7cm]{8}{\text{A long message for Alice}} \< \\ + \text{finalize} \< \< \< \< } +\end{lstlisting} +Note that for the last message from Charlie to Alice we needed to specify the number of passed +over colums (\lstinline$\sendmessageleftx[7cm]{8}{message}$). As we were passing +4 \lstinline$\<$ where each creates 2 columns, the total was 8 columns. + + +\subsection{Divisions} +You can use \lstinline$\pcintertext$ in order to divide protocols (or other pseudocode for that matter). +\begin{lstlisting} +\pcintertext[dotted|center]{Division Text} +\end{lstlisting} +Note that in order to use the \lstinline$\pcintertext$ you need to use \lstinline$\pclb$ as the line break for the line +before. Also see Chapter~\ref{chap:tabbing}. + +\begin{center} +\fbox{% +\protocol{My Protocol}{% +\textbf{Alice} \< \< \textbf{Bob} \\ + b \sample \bin \< \< \pclb + \pcintertext[dotted]{Some Division} \\ + \< \sendmessageright*{\text{send over } b} \< \\ + \< \< \text{do something} \pclb + \pcintertext[dotted]{Another Division} \\ + \< \sendmessageleft*{\text{message}} \< \\ + \text{finalize} \< \< } +} +\end{center} + +\begin{lstlisting} +\protocol{My Protocol}{% +\textbf{Alice} \< \< \textbf{Bob} \\ + b \sample \bin \< \< \pclb + \pcintertext[dotted]{Some Division} \\ + \< \sendmessageright*{\text{send over } b} \< \\ + \< \< \text{do something} \pclb + \pcintertext[dotted]{Another Division} \\ + \< \sendmessageleft*{\text{message}} \< \\ + \text{finalize} \< \< } +\end{lstlisting} + + + +\section{Line Numbering in Protocols} +Protocols can be numbered similarly to plain pseudocode. Additionally to the \lstinline$\pcln$ there are the commands \lstinline$\pclnr$ and \lstinline$\pcrln$. The first +allows you to right align line numbers but uses the same counter as \lstinline$\pcln$. The second uses a different counter. + +\begin{center} +\fbox{% +\protocol{My Protocol}{% +\pcln \textbf{Alice} \< \< \textbf{Bob} \< \\ +\pcln b \sample \bin \< \< \< \\ + \< \sendmessageright*{\text{send over } b} \< \< \pclnr\\ + \< \< \text{do something} \< \pclnr \\ + \< \sendmessageleft*{\text{send over sth. else}} \<\< \pclnr \\ +\pcln \text{finalize} \< \< \<} +} +\end{center} +Which is generated as +\begin{lstlisting} +\protocol{My Protocol}{% +\pcln \textbf{Alice} \< \< \textbf{Bob} \< \\ +\pcln b \sample \bin \< \< \< \\ + \< \sendmessageright*{\text{send over } b} \< \< \pclnr\\ + \< \< \text{do something} \< \pclnr \\ + \< \sendmessageleft*{\text{send over sth. else}} \<\< \pclnr \\ +\pcln \text{finalize} \< \< \<} +\end{lstlisting} + + + +And using \lstinline$\pcrln$: +\begin{center} +\fbox{% +\protocol{My Protocol}{% +\pcln \textbf{Alice} \< \< \textbf{Bob} \< \\ +\pcln b \sample \bin \< \< \< \\ + \< \sendmessageright*{\text{send over } b} \<\< \pcrln\\ + \< \< \text{do something} \< \pcrln \\ + \< \sendmessageleft*{\text{send over sth. else}} \< \< \pcrln \\ +\pcln \text{finalize} \< \< \< } +} +\end{center} +Which is generated as +\begin{lstlisting} +\protocol{My Protocol}{% +\pcln \textbf{Alice} \< \< \textbf{Bob} \\ +\pcln b \sample \bin \< \< \\ +\< \sendmessageright*{\text{send over } b} \< \pcrln\\ +\< \< \text{do something} \pcrln \\ +\< \sendmessageleft*{\text{send over sth. else}} \< \pcrln \\ +\pcln \text{finalize} \< \< } +\end{lstlisting} + + + + +\subsection{Separators} +\label{sec:protocol:separator} +The commands \lstinline$\pclnseparator$ and \lstinline$\pcrlnseparator$ define the separators between the pseudocode and line numbering. By default the left separator is set to (:) colon and the right separator is set to a space of 3 pt. + + +\section{Sub Protocols} + +Use the \enquote{subprocedure} function also to create sub protocols. + +\begin{center} +\fbox{% +\protocol{My Protocol}{% + \textbf{Alice} \< \< \textbf{Bob} \\ + b \sample \bin \< \< \\ + \< \sendmessageright*{\text{send over } b} \< \\ + \< \< \text{do something} \\ + \<\< \dbox{\begin{subprocedure}\pseudocode{ + \< \< \textbf{Charlie} \\ +\text{something more} \< \< \\ + \< \sendmessageright*[1.5cm]{\text{message}} \< \\ + \< \< \text{some processing} \\ + \< \< \text{more processing} \\ + \< \sendmessageleft*[1.5cm]{\text{message}} \< \\ + \< \sendmessageright*[1.5cm]{\text{message}} \< \\ + \< \sendmessageleft*[1.5cm]{\text{message}} \< \\ +}\end{subprocedure}} \\ + \< \sendmessageleft*{\text{send over sth. else}} \< \\ + \text{finalize} \< \< } +} +\end{center} + + + \begin{lstlisting} +\protocol{My Protocol}{% + \textbf{Alice} \< \< \textbf{Bob} \\ + b \sample \bin \< \< \\ + \< \sendmessageright*{\text{send over } b} \< \\ + \< \< \text{do something} \\ + \<\< \dbox{\begin{subprocedure}\pseudocode{ + \< \< \textbf{Charlie} \\ +\text{something more} \< \< \\ + \< \sendmessageright*[1.5cm]{\text{message}} \< \\ + \< \< \text{some processing} \\ + \< \< \text{more processing} \\ + \< \sendmessageleft*[1.5cm]{\text{message}} \< \\ + \< \sendmessageright*[1.5cm]{\text{message}} \< \\ + \< \sendmessageleft*[1.5cm]{\text{message}} \< \\ +}\end{subprocedure}} \\ + \< \sendmessageleft*{\text{send over sth. else}} \< \\ + \text{finalize} \< \< } +\end{lstlisting} + + + + + + +\chapter{Game Based Proofs} +\label{chap:gbproofs} + +\section{Basics} +\index{gameproof} +\index{gameprocedure} + +Besides displaying pseudocode the package also comes with commands to display game based proofs. A proof +is wrapped in the \emph{gameproof} environment. +\begin{lstlisting} +\begin{gameproof} +proof goes here +\end{gameproof} +\end{lstlisting} +Within the proof environment you can use the command \lstinline$\gameprocedure$ which works similarly to the pseudocode +command and produces a heading of the form $\pcgamename_{\text{counter}}$ where counter is a consecutive counter. +Thus, we can create the following setup +\begin{center} +\begin{gameproof} +\gameprocedure[linenumbering,mode=text]{% + Step 1 \\ + Step 2 + } +\gameprocedure[mode=text]{% + Step 1 \\ + Step 2 + } +\end{gameproof} +\end{center} +by using +\begin{lstlisting} +\begin{gameproof} +\gameprocedure[linenumbering,mode=text]{% + Step 1 \\ + Step 2 + } +\gameprocedure[mode=text]{% + Step 1 \\ + Step 2 + } +\end{gameproof} +\end{lstlisting} + + + +\subsection{Highlight Changes} +\index{gamechange} +In order to highlight changes from one game to the next use \lstinline$\gamechange$. +\begin{center} +\begin{gameproof} +\gameprocedure[linenumbering,mode=text]{% + Step 1 \\ + Step 2 + } +\gameprocedure[mode=text]{% + Step 1 \\ + \gamechange{Step 2} + } +\end{gameproof} +\end{center} +\begin{lstlisting} +\begin{gameproof} +\gameprocedure[linenumbering,mode=text]{% + Step 1 \\ + Step 2 + } +\gameprocedure[mode=text]{% + Step 1 \\ + \gamechange{Step 2} + } +\end{gameproof} +\end{lstlisting} + +\subsection{Boxed games} +\index{tbxgameprocedure} +Use \lstinline$\tbxgameprocedure$ in order to create two consecutive games where the second game is \emph{boxed}. Use +\lstinline$\pcbox$ to create boxed statements. +\begin{center} +\begin{gameproof} +\gameprocedure{% + \pcln \text{Step 1} \\ + \pcln \text{Step 2} + } +\tbxgameprocedure{% + \text{Step 1}; \pcbox{\text{Alternative step 1}} \\ + \gamechange{\text{Step 2 is different}} + } +\gameprocedure{% + \text{Step 1} \\ + \text{\gamechange{Step 2}} + } +\end{gameproof} +\end{center} + +\begin{lstlisting} +\begin{gameproof} +\gameprocedure{% + \pcln \text{Step 1} \\ + \pcln \text{Step 2} + } +\tbxgameprocedure{% + \text{Step 1}; \pcbox{\text{Alternative step 1}} \\ + \gamechange{\text{Step 2 is different}} + } +\gameprocedure{% + \pcln \text{Step 1} \\ + \pcln \text{\gamechange{Step 2}} + } +\end{gameproof} +\end{lstlisting} + +\subsection{Reduction Hints} +\index{addgamehop} +In a game based proof in order to go from one game to the next we usually give a reduction, for example, we show that +the difference between two games is bound by the security of some pseudorandom generator $\mathsf{PRG}$. To give a hint +within the pseudocode that the difference between two games is down to ``something'' you can use the \lstinline$\addgamehop$ +command. +\begin{lstlisting} +\addgamehop{startgame}{endgame}{options} +\end{lstlisting} +Here options allows you to specify the hint as well as the style. The following options are available +\begin{description} +\item[hint] +The hint text +\item[nodestyle] +A TIKZ style to be used for the node. +\item[pathstyle] +A TIKZ style to be used for the path. +\item[edgestyle] +A TIKZ style to be used for the edge. This defaults to \enquote{bend left}. +\end{description} + +\begin{center} +\begin{gameproof} +\gameprocedure{% + \pcln \text{Step 1} \\ + \pcln \text{Step 2} + } +\gameprocedure{% + \text{Step 1} \\ + \gamechange{\text{Step 2 is different}} + } +\addgamehop{1}{2}{hint=\footnotesize some hint,nodestyle=red} +\end{gameproof} +\end{center} +\begin{lstlisting} +\begin{gameproof} +\gameprocedure{% + \pcln \text{Step 1} \\ + \pcln \text{Step 2} + } +\gameprocedure{% + \text{Step 1} \\ + \gamechange{\text{Step 2 is different}} + } +\addgamehop{1}{2}{hint=\footnotesize some hint,nodestyle=red} +\end{gameproof} +\end{lstlisting} +The edgestyle allows you to specify how the hint is displayed. If you, for example want a straight line, rather than the curved arrow simply +use +\begin{lstlisting} +\addgamehop{1}{2}{hint=\footnotesize some hint,edgestyle=} +\end{lstlisting} + + + +If game proofs do not fit into a single picture you can specify start and end hints using the commands +\begin{lstlisting} +\addstartgamehop[first game]{options} +\addendgamehop[last game]{options} +\end{lstlisting} + +\begin{center} +\begin{gameproof} +\gameprocedure{% + \pcln \text{Step 1} \\ + \pcln \text{Step 2} + } +\gameprocedure{% + \text{Step 1} \\ + \gamechange{\text{Step 2 is different}} + } + \addstartgamehop{hint=\footnotesize some hint,edgestyle=} +\addgamehop{1}{2}{hint=\footnotesize some hint} + \addendgamehop{hint=\footnotesize some outgoing hint,edgestyle=} +\end{gameproof} +\end{center} + + +\begin{lstlisting} +\begin{gameproof} +\gameprocedure{% + \pcln \text{Step 1} \\ + \pcln \text{Step 2} + } +\gameprocedure{% + \text{Step 1} \\ + \gamechange{\text{Step 2 is different}} + } + \addstartgamehop{hint=\footnotesize some hint,edgestyle=} +\addgamehop{1}{2}{hint=\footnotesize some hint} + \addendgamehop{hint=\footnotesize some outgoing hint,edgestyle=} +\end{gameproof} +\end{lstlisting} + +\subsection{Numbering and Names} +By default the \emph{gameproof} environment starts to count from 1 onwards. Its optional parameters allow you to specify a custom +name for your game and the starting number. +\begin{lstlisting} +\begin{gameproof}[options] +\end{lstlisting} + +\begin{center} +\begin{gameproof}[nr=5,name=\mathsf{MyGame},arg=(1^n)] +\gameprocedure{% + \pcln \text{Step 1} \\ + \pcln \text{Step 2} + } +\gameprocedure{% + \text{Step 1} \\ + \gamechange{\text{Step 2 is different}} + } +\addstartgamehop{hint=\footnotesize some ingoing hint} +\addgamehop{6}{7}{hint=\footnotesize some hint} + \addendgamehop{hint=\footnotesize some outgoing hint} +\end{gameproof} +\end{center} + +\begin{lstlisting} +\begin{gameproof}[nr=5,name=$\mathsf{MyGame}$,arg=$(1^n)$] +\gameprocedure{% + \pcln \text{Step 1} \\ + \pcln \text{Step 2} + } +\gameprocedure{% + \text{Step 1} \\ + \gamechange{\text{Step 2 is different}} + } +\addstartgamehop{hint=\footnotesize some ingoing hint} +\addgamehop{6}{7}{hint=\footnotesize some hint} + \addendgamehop{hint=\footnotesize some outgoing hint} +\end{gameproof} +\end{lstlisting} + + +\subsection{Default Name and Argument} +The default name and argument are controlled via the commands \lstinline$\pcgamename$ and \lstinline$\gameprocedurearg$. + +\begin{center} +\begin{tabular}{ll} +\textbf{Command} & \textbf{Default} \\ +\lstinline$\pcgamename$ & \lstinline$\mathsf{Game}$ \\ +\lstinline$\gameprocedurearg$ & \lstinline$(\secpar)$ +\end{tabular} +\end{center} + + +\subsection{Two Directional Games} +\index{bxgameprocedure} +\index{addloopgamehop} +You can use the \lstinline$\bxgameprocedure$ to generate games for going in two directions. Use the \lstinline$\addloopgamehop$ +to add the gamehop in the middle. + +\vspace{1cm} +\begin{center} +\begin{gameproof} +\bxgameprocedure{4}{% + \pcln \text{Step 1}; \pcbox{Alternative} \\ + \pcln \text{Step 2} + } +\bxgameprocedure{3}{% + \text{Step 1}; \pcbox{Alternative} \\ + \gamechange{\text{Step 2 is different}} + } + \addstartgamehop{hint=\footnotesize some hint,edgestyle=} +\addgamehop{1}{2}{hint=\footnotesize some hint,edgestyle=} + \addloopgamehop{hint=\footnotesize some loop hint} + \addgamehop{2}{1}{hint=\footnotesize some hint} +\end{gameproof} +\end{center} + + +\begin{lstlisting} +\begin{gameproof} +\bxgameprocedure{4}{% + \pcln \text{Step 1}; \pcbox{Alternative} \\ + \pcln \text{Step 2} + } +\bxgameprocedure{3}{% + \text{Step 1}; \pcbox{Alternative} \\ + \gamechange{\text{Step 2 is different}} + } + \addstartgamehop{hint=\footnotesize some hint,edgestyle=} +\addgamehop{1}{2}{hint=\footnotesize some hint,edgestyle=} + \addloopgamehop{hint=\footnotesize some loop hint} + \addgamehop{2}{1}{hint=\footnotesize some hint} +\end{gameproof} +\end{lstlisting} + +\chapter{Black-box Reductions} +\label{chap:bbr} +\index{bbrenv} +\index{bbrbox} +\index{bbrinput} +\index{bbroutput} + +The cryptocode package comes with support for drawing basic black box reductions. A reduction is +always of the following form. + +\begin{lstlisting} +\begin{bbrenv}{A} +\begin{bbrbox}[name=Box Name] +% The Box's content +\end{bbrbox} +% Commands to display communication, input output etc +\end{bbrenv} +\end{lstlisting} +That is, a \enquote{bbrenv} (where bbr is short for black-box reduction) environment which takes a single +\enquote{bbrbox} environment and some additional commands. + +The following is a simple example drawing one (black)box with some code and input output: +\begin{bbrenv}{A} + \begin{bbrbox}[name=Box Name] + \pseudocode{ + \text{step 1} \\ + \text{step 2} \\ + \pcfor \text{some condition} \pcdo \\ + \pcind\text{step 3} + } + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} +This box is generated as +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Box Name] + \pseudocode{ + \text{step 1} \\ + \text{step 2} \\ + \pcfor \text{some condition} \pcdo \\ + \pcind\text{step 3} + } + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} +\end{lstlisting} + +The commands \lstinline$bbrinput$ and \lstinline$bbroutput$ allow to specify input and output for the latest +''bbrenv´´ environment. The single argument to the bbrenv environment needs to specify a unique identifier +(unique for the current reduction). This id is used as an internal TIKZ node name (\url{http://www.ctan.org/tex-archive/graphics/pgf/}). +\begin{lstlisting} +\begin{bbrenv}{UNIQUE IDENTIFIER} +\end{lstlisting} +As we are drawing a TIKZ image, note that we can easily later customize the image using the labels that we +have specified on the way. +\begin{bbrenv}{A} + \begin{bbrbox}[name=Box Name] + \pseudocode{ + \text{step 1} \\ + \text{step 2} \\ + \pcfor \text{some condition} \pcdo \\ + \pcind\text{step 3} + } + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} + + \filldraw[fill=blue] (A.north) circle (4pt); + \filldraw[fill=blue] (A.west) circle (4pt); + \filldraw[fill=blue] (A.east) circle (4pt); + \filldraw[fill=blue] (A.south) circle (4pt); +\end{bbrenv} +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Box Name] + \pseudocode{ + \text{step 1} \\ + \text{step 2} \\ + \pcfor \text{some condition} \pcdo \\ + \pcind\text{step 3} + } + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} + + \filldraw[fill=blue] (A.north) circle (4pt); + \filldraw[fill=blue] (A.west) circle (4pt); + \filldraw[fill=blue] (A.east) circle (4pt); + \filldraw[fill=blue] (A.south) circle (4pt); +\end{bbrenv} +\end{lstlisting} + +The \enquote{bbrbox} takes as single argument a comma separated list of key value pairs. In the example we have used +\begin{lstlisting} +name=Box Name +\end{lstlisting} +to specify the label. The following options are available + +\begin{tabular}{ll} +Option & Description \\ \hline +name & Specifies the box' label \\ +minheight & The minimal height \\ +xshift & Allows horizontal positioning \\ +style & allows to customize the node +\end{tabular} + + +\section{Nesting of Boxes} +Boxes can be nested. For this simply insert a bbrenv (together with a single bbrbox) environment into an +existing bbrbox. +\begin{bbrenv}{A} + \begin{bbrbox}[name=Box Name] + \pseudocode{ + \text{step 1} \\ + \text{step 2} \\ + \pcfor \text{some condition} \pcdo \\ + \pcind\text{step 3} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Inner Box] + \pseudocode{ + \text{inner step 1} \\ + \text{inner step 2} \\ + } + \end{bbrbox} + \end{bbrenv} + + \pseudocode{ + \text{step 4} \\ + \text{step 5} \\ + } + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} + +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Box Name] + \pseudocode{ + \text{step 1} \\ + \text{step 2} \\ + \pcfor \text{some condition} \pcdo \\ + \pcind\text{step 3} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Inner Box] + \pseudocode{ + \text{inner step 1} \\ + \text{inner step 2} \\ + } + \end{bbrbox} + \end{bbrenv} + + \pseudocode{ + \text{step 4} \\ + \text{step 5} \\ + } + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} +\end{lstlisting} + +\section{Messages and Queries} +\index{bbrmsgto} +\index{bbrmsgfrom} +\index{bbrqryto} +\index{bbrqryfrom} + +You can send messages and queries to boxes. For this use the commands +\begin{lstlisting} +\bbrmsgto{options} +\bbrmsgfrom{options} +\bbrqryto{options} +\bbrqryfrom{options} +\end{lstlisting} +By convention messages are on the left of boxes and queries on the right. Commands ending on to +make an arrow to the right while commands ending on from make an arrow to the left. The \emph{options} +define how the message is drawn and consists of a key-value pairs separated by \enquote{,}. + +For example, to draw a message with a label on top and on the side use +\begin{lstlisting} +\bbrmsgto{top=Top Label, side=Side Label} +\end{lstlisting} +If your label contains a \enquote{,} (comma), then group the label in $\{\}$ (curly brackets). +\begin{lstlisting} +\bbrmsgto{top=Top Label, side={Side, Label}} +\end{lstlisting} + +Following is a complete example. Notice that cryptocode takes care of the vertical positioning. + +\begin{bbrenv}{A} + \begin{bbrbox}[name=Box Name] + \pseudocode{ + \text{step 1} \\ + \text{step 2} \\ + \pcfor \text{some condition} \pcdo \\ + \pcind\text{step 3} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Inner Box] + \pseudocode{ + \text{inner step 1} \\ + \text{inner step 2} \\ + } + \end{bbrbox} + + \bbrmsgto{top={$m_0,m_1$}} + \bbrmsgfrom{top=$q$} + + + \bbrqryto{top={$m_0,m_1$}} + \bbrqryfrom{top=$q$} + + \end{bbrenv} + + \pseudocode{ + \text{step 4} \\ + \text{step 5} \\ + } + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} + +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Box Name] + \pseudocode{ + \text{step 1} \\ + \text{step 2} \\ + \pcfor \text{some condition} \pcdo \\ + \pcind\text{step 3} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Inner Box] + \pseudocode{ + \text{inner step 1} \\ + \text{inner step 2} \\ + } + \end{bbrbox} + + \bbrmsgto{top={$m_0,m_1$}} + \bbrmsgfrom{top=$q$} + + + \bbrqryto{top={$m_0,m_1$}} + \bbrqryfrom{top=$q$} + + \end{bbrenv} + + \pseudocode{ + \text{step 4} \\ + \text{step 5} \\ + } + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} +\end{lstlisting} + +\subsection{Options} +Besides specifying labels for top, side and bottom you can further specify how cryptocode renders the message. +Remember that tnderneath the reduction commands is a TIKZ image (\url{http://www.ctan.org/tex-archive/graphics/pgf/}). +For each label position (top, side, bottom) a node is generated. You can provide additional properties for +this node using the options: +\begin{itemize} +\item topstyle +\item sidestyle +\item bottomstyle +\end{itemize} +You can additionally provide custom names for the nodes for later reference using +\begin{itemize} +\item topname +\item sidename +\item osidename +\item bottomname +\end{itemize} +The \enquote{osidename} allows you to provide a name for the \enquote{other side}. + +Via the option \enquote{length} you can specifiy the length of the arrow. + + +\begin{bbrenv}{A} + \begin{bbrbox}[name=Box Name] + \pseudocode{ + \text{step 1} \\ + \text{step 2} \\ + \pcfor \text{some condition} \pcdo \\ + \pcind\text{step 3} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Inner Box] + \pseudocode{ + \text{inner step 1} \\ + \text{inner step 2} \\ + } + \end{bbrbox} + + \bbrmsgto{top={$m_0,m_1$},side=Side Label, bottom=$b$, length=2cm, + topstyle={draw, solid}, sidestyle={red}, bottomstyle={draw, dashed}} + + \end{bbrenv} + + \pseudocode{ + \text{step 4} \\ + \text{step 5} \\ + } + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} + +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Box Name] + \pseudocode{ + \text{step 1} \\ + \text{step 2} \\ + \pcfor \text{some condition} \pcdo \\ + \pcind\text{step 3} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Inner Box] + \pseudocode{ + \text{inner step 1} \\ + \text{inner step 2} \\ + } + \end{bbrbox} + + \bbrmsgto{top={$m_0,m_1$},side=Side Label, bottom=$b$, length=2cm, + topstyle={draw, solid}, sidestyle={red}, bottomstyle={draw, dashed}} + + \end{bbrenv} + + \pseudocode{ + \text{step 4} \\ + \text{step 5} \\ + } + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} +\end{lstlisting} + +\subsection{Loops} +\index{bbrloop} +Often an adversary may send poly many queries to an oracle, or a reduction sends many queries to an adversary. +Consider the following setting + +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + + \end{bbrbox} + + \bbrmsgto{top=$m$,sidename=BeginLoop} + \bbrmsgfrom{top=$\sigma$,sidename=EndLoop} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} + +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + + \end{bbrbox} + + \bbrmsgto{top=$m$} + \bbrmsgfrom{top=$\sigma$} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} +\end{lstlisting} + +First note that by specifying the minheight and xshift option we shifted the adversary box a bit to the right +and enlarged its box. Further we specified custom names for the node on the side of the two messages. We +can now use the \lstinline$bbrloop$ command to visualize that these two messages are exchanged $q$ many times +\begin{lstlisting} +\bbrloop{BeginLoop}{EndLoop}{center=$q$} +\end{lstlisting} +The \lstinline$bbrloop$ command takes two node names and a config which allows you to specify if the label is +to be shown on the left, center or right. Here is the result. +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + + \end{bbrbox} + + \bbrmsgto{top=$m$,sidename=BeginLoop} + \bbrmsgfrom{top=$\sigma$,sidename=EndLoop} + \bbrloop{BeginLoop}{EndLoop}{center=$q$} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} + +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + + \end{bbrbox} + + \bbrmsgto{top=$m$,sidename=BeginLoop} + \bbrmsgfrom{top=$\sigma$,sidename=EndLoop} + \bbrloop{BeginLoop}{EndLoop}{center=$q$} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} +\end{lstlisting} + +\subsection{Add Space} +\index{bbrmsgspace} +If the spacing between messages is not sufficient you can use the \lstinline$bbrmsgspace$ and +\lstinline$bbrqryspace$ commands to add additional space. +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + + \end{bbrbox} + + \bbrmsgto{top=$m$} + \bbrmsgspace{1.5cm} + \bbrmsgfrom{top=$\sigma$} + + \bbrqryto{top=$m$} + \bbrqryspace{1cm} + \bbrqryfrom{top=$\sigma$} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} + +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + + \end{bbrbox} + + \bbrmsgto{top=$m$} + \bbrmsgspace{1.5cm} + \bbrmsgfrom{top=$\sigma$} + + \bbrqryto{top=$m$} + \bbrqryspace{1cm} + \bbrqryfrom{top=$\sigma$} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} +\end{lstlisting} + + +\subsection{Intertext} +\index{bbrmsgtxt} +\index{bbrqrytxt} + +If your reduction needs to do some extra work between queries use the \lstinline$\bbrmsgtxt$ +and \lstinline$\bbrqrytxt$ commands. +\begin{lstlisting} +\bbrmsgtxt[options]{Text} +\bbrqrytxt[options]{Text} +\end{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + + \end{bbrbox} + + \bbrmsgto{top=$m$} + \bbrmsgtxt{\pseudocode{ + do \\ + some \\ + work + }} + \bbrmsgfrom{top=$\sigma$} + + \bbrqryto{top=$m$} + \bbrqrytxt[beforeskip=0.5cm,nodestyle={draw,dashed},xshift=2cm]{\pseudocode{ + do \\ + some \\ + work + }} + \bbrqryfrom{top=$\sigma$} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} + +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + + \end{bbrbox} + + \bbrmsgto{top=$m$} + \bbrmsgtxt{\pseudocode{ + do \\ + some \\ + work + }} + \bbrmsgfrom{top=$\sigma$} + + \bbrqryto{top=$m$} + \bbrqrytxt[beforeskip=0.5cm,nodestyle={draw,dashed},xshift=2cm]{\pseudocode{ + do \\ + some \\ + work + }} + \bbrqryfrom{top=$\sigma$} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} +\end{bbrenv} +\end{lstlisting} + +\section{Oracles} +\index{bbroracle} +Each box can have one or more oracles which are drawn on the right hand side of the box. An oracle +is created similarly to a \emph{bbrenv} environment using the \emph{bbroracle} environment. Oracles +go behind the single \emph{bbrbox} environment within an \emph{bbrenv} enviornment. + +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + \end{bbrbox} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} + + \begin{bbroracle}{OraA} + \begin{bbrbox}[name=Oracle 1] + \end{bbrbox} + \end{bbroracle} + + \begin{bbroracle}{OraB} + \begin{bbrbox}[name=Oracle 2] + \end{bbrbox} + \end{bbroracle} +\end{bbrenv} + + +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + \end{bbrbox} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} + + \begin{bbroracle}{OraA} + \begin{bbrbox}[name=Oracle 1] + \end{bbrbox} + \end{bbroracle} + + \begin{bbroracle}{OraB} + \begin{bbrbox}[name=Oracle 2] + \end{bbrbox} + \end{bbroracle} +\end{bbrenv} +\end{lstlisting} + +\subsection{Communicating with Oracles} +\index{bbroraclequeryfrom} +\index{bbroraclequeryto} +As oracles use the \emph{bbrbox} environment we can directly use the established ways to send messages and +queries to oracles. In addition you can use the \lstinline$\bbroraclequeryfrom$ and \lstinline$\bbroraclequeryto$. +\begin{lstlisting} +\bbroraclequeryfrom{options} +\bbroraclequeryto{options} +\end{lstlisting} +Here options allow you to specify where the label goes (top, bottom). In addition you can use +\lstinline$\bbroracleqryspace$ to generate extra space between oracle messages. Note +that oracle messages need to be added after the closing \lstinline$\end{bbroracle}$ command. + +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + \end{bbrbox} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} + + \begin{bbroracle}{OraA} + \begin{bbrbox}[name=Oracle 1,minheight=1cm] + \end{bbrbox} + \end{bbroracle} + \bbroraclequeryfrom{top=$m$} + \bbroraclequeryto{top=$b$} + + \begin{bbroracle}{OraB} + \begin{bbrbox}[name=Oracle 2,minheight=1cm] + \end{bbrbox} + \end{bbroracle} + \bbroraclequeryfrom{bottom=$m$} + \bbroraclequeryto{bottom=$b$} +\end{bbrenv} + +\begin{lstlisting} +\begin{bbrenv}{A} + \begin{bbrbox}[name=Reduction] + \pseudocode{ + \text{Do something} + } + + \begin{bbrenv}{B} + \begin{bbrbox}[name=Adversary,minheight=3cm,xshift=4cm] + \end{bbrbox} + + \end{bbrenv} + + \end{bbrbox} + \bbrinput{input} + \bbroutput{output} + + \begin{bbroracle}{OraA} + \begin{bbrbox}[name=Oracle 1,minheight=1cm] + \end{bbrbox} + \end{bbroracle} + \bbroraclequeryfrom{top=$m$} + \bbroraclequeryto{top=$b$} + + \begin{bbroracle}{OraB} + \begin{bbrbox}[name=Oracle 2,minheight=1cm] + \end{bbrbox} + \end{bbroracle} + \bbroraclequeryfrom{bottom=$m$} + \bbroraclequeryto{bottom=$b$} +\end{bbrenv} +\end{lstlisting} + +%\chapter{Known Issues} +% +%\section{Hyperref} +%\label{sec:hyperref} +%\index{pcfixhyperref} +%Referencing line numbers breaks the hyperref package. In order to fix this call +%\begin{lstlisting} +%\pcfixhyperref +%\end{lstlisting} +%after \lstinline$\begin{document}$. + +\printindex + + + +\end{document} + diff --git a/Master/texmf-dist/tex/latex/cryptocode/cryptocode.sty b/Master/texmf-dist/tex/latex/cryptocode/cryptocode.sty new file mode 100644 index 00000000000..1e1b843dfce --- /dev/null +++ b/Master/texmf-dist/tex/latex/cryptocode/cryptocode.sty @@ -0,0 +1,1406 @@ + %% Copyright 2015 Arno Mittelbach + % + % This work may be distributed and/or modified under the + % conditions of the LaTeX Project Public License, either version 1.3 + % of this license or (at your option) any later version. + % The latest version of this license is in + % http://www.latex-project.org/lppl.txt + % and version 1.3 or later is part of all distributions of LaTeX + % version 2005/12/01 or later. + % + % This work has the LPPL maintenance status `maintained'. + % + % The Current Maintainer of this work is Arno Mittelbach. + % + % This work consists of the files cryptocode.tex and cryptocode.sty +\NeedsTeXFormat{LaTeX2e} +\ProvidesPackage{cryptocode} + [2015/03/09 v0.01 Cryptocode LaTeX package for writing pseudocode in cryptographic settings] + + +\def\hi{Hello, this is Arno's crypto code package. } +\let\myDate\date + +%%% +% option modes +\newif\ifpc@orderofgrowth +\newif\ifpc@algorithmstyle +\newif\ifpc@amsfonts +\newif\ifpc@advantage +\newif\ifpc@primitives + +%%% +% +\DeclareOption{operators}{ + \providecommand{\sample}{\hskip2.3pt{\gets\!\!\mbox{\tiny${\$}$\normalsize}}\,} + + \providecommand{\floor}[1]{\ensuremath{\left\lfloor #1\right\rfloor}} + \providecommand{\ceil}[1]{\ensuremath{\left\lceil #1\right\rceil}} + \providecommand{\Angle}[1]{\ensuremath{\left\langle #1\right\rangle}} + \providecommand{\abs}[1]{\ensuremath{\left\lvert #1 \right\rvert}} + \providecommand{\norm}[1]{\ensuremath{\left\|#1\right\|}} + \providecommand{\concat}{\ensuremath{\|}} + + \providecommand{\emptystring}{\ensuremath{\varepsilon}} +} + +\DeclareOption{adversary}{ + \providecommand{\pcadvstyle}[1]{\mathcal{#1}} + + \providecommand{\adv}{\ensuremath{\pcadvstyle{A}}} + \providecommand{\bdv}{\ensuremath{\pcadvstyle{B}}} + \providecommand{\cdv}{\ensuremath{\pcadvstyle{C}}} + \providecommand{\ddv}{\ensuremath{\pcadvstyle{D}}} + \providecommand{\mdv}{\ensuremath{\pcadvstyle{M}}} + \providecommand{\pdv}{\ensuremath{\pcadvstyle{P}}} + \providecommand{\rdv}{\ensuremath{\pcadvstyle{R}}} + \providecommand{\sdv}{\ensuremath{\pcadvstyle{S}}} +} + +\DeclareOption{landau}{ + \pc@orderofgrowthtrue + + \providecommand{\bigO}[1]{\ensuremath{\mathcal{O}\olrk{#1}}} + \providecommand{\smallO}[1]{\ensuremath{\text{o}\olrk{#1}}} + \providecommand{\bigOmega}[1]{\ensuremath{\Omega\olrk{#1}}} + \providecommand{\smallOmega}[1]{\ensuremath{\omega\olrk{#1}}} + \providecommand{\bigsmallO}[1]{\ensuremath{\Theta\olrk{#1}}} +} + +\DeclareOption{probability}{ + \pc@orderofgrowthtrue + \pc@amsfontstrue + + \providecommand{\probname}{Pr} + \providecommand{\expectationname}{\ensuremath{\mathbb{E}}} + \providecommand{\supportname}{Supp} + + \providecommand{\prob}[1]{\ensuremath{\operatorname{\probname}\elrk{#1}}} + \providecommand{\probsub}[2]{\ensuremath{\operatorname{\probname}_{#1}\elrk{#2}}} + \providecommand{\condprob}[2]{\ensuremath{\prob{#1\,\left|\,#2\vphantom{#1}\right.}}} + \providecommand{\condprobsub}[3]{\ensuremath{\probsub{#1}{#2\,\left|\,#3\vphantom{#1}\right.}}} + + \providecommand{\expect}[1]{\ensuremath{\operatorname{\expectationname}\elrk{#1}}} + \providecommand{\expsub}[2]{\ensuremath{\operatorname{\expectationname}_{#1}\elrk{#2}}} + \providecommand{\condexp}[2]{\ensuremath{\expect{#1\,\left|\,#2\vphantom{#1}\right.}}} + \providecommand{\condexpsub}[3]{\ensuremath{\expsub{#1}{#2\,\left|\,#3\vphantom{#1}\right.}}} + + \providecommand{\supp}[1]{ \ensuremath{\operatorname{Supp}\olrk{#1}}} + + \providecommand{\entropy}[1]{\ensuremath{\operatorname{H}\olrk{#1}}} + \providecommand{\minentropy}[1]{\ensuremath{\operatorname{H_\infty}\olrk{#1}}} + \providecommand{\condminentropy}[2]{\ensuremath{\operatorname{\tilde{H}_\infty}\olrk{#1|#2}}} +} + +\DeclareOption{sets}{ + \pc@orderofgrowthtrue + \pc@amsfontstrue + + \providecommand\NN{\mathbb{N}} + \providecommand\ZZ{\mathbb{Z}} + \providecommand\QQ{\mathbb{Q}} + \providecommand\RR{\mathbb{R}} + \providecommand\PP{\mathbb{P}} + \providecommand\FF{\mathbb{F}} + \providecommand\GG{\mathbb{G}} + + \providecommand{\set}[1]{\ensuremath{\clrk{#1}}} + \providecommand{\sequence}[1]{\ensuremath{\olrk{#1}}} + \providecommand{\bin}{\ensuremath{\{0,1\}}} +} + +\DeclareOption{noamsfonts}{ + \pc@amsfontsfalse +} + + +\DeclareOption{notions}{ + \providecommand{\pcnotionstyle}[1]{\ensuremath{\mathrm{#1}}} + + \providecommand{\indcpa}{\pcnotionstyle{IND\pcmathhyphen{}CPA}} + \providecommand{\indcca}{\pcnotionstyle{IND\pcmathhyphen{}CCA}} + \providecommand{\indccai}{\pcnotionstyle{IND\pcmathhyphen{}CCA1}} + \providecommand{\indccaii}{\pcnotionstyle{IND\pcmathhyphen{}CCA2}} + \providecommand{\priv}{\pcnotionstyle{PRIV}} + \providecommand{\ind}{\pcnotionstyle{IND}} + \providecommand{\indcda}{\pcnotionstyle{IND\pcmathhyphen{}CDA}} + \providecommand{\prvcda}{\pcnotionstyle{PRV\pcmathhyphen{}CDA}} + \providecommand{\prvrcda}{\pcnotionstyle{PRV\$\pcmathhyphen{}CDA}} + \providecommand{\kiae}{\pcnotionstyle{KIAE}} + \providecommand{\kdae}{\pcnotionstyle{KDAE}} + \providecommand{\mle}{\pcnotionstyle{MLE}} + \providecommand{\uce}{\pcnotionstyle{UCE}} +} + +\DeclareOption{logic}{ + \providecommand{\AND}{\ensuremath{\mathrm{AND}}} + \providecommand{\OR}{\ensuremath{\mathrm{OR}}} + \providecommand{\NOT}{\ensuremath{\mathrm{NOT}}} + \providecommand{\xor}{\ensuremath{\oplus}} + \providecommand{\false}{\mathsf{false}} + \providecommand{\true}{\mathsf{true}} +} + + +% Function Families +\DeclareOption{ff}{ + \pc@algorithmstyletrue + + \providecommand{\kgen}{\pcalgostyle{KGen}} + \providecommand{\pgen}{\pcalgostyle{Pgen}} + \providecommand{\eval}{\pcalgostyle{Eval}} + + \providecommand{\il}{\pcalgostyle{il}} + \providecommand{\ol}{\pcalgostyle{ol}} + \providecommand{\kl}{\pcalgostyle{kl}} + \providecommand{\nl}{\pcalgostyle{nl}} + \providecommand{\rl}{\pcalgostyle{rl}} +} + +% Machine Model +\DeclareOption{mm}{ + \pc@algorithmstyletrue + + \providecommand{\pcmachinemodelstyle}[1]{\ensuremath{\mathsf{#1}}} + + \providecommand{\CRKT}{\pcmachinemodelstyle{C}} + \providecommand{\TM}{\pcmachinemodelstyle{M}} + \providecommand{\PROG}{\pcmachinemodelstyle{P}} + + \providecommand{\uTM}{\pcmachinemodelstyle{UM}} + \providecommand{\uC}{\pcmachinemodelstyle{UC}} + \providecommand{\uP}{\pcmachinemodelstyle{UEval}} + + \providecommand{\csize}{\pcmachinemodelstyle{size}} + \providecommand{\tmtime}{\pcmachinemodelstyle{time}} + \providecommand{\ppt}{\pcalgostyle{PPT}} +} + +\DeclareOption{advantage}{ + \pc@advantagetrue +} + +\DeclareOption{primitives}{ + \pc@primitivestrue + \pc@algorithmstyletrue +} + +\DeclareOption{events}{ + \providecommand{\event}[1]{\ensuremath{\mathsf{#1}}} + \providecommand{\nevent}[1]{\ensuremath{\overline{\event{#1}}}} + + \providecommand{\bad}{\ensuremath{\event{bad}}} +} + +\DeclareOption{complexity}{ + \providecommand{\pccomplexitystyle}[1]{\ensuremath{\mathsf{#1}}} + + \providecommand{\npol}{\pccomplexitystyle{NP}} + \providecommand{\conpol}{\ensuremath{\mathsf{co}}\pccomplexitystyle{NP}} + \providecommand{\pol}{\pccomplexitystyle{P}} + \providecommand{\bpp}{\pccomplexitystyle{BPP}} + \providecommand{\ppoly}{\ensuremath{\pol/\mathrm{poly}}} + + \providecommand{\AM}{\pccomplexitystyle{AM}} + \providecommand{\coAM}{\ensuremath{\mathsf{co}}\pccomplexitystyle{AM}} + + \providecommand{\AC}[1]{\ensuremath{\ifthenelse{\equal{#1}{}}{\pccomplexitystyle{AC}}{\pccomplexitystyle{AC}^{#1}}}} + \providecommand{\NC}[1]{\ensuremath{\ifthenelse{\equal{#1}{}}{\pccomplexitystyle{NC}}{\pccomplexitystyle{NC}^{#1}}}} + \providecommand{\TC}[1]{\ensuremath{\ifthenelse{\equal{#1}{}}{\pccomplexitystyle{TC}}{\pccomplexitystyle{TC}^{#1}}}} +} + +\DeclareOption{asymptotics}{ + \pc@orderofgrowthtrue + + \providecommand{\pcpolynomialstyle}[1]{\mathsf{#1}} + + \providecommand{\negl}[1][\secpar]{\ensuremath{\pcpolynomialstyle{negl}\ifthenelse{\equal{#1}{}}{}{\olrk{#1}}}} + \providecommand{\poly}[1][\secpar]{\ensuremath{\pcpolynomialstyle{poly}\ifthenelse{\equal{#1}{}}{}{\olrk{#1}}}} + + \providecommand{\pp}{\ensuremath{\pcpolynomialstyle{p}}} + \providecommand{\qq}{\ensuremath{\pcpolynomialstyle{q}}} +} + +\DeclareOption{keys}{ + \providecommand{\pckeystyle}[1]{\ensuremath{\mathsf{#1}}} + + \providecommand{\pk}{\pckeystyle{pk}} + \providecommand{\vk}{\pckeystyle{vk}} + \providecommand{\sk}{\pckeystyle{sk}} + \providecommand{\key}{\pckeystyle{k}} + \providecommand{\hk}{\pckeystyle{hk}} + \providecommand{\gk}{\pckeystyle{gk}} + \providecommand{\fk}{\pckeystyle{fk}} + + \providecommand{\st}{\pckeystyle{st}} + \providecommand{\state}{\pckeystyle{state}} +} + +\DeclareOption{n}{ + \providecommand{\secpar}{\ensuremath{n}} + \providecommand{\secparam}{\ensuremath{1^\secpar}} +} + +\DeclareOption{lambda}{ + \providecommand{\secpar}{\ensuremath{\lambda}} + \providecommand{\secparam}{\ensuremath{1^\secpar}} +} + +\DeclareOption*{% + \PackageError{crypto code}{Unknown option ‘\CurrentOption’}% +} + +\ExecuteOptions{n} + +\ProcessOptions\relax + +%amsfonts +\RequirePackage{amsmath} +\ifpc@amsfonts + \RequirePackage{amsfonts} +\fi +\RequirePackage{mathtools} +\RequirePackage{xcolor} +\RequirePackage{calc} +\RequirePackage{tikz} +\usetikzlibrary{positioning,calc} +\RequirePackage{ifthen} +\RequirePackage{xargs} +\RequirePackage{pgf} +\RequirePackage{mathabx} +\RequirePackage{forloop} +\RequirePackage{array} +\RequirePackage{xparse} +\RequirePackage{pbox} +\RequirePackage{varwidth} +\RequirePackage{suffix} +\RequirePackage{etoolbox} +\RequirePackage{etex} +\RequirePackage{etextools} +\RequirePackage{environ} +\RequirePackage{xstring} +\RequirePackage{xspace} +\RequirePackage{xkeyval} + +\ifpc@advantage + \newcommandx*{\advantage}[3][3=(\secpar)]{\ensuremath{\mathsf{Adv}^{\mathrm{\MakeLowercase{#1}}}_{#2}#3}} +\fi + +\ifpc@primitives + % zero knowledge + \providecommand{\prover}{\pcalgostyle{P}} + \providecommand{\verifier}{\pcalgostyle{V}} + \providecommand{\nizk}{\pcalgostyle{NIZK}} + + % hash + \providecommand{\hash}{\pcalgostyle{H}} + \providecommand{\gash}{\pcalgostyle{G}} + \providecommand{\fash}{\pcalgostyle{F}} + + % encryption + \providecommand{\enc}{\pcalgostyle{Enc}} + \providecommand{\dec}{\pcalgostyle{Dec}} + + % signatures + \providecommand{\sig}{\pcalgostyle{Sig}} + \providecommand{\verify}{\pcalgostyle{Vf}} + + % obfuscation + \providecommand{\obf}{\pcalgostyle{O}} + \providecommand{\iO}{\pcalgostyle{iO}} + \providecommand{\diO}{\pcalgostyle{diO}} + + % PRF, PRG + \providecommand{\prf}{\pcalgostyle{PRF}} + \providecommand{\prg}{\pcalgostyle{PRG}} + + % Mac + \providecommand{\mac}{\pcalgostyle{MAC}} + + % puncture + \providecommand{\puncture}{\pcalgostyle{Puncture}} + + % Misc + \providecommand{\source}{\pcalgostyle{S}} + \providecommand{\predictor}{\pcalgostyle{P}} + \providecommand{\sam}{\pcalgostyle{Sam}} + \providecommand{\dist}{\pcalgostyle{D}} + \providecommand{\distinguisher}{\pcalgostyle{Dist}} + \providecommand{\simulator}{\pcalgostyle{Sim}} + \providecommand{\ext}{\pcalgostyle{Ext}} +\fi + +%% +% math hyphen +\mathchardef\pcmathhyphen ="2D + +%%% +% order of growth helper +\ifpc@orderofgrowth + \providecommand{\olrk}[1]{% + \ifx\nursymbol#1\else\!\!\mskip4.5mu plus 0.5mu\left(#1\right)\fi} + \providecommand{\elrk}[1]{% + \ifx\nursymbol#1\else% + \!\!\mskip4.5mu plus0.5mu\left[\mskip2.5mu plus0.5mu #1\right]\fi} + \providecommand{\clrk}[1]{% + \ifx\nursymbol#1\else% + \!\!\mskip4.5mu plus0.5mu\left\{\mskip2.5mu plus0.5mu #1\right\}\fi} +\fi + +\ifpc@algorithmstyle + \providecommand{\pcalgostyle}[1]{\ensuremath{\mathsf{#1}}} +\fi + +%%% +% create command to measure width of align +% +\newcommand{\@settowidthofalign}[2]{% + \setbox\z@=\vbox{ + \begin{flalign*} + #2 + \ifmeasuring@\else\global\let\got@maxcolwd\maxcolumn@widths\fi + \end{flalign*} + }% + \begingroup + \def\or{+}\edef\x{\endgroup#1=\dimexpr\got@maxcolwd\relax}\x} + +\newcommand{\@settowidthofaligned}[2]{% + \settowidth{#1}{$\begin{aligned}#2\end{aligned}$} +} + + +% run stuff in an empty box +\newcommand{\@pcexecuteblindly}[1]{% + \setbox\z@=\vbox{#1 }} + +% copy label command +\AtBeginDocument{ + \let\pc@original@label\ltx@label +} + + +%%%%%% +\newcommand*{\@pc@globaladdtolength}[2]{% +\addtolength{#1}{#2}% +\global#1=#1\relax} + +\newcommand*{\@pc@globalsetlength}[2]{% +\setlength{#1}{#2}% +\global#1=#1\relax} + + + +% The size to be used by the pseudocode procedure +\providecommand{\pcsize}{\small} +% The size to be used by the pseudocode procedure when writing subprocedures +\providecommand{\pcsubsize}{\footnotesize} + +%%%%% +% spaces before and after pseudo codes (left and right) +\providecommand{\beforepcskip}{2pt} +\providecommand{\afterpcskip}{0pt} + +%%% +% a global counter of the number of times the pseudocode command was triggered +\newcounter{@pc@global@pc@cnt} +\newcounter{@pc@global@pc@nestcnt} + +%%% +% Fix hyperref package.. gnarl http://tex.stackexchange.com/questions/130319/incompatibility-between-etoolbox-and-hyperref +\providecommand{\pcfixhyperref}{ +\global\let\textlabel\label +\global\let\pc@original@label\textlabel +%\global\let\pc@original@label\relax +%\global\let\label\relax +} + +%%%%%%%% +% line numbers +%%%%%%%% +% The following commands handle line numbering within the pseudocode command. The +% pseudocode command itself does need to do some counter magic +\newcounter{pclinenumber} +\newcounter{Hpclinenumber} % make hyperref happy +\newcounter{@pclinenumbertmp} +\newcounter{pcgamecounter} +\newcounter{Hpcgamecounter} +\newcounter{pcrlinenumber} +\newcounter{Hpcrlinenumber} +\newcounter{@pcrlinenumbertmp} + +% separators +\providecommand{\pclnseparator}{:} +\providecommand{\pcrlnseparator}{\hspace{1pt}} + +% spacing for linenumbers +\providecommand{\pclnspace}{0pt} +\providecommand{\pclnrspace}{5pt} + +% left align line numbers +\providecommand{\pcln}[1][]{% +\refstepcounter{pclinenumber}% +\stepcounter{Hpclinenumber}% +\ifthenelse{\equal{#1}{}}{}{% +%keep hyperref happy +\ifmeasuring@\else\pc@original@label{#1}\fi% +}% +\hspace{\pclnspace}\text{\scriptsize\arabic{pclinenumber}}\pclnseparator\quad}% + + +% right align line numbers (same counter) +\providecommand{\pclnr}{% +\refstepcounter{pclinenumber}% +\quad\text{\scriptsize\pcrlnseparator\arabic{pclinenumber}}\hspace{5pt}} + +% right align line numbers different counter +\providecommand{\pcrln}{ +\refstepcounter{pcrlinenumber}% +\stepcounter{Hpcrlinenumber}% +\text{\scriptsize\pcrlnseparator\arabic{pcrlinenumber}}\hspace{\pclnrspace}} + + +%%% +% indentation +\newlength{\@pcindentwidth} +\providecommand{\pcind}[1][1]{% +\setlength{\@pcindentwidth}{\widthof{\ensuremath{\quad}}*#1}% +\ensuremath{\mathmakebox[\@pcindentwidth]{}}} + + +% create length +\newlength{\@pc@minipage@length} +\newlength{\@pc@alt@minipage@length} + +% backward games +\newif\ifbxgame +\newcommand{\@bxgameheader}{} + + +%%%%%%%%%%%% +% The pseudocode Command +%%%%% +\newlength{\@pc@length@tmp@width@vstack} + + +\newcommand{\@pc@beginnewline}{\@pc@and\@pseudocodelinenumber\@pc@modebegin} +\newcommand{\@pc@and}{&} +\newcommand{\@pc@and@wrap@end}{\@pc@modeend&} +\newcommand{\@pc@and@wrap@start}{\@pc@beginnewline} +\newcommand{\pctabname}{>} +\newcommand{\pcdbltabname}{<} +\newcommand{\pcindentname}{t} + + + +\newcommand*\@pseudocodehead{} +\newcommand*\@pseudocodewidth{} +\newcommand*\@pseudocodexshift{0pt} +\newcommand*\@pseudocodelinenumber{} +\newcommand*\@pseudocodebeforeskip{0ex} +\newcommand*\@pseudocodeafterskip{0ex} +\newcommand*\@pseudocodelnstart{0} +\newcommand*\@pseudocodelnstartright{0} +\newcommand*\@pseudocodesyntaxhighlighting{} +\newcommand*\@pseudocodekeywords{for ,foreach ,return ,{ do }, in ,new ,if ,null ,null,true ,true,until ,{ to },false ,false,{ then },repeat ,else ,done ,done,fi } +\newcommand*\@pseudocodeaddkeywords{} +\define@key{pseudocode}{head}[]{\renewcommand*\@pseudocodehead{#1}} +\define@key{pseudocode}{width}[]{\renewcommand*\@pseudocodewidth{#1}} +\define@key{pseudocode}{xshift}[]{\renewcommand*\@pseudocodexshift{#1}} +\define@key{pseudocode}{linenumbering}[on]{\ifthenelse{\equal{#1}{on}}{\renewcommand*\@pseudocodelinenumber{\pcln}}{\renewcommand*\@pseudocodelinenumber{}}} +\define@key{pseudocode}{beforeskip}[]{\renewcommand*\@pseudocodebeforeskip{#1}} +\define@key{pseudocode}{afterskip}[]{\renewcommand*\@pseudocodeafterskip{#1}} +\define@key{pseudocode}{lnstart}[0]{\renewcommand*\@pseudocodelnstart{#1}} +\define@key{pseudocode}{lnstartright}[0]{\renewcommand*\@pseudocodelnstartright{#1}} +\define@key{pseudocode}{mode}[math]{% +\ifthenelse{\equal{#1}{text}}{% +\renewcommand*\@pc@modebegin{\begin{varwidth}{\textwidth}% +%introduce line magic for text mode +\let\@pc@lb\\% +\renewcommandx*{\\}[2][1=,2=]{\@pc@modeend\@pc@and \ifthenelse{\equal{####1}{}}{\@pc@lb}{\@pc@lb[####1]}####2 \@pc@beginnewline}% +\def\pclb{\let\\\@pc@lb\relax\@pc@modeend\\}% +}% +\renewcommand*\@pc@modeend{\end{varwidth}} +}{}% +} +\define@key{pseudocode}{keywords}[]{\renewcommand*\@pseudocodekeywords{#1}} +\define@key{pseudocode}{addkeywords}[]{\renewcommand*\@pseudocodeaddkeywords{#1}} +\define@key{pseudocode}{syntaxhighlight}[]{\renewcommand*\@pseudocodesyntaxhighlighting{#1}} + +\newcommand{\@pc@modebegin}{} +\newcommand{\@pc@modeend}{} +\newcommand{\@pc@thecontent}{} + +\newcommand{\@pc@syntaxhighlight}[1]{% +\ifthenelse{\equal{\@pseudocodesyntaxhighlighting}{auto}}{% +\saveexploremode\expandarg % suppress expansions made by xstring +\def\@shtmp{#1}% first step +\edef\@tmpkeywords{\@pseudocodekeywords,\@pseudocodeaddkeywords}% +\foreach \@pckw in \@tmpkeywords{% +\ifthenelse{\equal{\@pckw}{}}{}{% +\StrSubstitute{\@pckw}{ }{PCXXMYBREAKSPACE}[\@pckwspace]% take care of spaces +\StrSubstitute{\@shtmp}{\@pckw}{\expandafter\@pc@highlight\expandafter{\@pckwspace}}[\@shtmpA]% +\global\let\@shtmp\@shtmpA% +}}% +\restoreexploremode\@shtmp% +}{#1}% +} + +\newcommand{\@pc@highlight}[1]{% +\StrSubstitute{#1}{PCXXMYBREAKSPACE}{}[\@pctmpname]% +\StrSubstitute{#1}{PCXXMYBREAKSPACE}{ }[\@pctmporg]% +\StrSubstitute{#1}{PCXXMYBREAKSPACE}{~}[\@pctmpres]% +\ifcsname dohighlight\@pctmpname\endcsname% +\csname dohighlight\@pctmpname\endcsname{\@pctmporg}% +\else\pseudocodeconstant[]{\@pctmpres}\fi% +} + +% store original halign +\let\@pc@halign\halign% + + +\providecommand{\pseudocode}[2][]{% +\begingroup% +\setkeys{pseudocode}{#1}% +\addtocounter{@pc@global@pc@nestcnt}{1}% +% allow for tikz usage +\@pc@ensureremember% +% +% create tabbing command +\ifcsname \pctabname\endcsname% +\expandafter\renewcommand\csname \pctabname\endcsname{\@pc@modeend&\@pc@modebegin}% +\else% +\expandafter\newcommand\csname \pctabname\endcsname{\@pc@modeend&\@pc@modebegin}% +\fi% +\ifcsname \pcdbltabname\endcsname% +\expandafter\renewcommand\csname \pcdbltabname\endcsname{\@pc@modeend&&\@pc@modebegin}% +\else% +\expandafter\newcommand\csname \pcdbltabname\endcsname{\@pc@modeend&&\@pc@modebegin}% +\fi% +% create indent command +\expandafter\let\csname \pcindentname\endcsname\pcind% +% wrap content if necessary +\renewcommand{\@pc@thecontent}{\@pc@and@wrap@start\@pc@syntaxhighlight{#2}\@pc@and@wrap@end}% +% +%take care of counters +\stepcounter{@pc@global@pc@cnt}% +\setcounter{pclinenumber}{\@pseudocodelnstart}% +\setcounter{pcrlinenumber}{\@pseudocodelnstartright}% +\setlength{\@pc@minipage@length}{0pt}% +\setlength{\@pc@alt@minipage@length}{0pt}% +\setcounter{@pclinenumbertmp}{\value{pclinenumber}}% +\setcounter{@pcrlinenumbertmp}{\value{pcrlinenumber}}% +% +% +% line magic +\ifthenelse{\value{@pc@global@pc@nestcnt}=1}{% +\let\@pc@halign\halign% +\def\halign{% +\renewcommand{\label}[1]{\ifmeasuring@\else\pc@original@label{####1}\fi}% +\let\@pc@lb\\% +\renewcommandx*{\\}[2][1=,2=]{\@pc@modeend\@pc@and \ifthenelse{\equal{####1}{}}{\@pc@lb}{\@pc@lb[####1]}####2 \@pc@beginnewline}% +\def\pclb{\let\\\@pc@lb\relax\@pc@modeend\\}% +\@pc@halign}% +}{}% +% +%align column separation +\renewcommand*{\minalignsep}{0em}% +% +% if no width is set compute width and store in circuitlength +\ifthenelse{\equal{\@pseudocodewidth}{}}{% +% compute length of pseudocode +\ifthenelse{\value{@pcsubprogstep}=0}{% +\@settowidthofalign{\@pc@minipage@length}{\@pc@thecontent}% +}{% +\@settowidthofaligned{\@pc@minipage@length}{\@pc@thecontent}% +}% +%compute length of header +\addtolength{\@pc@alt@minipage@length}{\widthof{\@pseudocodehead}}% +% use header length if longer and add some points for good measure +\ifdim\@pc@alt@minipage@length>\@pc@minipage@length% +\setlength{\@pc@minipage@length}{\@pc@alt@minipage@length}% +\fi% +\addtolength{\@pc@minipage@length}{5pt}% +}{\addtolength{\@pc@minipage@length}{\@pseudocodewidth}}% +% reset counter +\setcounter{pclinenumber}{\value{@pclinenumbertmp}}% +\setcounter{pcrlinenumber}{\value{@pcrlinenumbertmp}}% +% begin actual output +% +% +%do the actual mini page +\hspace{\@pseudocodexshift}% +\begin{minipage}[t]{\@pc@minipage@length}% +\ifthenelse{\value{@pcsubprogstep}=0}{% +\pc@display@pseudocode{\@pseudocodehead}{\@pc@thecontent}% +}{% if sub procedure +\pc@display@subcode{\@pseudocodehead}{\@pc@thecontent}% +}% +\end{minipage}% +\hspace{\afterpcskip}% +% tikz usage +\@pc@releaseremember% +\addtocounter{@pc@global@pc@nestcnt}{-1}% +\endgroup% +} + + +\let\pclb\relax +% +\newcommand{\pc@display@pseudocode}[2]{% +\ifthenelse{\equal{#1}{}}{\vspace{-0.8\baselineskip}\pcsize}{% +\tikz{\gdef\i{\thepcgamecounter}% +\node[anchor=base] (gamenode\i) {\hspace{-2pt}#1\vphantom{$\sum^A_{A_b}$}}; +\ifbxgame\node[draw,anchor=base, above=0.1cm of gamenode\i] (bgamenode\i) {\@bxgameheader\vphantom{$\sum^A_{A_b}$}};\fi % +}\vspace{-0.1\baselineskip}\hrule\small\vspace{-0.5\baselineskip}}% +\begin{flalign*} #2 \end{flalign*} +} + + +\newcommand{\pc@display@subcode}[2]{% +\begingroup% +\ifthenelse{\equal{#1}{}}{}{#1\vphantom{$\sum^A_{A_b}$}\hrule \vspace{0.2\baselineskip}}% +\pcsubsize% +$\begin{aligned} #2 \end{aligned}$% +\endgroup% +} + + +\newcommand{\@pc@gettikzwidth}[2]{ % #1 = width, #2 = height + \pgfextractx{\@tempdima}{\pgfpointdiff{\pgfpointanchor{current bounding box}{south west}} + {\pgfpointanchor{current bounding box}{north east}}} + \global#1=\@tempdima + \pgfextracty{\@tempdima}{\pgfpointdiff{\pgfpointanchor{current bounding box}{south west}} + {\pgfpointanchor{current bounding box}{north east}}} + \global#2=\@tempdima +} + + +%%%%%%%%%%%%%%%%%%% +% remember pictues +\newcounter{@pc@remember} + +\newcommand{\@pc@ensureremember}{% +\ifthenelse{\value{@pc@remember}=0}{\tikzstyle{every picture}+=[remember picture]}{}% +\addtocounter{@pc@remember}{1} +} + +\newcommand{\@pc@releaseremember}{% +\addtocounter{@pc@remember}{-1}% +\ifthenelse{\value{@pc@remember}=0}{\tikzstyle{every picture}-=[remember picture]}{}% +} + + +%%%%%%%%%%%%%%%%%%% +% pcimage +\newenvironment{pcimage}{% +\begingroup\@pc@ensureremember% +}{% +\@pc@releaseremember\endgroup% +} + +\newcommand*\@pcnodecontent{} +\newcommand*\@pcnodestyle{} +\newcommand*\@pcnodedraw{} +\define@key{pcnode}{content}[]{\renewcommand*\@pcnodecontent{#1}} +\define@key{pcnode}{style}[]{\renewcommand*\@pcnodestyle{#1}} +\define@key{pcnode}{draw}[]{\renewcommand*\@pcnodedraw{#1}} + +\newcommandx*{\pcnode}[2][2=]{% +\begingroup\setkeys{pcnode}{#2}% +\tikzset{PCNODE-STYLE/.style/.expand once=\@pcnodestyle}% +\begin{tikzpicture}[inner sep=0ex,baseline=0pt]% +\node[PCNODE-STYLE] (#1) {\@pcnodecontent}; % +\end{tikzpicture}% +\ifdefempty{\@pcnodedraw}{}{% +\begin{tikzpicture}[overlay,inner sep=0ex,baseline=0pt]\@pcnodedraw\end{tikzpicture} +}% +\endgroup} + +\newcommandx*{\pcdraw}[1]{% +\begin{tikzpicture}[overlay,inner sep=0ex,baseline=0pt] +#1 +\end{tikzpicture}} + + +%%%%%%%%%%%%%%%%%%%%%%%%% +% Reductions +\newcommand{\@bb@lastbox}{} +\newcommand{\@bb@lastoracle}{} + +\newlength{\@bb@message@hoffset} +\newlength{\@bb@query@hoffset} +\newlength{\@bb@oraclequery@hoffset} + +\newcounter{@bb@oracle@cnt} +\newcounter{@bb@oracle@nestcnt} +\newcounter{@bb@env@nestcnt} + +\newcommand{\bbroraclenodenameprefix}{ora-} +\newcommand{\bbrenvnodenameprefix}{env-} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Black Box Reduction Enviconment +\newenvironmentx{bbrenv}[3][1=0pt,3=0pt]{ +\addtocounter{@bb@env@nestcnt}{1} +\renewcommand{\@bb@lastbox}{#2} + +% reset lengths +\setlength{\@bb@message@hoffset}{0pt} +\setlength{\@bb@query@hoffset}{0pt} +\@pc@globalsetlength{\@bb@oraclequery@hoffset}{0pt} + +%reset oracle counter and oracle query offset +\ifthenelse{\value{@bb@oracle@nestcnt}=0}{ + \setcounter{@bb@oracle@cnt}{0} +}{ +} + +\def\@bbendskip{#3} +\vspace{#1} +\ifthenelse{\value{@bb@env@nestcnt}=1}{ +\@pc@ensureremember +\begin{tikzpicture} +}{\tikz\bgroup} +}{ +\ifthenelse{\value{@bb@env@nestcnt}=1}{ +\end{tikzpicture} +\@pc@releaseremember +}{\egroup} +\vspace{\@bbendskip} +\addtocounter{@bb@env@nestcnt}{-1} +} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% black box reduction box +% option keys +\newcommand*\bbrboxname{} +\newcommand*\bbrboxstyle{draw} +\newcommand*\bbrboxafterskip{} +\newcommand*\bbrboxxshift{-2cm} +\define@key{bbrbox}{name}[]{\renewcommand*\bbrboxname{#1}} +\define@key{bbrbox}{style}[draw]{\renewcommand*\bbrboxstyle{#1}} +\define@key{bbrbox}{minheight}[]{\renewcommand*\bbrboxafterskip{#1}} +\define@key{bbrbox}{xshift}[]{\renewcommand*\bbrboxxshift{#1}} + + +\NewEnviron{bbrbox}[1][]{% +\setkeys{bbrbox}{#1}% + +\tikzset{BBRBOXSTYLE/.style/.expand once=\bbrboxstyle}% +\node[inner sep=0pt,outer sep=0pt] (bbrshift) {}; +\node[BBRBOXSTYLE,xshift=\bbrboxxshift] (\@bb@lastbox) at (bbrshift) \bgroup + \tikz{ + \node (inner) {\begin{varwidth}{\linewidth}\BODY\end{varwidth}}; + \node[right=0.05cm of inner.north east] (tmpne) {}; + \node[above left=0.cm and 0pt of tmpne.north] (name) {\bbrboxname}; + \ifthenelse{\equal{\bbrboxafterskip}{}}{}{ + \node[below=0cm of inner,minimum height=\bbrboxafterskip] {}; + } + } +\egroup; +} + + +\newcommand*\bbroracledistance{1cm} +\define@key{bbroracle}{distance}[]{\renewcommand*\bbroracledistance{#1}} + +% ORACLES +\newenvironmentx{bbroracle}[2][2=]{% + \begingroup + \setkeys{bbroracle}{#2} + %add to nesting cout + \addtocounter{@bb@oracle@nestcnt}{1} + %if first oracle, then put it to the right, else stack them vertically + \addtocounter{@bb@oracle@cnt}{1} + \ifthenelse{\value{@bb@oracle@cnt}=1}{ + \node[below right=0cm and \bbroracledistance of \@bb@lastbox.north east] (\bbroraclenodenameprefix#1) \bgroup + }{ + \node[below=0.05cm of \bbroraclenodenameprefix \@bb@lastoracle.south west, anchor=north west] (\bbroraclenodenameprefix#1) \bgroup + } + \global\def\@bb@lastoracle{#1} + \begin{bbrenv}{#1} +}{ + \end{bbrenv} + \egroup; + + \addtocounter{@bb@oracle@nestcnt}{-1} + \endgroup +} + +\newcommandx{\bbrinput}[2][1=0.75cm]{% +\node[above right=#1 of \@bb@lastbox.north west] (input) {#2}; +\draw[->] (input) --++ (0,-0.75cm); +} + +\newcommandx{\bbroutput}[2][1=0.75cm]{% +\node[below right=#1 of \@bb@lastbox.south west] (output) {#2}; +\draw[<-] (output) --++ (0,#1); +} + +%%%%%%%%%%% +% communication +%temporary lengths +\newlength{\@bb@com@tmpoffset} +\newlength{\@bb@tmplength@b} +\newcommand{\@bb@firstmessageheight}{-0.15cm} +\newcommand{\@bb@msglength}{1.25cm} +\newcommand{\@bb@qrylength}{1.5cm} + +%keys +\newcommand*\bbrcomnsidestyle{} +\newcommand*\bbrcomtopstyle{} +\newcommand*\bbrcombottomstyle{} +\newcommand*\bbrcomside{} +\newcommand*\bbrcomtop{} +\newcommand*\bbrcombottom{} +\newcommand*\bbrcomedgestyle{} +\newcommand*\bbrcomlength{1.25cm} +\newcommand*\bbrcomtopname{bbrcomtop} +\newcommand*\bbrcombottomname{bbrcombottom} +\newcommand*\bbrcomsidename{bbrcomside} +\newcommand*\bbrcomosidename{bbrcomoside} +\newcommand*\bbrcombeforeskip{0pt} +\newcommand*\bbrcomafterskip{0pt} +\define@key{bbrcom}{sidestyle}[]{\renewcommand*\bbrcomnsidestyle{#1}} +\define@key{bbrcom}{topstyle}[]{\renewcommand*\bbrcomtopstyle{#1}} +\define@key{bbrcom}{bottomstyle}[]{\renewcommand*\bbrcombottomstyle{#1}} +\define@key{bbrcom}{side}[]{\renewcommand*\bbrcomside{#1}} +\define@key{bbrcom}{top}[]{\renewcommand*\bbrcomtop{#1}} +\define@key{bbrcom}{bottom}[]{\renewcommand*\bbrcombottom{#1}} +\define@key{bbrcom}{edgestyle}[]{\renewcommand*\bbrcomedgestyle{#1}} +\define@key{bbrcom}{length}[]{\renewcommand*\bbrcomlength{#1}} +\define@key{bbrcom}{topname}[]{\renewcommand*\bbrcomtopname{#1}} +\define@key{bbrcom}{bottomname}[]{\renewcommand*\bbrcombottomname{#1}} +\define@key{bbrcom}{sidename}[]{\renewcommand*\bbrcomsidename{#1}} +\define@key{bbrcom}{osidename}[]{\renewcommand*\bbrcomosidename{#1}} +\define@key{bbrcom}{beforeskip}[]{\renewcommand*\bbrcombeforeskip{#1}} +\define@key{bbrcom}{afterskip}[]{\renewcommand*\bbrcomafterskip{#1}} + +\newcommand*\bbrbasenodestyle{} +\newcommand*\bbrbasenodename{bbrtmpname} +\define@key{bbrabase}{nodestyle}[]{\renewcommand*\bbrbasenodestyle{#1}} +\define@key{bbrabase}{nodename}[]{\renewcommand*\bbrbasenodename{#1}} + + +\newcommand{\@bb@comsetup}[3]{ + %load keys + \begingroup % for local keys + + \setkeys{bbrcom}{#1}% + + %set styles + \tikzset{BBRCOM-SIDESTYLE/.style/.expand once=\bbrcomnsidestyle}% + \tikzset{BBRCOM-TOPSTYLE/.style/.expand once=\bbrcomtopstyle}% + \tikzset{BBRCOM-BOTTOMSTYLE/.style/.expand once=\bbrcombottomstyle}% + \tikzset{BBRCOM-EDGESTYLE/.style/.expand once=\bbrcomedgestyle}% + + % increase space + #3\baselineskip + \ifthenelse{\equal{\bbrcomtop}{}}{}{#3\baselineskip} + + \setlength{\@bb@com@tmpoffset}{#2+\@bb@firstmessageheight+\bbrcombeforeskip}% +} + +\newcommand{\@bb@comfinalize}[1]{ + \ifthenelse{\equal{\bbrcombottom}{}}{}{#1{\baselineskip}} + #1{\bbrcomafterskip} + \endgroup +} + +\newcommand{\@bbrmsg}[7]{ + \@bb@comsetup{#1}{#6}{#7} + % + \node[#3=\@bb@com@tmpoffset and \bbrcomlength of \@bb@lastbox.#4,BBRCOM-SIDESTYLE] (\bbrcomsidename) {\bbrcomside}; + \path[#2] (\bbrcomsidename) edge[BBRCOM-EDGESTYLE] node[above,BBRCOM-TOPSTYLE] (\bbrcomtopname) {\bbrcomtop} node[below,BBRCOM-BOTTOMSTYLE] (\bbrcombottomname) {\bbrcombottom} (\@bb@lastbox.#5|-\bbrcomsidename) node[inner sep=0pt,outer sep=0pt] (\bbrcomosidename) {}; + % + \@bb@comfinalize{#7} +} + +\newcommandx{\bbrmsgto}[1]{% +\@bbrmsg{#1}{->}{below left}{north west}{west}{\@bb@message@hoffset}{\bbrmsgspace} +} +\newcommandx{\bbrmsgfrom}[1]{% +\@bbrmsg{#1}{<-}{below left}{north west}{west}{\@bb@message@hoffset}{\bbrmsgspace} +} +\newcommandx{\bbrqryto}[1]{% +\@bbrmsg{#1}{<-}{below right}{north east}{east}{\@bb@query@hoffset}{\bbrqryspace} +} +\newcommandx{\bbrqryfrom}[1]{% +\@bbrmsg{#1}{->}{below right}{north east}{east}{\@bb@query@hoffset}{\bbrqryspace} +} + +\newcommand{\@bbroracleqry}[4]{ + \@bb@comsetup{#1}{#3}{#4} + % + + \path[#2] (\@bb@lastoracle.north west) -- ++ (0,-\@bb@com@tmpoffset) node[inner sep=0pt,outer sep=0pt] (\bbrcomsidename){} edge[BBRCOM-EDGESTYLE] node[above,BBRCOM-TOPSTYLE] (\bbrcomtopname) {\bbrcomtop} node[below,BBRCOM-BOTTOMSTYLE] (\bbrcombottomname) {\bbrcombottom} (\@bb@lastbox.east|-\bbrcomsidename) node[inner sep=0pt,outer sep=0pt] (\bbrcomosidename) {}; + % + \@bb@comfinalize{#4} +} + +\newcommand{\bbroraclequeryfrom}[1]{ + \@bbroracleqry{#1}{->}{\@bb@oraclequery@hoffset}{\bbroracleqryspace} +} + +\newcommand{\bbroraclequeryto}[1]{ + \@bbroracleqry{#1}{<-}{\@bb@oraclequery@hoffset}{\bbroracleqryspace} +} + + +\newcommand*\bbrcomloopleft{} +\newcommand*\bbrcomloopright{} +\newcommand*\bbrcomloopcenter{} +\define@key{bbrcomloop}{left}[]{\renewcommand*\bbrcomloopleft{#1}} +\define@key{bbrcomloop}{right}[]{\renewcommand*\bbrcomloopright{#1}} +\define@key{bbrcomloop}{center}[]{\renewcommand*\bbrcomloopcenter{#1}} + +\newcommand{\bbrloop}[3]{ + \begingroup % for local keys + \setkeys{bbrcomloop}{#3}% + + \path[->] (#1) edge[bend right=50] node[left] (bbrleft) {\bbrcomloopleft} (#2); + \path[->] (#2) edge[bend right=50] node[right] (bbrright) {\bbrcomloopright} (#1); + \node () at ($(bbrleft)!0.5!(bbrright)$) {\bbrcomloopcenter}; + + \endgroup +} + +\newcommand*\bbrintertexthoffset{1.5cm} +\define@key{bbrintertext}{xshift}[]{\renewcommand*\bbrintertexthoffset{#1}} + +\newcommand{\@bb@intertextsetup}[1]{ + %load keys + \begingroup % for local keys + + \setkeys{bbrcom,bbrabase,bbrintertext}{#1}% + + \tikzset{BBRBASE-NODESTYLE/.style/.expand once=\bbrbasenodestyle}% +} + +\newcommand{\@bb@intertextfinalize}[1]{ + #1{\bbrcomafterskip} + \endgroup +} + +\newcommand{\@bbrintertext}[6]{ + \@bb@intertextsetup{#1} + + %introduce space + #5{\baselineskip} + + %compute offset + \setlength{\@bb@com@tmpoffset}{#4+\@bb@firstmessageheight+\bbrcombeforeskip}% + + % + \node[#2=\@bb@com@tmpoffset and \bbrintertexthoffset of \@bb@lastbox.#3,BBRBASE-NODESTYLE] (\bbrbasenodename) {#6}; + % + % compute height of node + \coordinate (@bbtmpcoord) at (\bbrbasenodename.north); + \path (@bbtmpcoord); + \pgfgetlastxy{\XCoord}{\YCoordA} + \coordinate (@bbtmpcoord) at (\bbrbasenodename.south); + \path (@bbtmpcoord); + \pgfgetlastxy{\XCoord}{\YCoordB} + + % update hoffset + \setlength{\@bb@tmplength@b}{\YCoordA-\YCoordB} + #5{\the\@bb@tmplength@b} + + \@bb@intertextfinalize{#5} +} + +\newcommand{\bbrmsgtxt}[2][]{ + \@bbrintertext{#1}{below left}{north west}{\@bb@message@hoffset}{\bbrmsgspace}{#2} +} + +\newcommand{\bbrqrytxt}[2][]{ + \@bbrintertext{#1}{below right}{north east}{\@bb@query@hoffset}{\bbrqryspace}{#2} +} + +\newcommand{\bbrmsgspace}[1]{ +\@pc@globaladdtolength{\@bb@message@hoffset}{#1} +} + +\newcommand{\bbrqryspace}[1]{ +\@pc@globaladdtolength{\@bb@query@hoffset}{#1} +} + +\newcommand{\bbroracleqryspace}[1]{ +\@pc@globaladdtolength{\@bb@oraclequery@hoffset}{#1} +} + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% stacking +\providecommand{\pccenteraboveskip}{0.5\baselineskip} +\providecommand{\pccenterbelowskip}{0.5\baselineskip} +\newenvironment{pccenter}{% +\setlength\topsep{0pt}\setlength\parskip{0pt}% +\begin{center}\vspace{\pccenteraboveskip} +}{% +\vspace{\pccenteraboveskip}% +\end{center}} + + +%%%%%%%%%%%%%%%%%%%%% +% horizontal stacking +% space before hstacks +\newlength{\pcbeforehstackskip} + +\NewEnviron{pchstack}[1][]{% +% write out content +\ifthenelse{\equal{#1}{center}}{% +\begin{pccenter}\mbox{\hspace{\pcbeforehstackskip}\BODY}\end{pccenter}}{% +\mbox{\hspace{\pcbeforehstackskip}\BODY}}% +} + + +%%%%%%%%%%%%%%%%%%%%%%% +\NewEnviron{pcvstack}[1][]{% +% display minipage +\ifthenelse{\equal{#1}{center}}{\begin{pccenter}}{} +\begin{varwidth}[t]{15cm}\BODY\end{varwidth} +\ifthenelse{\equal{#1}{center}}{\end{pccenter}}{} +} + + +% spacing for stacking +\newcommand{\pchspace}[1][1em]{\hspace{#1}} +\newcommand{\pcvspace}[1][\baselineskip]{\par\vspace{#1}} + + + + + +%%%% +% subprocedures +\newcounter{@pcsubprogcnt1} +\newcounter{@pcrsubprogcnt1} +\newcounter{@pcsubprogcnt2} +\newcounter{@pcrsubprogcnt2} +\newcounter{@pcsubprogcnt3} +\newcounter{@pcrsubprogcnt3} +\newcounter{@pcsubprogcnt4} +\newcounter{@pcrsubprogcnt4} +\newcounter{@pcsubprogcnt5} +\newcounter{@pcrsubprogcnt5} +\newcounter{@pcsubprogcnt6} +\newcounter{@pcrsubprogcnt6} +\newcounter{@pcsubprogcnt7} +\newcounter{@pcrsubprogcnt7} +\newcounter{@pcsubprogcnt8} +\newcounter{@pcrsubprogcnt8} +\newcounter{@pcsubprogcnt9} +\newcounter{@pcrsubprogcnt9} +\newcounter{@pcsubprogstep} + +\newenvironment{subprocedure}{% +\addtocounter{@pcsubprogstep}{1}% +% store old counter values +\setcounter{@pcsubprogcnt\the@pcsubprogstep}{\value{pclinenumber}}% +\setcounter{@pcrsubprogcnt\the@pcsubprogstep}{\value{pcrlinenumber}}% +}{% +\setcounter{pclinenumber}{\value{@pcsubprogcnt\the@pcsubprogstep}}% +\setcounter{pcrlinenumber}{\value{@pcrsubprogcnt\the@pcsubprogstep}}% +\addtocounter{@pcsubprogstep}{-1}} + + + +%%% some basic procedure commands +\newcommand{\pcmainname}{\textsc{Main }} +\newcommand{\pcalgorithmname}{\textsc{Algo. }} +\newcommand{\pccircuitname}{\textsc{Circ. }} +\newcommand{\pcprogramname}{\textsc{Prog. }} +\newcommand{\pcprotocolname}{\textsc{Protocol }} + +\providecommand{\procedure}[3][]{\pseudocode[head={#2},#1]{#3}} +\providecommand{\mainprocedure}[3][]{\pseudocode[head={\pcmainname#2},#1]{#3}} +\providecommand{\algorithm}[3][]{\pseudocode[head={\pcalgorithmname#2},#1]{#3}} +\providecommand{\circuit}[3][]{\pseudocode[head={\pccircuitname#2},#1]{#3}} +\providecommand{\program}[3][]{\pseudocode[head={\pcprogramname#2},#1]{#3}} +\providecommand{\protocol}[3][]{\pseudocode[head={\pcprotocolname#2},#1]{#3}} + + +%%% +% send message +\newcommand{\pcshortmessageoffset}{0.5cm} +\newcommand{\pcdefaultmessagelength}{3.5cm} +\newcommand{\pcdefaultlongmessagelength}{6cm} +\newcommand{\pcbeforemessageskip}{0pt} +\newcommand{\pcaftermessageskip}{10pt} +\newlength{\pcmessagearrow} + +\newcommand*\@pcsendmessagelength{\pcdefaultmessagelength} +\newcommand*\@pcsendmessagecol{} +\newcommand*\@pcsendmessagewidth{} +\newcommand*\@pcsendmessagestyle{} +\newcommand*\@pcsendmessagetop{} +\newcommand*\@pcsendmessagebottom{} +\newcommand*\@pcsendmessageright{} +\newcommand*\@pcsendmessageleft{} +\newcommand*\@pcsendmessagetopname{t} +\newcommand*\@pcsendmessagebottomname{b} +\newcommand*\@pcsendmessagerightname{r} +\newcommand*\@pcsendmessageleftname{l} +\newcommand*\@pcsendmessagetopstyle{} +\newcommand*\@pcsendmessagebottomstyle{} +\newcommand*\@pcsendmessagerightstyle{} +\newcommand*\@pcsendmessageleftstyle{} +\newcommand*\@pcsendmessagebeforeskip{\pcbeforemessageskip} +\newcommand*\@pcsendmessageafterskip{\pcaftermessageskip} +\define@key{pcsendmessage}{centercol}[]{\renewcommand*\@pcsendmessagecol{#1}} +\define@key{pcsendmessage}{width}[]{\renewcommand*\@pcsendmessagewidth{#1}} +\define@key{pcsendmessage}{style}[]{\renewcommand*\@pcsendmessagestyle{#1}} +\define@key{pcsendmessage}{length}[]{\renewcommand*\@pcsendmessagelength{#1}} +\define@key{pcsendmessage}{top}[]{\renewcommand*\@pcsendmessagetop{#1}} +\define@key{pcsendmessage}{bottom}[]{\renewcommand*\@pcsendmessagebottom{#1}} +\define@key{pcsendmessage}{right}[]{\renewcommand*\@pcsendmessageright{#1}} +\define@key{pcsendmessage}{left}[]{\renewcommand*\@pcsendmessageleft{#1}} +\define@key{pcsendmessage}{topname}[]{\renewcommand*\@pcsendmessagetopname{#1}} +\define@key{pcsendmessage}{bottomname}[]{\renewcommand*\@pcsendmessagebottomname{#1}} +\define@key{pcsendmessage}{rightname}[]{\renewcommand*\@pcsendmessagerightname{#1}} +\define@key{pcsendmessage}{leftname}[]{\renewcommand*\@pcsendmessageleftname{#1}} +\define@key{pcsendmessage}{topstyle}[]{\renewcommand*\@pcsendmessagetopstyle{#1}} +\define@key{pcsendmessage}{bottomstyle}[]{\renewcommand*\@pcsendmessagebottomstyle{#1}} +\define@key{pcsendmessage}{rightstyle}[]{\renewcommand*\@pcsendmessagerightstyle{#1}} +\define@key{pcsendmessage}{leftstyle}[]{\renewcommand*\@pcsendmessageleftstyle{#1}} +\define@key{pcsendmessage}{beforeskip}[]{\renewcommand*\@pcsendmessagebeforeskip{#1}} +\define@key{pcsendmessage}{afterskip}[]{\renewcommand*\@pcsendmessageafterskip{#1}} + + +\newcommand{\centerincol}[2]{% +\ifmeasuring@% +#2% +\else% +\makebox[\ifcase\expandafter #1\maxcolumn@widths\fi]{$\displaystyle#2$}% +\fi% +} + +\newcommand{\@do@sendmessage}[1]{% +\ifthenelse{\equal{\@pcsendmessagecol}{}}{% +\ifthenelse{\equal{\@pcsendmessagewidth}{}}{#1}{% we have some width +\makebox[\@pcsendmessagewidth]{$\displaystyle#1$}% +}}{%we know the column to center on +\centerincol{\@pcsendmessagecol}{#1}% +}% +} + +\newcommandx*{\sendmessage}[2]{% +\begingroup\setkeys{pcsendmessage}{#2}% +\tikzset{PCSENDMSG-PATH-STYLE/.style/.expand once=\@pcsendmessagestyle}% +\tikzset{PCSENDMSG-TOP-STYLE/.style/.expand once=\@pcsendmessagetopstyle}% +\tikzset{PCSENDMSG-BOTTOM-STYLE/.style/.expand once=\@pcsendmessagebottomstyle}% +\tikzset{PCSENDMSG-LEFT-STYLE/.style/.expand once=\@pcsendmessageleftstyle}% +\tikzset{PCSENDMSG-RIGHT-STYLE/.style/.expand once=\@pcsendmessagerightstyle}% +%restore halign +% +\hspace{\@pcsendmessagebeforeskip}% +\begin{varwidth}{\linewidth} +\@do@sendmessage{ + \begin{tikzpicture}% + \node[PCSENDMSG-LEFT-STYLE] (\@pcsendmessageleftname) {\@pcsendmessageleft}; + \node[right=\@pcsendmessagelength of \@pcsendmessageleftname,PCSENDMSG-RIGHT-STYLE] (\@pcsendmessagerightname) {\@pcsendmessageright}; + \path[#1,PCSENDMSG-PATH-STYLE] (\@pcsendmessageleftname) edge[] node[above,PCSENDMSG-TOP-STYLE] (\@pcsendmessagetopname) {\@pcsendmessagetop} node[below,PCSENDMSG-BOTTOM-STYLE] (\@pcsendmessagebottomname) {\@pcsendmessagebottom} (\@pcsendmessagerightname); + \end{tikzpicture}% +}% +\end{varwidth} +\hspace{\@pcsendmessageafterskip}% +\endgroup% +} + +\newcommandx*{\sendmessageright}[2][1=->]{% +\sendmessage{#1}{#2}% +} + +\newcommandx*{\sendmessageleft}[2][1=<-]{% +\sendmessage{#1}{#2}% +} + +\WithSuffix\newcommand\sendmessageleft*[2][\pcdefaultmessagelength]{% +\begingroup% +\renewcommand{\@pcsendmessagetop}{\let\halign\@pc@halign$\begin{aligned}#2\end{aligned}$}% +\sendmessage{<-}{length=#1}% +\endgroup% +} + + +\WithSuffix\newcommand\sendmessageright*[2][\pcdefaultmessagelength]{% +\begingroup% +\renewcommand{\@pcsendmessagetop}{\let\halign\@pc@halign$\begin{aligned}#2\end{aligned}$}% +\sendmessage{->}{length=#1}% +\endgroup% +} + + + +\DeclareExpandableDocumentCommand{\sendmessagerightx}{O{\pcdefaultlongmessagelength}mO{}m}{% +\multicolumn{#2}{c}{\ensuremath{\hspace{\pcbeforemessageskip}\xrightarrow[\begin{aligned}#3\end{aligned}]{\mathmakebox[#1]{\begin{aligned}#4\end{aligned}}}\hspace{\pcaftermessageskip}}} +} + +\DeclareExpandableDocumentCommand{\sendmessageleftx}{O{\pcdefaultlongmessagelength}mO{}m}{% +\multicolumn{#2}{c}{\ensuremath{\hspace{\pcbeforemessageskip}\xleftarrow[\begin{aligned}#3\end{aligned}]{\mathmakebox[#1]{\begin{aligned}#4\end{aligned}}}\hspace{\pcaftermessageskip}}} +} + +%%% +% Division +\DeclareExpandableDocumentCommand{\pcintertext}{O{}m}{\intertext{% +\ifthenelse{\equal{#1}{center}}{\makebox[\linewidth][c]{#2}}{}% +\ifthenelse{\equal{#1}{dotted}}{\dotfill#2\dotfill}{}% +\ifthenelse{\equal{#1}{}}{#2}{}% +}\@pc@beginnewline} + + + +%%% +% Games +% +\newcounter{pcstartgamecounter} + +\newcommand*{\pcgamename}{\ensuremath{\mathsf{Game}}} +\newcommand*{\gameprocedurearg}{\ensuremath{(\secpar)}} +\newcommand*\@pcgameproofgamenr{0} +\define@key{pcgameproof}{nr}[]{\renewcommand*\@pcgameproofgamenr{#1}} +\define@key{pcgameproof}{name}[]{\renewcommand*\pcgamename{\ensuremath{#1}}} +\define@key{pcgameproof}{arg}[]{\renewcommand*\gameprocedurearg{\ensuremath{#1}}} + +\newenvironment{gameproof}[1][]{% +\begingroup% +\setkeys{pcgameproof}{#1} +\bxgamefalse% +\@pc@ensureremember% +\setcounter{pcgamecounter}{\@pcgameproofgamenr}% +\setcounter{pcstartgamecounter}{\@pcgameproofgamenr}\stepcounter{pcstartgamecounter}% +}{\@pc@releaseremember\endgroup} + +\newcommand{\gameprocedure}[2][]{\stepcounter{pcgamecounter}% +\pseudocode[head=\ensuremath{\pcgamename_{\thepcgamecounter}\gameprocedurearg},#1]{#2}} + +\newcommand{\bxgameprocedure}[3][]{% +\renewcommand{\@bxgameheader}{$\pcgamename_{#2}$\gameprocedurearg}% +\bxgametrue% +\stepcounter{pcgamecounter}% +\pseudocode[head=\ensuremath{\pcgamename_{\thepcgamecounter}\gameprocedurearg},#1]{#3}% +\bxgamefalse} + +\newcounter{@pc@game@tmpcnt@a} +\newcommand{\tbxgameprocedure}[2][]{\addtocounter{pcgamecounter}{1}% +\setcounter{@pc@game@tmpcnt@a}{\value{pcgamecounter}+1} +\pseudocode[head={\ensuremath{\pcgamename_{\thepcgamecounter}\gameprocedurearg}% +\ \setlength{\fboxsep}{3pt}\protect\fbox{\ensuremath{\pcgamename_{\thepcgamecounter}\gameprocedurearg}}},#1]{#2}% +\addtocounter{pcgamecounter}{1}} + + +\newcommand*\@pcgamehopnodestyle{} +\newcommand*\@pcgamehopedgestyle{bend left} +\newcommand*\@pcgamehoppathestyle{} +\newcommand*\@pcgamehophint{} +\newcommand*\@pcgamehoplength{1.5cm} +\define@key{pcgamehop}{nodestyle}[]{\renewcommand*\@pcgamehopnodestyle{#1}} +\define@key{pcgamehop}{edgestyle}[]{\renewcommand*\@pcgamehopedgestyle{#1}} +\define@key{pcgamehop}{pathstyle}[]{\renewcommand*\@pcgamehoppathestyle{#1}} +\define@key{pcgamehop}{hint}[]{\renewcommand*\@pcgamehophint{#1}} +\define@key{pcgamehop}{length}[]{\renewcommand*\@pcgamehoplength{#1}} + + +\newcommand{\@pc@setupgamehop}[1]{ +\begingroup\setkeys{pcgamehop}{#1}% +\tikzset{GAMEHOP-PATH-STYLE/.style/.expand once=\@pcgamehoppathestyle}% +\tikzset{GAMEHOP-NODE-STYLE/.style/.expand once=\@pcgamehopnodestyle}% +\tikzset{GAMEHOP-EDGE-STYLE/.style/.expand once=\@pcgamehopedgestyle}% +} + +\newcommand{\@pc@finalizegamehop}{ +\endgroup +} + +\newcommandx*{\addgamehop}[3]{% +\begingroup +\ifthenelse{#1<#2}{}{\renewcommand*\@pcgamehopedgestyle{bend right}} +\@pc@setupgamehop{#3} +\begin{tikzpicture}[overlay] +\ifthenelse{#1<#2}{ + \path[->,GAMEHOP-PATH-STYLE] (gamenode#1) edge[GAMEHOP-EDGE-STYLE] node[above,GAMEHOP-NODE-STYLE] {\@pcgamehophint} (gamenode#2); +}{ + \path[->,GAMEHOP-PATH-STYLE] (bgamenode#1) edge[GAMEHOP-EDGE-STYLE] node[above,GAMEHOP-NODE-STYLE] {\@pcgamehophint} (bgamenode#2); +} +\end{tikzpicture} +\@pc@finalizegamehop +\endgroup +} +\newcommandx*{\addstartgamehop}[2][1=\thepcstartgamecounter]{% +\@pc@setupgamehop{#2} +\begin{tikzpicture}[overlay] + \node[left=\@pcgamehoplength of gamenode#1] (tmpgamenode0) {}; + \path[->,GAMEHOP-PATH-STYLE] (tmpgamenode0) edge[GAMEHOP-EDGE-STYLE] node[above,GAMEHOP-NODE-STYLE] {\@pcgamehophint} (gamenode#1); +\end{tikzpicture} +\@pc@finalizegamehop +} +\newcommandx*{\addendgamehop}[2][1=\thepcgamecounter]{% +\@pc@setupgamehop{#2} +\begin{tikzpicture}[overlay] + \node[right=\@pcgamehoplength of gamenode#1] (tmpgamenode#1) {}; + \path[->,GAMEHOP-PATH-STYLE] (gamenode#1) edge[GAMEHOP-EDGE-STYLE] node[above,GAMEHOP-NODE-STYLE] {\@pcgamehophint} (tmpgamenode#1); +\end{tikzpicture} +\@pc@finalizegamehop +} +\newcommandx*{\addbxgamehop}[3]{% +\@pc@setupgamehop{#3} +\begin{tikzpicture}[overlay] + \path[->,GAMEHOP-PATH-STYLE] (bgamenode#1) edge[GAMEHOP-EDGE-STYLE] node[above,GAMEHOP-NODE-STYLE]] {\@pcgamehophint} (bgamenode#2); +\end{tikzpicture} +\@pc@finalizegamehop +} +\newcommandx*{\addloopgamehop}[2][1=\thepcgamecounter]{% +\@pc@setupgamehop{#2} +\begin{tikzpicture}[overlay] + \node (looptemp1) [right=0.5cm of gamenode#1] {}; + \draw[->,GAMEHOP-PATH-STYLE] (gamenode#1) -- (looptemp1|-gamenode#1) -- node[right,GAMEHOP-NODE-STYLE] {\@pcgamehophint} (looptemp1|-bgamenode#1)-- (bgamenode#1); +\end{tikzpicture} +\@pc@finalizegamehop +} + + + +%%%%%%%% +% basic pseudocode constants + +\newcommand{\pseudocodeconstant}[2][\ ]{\ensuremath{\mathbf{#2}}#1} + +\newcommand{\pcglobvar}{\pseudocodeconstant{gbl}} +\newcommand{\pcnew}{\pseudocodeconstant{new}} +\newcommand{\pcwhile}{\pseudocodeconstant{while}} +\newcommandx*{\pcdo}[2][1=\ ,2=]{#1\pseudocodeconstant[#2]{do}} +\newcommand{\pcif}{\pseudocodeconstant{if}} +\newcommand{\pcelse}{\pseudocodeconstant{else}} +\newcommand{\pcfi}{\pseudocodeconstant{fi}} +\newcommandx*{\pcthen}[2][1=\ ,2=]{#1\pseudocodeconstant[#2]{then}} +\newcommand{\pcreturn}{\pseudocodeconstant{return}} +\newcommandx*{\pcin}[2][1=\ ,2=]{#1\pseudocodeconstant[#2]{in}} +\newcommand{\pcfor}{\pseudocodeconstant{for}} +\newcommand{\pcrepeat}[1]{\ensuremath{\pseudocodeconstant{repeat} #1\ \pseudocodeconstant{times}}} +\newcommand{\pcrepeatuntil}[2]{\ensuremath{\pseudocodeconstant{repeat}\ #1\ \pseudocodeconstant{until}\ #2}} +\newcommand{\pcforeach}{\pseudocodeconstant{for each}} +\newcommand{\pcuntil}{\pseudocodeconstant{until}} +\newcommand{\pccontinue}{\pseudocodeconstant{continue}} +\newcommand{\pcfalse}{\pseudocodeconstant{false}} +\newcommand{\pctrue}{\pseudocodeconstant{true}} +\newcommand{\pcnull}{\pseudocodeconstant{null}} +\newcommand{\pccomment}[1]{{\mbox{/\!\!/ } \text{\scriptsize#1}}} +\newcommand{\pcdone}{\pseudocodeconstant{done}} +\newcommand{\pcparse}{\pseudocodeconstant{parse}} + +%%% +% highlighting +\definecolor{highlight-gray}{gray}{0.90} +\newcommand{\gamechange}[2][highlight-gray]{% +{\setlength{\fboxsep}{0pt}\colorbox{#1}{\ifmmode$\displaystyle#2$\else#2\fi}} +} + +%%% +% boxing +\newcommand{\pcbox}[1]{% +{\setlength{\fboxsep}{3pt}\fbox{$\displaystyle#1$}} +} + +\endinput
\ No newline at end of file diff --git a/Master/tlpkg/bin/tlpkg-ctan-check b/Master/tlpkg/bin/tlpkg-ctan-check index 75facf1efe2..52603c4d7bd 100755 --- a/Master/tlpkg/bin/tlpkg-ctan-check +++ b/Master/tlpkg/bin/tlpkg-ctan-check @@ -153,7 +153,7 @@ my @TLP_working = qw( countriesofeurope counttexruns courier-scaled courseoutline coursepaper coverpage covington cprotect - crbox crop crossreference crossrefware crossword crosswrd cryst + crbox crop crossreference crossrefware crossword crosswrd cryptocode cryst cs csbulletin cslatex csplain csquotes csquotes-de csvsimple csvtools cstex ctan_chk ctanify ctanupload ctable ctex ctex-faq cursolatex cuisine diff --git a/Master/tlpkg/tlpsrc/collection-science.tlpsrc b/Master/tlpkg/tlpsrc/collection-science.tlpsrc index 52340208278..43b4b8d6df9 100644 --- a/Master/tlpkg/tlpsrc/collection-science.tlpsrc +++ b/Master/tlpkg/tlpsrc/collection-science.tlpsrc @@ -27,6 +27,7 @@ depend clrscode depend clrscode3e depend complexity depend computational-complexity +depend cryptocode depend digiconfigs depend drawstack depend dyntree diff --git a/Master/tlpkg/tlpsrc/cryptocode.tlpsrc b/Master/tlpkg/tlpsrc/cryptocode.tlpsrc new file mode 100644 index 00000000000..e69de29bb2d --- /dev/null +++ b/Master/tlpkg/tlpsrc/cryptocode.tlpsrc |