chiark / gitweb /
Provide MGF macros.
[tripe] / doc / wrestlers.tex
CommitLineData
74eb47db 1%%% -*-latex-*-
2%%%
1a981bdb 3%%% $Id: wrestlers.tex,v 1.4 2001/06/29 19:36:05 mdw Exp $
74eb47db 4%%%
5%%% Description of the Wrestlers Protocol
6%%%
7%%% (c) 2001 Mark Wooding
8%%%
9
10%%%----- Revision history ---------------------------------------------------
11%%%
12%%% $Log: wrestlers.tex,v $
1a981bdb 13%%% Revision 1.4 2001/06/29 19:36:05 mdw
14%%% Some progress made on laptop.
15%%%
90d03a85 16%%% Revision 1.3 2001/06/22 19:41:31 mdw
17%%% Restart with different structure and rather more formal objectives.
18%%%
874aed51 19%%% Revision 1.2 2001/02/22 09:09:05 mdw
20%%% Partially through reworking.
21%%%
74eb47db 22%%% Revision 1.1 2001/02/16 21:43:33 mdw
23%%% Initial versions of documentation.
24%%%
25
1a981bdb 26\documentclass[a4paper]{article}
27\usepackage{a4wide}
74eb47db 28\usepackage{amssymb}
90d03a85 29\usepackage{amstext}
1a981bdb 30\usepackage{mdwtab}
74eb47db 31
90d03a85 32\errorcontextlines=999
33\makeatletter
74eb47db 34
90d03a85 35\title{The Wrestlers Protocol: proof-of-receipt and secure key exchange}
36\author{Mark Wooding \and Clive Jones}
74eb47db 37
90d03a85 38\bibliographystyle{alpha}
74eb47db 39
90d03a85 40\newtheorem{theorem}{Theorem}
41\newenvironment{proof}[1][Proof]{%
1a981bdb 42 \par\noindent\textbf{#1}\ %
90d03a85 43}{%
44 \penalty\@M\hfill\vadjust{}%
45 \penalty\z@\relax\vadjust{}%
46 \penalty\@M\hfill$\square$%
47 \par%
48}
74eb47db 49
1a981bdb 50\newcommand{\rgets}{\stackrel{\scriptscriptstyle R}{\gets}}
51\newcommand{\oracle}[1]{\mathcal{#1}}
52
53\newcommand{\expt}[2]{\mathbf{Exp}^{\text{\normalfont#1}}_{#2}}
54\newcommand{\adv}[2]{\mathbf{Adv}^{\text{\normalfont#1}}_{#2}}
55\newcommand{\ord}{\mathop{\operator@font ord}}
56\newcommand{\poly}{\mathrm{poly}}
57\newcommand{\compind}{\stackrel{c}{\approx}}
58
59\newcolumntype{G}{p{0pt}}
60
61\newenvironment{program}
62 {\begin{tabbing}}
63 {\end{tabbing}}
64
90d03a85 65\begin{document}
74eb47db 66
90d03a85 67\maketitle
68\begin{abstract}
69 Fill this in later.
70\end{abstract}
71\tableofcontents
72\newpage
74eb47db 73
90d03a85 74%%%--------------------------------------------------------------------------
74eb47db 75
90d03a85 76\section{Introduction}
77% Some waffle here about the desirability of a key-exchange protocol that
78% doesn't leave signatures lying around, followed by an extended report of
79% the various results.
74eb47db 80
90d03a85 81%%%--------------------------------------------------------------------------
74eb47db 82
83\section{A simple authentication protocol}
90d03a85 84% Present the basic Diffie-Hellman-based authenticator, and prove that an
85% authentication oracle is useless if the hash function has appropriate
86% properties.
74eb47db 87
1a981bdb 88We start by introducing a simple proof-of-identity protocol, based on the
89Diffie-Hellman key-exchange protocol \cite{Diffie:1976:NDC} and prove some of
90its useful properties.
91
92\subsection{Introduction}
93
94Suppose that $G$ is some cyclic group of prime order $q$, generated by an
95element $g$, in which the decision Diffie-Hellman problem
96\cite{Boneh:1998:DDP} is hard.
97
98Alice can choose a private key $1 < \alpha < q$ and publish her corresponding
99public key $A = g^\alpha$.
100
101A simplistic proof-of-identity protocol might then proceed as follows:
102\begin{enumerate}
103\item Bob chooses a random exponent $1 < \beta < q$, and sends a
104 \emph{challenge} $B = g^\beta$ to Alice.
105\item Alice computes $B^\alpha$ and returns it to Bob.
106\item If Alice's response is equal to $A^\beta$ then Bob is satisfied.
107\end{enumerate}
108This is evidently secure if the Diffie-Hellman problem is hard: computing
109$g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely the
110Diffie-Hellman problem.
111
112This protocol has a flaw, though: by using Alice as an oracle for the
113function $x \mapsto x^\alpha$, he could conceivably acquire information about
114Alice's private key which he could later use to impersonate her. As an
115example, Bob can submit $-g^\beta$ as a challenge: if the reply
116$(-g^\beta)^\alpha = g^{\alpha\beta}$, Bob can conclude that $\alpha$ is
117even.
118
119We fix this protocol by requiring that Bob prove that he already knows the
120answer to his challenge. Instead of sending just his challenge $B$, he sends
121the pair $(B, h(A^\beta))$ for some function $h$: Alice verifies that
122$h(B^\alpha) = h(A^\beta)$ before returning her response. We need to choose
123the function $h$ such that
124\begin{itemize}
125\item $h$ is one-way, so that providing $h(A^\beta)$ doesn't provide an
126 impersonator with an additional clue to guessing the correct response; and
127\item providing $h(A^\beta)$ is hard without previously knowing the value of
128 $A^\beta$.
129\end{itemize}
130
131\subsection{Analysis}
132
133We now examine the protocol in a more formal setting, with the objective of
134characterizing our requirements for the function $\oracle{H}$. Fix a
135\emph{group description} $\mathcal{G} = (G, q, g)$, where $G$ is a cyclic
136group of prime order $q$ generated by $g \in G$, and a function
137$\oracle{H}\colon \{ 0, 1 \}^* \to \{ 0, 1 \}^L$. Define the
138\emph{authentication oracle} $\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, x,
139h)$, where $\alpha \in \mathbb{Z} / q \mathbb{Z}$, $x \in g$ and $h \in \{ 0,
1401 \}^L$, to return $x^\alpha$ if $h = \oracle{H}(x^\alpha)$ and the symbol
141$\bot$ otherwise.
142
143We introduce two experiments:
144\begin{tabular}[C]{@{}G|G@{}}
145 \begin{program}
146 \quad \= \quad \= \kill
147 Experiment $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$ \\
148 \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\
149 \> $R \gets
150 A_{\text{cca}}
151 ^{\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, \cdot, \cdot),
152 \oracle{H}
153 (\cdot)}
154 (g^\alpha, g^\tau, \oracle{H}(g^{\alpha\tau}))$; \\
155 \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\
156 \> \textbf{else} \textbf{return} $0$;
157 \end{program}
158 &
159 \begin{program}
160 \quad \= \quad \= \kill
161 Experiment $\expt{uni-no}{A}(\mathcal{G})$ \\
162 \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\
163 \> $R \gets A(g^\alpha, g^\tau)$; \\
164 \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\
165 \> \textbf{else} \textbf{return} $0$;
166 \end{program}
167\end{tabular}
168We mandate that the adversary $A_{\text{cca}}$ never query its authentication
169oracle with the test challenge $g^\tau$.
170
171We will consider a function $\oracle{H}$ to be suitable for our purposes if
172for any adversary $A_{\text{cca}}$, there is an adversary $A$ for which the
173distributions of $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$
174and $\expt{uni-no}{A}(\mathcal{G})$ are computationally indistinguishable.
175Intuitively, this means that the authentication oracle isn't useful in
176attacking the protocol: any adversary which has access to an oracle can be
177replaced by one which has approximately the same probability of success but
178without oracle access.
179
180We first prove that a random oracle \cite{Bellare:1993:ROP} makes a
181`suitable' function.
182
183\begin{theorem}
184 If $\oracle{H}$ is a random oracle with $L$-bit output, where $L$ is some
185 polynomial function of the length of $q$, then, for any adversary
186 $A_{\text{cca}}$, there exists an adversary $A$ such that
187 \[ \expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})
188 \compind \expt{uni-no}{A}(\mathcal{G}) \]
189\end{theorem}
190\begin{proof}
191 The idea behind the proof is that we construct an adversary $A$ in terms of
192 the given adversary $A_{\text{cca}}$ with the same output in all but
193 negligibly few cases.
194
195 Our adversary $A$ isn't provided with either oracle supplied to
196 $A_{\text{cca}}$.
197
198 Simulating the random oracle is easy. $A$ maintains a table, initially
199 empty, of pairs $(q, r)$. When the oracle is invoked on input $q$, we look
200 it up in the table: if there is some entry $(q, r)$, it returns $r$;
201 otherwise we toss coins to choose a new output $r$ and add $(q, r)$ to the
202 table. This is obviously a polynomial-time activity, since
203 $A_{\text{cca}}$ makes only polynomially many queries, and answering each
204 one takes polynomial time.
205
206 The authentication oracle is a little harder. Suppose $A_{\text{cca}}$
207 makes a query $(x, h)$. If there is an entry $(q, h)$ in the random oracle
208 table, the authentication oracle returns $q$; otherwise it returns $\bot$.
209
210 It remains to show that this is a valid thing to do.
211\end{proof}
212
213
214
215
216
217
218
219
220
221
222
223
874aed51 224
90d03a85 225%%%--------------------------------------------------------------------------
874aed51 226
90d03a85 227\section{An MT-authenticator}
228% Use the protocol of the previous section as an MT-authenticator, within the
229% meaning of [Canetti:2001:AKE].
74eb47db 230
90d03a85 231%%%--------------------------------------------------------------------------
74eb47db 232
90d03a85 233\section{A key-exchange protocol}
234% Present the Wrestlers protocol in all its glory. Show, by means of the
235% previous proofs, that the Wrestlers protocol is simulatable in the
236% authenticated model using a much simpler protocol. Show that the simpler
237% protocol is SK-secure.
74eb47db 238
239%%%----- That's all, folks --------------------------------------------------
240
90d03a85 241\bibliography{cryptography,mdw-crypto}
74eb47db 242\end{document}
243
244%%% Local Variables:
245%%% mode: latex
246%%% TeX-master: "wrestlers"
247%%% End: