Commit | Line | Data |
---|---|---|

74eb47db | 1 | %%% -*-latex-*- |

2 | %%% | |

d7d62ac0 | 3 | %%% $Id: wrestlers.tex,v 1.5 2002/01/13 14:55:31 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 $ | |

d7d62ac0 | 13 | %%% Revision 1.5 2002/01/13 14:55:31 mdw |

14 | %%% More incomplete stuff. | |

15 | %%% | |

1a981bdb | 16 | %%% Revision 1.4 2001/06/29 19:36:05 mdw |

17 | %%% Some progress made on laptop. | |

18 | %%% | |

90d03a85 | 19 | %%% Revision 1.3 2001/06/22 19:41:31 mdw |

20 | %%% Restart with different structure and rather more formal objectives. | |

21 | %%% | |

874aed51 | 22 | %%% Revision 1.2 2001/02/22 09:09:05 mdw |

23 | %%% Partially through reworking. | |

24 | %%% | |

74eb47db | 25 | %%% Revision 1.1 2001/02/16 21:43:33 mdw |

26 | %%% Initial versions of documentation. | |

27 | %%% | |

28 | ||

d7d62ac0 | 29 | \newif\iffancystyle\fancystylefalse |

30 | ||

31 | \iffancystyle | |

32 | \documentclass | |

33 | [a4paper, article, 10pt, numbering, noherefloats, notitlepage] | |

34 | {strayman} | |

35 | \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts} | |

36 | \usepackage[margin]{amsthm} | |

37 | \else | |

38 | \documentclass[a4paper]{article} | |

39 | \usepackage{a4wide} | |

40 | \usepackage{amsthm} | |

41 | \fi | |

42 | ||

43 | \usepackage{amssymb, amstext} | |

44 | \usepackage{mdwtab, mathenv} | |

74eb47db | 45 | |

90d03a85 | 46 | \errorcontextlines=999 |

d7d62ac0 | 47 | \showboxbreadth=999 |

48 | \showboxdepth=999 | |

90d03a85 | 49 | \makeatletter |

74eb47db | 50 | |

90d03a85 | 51 | \title{The Wrestlers Protocol: proof-of-receipt and secure key exchange} |

52 | \author{Mark Wooding \and Clive Jones} | |

74eb47db | 53 | |

90d03a85 | 54 | \bibliographystyle{alpha} |

74eb47db | 55 | |

90d03a85 | 56 | \newtheorem{theorem}{Theorem} |

d7d62ac0 | 57 | \renewcommand{\qedsymbol}{$\square$} |

58 | ||

59 | \newcommand{\getsr}{\stackrel{\scriptscriptstyle R}{\gets}} | |

60 | \newcommand{\inr}{\in_{\scriptscriptstyle R}} | |

1a981bdb | 61 | \newcommand{\oracle}[1]{\mathcal{#1}} |

62 | ||

63 | \newcommand{\expt}[2]{\mathbf{Exp}^{\text{\normalfont#1}}_{#2}} | |

64 | \newcommand{\adv}[2]{\mathbf{Adv}^{\text{\normalfont#1}}_{#2}} | |

65 | \newcommand{\ord}{\mathop{\operator@font ord}} | |

d7d62ac0 | 66 | \newcommand{\poly}[1]{\mathop{\operator@font poly}({#1})} |

67 | \newcommand{\negl}[1]{\mathop{\operator@font negl}({#1})} | |

1a981bdb | 68 | \newcommand{\compind}{\stackrel{c}{\approx}} |

69 | ||

70 | \newcolumntype{G}{p{0pt}} | |

71 | ||

d7d62ac0 | 72 | \newcommand{\xor}{\oplus} |

73 | \renewcommand{\epsilon}{\varepsilon} | |

74 | ||

1a981bdb | 75 | \newenvironment{program} |

d7d62ac0 | 76 | {\begin{tabular}[C]{|G|}\hlx{hv[][\tabcolsep]}\begin{tabbing}} |

77 | {\end{tabbing}\\\hlx{v[][\tabcolsep]h}\end{tabular}} | |

1a981bdb | 78 | |

90d03a85 | 79 | \begin{document} |

74eb47db | 80 | |

90d03a85 | 81 | \maketitle |

82 | \begin{abstract} | |

83 | Fill this in later. | |

84 | \end{abstract} | |

85 | \tableofcontents | |

86 | \newpage | |

74eb47db | 87 | |

90d03a85 | 88 | %%%-------------------------------------------------------------------------- |

74eb47db | 89 | |

90d03a85 | 90 | \section{Introduction} |

91 | % Some waffle here about the desirability of a key-exchange protocol that | |

92 | % doesn't leave signatures lying around, followed by an extended report of | |

93 | % the various results. | |

74eb47db | 94 | |

90d03a85 | 95 | %%%-------------------------------------------------------------------------- |

74eb47db | 96 | |

97 | \section{A simple authentication protocol} | |

90d03a85 | 98 | % Present the basic Diffie-Hellman-based authenticator, and prove that an |

99 | % authentication oracle is useless if the hash function has appropriate | |

100 | % properties. | |

74eb47db | 101 | |

d7d62ac0 | 102 | We begin by introducing a simple proof-of-identity protocol, based on the |

1a981bdb | 103 | Diffie-Hellman key-exchange protocol \cite{Diffie:1976:NDC} and prove some of |

104 | its useful properties. | |

105 | ||

106 | \subsection{Introduction} | |

107 | ||

d7d62ac0 | 108 | We start by selecting a security parameter $k$. We choose a cyclic group $G |

109 | = \langle g \rangle$ with $q = |G|$ prime, in which the decision | |

110 | Diffie-Hellman problem is assumed to be hard \cite{Boneh:1998:DDP}; we | |

111 | require that $q$ is a $k$-bit number. Suitable groups include elliptic | |

112 | curves over finite fields and prime-order subgroups of prime fields. | |

113 | Throughout, we shall write the group operation as multiplication, and we | |

114 | shall assume that group elements are interchangeable with their binary | |

115 | representations. | |

1a981bdb | 116 | |

d7d62ac0 | 117 | Alice can choose a private key $\alpha$ from the set $\{ 1, 2, \ldots, q - 1 |

118 | \}$ and publish her corresponding public key $a = g^\alpha$. | |

1a981bdb | 119 | |

120 | A simplistic proof-of-identity protocol might then proceed as follows: | |

121 | \begin{enumerate} | |

d7d62ac0 | 122 | \item Bob chooses a random exponent $\beta$, also from $\{ 1, 2, \ldots, q - |

123 | 1 \}$, and sends a \emph{challenge} $b = g^\beta$ to Alice. | |

124 | \item Alice computes her \emph{response} $b^\alpha$ and returns it to Bob. | |

125 | \item If Alice's response is equal to $a^\beta$ then Bob is satisfied. | |

1a981bdb | 126 | \end{enumerate} |

d7d62ac0 | 127 | If Bob always plays by the rules then this protocol is evidently secure, |

128 | since computing $g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely | |

129 | the Diffie-Hellman problem. | |

1a981bdb | 130 | |

131 | This protocol has a flaw, though: by using Alice as an oracle for the | |

132 | function $x \mapsto x^\alpha$, he could conceivably acquire information about | |

133 | Alice's private key which he could later use to impersonate her. As an | |

134 | example, Bob can submit $-g^\beta$ as a challenge: if the reply | |

135 | $(-g^\beta)^\alpha = g^{\alpha\beta}$, Bob can conclude that $\alpha$ is | |

136 | even. | |

137 | ||

d7d62ac0 | 138 | We fix the protocol by requiring that Bob prove that he already knows the |

139 | answer to his challenge. We introduce a hash function $h$ whose properties | |

140 | we shall investigate later. The \emph{Wrestlers Authentication Protocol} is | |

141 | then: | |

142 | \begin{enumerate} | |

143 | \item Bob chooses a secret $\beta \getsr \{ 1, 2, \ldots, q - 1 \}$. He | |

144 | computes his \emph{challenge} $b \gets g^\beta$ and also a \emph{check | |

145 | value} $c \gets \beta \xor h(a^\beta)$. He sends the pair $(b, c)$. | |

146 | \item Alice receives $(b', c')$. She computes $r \gets b'^\alpha$ and | |

147 | $\gamma \gets c' \xor h(R)$. If $b' = g^\gamma$, she sends $r$ back as her | |

148 | \emph{response}; otherwise she sends the distinguished value $\bot$. | |

149 | \item Bob receives $r'$. If $r' = a^\beta$ then he accepts that he's talking | |

150 | to Alice. | |

151 | \end{enumerate} | |

152 | We show that the introduction of the check value has indeed patched up the | |

153 | weakness described above, and that the check value itself hasn't made an | |

154 | impersonator's job much easier. | |

155 | ||

156 | \subsection{Analysis in the random oracle model} | |

157 | ||

158 | Here, we prove that the Wrestlers Authentication Protocol is secure if $h$ is | |

159 | implemented by a public \emph{random oracle} \cite{Bellare:1993:ROP}. | |

160 | ||

161 | Fix a private key $\alpha \inr \{ 1, 2, \ldots, q - 1\}$ and the corresponding public | |

162 | key $a = g^\alpha$, and consider a probabilistic polynomial-time adversary | |

163 | $A$, equipped with two oracles. One is a random oracle $\oracle{H}\colon | |

164 | \{0, 1\}^* \to \{0, 1\}^k$, which implements a function $h$ randomly selected | |

165 | from the set of all functions with that signature; the other is an | |

166 | authentication oracle $\oracle{O}\colon G \times \{0, 1\}^k \to G \cup \{ | |

167 | \bot \}$ defined by: | |

168 | \[ | |

169 | \oracle{O}^(b, c) = \begin{cases} | |

170 | b^\alpha & if $b = g^{c \xor h(b^\alpha)}$ \\ | |

171 | \bot & otherwise | |

172 | \end{cases} | |

173 | \] | |

174 | The authentication oracle will play the part of Alice in the following. We | |

175 | first show that access to this authentication oracle can't help an adversary | |

176 | learn how to impersonate Alice. | |

1a981bdb | 177 | |

178 | \begin{theorem} | |

d7d62ac0 | 179 | The Wrestlers Authentication Protocol with random oracle is computational |

180 | zero knowledge \cite{Brassard:1989:SZK}. | |

181 | \label{thm:wap-czk} | |

1a981bdb | 182 | \end{theorem} |

183 | \begin{proof} | |

d7d62ac0 | 184 | \newcommand{\Hlist}{\textit{$\oracle{H}$-list}} |

185 | \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}} | |

186 | \newcommand{\Osim}{\textit{$\oracle{O}$-sim}} | |

187 | \renewcommand{\H}{\oracle{H}} | |

188 | \renewcommand{\O}{\oracle{O}} | |

189 | % | |

190 | Let $A$ be any probabilistic polynomial-time adversary with access to a | |

191 | random. We shall construct a probabilistic polynomial-time adversary $A'$ | |

192 | without either oracle such that the probability distributions on the output | |

193 | of $A$ and $A'$ are equal. Specifically, $A'$ runs $A$ with simulated | |

194 | random and authentication oracles whose behaviour is computationally | |

195 | indistinguishable from the originals. The algorithm for $A'$ and the | |

196 | simulated oracles is shown in figure~\ref{fig:wap-czk-sim}. | |

197 | ||

198 | \begin{figure} | |

199 | \begin{program} | |

200 | \quad \= \kill | |

201 | Adversary $A'^{\H(\cdot)}$: \+ \\ | |

202 | $\Hlist \gets \emptyset$; \\ | |

203 | $r \gets A^{\Hsim(\cdot), \Osim(\cdot, \cdot)}$; \\ | |

204 | \textbf{return} $r$; \- \\[\medskipamount] | |

205 | % | |

206 | Simulated random oracle $\Hsim(q)$: \+ \\ | |

207 | \textbf{if} $\exists r : (q, r) \in \Hlist$ \textbf{then} | |

208 | \textbf{return} $r$; \\ | |

209 | $r \getsr \H(q)$; \\ | |

210 | $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\ | |

211 | \textbf{return} $r$; \- \\[\medskipamount] | |

212 | % | |

213 | Simulated authentication oracle $\Osim(b, c)$: \+ \\ | |

214 | \textbf{if} $\exists q, r : (q, r) \in \Hlist \wedge | |

215 | b = g^{c \xor r} \wedge | |

216 | q = a^{c \xor r}$ \textbf{then} | |

217 | \textbf{return} $a^{c \xor r}$; \\ | |

218 | \textbf{else} \textbf{return} $\bot$; | |

219 | \end{program} | |

220 | % | |

221 | \caption{The algorithm and simulated oracles for the proof of | |

222 | theorem~\ref{thm:wap-czk}.} | |

223 | \label{fig:wap-czk-sim} | |

224 | \end{figure} | |

1a981bdb | 225 | |

d7d62ac0 | 226 | Firstly we show that $A'$ runs in polynomial time. The only modifications |

227 | to $\Hlist$ are in $\Hsim$, which adds at most one element for each oracle | |

228 | query. Since $\Hlist$ is initially empty and $A$ can only make $\poly{k}$ | |

229 | queries to $\Hsim$, this implies that $|\Hlist|$ is always | |

230 | polynomially-bounded. Each query can be answered in polynomial time: | |

231 | indeed, the search implied by the test $\exists r : (q, r) \in \Hlist$ can | |

232 | be performed in $O(\log q)$ time by indexing $\Hlist$ on $q$ using a radix | |

233 | tree. Now, since $|\Hlist|$ is polynomially bounded, the test $\exists q, | |

234 | r : (q, r) \in \Hlist \wedge b = g^{c \xor r} \wedge q = a^{c \xor r}$ at | |

235 | the start of $\Osim$ runs in polynomial time even though it requires an | |

236 | exhaustive search of the history of $A$'s queries to its simulated random | |

237 | oracle. | |

1a981bdb | 238 | |

d7d62ac0 | 239 | Next, we examine the behaviour of the simulated oracles. Since $\Hsim$ is |

240 | implemented in terms of the public random oracle $\H$, and returns the same | |

241 | answers to queries, its probability distribution must be identical. | |

242 | ||

243 | We turn our attention to the simulation of the authentication oracle. | |

244 | Consider a query $(b, c)$ made by $A$ to its authentication oracle. | |

245 | ||

246 | Firstly, suppose that there is a $\beta$ such that $b = g^\beta$ and $c = | |

247 | \beta \xor r$ where $r$ is the response to a previous query made by $A$ to | |

248 | its random oracle on $a^\beta$. Then the true authentication oracle $\O$ | |

249 | is satisfied because $b = g^\beta = g^{c \xor r} = g^{c \xor h(a^\beta)} = | |

250 | g^{c \xor h(b^\alpha)}$, and returns $b^\alpha$. Similarly, the simulated | |

251 | authentication oracle $\Osim$ will find the pair $(a^\beta, r) \in \Hlist$, | |

252 | recover $\beta = c \xor r$, confirm that $b = g^\beta$, and return | |

253 | $a^\beta$ as required. These events all occur with probability 1. | |

254 | ||

255 | Conversely, suppose that there is no such $\beta$. Then the simulated | |

256 | oracle $\Osim$ will reject the query, returning $\bot$, again with | |

257 | probability 1. However, a genuine authentication oracle $\O$ will succeed | |

258 | and return $b^\alpha$ with probability $2^{-k}$. To see this, note that $b | |

259 | = g^\gamma$ for some $\gamma \in \{ 0, 1, \ldots, q - 1 \}$, and the | |

260 | probability that $h(b^\alpha) = c \xor \gamma$ is precisely $2^{-k}$, since | |

261 | $c$ and $\gamma$ are $k$-bit strings. Since this probability is | |

262 | negligible, we have shown that the distributions of the simulated oracles | |

263 | $\Hsim$ and $\Osim$ are computationally indistinguishable from the genuine | |

264 | oracles $\H$ and $\O$. The theorem follows. | |

1a981bdb | 265 | \end{proof} |

266 | ||

d7d62ac0 | 267 | Our next objective is to show that pretending to be Alice is hard without |

268 | knowledge of her secret $\alpha$. We say that an adversary $A$ | |

269 | \emph{impersonates} in the Wrestlers Authentication Protocol with probability | |

270 | $\epsilon$ if | |

271 | \[ \Pr[A^{\oracle{H}(\cdot)}(g^\alpha, g^\beta, | |

272 | \beta \xor h(g^{\alpha\beta})) | |

273 | = g^{\alpha\beta}] | |

274 | = \epsilon | |

275 | \] | |

276 | where the probability is taken over all choices of $\alpha, \beta \in \{ 1, | |

277 | 2, \ldots, q - 1 \}$ and random oracles $\oracle{H}$. | |

1a981bdb | 278 | |

d7d62ac0 | 279 | \begin{theorem} |

280 | Assuming that the Diffie-Hellman problem is hard in $G$, no probabilistic | |

281 | polynomial-time adversary can impersonate in the Wrestlers Authentication | |

282 | Protocol with random oracle with better than negligible probability. | |

283 | \label{thm:wap-dhp} | |

284 | \end{theorem} | |

285 | \begin{proof} | |

286 | \newcommand{\Hlist}{\textit{$\oracle{H}$-list}} | |

287 | \newcommand{\Hqueries}{\textit{$\oracle{H}$-queries}} | |

288 | \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}} | |

289 | \renewcommand{\H}{\oracle{H}} | |

290 | % | |

291 | We prove the theorem by contradiction. Given a polynomial-time adversary | |

292 | $A$ which impersonates Alice with non-negligible probability $\epsilon$, we | |

293 | construct an adversary which solves the Diffie-Hellman problem with | |

294 | probability no less than $\epsilon \poly{k}$, i.e., | |

295 | \[ \Pr[A'(g^\alpha, g^\beta) = g^{\alpha\beta}] \ge \epsilon \poly{k}. \] | |

296 | Thus, if there is any polynomial-time $A$ which impersonates with better | |

297 | than negligible probability, then there is a polynomial-time $A'$ which | |

298 | solves Diffie-Hellman with essentially the same probability, which would | |

299 | violate our assumption of the hardness of Diffie-Hellman. | |

300 | ||

301 | The idea behind the proof is that the check value is only useful to $A$ | |

302 | once it has discovered the correct response to the challenge, which it must | |

303 | have done by solving the Diffie-Hellman problem. Hence, our Diffie-Hellman | |

304 | ||

305 | \begin{figure} | |

306 | \begin{program} | |

307 | \quad \= \kill | |

308 | Adversary $A'(a, b)$: \+ \\ | |

309 | $\Hlist \gets \emptyset$; \\ | |

310 | $\Hqueries \gets \emptyset$; \\ | |

311 | $r \getsr \{ 0, 1 \}^k$; \\ | |

312 | $x \gets A^{\Hsim(\cdot)}(a, b, r)$; \\ | |

313 | $c \getsr (\Hlist \cup \{ x \}) \cap G$; \\ | |

314 | \textbf{return} $c$; \- \\[\medskipamount] | |

315 | % | |

316 | Simulated random oracle $\Hsim(q)$: \+ \\ | |

317 | \textbf{if} $\exists r : (q, r) \in \Hlist$ | |

318 | \textbf{then} \textbf{return} $r$; \\ | |

319 | $r \gets \{ 0, 1 \}^k$; \\ | |

320 | $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\ | |

321 | $\Hqueries \gets \Hqueries \cup \{ q \}$; \\ | |

322 | \textbf{return} $r$; | |

323 | \end{program} | |

324 | % | |

325 | \caption{The algorithm for the proof of theorem~\ref{thm:wap-dhp}} | |

326 | \label{fig:wap-dhp-rdc} | |

327 | \end{figure} | |

328 | ||

329 | The adversary $A'$ is shown in figure~\ref{fig:wap-dhp-rdc}. It generates | |

330 | a random check-value and runs the impersonator $A$. | |

331 | ||

332 | The simulated random oracle $\Hsim$ gathers together the results of all of | |

333 | the random oracle queries made by $A$. The final result returned by $A'$ | |

334 | is randomly chosen from among all of the `plausible' random oracle queries | |

335 | and $A$'s output, i.e., those queries which are actually members of the | |

336 | group. The check value given to $A$ is most likely incorrect (with | |

337 | probability $1 - 2^{-k}$): the intuition is that $A$ can only notice if it | |

338 | actually computes the right answer and then checks explicitly. | |

339 | ||

340 | If $A$ does compute the correct answer $g^{\alpha\beta}$ and either returns | |

341 | it or queries $\Hsim$ on it, then $A'$ succeeds with probability $\epsilon | |

342 | / |(\Hlist \cup \{ x \}) \cap G| = \epsilon \poly{k}$, since $|\Hlist|$ is | |

343 | no greater than the number of random oracle queries made by $A$ (which must | |

344 | be polynomially bounded).\footnote{% | |

345 | This polynomial factor introduces a loss in the perceived security of the | |

346 | authentication protocol. It appears that this loss is only caused by the | |

347 | possibility of the adversary $A$ being deliberately awkward and checking | |

348 | the value of $c$ after having computed the answer. However, we can't see | |

349 | a way to improve the security bound on the scheme without imposing | |

350 | artificial requirements on $A$.} % | |

351 | ||

352 | It remains to show that if $A$ never queries its random oracle on | |

353 | $g^{\alpha\beta}$ then it cannot distinguish the random check value $r$ | |

354 | from the correct one $\beta \xor \H(g^{\alpha\beta})$, and hence won't | |

355 | notice that $A'$ is lying to it. But this is obvious: $A$'s probability of | |

356 | guessing the random value that would have been returned had it actually | |

357 | queried $\Hsim$ on the input $g^{\alpha\beta}$ is equal to the probability | |

358 | of it guessing $\beta \xor r$ instead, since $\Hsim$ chooses its responses | |

359 | uniformly at random. This completes the proof. | |

360 | \end{proof} | |

1a981bdb | 361 | |

d7d62ac0 | 362 | We conclude here that the Wrestlers Authentication Protocol is a secure |

363 | authentication protocol in the random oracle model: impersonation is hard if | |

364 | the Diffie-Hellman problem is hard, and proving one's identity doesn't leak | |

365 | secret key information. | |

1a981bdb | 366 | |

d7d62ac0 | 367 | \subsection{Requirements on hash functions} |

1a981bdb | 368 | |

d7d62ac0 | 369 | Having seen that the Wrestlers Authentication Protocol is secure in the |

370 | random oracle model, we now ask which properties we require from the hash | |

371 | function. This at least demonstrates that the protocol isn't deeply flawed, | |

372 | and suggests an efficient implementation in terms of conventional hash | |

373 | functions. | |

1a981bdb | 374 | |

d7d62ac0 | 375 | Here we investigate more carefully the properties required of the hash |

376 | function, and provide a more quantitative analysis of the protocol. | |

1a981bdb | 377 | |

d7d62ac0 | 378 | Looking at the proofs of the previous two sections, we see that the random |

379 | oracles are mainly a device which allow our constructions to `grab hold' of | |

380 | the hashing operations performed by the adversary. | |

1a981bdb | 381 | |

d7d62ac0 | 382 | %%%-------------------------------------------------------------------------- |

1a981bdb | 383 | |

d7d62ac0 | 384 | \section{A key-exchange protocol} |

385 | % Present the Wrestlers protocol in all its glory. Show, by means of the | |

386 | % previous proofs, that the Wrestlers protocol is simulatable in the | |

387 | % authenticated model using a much simpler protocol. Show that the simpler | |

388 | % protocol is SK-secure. | |

1a981bdb | 389 | |

390 | ||

d7d62ac0 | 391 | % messages |

392 | % | |

393 | % pre-challenge: g^b | |

394 | % cookie: g^b, h(cookie, g^b') | |

395 | % challenge: g^b, h(g^b'), b + h(reply-check, g^b, g^b', g^ab') | |

396 | % reply: g^b, h(g^b'), b + h(reply-check, g^b, g^b', g^ab'), E_k(g^a'b) | |

397 | % switch: h(g^b), h(g^b'), E_k(g^a'b, h(switch-request, g^a, g^a')) | |

398 | % switch-ok: E_k(g^ab, h(switch-confirm, g^a, g^a'))begin{ | |

1a981bdb | 399 | |

874aed51 | 400 | |

d7d62ac0 | 401 | We now describe the full Wrestlers Protocol, in a multi-party setting. Fix a |

402 | cyclic group $G = \langle g \rangle$ of order $q = |G|$. Each player $P_i$ | |

403 | chooses a private key $\alpha_i \in \{ 1, 2, \ldots, q - 1 \}$ and publishes | |

404 | the corresponding public key $a_i = g^{\alpha_i}$ to the other players. | |

874aed51 | 405 | |

74eb47db | 406 | |

74eb47db | 407 | |

74eb47db | 408 | |

409 | %%%----- That's all, folks -------------------------------------------------- | |

410 | ||

90d03a85 | 411 | \bibliography{cryptography,mdw-crypto} |

74eb47db | 412 | \end{document} |

413 | ||

414 | %%% Local Variables: | |

415 | %%% mode: latex | |

416 | %%% TeX-master: "wrestlers" | |

d7d62ac0 | 417 | %%% End: |