chiark / gitweb /
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
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}{%
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}}
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}
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}
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
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: