| 1 | \xcalways\section{Basics}\x |
| 2 | |
| 3 | \xcalways\subsection{Introduction and motivation}\x |
| 4 | |
| 5 | \begin{slide} |
| 6 | \topic{joke} |
| 7 | \head{Mandatory joke} |
| 8 | |
| 9 | An elderly Frenchman rises every morning at 5, goes out to the street in |
| 10 | front of his house, and sprinkles a white powder up and down the street. |
| 11 | |
| 12 | One day, a neighbour, who has watched his routine for many years, confronts |
| 13 | him. `What is this powder you sprinkle on the street every morning, |
| 14 | Pierre?' |
| 15 | |
| 16 | `It is elephant powder, \emph{mon ami},' the gentleman says. `It keeps the |
| 17 | elephants away.' |
| 18 | |
| 19 | `But Pierre,' says the neighbour. `Everybody knows that there are no |
| 20 | elephants in France.' |
| 21 | |
| 22 | Says the older man matter-of-factly, `I guess it must be working, then.' |
| 23 | \end{slide} |
| 24 | |
| 25 | The joke has its mandatory corresponding serious message. Cryptography is |
| 26 | like elephant powder. If it seems to work, and keeps the attackers -- our |
| 27 | elephants -- away, then we trust it. This isn't really very satisfactory. |
| 28 | When the elephant powder fails, a 2-ton elephant turns up, with three of its |
| 29 | chums in a Mini, and you notice it hiding upside-down in your bowl of |
| 30 | custard. Let's face it: elephants aren't good at being surreptitious. |
| 31 | |
| 32 | But if your cryptography is no good, you may never know. |
| 33 | |
| 34 | \begin{slide} |
| 35 | \topic{serious message} |
| 36 | \head{Cryptography is elephant powder} |
| 37 | |
| 38 | So, what can we do about the situation? |
| 39 | \begin{itemize} |
| 40 | \item Design simple cryptographic primitives, e.g., block ciphers, hash |
| 41 | functions. Develop techniques for analysing them, and attempt to stay |
| 42 | ahead of the bad guy. |
| 43 | \item Build useful constructions from trusted primitives in a modular way. |
| 44 | \emph{Prove that the constructions are secure.} |
| 45 | \end{itemize} |
| 46 | Here we look at this second part of the approach. |
| 47 | \end{slide} |
| 48 | |
| 49 | \xcalways\subsection{Approach}\x |
| 50 | |
| 51 | \begin{slide} |
| 52 | \head{The provable security approach} |
| 53 | |
| 54 | \begin{itemize} |
| 55 | \item Define notions of security. Now we know what to aim for, and what to |
| 56 | expect of our components. |
| 57 | \item Prove how the security of a construction relates to the security of |
| 58 | its primitives. If it breaks, we know who to blame. |
| 59 | \end{itemize} |
| 60 | \end{slide} |
| 61 | |
| 62 | \begin{slide} |
| 63 | \topic{adversaries} |
| 64 | \head{Adversaries} |
| 65 | |
| 66 | We model our adversary as a \emph{probabilistic algorithm}; i.e., the |
| 67 | algorithm is allowed to \emph{flip coins} to make decisions. The |
| 68 | adversary's output (for some input) follows a probability distribution. We |
| 69 | define what it means for an adversary to \emph{break} our construction, and |
| 70 | examine the probability with which this happens. |
| 71 | |
| 72 | We provide the adversary with \emph{oracles}: |
| 73 | \begin{itemize} |
| 74 | \item Oracles compute using secrets hidden from the adversary. |
| 75 | \item We count the number of \emph{queries} made to an oracle. |
| 76 | \item We can restrict the types of queries the adversary makes. |
| 77 | \end{itemize} |
| 78 | |
| 79 | Oracles are written as superscripts. For example, an adversary given a |
| 80 | chosen-plaintext oracle might be written as $A^{E_K(\cdot)}$. |
| 81 | \end{slide} |
| 82 | |
| 83 | \begin{slide} |
| 84 | \topic{the asymptotic approach} |
| 85 | \resetseq |
| 86 | \head{The asymptotic approach, \seq} |
| 87 | |
| 88 | A function $\nu\colon \N \to \R$ is \emph{negligible} if, for any integer |
| 89 | $c$, there exists an $n \in \N$ such that $0 \le \nu(k) < k^{-c}$ for all |
| 90 | $k \ge n$. That is, $\nu(k)$ is `eventually' less than any polynomial |
| 91 | function of $k$. |
| 92 | |
| 93 | We examine families of constructions, with a \emph{security parameter} $k$. |
| 94 | We say that a function is (asymptotically) secure in some sense if, for any |
| 95 | polynomial $p(k)$ there is a negligible function $\nu(k)$ such that, for |
| 96 | any construction in the family, parameterized by $k$, no adversary which |
| 97 | runs for time $p(k)$ has success probability better than $\nu(k)$. |
| 98 | \end{slide} |
| 99 | |
| 100 | \begin{slide} |
| 101 | \head{The asymptotic approach, \seq} |
| 102 | |
| 103 | Suppose we build an encryption scheme from a one-way function. We'd like |
| 104 | to prove that the encryption is good if the one-way function is secure. We |
| 105 | do this by contradiction: |
| 106 | \begin{enumerate} |
| 107 | \item Suppose an adversary $A$ breaks the encryption scheme with |
| 108 | better-than-negligible probability. |
| 109 | \item Show a polynomial-time \emph{reduction}: an algorithm which uses $A$ |
| 110 | to break the one-way function, in polynomial time, and with |
| 111 | better-than-negligible probability, |
| 112 | \item Claim that this violates the assumption of a secure one-way function. |
| 113 | \end{enumerate} |
| 114 | |
| 115 | This doesn't work with real constructions. We don't know where the |
| 116 | asymptotics set in, and they can conceal large constants. It's still |
| 117 | better than nothing. |
| 118 | \end{slide} |
| 119 | |
| 120 | \begin{slide} |
| 121 | \topic{the concrete (quantitative) approach} |
| 122 | \head{The concrete (quantitative) approach} |
| 123 | |
| 124 | We constrain the resources we allow the adversary: |
| 125 | \begin{itemize} |
| 126 | \item Running time (including program size). |
| 127 | \item Number of oracle queries. |
| 128 | \item Maximum size of oracle queries. |
| 129 | \end{itemize} |
| 130 | Write that something is \emph{$(t, q, \epsilon)$-secure} if no adversary |
| 131 | which runs in time $t$ and makes $q$ oracle queries can break it with |
| 132 | probability better than $\epsilon$. |
| 133 | |
| 134 | We make statements like `foo is $(t, q, 2 q \epsilon)$-secure if bar is $(t |
| 135 | + O(q), 2 q, \epsilon)$-secure'. |
| 136 | |
| 137 | This is a much more satisfactory approach. However, we still have to |
| 138 | \emph{assume} the security of our primitive operations. |
| 139 | \end{slide} |
| 140 | |
| 141 | \xcalways\subsection{Notation}\x |
| 142 | |
| 143 | \begin{slide} |
| 144 | \topic{boolean operators} |
| 145 | \resetseq |
| 146 | \head{Notation, \seq: boolean operators} |
| 147 | |
| 148 | If $P$ and $Q$ are \emph{predicates} -- i.e., either true or false -- then: |
| 149 | \begin{itemize} |
| 150 | \item $P \land Q$ is true if both $P$ \emph{and} $Q$ is true; |
| 151 | \item $P \lor Q$ is true if either $P$ \emph{or} $Q$ (or both) is true; |
| 152 | \item $\lnot P$ is true if $P$ is false; and |
| 153 | \item $P \implies Q$ is true if $Q$ is true or $P$ is false. |
| 154 | \end{itemize} |
| 155 | \end{slide} |
| 156 | |
| 157 | \begin{slide} |
| 158 | \topic{sets} |
| 159 | \head{Notation, \seq: sets} |
| 160 | |
| 161 | For our purposes, we can think of sets as being collections of objects. |
| 162 | |
| 163 | We use the usual notations for set membership ($x \in X$), intersection ($X |
| 164 | \cap Y$), union ($X \cup Y$) and subset containment ($X \subseteq Y$). The |
| 165 | \emph{empty set}, which contains no elements, is written $\emptyset$. |
| 166 | |
| 167 | The notation $\{\, f(x) \mid P(x) \,\}$ describes the set containing those |
| 168 | items $f(x)$ for those $x$ for which the predicate $P(x)$ is true. |
| 169 | |
| 170 | The \emph{cardinality} $|X|$ of a (finite) set $X$ is the number of |
| 171 | elements in the set. |
| 172 | |
| 173 | The power set $\powerset(X)$ of a set $X$ is the set of all subsets of $X$. |
| 174 | |
| 175 | The \emph{Cartesian product} of two sets $X \times Y$ is the set of all |
| 176 | ordered pairs $\{\, (x, y) \mid x \in X \land y \in Y \,\}$. We use |
| 177 | exponents to indicate the product of a set with itself: hence, $X^2 = X |
| 178 | \times X$. |
| 179 | |
| 180 | A \emph{relation} $R$ is a subset of a Cartesian product. We write $R(x, |
| 181 | y)$ if $(x, y) \in R$. Relations between two sets are often written as |
| 182 | infix symbols: e.g., $x \sim y$. |
| 183 | \end{slide} |
| 184 | |
| 185 | \begin{slide} |
| 186 | \head{Notation, \seq: sets (cont.)} |
| 187 | |
| 188 | In addition to strings, defined later, we use the following standard sets: |
| 189 | \begin{itemize} |
| 190 | \item the set $\Z$ of integers; |
| 191 | \item the set $\N = \{\, x \in \Z \mid x \ge 0 \,\}$ of natural numbers; |
| 192 | \item the set $\R$ of real numbers; |
| 193 | \item closed intervals $[a, b] = \{\, x \in \R \mid a \le x \le b \,\}$; |
| 194 | \item the finite field $\F_q$ of $q$ elements, and its multiplicative |
| 195 | subgroup $\F_q^* = \F_q \setminus \{0\}$; and |
| 196 | \item the ring $\Z/n\Z$ of residue classes modulo $n$ (i.e., if $x \in |
| 197 | \Z/n\Z$ and $a, b \in x$ then $a \equiv b \pmod{n}$), and its |
| 198 | multiplicative subgroup $(\Z/n\Z)^* = \Z/n\Z - \{\, x + n\Z \mid \gcd(x, |
| 199 | n) > 1 \,\}$. |
| 200 | \end{itemize} |
| 201 | \end{slide} |
| 202 | |
| 203 | \begin{slide} |
| 204 | \topic{functions} |
| 205 | \head{Notation, \seq: functions} |
| 206 | |
| 207 | A \emph{function} $f\colon X \to Y$ is a mapping which assigns every |
| 208 | element $x$ in the \emph{domain} $X$ a corresponding element $f(x)$ in the |
| 209 | \emph{range} (or sometimes \emph{codomain}) $Y$. The notation $\dom f$ |
| 210 | describes the domain of an arbitrary function; $\ran f$ describes its |
| 211 | range. |
| 212 | |
| 213 | We sometimes apply the function notation to sets, indicating that the |
| 214 | function should be applied pointwise; i.e., $f(Z) = \{ f(z) \mid z \in Z |
| 215 | \}$. The \emph{image} of a function $f$ is the set $f(\dom f)$. |
| 216 | |
| 217 | If $f\colon X \to Y$ preserves equality, i.e., $f(x) = f(x') \implies x = |
| 218 | x'$ for all $x, x' \in X$, then we say $f$ is \emph{injective} (or |
| 219 | \emph{1-to-1}). If $f(X) = Y$ then we say that it is \emph{surjective} (or |
| 220 | \emph{onto}). If $f$ is both injective and surjective then we say that it |
| 221 | is \emph{bijective}. In this case, there is a well-defined inverse |
| 222 | $f^{-1}\colon Y \to X$ defined by $f(f^{-1}(y)) = y$ for all $y \in Y$. |
| 223 | |
| 224 | If $f\colon X \to X$ (i.e., its domain and range are the same set) is |
| 225 | bijective, then we say that $f$ is a \emph{permutation on $X$}. |
| 226 | \end{slide} |
| 227 | |
| 228 | \begin{slide} |
| 229 | \head{Notation, \seq: functions (cont.)} |
| 230 | |
| 231 | We can consider a function $f\colon X \to Y$ to be a particular sort of |
| 232 | relation $f \subseteq X \times Y$, subject to the constraint that if $(x, |
| 233 | y) \in f$ and $(x, y') \in f$ then $y = y'$. |
| 234 | |
| 235 | We shall use this view in some of the algorithms we present. In addition, |
| 236 | we shall use the \emph{maplet} notation $x \mapsto y$ rather than the |
| 237 | ordered pair notation $(x, y)$ to reinforce the notion of a mapping. |
| 238 | |
| 239 | We might write, for example, |
| 240 | \begin{program} |
| 241 | $f \gets f \cup \{ x \mapsto y \}$; |
| 242 | \end{program} |
| 243 | to augment a function by the addition of a new mapping. This is clearly |
| 244 | only valid if $x \notin \dom f$ (or $f(x) = y$) initially. |
| 245 | \end{slide} |
| 246 | |
| 247 | \begin{slide} |
| 248 | \topic{strings} |
| 249 | \head{Notation, \seq: strings} |
| 250 | |
| 251 | An \emph{alphabet} is a finite set of \emph{symbols}. The one we'll use |
| 252 | most of the time is the set $\Sigma = \{0, 1\}$ of \emph{bits}. |
| 253 | |
| 254 | Suppose $A$ is an alphabet. The set of sequences of exactly $n$ symbols |
| 255 | from $A$ is written $A^n$. Hence, $\{0, 1\}^{64}$ is the set of all 64-bit |
| 256 | sequences. The set of (finite) \emph{strings} over an alphabet $A$ is $A^* |
| 257 | = \bigcup_{i \in \N} A^i$. The empty string is named $\emptystring$. |
| 258 | |
| 259 | The \emph{length} of a string $a \in A^*$, written $|a|$, is the natural |
| 260 | number $n$ where $a \in A^n$. |
| 261 | |
| 262 | If $x, y \in A^*$ are strings then their \emph{concatenation}, written $x |
| 263 | \cat y$, or sometimes just $x y$, is the result of writing the symbols in |
| 264 | $x$ followed by the symbols in $y$, in order. We have $|x y| = |x| + |y|$. |
| 265 | \end{slide} |
| 266 | |
| 267 | \begin{slide} |
| 268 | \head{Notation, \seq: strings (cont.)} |
| 269 | |
| 270 | There are natural (injective) mappings between bit strings and natural |
| 271 | numbers. |
| 272 | |
| 273 | If $x = x_0 x_1 \ldots x_{n-1} \in \{0, 1\}^*$ then we can associate with |
| 274 | it the natural number |
| 275 | \[ \overrightarrow{x} = \sum_{0 \le i < n} 2^i x_i. \] |
| 276 | |
| 277 | The other natural mapping is |
| 278 | \[ \overleftarrow{x} = \sum_{0 \le i < n} 2^{n-i-1} x_i. \] |
| 279 | It doesn't matter which you choose, as long as you're consistent. |
| 280 | |
| 281 | For simplicity's sake, we shall tend to switch between strings and the |
| 282 | numbers (and occasionally more exotic objects) they represent implicitly. |
| 283 | \end{slide} |
| 284 | |
| 285 | \begin{slide} |
| 286 | \topic{parsing} |
| 287 | \head{Notation, \seq: parsing} |
| 288 | |
| 289 | We'll find it useful to be able to break up strings in the algorithms we |
| 290 | present. We use the statement |
| 291 | \begin{program} |
| 292 | \PARSE $x$ \AS $n_0\colon x_0, n_1\colon x_1, \ldots, n_k\colon x_k$; |
| 293 | \end{program} |
| 294 | to mean that the string $x$ is broken up into individual strings $x_0$, |
| 295 | $x_1$, \ldots, $x_k$, such that |
| 296 | \begin{itemize} |
| 297 | \item $x = x_0 \cat x_1 \cat \cdots \cat x_k$; and |
| 298 | \item $|x_i| = n_i$ for all $0 \le i \le k$. |
| 299 | \end{itemize} |
| 300 | We may omit one of the $n_i$ length indicators, since it can be deduced |
| 301 | from the length of the string $x$ and the other $n_j$. |
| 302 | \end{slide} |
| 303 | |
| 304 | \begin{slide} |
| 305 | \topic{vectors} |
| 306 | \head{Notation, \seq: vectors} |
| 307 | |
| 308 | A \emph{vector} $\vect{x}$ is a finite ordered collection of elements from |
| 309 | some set $X$. If $\vect{x}$ contains $n$ elements then we write $\vect{x} |
| 310 | \in X^n$, and that $|\vect{x}| = n$. We write the individual elements as |
| 311 | $\vect{x}[0], \vect{x}[1], \ldots, \vect{x}[n - 1]$. |
| 312 | |
| 313 | We shall abuse set membership notation for vectors; i.e., we write $x \in |
| 314 | \vect{x}$ if there is an $i$ ($0 \le i < |\vect{x}|$) such that |
| 315 | $\vect{x}[i] = x$. |
| 316 | |
| 317 | When we apply functions to vectors, we mean that they are applied |
| 318 | pointwise, as for sets. Thus, if we write that $\vect{y} = |
| 319 | f(\vect{x})$ then $|\vect{y}| = |\vect{x}|$ and $\vect{y}[i] = |
| 320 | f(\vect{x}[i])$ for all $0 \le i < |\vect{x}|$. |
| 321 | \end{slide} |
| 322 | |
| 323 | \begin{slide} |
| 324 | \topic{distributions and randomness} |
| 325 | \head{Notation, \seq: distributions and randomness} |
| 326 | |
| 327 | A \emph{probability distribution} over a (countable) set $X$ is a |
| 328 | function $\mathcal{D}\colon X \to [0, 1]$ such that |
| 329 | \[ \sum_{x \in X} \mathcal{D}(x) = 1. \] |
| 330 | |
| 331 | The \emph{support} of $\mathcal{D}$, written $\supp \mathcal{D}$, is the |
| 332 | set $\{ x \in X \mid \mathcal{D}(x) \ne 0 \}$; i.e., those elements of $X$ |
| 333 | which occur with nonzero probability. |
| 334 | |
| 335 | We write $x \getsr \mathcal{D}$ in algorithms to indicate that $x$ is to be |
| 336 | chosen independently at random, according to the distribution |
| 337 | $\mathcal{D}$. The notation $x \inr \mathcal{D}$ indicates that $x$ has |
| 338 | been chosen at independently at random according to $\mathcal{D}$. |
| 339 | |
| 340 | The \emph{uniform distribution} over a (finite) set $X$ is |
| 341 | $\mathcal{U}_X\colon X \to [0, 1]$ defined by $\mathcal{U}_X(x) = 1/|X|$ |
| 342 | for all $x \in X$. We shall write $x \getsr X$ and $x \inr X$ as |
| 343 | convenient shorthands, meaning $x \getsr \mathcal{U}_X$ and $x \inr |
| 344 | \mathcal{U}_X$ respectively. |
| 345 | \end{slide} |
| 346 | |
| 347 | \xcalways\subsection{Background}\x |
| 348 | |
| 349 | \begin{slide} |
| 350 | \topic{distinguishability} |
| 351 | \resetseq |
| 352 | \head{Distinguishability, \seq} |
| 353 | |
| 354 | Suppose that $\mathcal{X}$ and $\mathcal{Y}$ are two probability |
| 355 | distributions. |
| 356 | |
| 357 | Let $X$ be a random variable distributed according to $\mathcal{X}$, and |
| 358 | let $Y$ be a random variable distributed according to $\mathcal{Y}$. We |
| 359 | say that $\mathcal{X}$ and $\mathcal{Y}$ are \emph{identically |
| 360 | distributed}, and write that $\mathcal{X} \equiv \mathcal{Y}$, if, for |
| 361 | all possible values $x$ of $X$, we have |
| 362 | \[ \Pr[X = x] = \Pr[Y = x]. \] |
| 363 | |
| 364 | Equivalently, we require that, for all $x \in \supp \mathcal{X}$ we have |
| 365 | \[ x \in \supp \mathcal{Y} \land \mathcal{X}(x) = \mathcal{Y}(y). \] |
| 366 | \end{slide} |
| 367 | |
| 368 | \begin{slide} |
| 369 | \head{Distinguishability, \seq: statistical closeness} |
| 370 | |
| 371 | Now we generalize the setting slightly. Consider two \emph{families} of |
| 372 | distributions, $\{\mathcal{X}_k\}_{k\in\N}$ and |
| 373 | $\{\mathcal{Y}_k\}_{k\in\N}$, parameterized by a security parameter $k$, |
| 374 | where $\dom\mathcal{X}_k = \dom\mathcal{Y}_k$. To make the asymptotics |
| 375 | work, we require that $|x| \le p(k)$ for some polynomial $p(\cdot)$, for |
| 376 | all $x \in \dom\mathcal{X}_k$. |
| 377 | |
| 378 | Fix a value of $k$. Again, let $X$ be distributed according to |
| 379 | $\mathcal{X}_k$, and let $Y$ be distributed according to $\mathcal{Y}_k$. |
| 380 | We say that $\{\mathcal{X}_k\}_{k \in \N}$ and $\{\mathcal{Y}_k\}_{k\in\N}$ |
| 381 | are \emph{statistically close}, and write that $\{\mathcal{X}_k\}_{k\in\N} |
| 382 | \statclose \{\mathcal{Y}_k\}_{k\in\N}$, if there is a negligible function |
| 383 | $\nu(\cdot)$ such that, for any $k \in \N$, |
| 384 | \[ \sum_{x\in\dom{\mathcal{X}_k}} |
| 385 | |{\Pr[X = x]} - \Pr[Y = x]| \le \nu(k). \]% |
| 386 | (Reminder: Saying that $\nu\colon \N \to \R$ is \emph{negligible} means |
| 387 | that, for any $c \in \Z$ there is an $n \in N$ such that $\nu(k) < |
| 388 | k^{-c}$.) |
| 389 | \end{slide} |
| 390 | |
| 391 | \begin{slide} |
| 392 | \head{Distinguishability, \seq: computational indistinguishability} |
| 393 | |
| 394 | We say that two families of distributions are computationally |
| 395 | indistinguishable if no `efficient' algorithm can tell them apart with |
| 396 | better than `negligible' probability. |
| 397 | |
| 398 | So, we say that $\{\mathcal{X}_k\}_{k\in\N}$ and |
| 399 | $\{\mathcal{Y}_k\}_{k\in\N}$ are \emph{computationally indistinguishable} |
| 400 | and write that $\{\mathcal{X}_k\}_{k\in\N} \compind |
| 401 | \{\mathcal{Y}_k\}_{k\in\N}$, if, for any probabilistic polynomial-time |
| 402 | algorithm $A$, there is a negligible function $\nu(\cdot)$ such that, for |
| 403 | any $k$: |
| 404 | \[ \Pr[x \getsr \mathcal{X}_k; b \gets A(x) : b = 1] - |
| 405 | \Pr[y \getsr \mathcal{Y}_k; b \gets A(y) : b = 1] \le \nu(k). \]% |
| 406 | Statistical closeness implies computational indistinguishability. |
| 407 | \end{slide} |
| 408 | |
| 409 | \begin{proof} |
| 410 | Let two statistically close distributions $\{\mathcal{X}_k\}_{k\in\N} |
| 411 | \statclose \{\mathcal{Y}_k\}_{y\in\N}$ be given. Fix some $k$, and let $Z |
| 412 | = \dom\mathcal{X}_k = \dom\mathcal{Y}_k$. Now note that the adversary's |
| 413 | advantage is given by $\sum_{z\in Z} \Pr[b \gets A(z) : b = 1] |
| 414 | |\mathcal{X}_k(z) - \mathcal{Y}_k(z)| \le \sum_{z\in Z} |\mathcal{X}_k(z) - |
| 415 | \mathcal{Y}_k(z)| \le \nu(k)$. Hence the two distributions are |
| 416 | computationally indistinguishable. |
| 417 | \end{proof} |
| 418 | |
| 419 | \begin{slide} |
| 420 | \topic{collisions} |
| 421 | \head{Collisions -- the Birthday `paradox'} |
| 422 | |
| 423 | Suppose we throw $q$ balls into $n$ bins at random (with $q \le n$). Let |
| 424 | $C_{q, n}$ be the event that, at the end of this, we have a bin containing |
| 425 | more than one ball -- a \emph{collision}. |
| 426 | |
| 427 | Let $B_{q, n}$ be the event that the $q$-th ball collides with a |
| 428 | previous one. Obviously, the worst case for this is when none of the other |
| 429 | balls have collided, so |
| 430 | \[ \Pr[B_{q, n}] \le \frac{q - 1}{n}. \] |
| 431 | Then |
| 432 | \begin{eqnarray*}[rl] |
| 433 | \Pr[C_{q, n}] |
| 434 | &\le \Pr[B_{2, n}] + \Pr[B_{3, n}] + \cdots + \Pr[B_{q, n}] \\ |
| 435 | &\le \frac{1}{n} + \frac{2}{n} + \cdots + \frac{q - 1}{n} \\ |
| 436 | &= \frac{q(q - 1)}{2 n}. |
| 437 | \end{eqnarray*} |
| 438 | This is an extremely useful result, and we shall need it often. |
| 439 | \end{slide} |
| 440 | |
| 441 | \xcalways\subsection{Primitives}\x |
| 442 | |
| 443 | \begin{slide} |
| 444 | \topic{one-way functions} |
| 445 | \resetseq |
| 446 | \head{One-way functions, \seq: introduction} |
| 447 | |
| 448 | Intuition: a one-way function is easy to compute but hard to invert. |
| 449 | |
| 450 | Choose a function $f\colon X \to Y$. Let $I$ be a prospective inverter. |
| 451 | Now we play a game: |
| 452 | \begin{enumerate} |
| 453 | \item Choose $x \in X$ at random. Compute $y = f(x)$. |
| 454 | \item Let $x'$ be the output of $I$ when run on input $y$. |
| 455 | \item We say that $I$ `wins' if $f(x') = y$; otherwise it loses. |
| 456 | \end{enumerate} |
| 457 | Note that we don't care whether $x = x'$. |
| 458 | |
| 459 | Examples: SHA-1, or $x \mapsto g^x \bmod p$. |
| 460 | \end{slide} |
| 461 | |
| 462 | \begin{slide} |
| 463 | \head{One-way functions, \seq: formalism} |
| 464 | |
| 465 | The \emph{success probability} of an inverter $I$ against the function $f$ |
| 466 | is |
| 467 | \[ \Succ{owf}{f}(I) = |
| 468 | \Pr[x \getsr X; |
| 469 | y \gets f(x); |
| 470 | x' \gets I(y) : |
| 471 | f(x') = y] \]% |
| 472 | where the probability is taken over all choices of $x$ and all coin flips |
| 473 | made by $I$. |
| 474 | |
| 475 | We measure the \emph{insecurity} of a one-way function (OWF) by maximizing |
| 476 | over possible inverters: |
| 477 | \[ \InSec{owf}(f; t) = \max_I \Succ{owf}{f}(I) \] |
| 478 | where the maximum is taken over all $I$ running in time $t$. |
| 479 | |
| 480 | If $\InSec{owf}(f; t) \le \epsilon$ then we say that $f$ is a \emph{$(t, |
| 481 | \epsilon)$-secure one-way function}. |
| 482 | \end{slide} |
| 483 | |
| 484 | \begin{slide} |
| 485 | \head{One-way functions, \seq: trapdoors} |
| 486 | |
| 487 | Intuition: a \emph{trapdoor} is secret information which makes inverting a |
| 488 | one-way function easy. This is most useful when the one-way function is a |
| 489 | permutation. A trapdoor one-way function generator $\mathcal{T} = (G, f, |
| 490 | T)$ is a triple of algorithms: |
| 491 | |
| 492 | \begin{itemize} |
| 493 | \item The probabilistic algorithm $G$ is given some parameter $k$ and |
| 494 | returns a pair $(P, K)$, containing the public parameters $P$ for |
| 495 | computing an instance of the one-way function, and the secret trapdoor |
| 496 | information $K$ for inverting it. We write $(P, K) \in G(k)$. |
| 497 | |
| 498 | \item The algorithm $f$ implements the one-way function. That is, if $(P, |
| 499 | K) \in G(k)$ then $f(P, \cdot)$ (usually written $f_P(\cdot)$) is a |
| 500 | one-way function. |
| 501 | |
| 502 | \item The algorithm $T$ inverts $f$ using the trapdoor information. That |
| 503 | is, if $(P, K) \in G(k)$ and $y = f_P(x)$ for some $x$, then $y = |
| 504 | f_P(T(K, y))$. We usually write $T_K(\cdot)$ instead of $T(K, \cdot)$. |
| 505 | \end{itemize} |
| 506 | \end{slide} |
| 507 | |
| 508 | \begin{slide} |
| 509 | \topic{pseudorandom generators (PRGs)} |
| 510 | \head{Pseudorandom generators (PRGs)} |
| 511 | |
| 512 | A pseudorandom generator (PRG) `stretches' an input seed into a longer |
| 513 | string which `looks' random. |
| 514 | |
| 515 | Let $G\colon \{0, 1\}^k \to \{0, 1\}^L$ be a function from $k$-bit strings |
| 516 | to $L$-bit strings. The \emph{advantage} of a distinguisher $D$ against |
| 517 | $G$ is: |
| 518 | \begin{eqnarray*}[rl] |
| 519 | \Adv{prg}{G}(D) = & |
| 520 | \Pr[x \getsr \{0, 1\}^k; y \gets G(x) : D(y) = 1] - {}\\ |
| 521 | & \Pr[y \getsr \{0, 1\}^L : D(y) = 1]. |
| 522 | \end{eqnarray*} |
| 523 | The \emph{insecurity} is simply the maximum advantage: |
| 524 | \[ \InSec{prg}(G; t) = \max_D \Adv{prg}{G}(D) \] |
| 525 | where the maximum is taken over all distinguishers $D$ running in time |
| 526 | $t$. If $\InSec{prg}(G; t) \le \epsilon$ then we also say that $G$ is a |
| 527 | $(t, \epsilon)$-secure PRG\@. |
| 528 | \end{slide} |
| 529 | |
| 530 | \begin{exercise} |
| 531 | We say that a PRG $g\colon \{0, 1\}^k \to \{0, 1\}^L$ is \emph{trivial} if |
| 532 | $k \ge L$. |
| 533 | \begin{enumerate} |
| 534 | \item Show that trivial PRGs exist. |
| 535 | \item Show that if $g$ is nontrivial, then $g$ is also a one-way function, |
| 536 | with |
| 537 | \[ \InSec{owf}(g; t) \le \InSec{prg}(g; t) + 2^{k-L}. \] |
| 538 | \end{enumerate} |
| 539 | \answer% |
| 540 | \begin{parenum} |
| 541 | \item The identity function $I(x) = x$ is a trivial PRG, with |
| 542 | $\InSec{prg}(I, t) = 0$, as is easily seen from the definition. |
| 543 | \item Suppose $A$ inverts $g$. Then consider adversary $B(y)$: \{ $x \gets |
| 544 | A(y)$; \IF $g(x) = y$ \THEN \RETURN $1$; \ELSE \RETURN $0$;~\}. If $y$ |
| 545 | is the output of $g$, then $A$ inverts $y$ with probability |
| 546 | $\Succ{owf}{g}(A)$; if $y$ is random in $\{0, 1\}^L$ then there is a |
| 547 | probability at least $1 - 2^{k-L}$ that $y$ has \emph{no} inverse, |
| 548 | proving the result. Note that \cite{Wagner:2000:PSU} provides a better |
| 549 | security bound than this simplistic analysis. |
| 550 | \end{parenum} |
| 551 | \end{exercise} |
| 552 | |
| 553 | \begin{exercise} |
| 554 | \label{ex:dbl-prg} |
| 555 | Suppose that we have a \emph{length-doubling} PRG $g\colon \{0, 1\}^k \to |
| 556 | \{0, 1\}^{2k}$. Let $g_0(\cdot)$ be the first $k$ bits of $g(x)$ and |
| 557 | $g_1(\cdot)$ be the second $k$ bits. Define the sequence of generators |
| 558 | $g^{(i)}$ (for $i >= 1$) by |
| 559 | \[ g^{(1)}(x) = g(x); \qquad |
| 560 | g^{(i+1)}(x) = g_0(x) \cat g^{(i)}(g_1(x)). \]% |
| 561 | Relate the security of $g^{(i)}$ to that of $g$. |
| 562 | \answer% |
| 563 | The description of the function $g^{(i)}$ is deliberately terse and |
| 564 | unhelpful. It probably helps understanding if you make a diagram. |
| 565 | |
| 566 | Let $A$ be an adversary running in time $t$ and attacking $g^{(i+1)}$. |
| 567 | Firstly, we attack $g$: consider adversary $B(y)$: \{ \PARSE $y$ \AS $y_0, |
| 568 | k\colon y_1$; $z \gets g^{(i)}$; $b \gets A(y_0 \cat z)$; \RETURN $b$;~\}. |
| 569 | Then $\Adv{prg}{g}(B) \ge \Adv{prg}{g^{(i+1)}}(A) + \delta$, so |
| 570 | $\InSec{prg}(g^{(i+1)}; t) \le \InSec{prg}(g; t) + \delta$, where |
| 571 | \begin{eqnarray*}[rl] |
| 572 | \delta = &\Pr[x_0 \gets \{0, 1\}^k; x_1 \gets \{0, 1\}^k; |
| 573 | y \gets g^{(i)}(x) : A(x_0 \cat y) = 1] - \\ |
| 574 | &\Pr[y \getsr \{0, 1\}^{(i+2)k} : A(y) = 1]. |
| 575 | \end{eqnarray*} |
| 576 | We attack $g^{(i)}$ to bound $\delta$: consider adversary $C(y)$: \{ $x_0 |
| 577 | \getsr \{0, 1\}^k$; $b \gets A(x_0 \cat y)$; \RETURN $b$;~\}. Now $\delta |
| 578 | \le \Adv{prg}{g^{(i)}}(C) \le \InSec{prg}(g^{(i)}; t)$. So by induction, |
| 579 | \[ \InSec{prg}(g^{(i)}; t) \le i \cdot \InSec{prg}(g; t). \] |
| 580 | \end{exercise} |
| 581 | |
| 582 | \begin{slide} |
| 583 | \topic{advantage} |
| 584 | \head{Notes about advantage} |
| 585 | |
| 586 | Advantage is a concept used in many definitions of security notions: |
| 587 | \begin{eqnarray*}[rl] |
| 588 | \Adv{}{}(A) = & |
| 589 | \Pr[\text{$A$ returns 1 in setting $a$}] - {} \\ |
| 590 | & \Pr[\text{$A$ returns 1 in setting $b$}]. |
| 591 | \end{eqnarray*} |
| 592 | \begin{enumerate} |
| 593 | \item We have $-1 \le \Adv{}{}(A) \le +1$. |
| 594 | \item Zero means that the adversary couldn't distinguish. |
| 595 | \item Negative advantage means the adversary got them the wrong way |
| 596 | around. There is another adversary which uses the same resources but has |
| 597 | positive advantage. |
| 598 | \item \label{item:adv-guess} If $A$ is attempting to guess some hidden bit |
| 599 | $b^* \inr \{0, 1\}$, we have |
| 600 | \[ \Pr[b \gets A : b = b^*] = \frac{\Adv{}{}(A)}{2} + \frac{1}{2}. \] |
| 601 | \end{enumerate} |
| 602 | \end{slide} |
| 603 | |
| 604 | \begin{proof} |
| 605 | Let $b$ be the bit that $A$ returns, and let $b^*$ be the experiment's |
| 606 | hidden bit. Then |
| 607 | \[ \Adv{}{}(A) = \Pr[b = 1 \mid b^* = 1] - \Pr[b = 1 \mid b^* = 0]. \] |
| 608 | Addressing the above claims in order: |
| 609 | \begin{enumerate} |
| 610 | \item By definition of probability, $0 \le \Pr[b = 1 \mid b^* = 1] \le 1$ |
| 611 | and $0 \le \Pr[b = 1 \mid b^* = 0]$, so their absolute difference can be |
| 612 | at most 1. |
| 613 | \item This is a corollary of \ref{item:adv-guess}. |
| 614 | \item Consider the adversary $\bar{A}$ which runs $A$ and returns the |
| 615 | complement bit $\bar{b} = b \xor 1$. Then |
| 616 | \begin{eqnarray*}[rl] |
| 617 | \Adv{}{}(\bar{A}) |
| 618 | &= \Pr[\bar{b} = 1 \mid b^* = 1] - \Pr[\bar{b} = 1 \mid b^* = 0] \\ |
| 619 | &= \Pr[b = 0 \mid b^* = 1] - \Pr[b = 0 \mid b^* = 0] \\ |
| 620 | &= (1 - \Pr[b = 1 \mid b^* = 1]) - (1 - \Pr[b = 1 \mid b^* = 0]) \\ |
| 621 | &= \Pr[b = 1 \mid b^* = 0] - \Pr[b = 1 \mid b^* = 1] \\ |
| 622 | &= -\Adv{}{}(A). |
| 623 | \end{eqnarray*} |
| 624 | \item Note that $\Pr[b^* = 1] = \Pr[b^* = 0] = \frac{1}{2}$. Then |
| 625 | \begin{eqnarray*}[rl] |
| 626 | \Pr[b = b^*] |
| 627 | &= \Pr[b = 1 \land b^* = 1] + \Pr[b = 0 \land b^* = 0] \\ |
| 628 | &= \frac{1}{2}(\Pr[b = 1 \mid b^* = 1] + \Pr[b = 1 \mid b^* = 0]) \\ |
| 629 | &= \frac{1}{2}(\Pr[b = 1 \mid b^* = 1] + |
| 630 | (1 - \Pr[b = 0 \mid b^* = 0])) \\ |
| 631 | &= \frac{1}{2}(1 + \Pr[b = 1 \mid b^* = 1] - |
| 632 | \Pr[b = 0 \mid b^* = 0]) \\ |
| 633 | &= \frac{\Adv{}{}(A)}{2} + \frac{1}{2}. |
| 634 | \end{eqnarray*} |
| 635 | \end{enumerate} |
| 636 | All present and correct. |
| 637 | \end{proof} |
| 638 | |
| 639 | \begin{slide} |
| 640 | \topic{pseudorandom functions (PRFs)} |
| 641 | \head{Pseudorandom functions (PRFs)} |
| 642 | |
| 643 | A \emph{pseudorandom function family} (PRF) is a collection of functions |
| 644 | $F_K\colon \{0, 1\}^l \to \{0, 1\}^L$, where $K$ is some index, typically |
| 645 | from a set of fixed-size strings $\{0, 1\}^k$. We shall often consider a |
| 646 | PRF to be a single function $F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0, |
| 647 | 1\}^L$. |
| 648 | |
| 649 | We want to say that $F$ is a strong PRF if adversaries find it hard to |
| 650 | distinguish an instance $F_K$ from a function chosen completely at random |
| 651 | with the same `shape'. |
| 652 | |
| 653 | We provide the adversary with an \emph{oracle}, either for a randomly |
| 654 | selected $F_K$, or for completely random function, and ask it to try and |
| 655 | say which it is given. |
| 656 | |
| 657 | We write $\Func{l}{L}$ as the set of \emph{all} functions from $\{0, 1\}^l$ |
| 658 | to $\{0, 1\}^L$. |
| 659 | \end{slide} |
| 660 | |
| 661 | \begin{slide} |
| 662 | \head{Pseudorandom functions (cont.)} |
| 663 | |
| 664 | We define the advantage of a distinguisher $D$ against the PRF $F$ as |
| 665 | follows: |
| 666 | \begin{eqnarray*}[rl] |
| 667 | \Adv{prf}{F}(D) = & |
| 668 | \Pr[K \getsr \{0, 1\}^k : D^{F_K(\cdot)} = 1] - {}\\ |
| 669 | & \Pr[R \getsr \Func{l}{L} : D^{R(\cdot)} = 1]. |
| 670 | \end{eqnarray*} |
| 671 | The insecurity of the PRF is then measured as |
| 672 | \[ \InSec{prf}(F; t, q) = \max_D \Adv{prf}{F}(D) \] |
| 673 | where the maximum is taken over all distinguishers $D$ which run for time |
| 674 | $t$ and make $q$ oracle queries. As is usual, if $\InSec{prf}(F; t, q) |
| 675 | \le \epsilon$ then we say that $F$ is a $(t, q, \epsilon)$-secure PRF. |
| 676 | \end{slide} |
| 677 | |
| 678 | \begin{slide} |
| 679 | \topic{pseudorandom permutations (PRPs)} |
| 680 | \head{Pseudorandom permutations (PRPs)} |
| 681 | |
| 682 | We define a \emph{pseudorandom permutation family} (PRP) in a similar way |
| 683 | to the PRFs we've already seen. A PRP is a family $F_K\colon \{0, 1\}^L |
| 684 | \to \{0, 1\}^L$ is a of permutations, indexed by elements of some finite |
| 685 | set, e.g., $\{0, 1\}^k$. We shall often consider a PRP to be a single |
| 686 | function $F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0, 1\}^L$. |
| 687 | |
| 688 | Let $\Perm{L}$ be the set of \emph{all} permutations over the set of |
| 689 | $L$-bit strings $\{0, 1\}^L$. |
| 690 | |
| 691 | The advantage of a distinguisher $D$ against the PRP $F$ is |
| 692 | \begin{eqnarray*}[rl] |
| 693 | \Adv{prp}{F}(D) = & |
| 694 | \Pr[K \getsr \{0, 1\}^k : D^{F_K(\cdot)} = 1] - {}\\ |
| 695 | & \Pr[R \getsr \Perm{L} : D^{R(\cdot)} = 1]. |
| 696 | \end{eqnarray*} |
| 697 | |
| 698 | We define $\InSec{prp}(F; t, q) = \max_D \Adv{prp}{F}(D)$ exactly as for |
| 699 | PRFs, and the notion of $(t, q, \epsilon)$-security is the same. |
| 700 | \end{slide} |
| 701 | |
| 702 | \begin{slide} |
| 703 | \head{Super pseudorandom permutations} |
| 704 | |
| 705 | PRPs are bijective. A \emph{super PRP} is a PRP which remains secure when |
| 706 | the distinguisher is allowed to make inverse queries: |
| 707 | \begin{eqnarray*}[rl] |
| 708 | \Adv{sprp}{F}(D) = & |
| 709 | \Pr[K \getsr \{0, 1\}^k : D^{F_K(\cdot), F_K^{-1}(\cdot)} = 1] - {} \\ |
| 710 | & \Pr[R \getsr \Perm{L} : D^{R(\cdot), R^{-1}(\cdot)} = 1]. |
| 711 | \end{eqnarray*} |
| 712 | Since there are two oracles, we count queries to both when evaluating the |
| 713 | insecurity: |
| 714 | \[ \InSec{sprp}(F; t, q, q') = \max_D \Adv{sprp}{F}(D) \] |
| 715 | where the maximum is taken over all distinguishers $D$ which run for time |
| 716 | $t$, make $q$ queries to the standard oracle, and $q'$ queries to the |
| 717 | inverse oracle. If $\InSec{sprp}(F; t, q, q') \le \epsilon$ then we say |
| 718 | $F$ is a $(t, q, q', \epsilon)$-secure super PRP\@. |
| 719 | \end{slide} |
| 720 | |
| 721 | \begin{exercise} |
| 722 | Note that the key length hasn't appeared anywhere in the definition of |
| 723 | insecurity for a PRP. Derive lower bounds for the insecurity of a PRP with |
| 724 | a $k$-bit key. |
| 725 | \answer% |
| 726 | Let $E\colon \{0, 1\}^k \times \{0, 1\}^L \to \{0, 1\}^L$ be a PRP. Fix |
| 727 | $n$ and $c$. Then consider adversary $S^{E(\cdot)}$: \{ \FOR $i = 0$ \TO |
| 728 | $c - 1$ \DO $y[i] \gets E(i)$; \FOR $K = 0$ \TO $n - 1$ \DO \{ $i \gets 0$; |
| 729 | $\id{good} \gets 1$; \WHILE $i < c \land \id{good} = 1$ \DO \{ \IF $E_K(i) |
| 730 | \ne y[i]$ \THEN $\id{good} \gets 0$;~\} \IF $\id{good} = 1$ \THEN \RETURN |
| 731 | $1$;~\}~\}. Then $\Adv{prp}{E}(S) \ge n(2^{-k} - 2^{-Lc})$. |
| 732 | \end{exercise} |
| 733 | |
| 734 | \begin{slide} |
| 735 | \resetseq |
| 736 | \head{PRPs are PRFs, \seq} |
| 737 | |
| 738 | We model block ciphers as families of PRPs (not super PRPs). Most of the |
| 739 | analysis works best on PRFs, though. We show that a PRP makes a `pretty |
| 740 | good' PRF, as long as it's not over-used. |
| 741 | |
| 742 | Let $F$ be any PRP family. Then |
| 743 | \[ \InSec{prf}(F; t, q) \le |
| 744 | \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}}. \]% |
| 745 | This is a useful result. As long as $q^2$ is small compared to $2^L$ -- |
| 746 | the block size -- then a PRP makes a good PRF. |
| 747 | |
| 748 | The value $2^{L/2}$ is often called the \emph{Birthday bound}. We shall |
| 749 | meet it often when we examine modes of operation. We shall examine the |
| 750 | proof, because it illustrates some useful techniques. |
| 751 | \end{slide} |
| 752 | |
| 753 | \begin{slide} |
| 754 | \head{Shoup's lemma} |
| 755 | |
| 756 | This handy lemma states that the difference in the probability of some |
| 757 | outcome between the two games is bounded above by the probability that the |
| 758 | games differ. |
| 759 | |
| 760 | \begin{lemma}[Shoup \cite{Shoup:2001:OAEPR}] |
| 761 | \label{lem:shoup} |
| 762 | If $X$, $Y$ and $F$ are events, and $\Pr[X \land \lnot F] = \Pr[Y \land |
| 763 | \lnot F]$ then $|{\Pr[X]} - \Pr[Y]| \le \Pr[F]$. |
| 764 | \end{lemma} |
| 765 | \begin{proof} |
| 766 | We have: |
| 767 | \begin{eqnarray*}[rll] |
| 768 | \Pr[X] &= \Pr[X \land F] &+ \Pr[X \land \lnot F] \\ |
| 769 | \Pr[Y] &= \Pr[Y \land F] &+ \Pr[Y \land \lnot F] |
| 770 | \end{eqnarray*} |
| 771 | Subtracting gives |
| 772 | \[ |{\Pr[X]} - \Pr[Y]| = |{\Pr[X \land F]} - |
| 773 | \Pr[Y \land F]| \le \Pr[F] \]% |
| 774 | as required. |
| 775 | \end{proof} |
| 776 | \end{slide} |
| 777 | |
| 778 | \begin{slide} |
| 779 | \head{PRPs are PRFs, \seq: proof} |
| 780 | |
| 781 | Let $F\colon \{0, 1\}^k \times \{0, 1\}^L \to \{0, 1\}^L$ be a pseudorandom |
| 782 | permutation. We aim to show that $F$ is also a pseudorandom function. |
| 783 | |
| 784 | Let $A$ be an adversary which distinguishes~$F$ from a pseudorandom |
| 785 | function in time~$t$, after making $q$ oracle queries. We consider a |
| 786 | sequence of games $\G{i}$ played with the adversary. In each game $\G{i}$, |
| 787 | let $S_i$ be the event that the adversary returns~$1$ at the end of the |
| 788 | game. |
| 789 | |
| 790 | Game~$\G0$ is the `random function' game. We given $A$ an oracle |
| 791 | containing a random function $R \inr \Func{L}{L}$. |
| 792 | |
| 793 | Game~$\G1$ is the `PRF' game. We give $A$ an oracle which computes |
| 794 | $F_K(\cdot)$ for some randomly chosen $K \inr \{0, 1\}^k$. |
| 795 | |
| 796 | By definition, then, |
| 797 | \[ \Adv{prf}{F}(A) = \Pr[S_1] - \Pr[S_0]. \] |
| 798 | \end{slide} |
| 799 | |
| 800 | \begin{slide} |
| 801 | \head{PRPs are PRFs, \seq: proof (cont.)} |
| 802 | |
| 803 | Let $x_0, x_1, \ldots, x_{q-1}$ be the oracle queries made by $A$, and let |
| 804 | $y_0, y_1, \ldots, y_{q-1}$ be the corresponding responses. |
| 805 | |
| 806 | Game~$\G2$ works in the same way as $\G0$, except that if there is a |
| 807 | \emph{collision} in the query replies (i.e., $y_i = y_j$ but $x_i \ne x_j$ |
| 808 | for any $0 \le i, j < q$) then we stop the game immediately. Let $F_2$ be |
| 809 | the event that this occurs. |
| 810 | |
| 811 | Because $\G2$ behaves exactly the same as $\G0$ unless $F_2$ occurs, we |
| 812 | must have |
| 813 | \[ \Pr[S_2 \land \lnot F_2] = \Pr[S_0 \land \lnot F_2] \] |
| 814 | so we invoke Lemma~\ref{lem:shoup} and discover that |
| 815 | \[ |{\Pr[S_2]} - \Pr[S_0]| \le \Pr[F_2]. \] |
| 816 | Using the earlier result on collisions, it's easy to see that |
| 817 | \[ \Pr[F_2] \le \frac{q(q - 1)}{2^{L+1}}. \] |
| 818 | \end{slide} |
| 819 | |
| 820 | \begin{slide} |
| 821 | \head{PRPs are PRFs, \seq: proof (cont.)} |
| 822 | |
| 823 | Game~$\G3$ works in the same way as $\G2$, except that we use a random |
| 824 | permutation $P \inr \Perm{L}$ instead of a random function $R \inr |
| 825 | \Func{L}{L}$. Firstly, note that $F_2$ can't occur in $\G3$. But, if |
| 826 | $F_2$ doesn't occur in $\G2$ (i.e., there is no collision), then the random |
| 827 | function is indistinguishable from a random permutation. So |
| 828 | \[ \Pr[S_3] = \Pr[S_2]. \] |
| 829 | |
| 830 | By definition, we have |
| 831 | \[ \Adv{prp}{F}(A) = \Pr[S_1] - \Pr[S_3]. \] |
| 832 | We can now tie all of this together. |
| 833 | \end{slide} |
| 834 | |
| 835 | \begin{slide} |
| 836 | \head{PRPs are PRFs, \seq: proof (cont.)} |
| 837 | |
| 838 | A simple calculation shows that |
| 839 | \begin{eqnarray*}[rl] |
| 840 | \Adv{prf}{F}(A) &= \Pr[S_1] - \Pr[S_0] \\ |
| 841 | &\le \Pr[S_1] - \Pr[S_2] + \Pr[F_2] \\ |
| 842 | &= \Pr[S_1] - \Pr[S_3] + \Pr[F_2] \\ |
| 843 | &= \Adv{prp}{F}(A) + \Pr[F_2] \\ |
| 844 | &\le \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}}. |
| 845 | \end{eqnarray*} |
| 846 | In the second line, we used the bound we computed on the absolute |
| 847 | difference between $\Pr[S_2]$ and $\Pr[S_0]$; in the third, we noted that |
| 848 | $\Pr[S_2] = \Pr[S_3]$; in the fourth, we used the definition of advantage |
| 849 | against a PRP; and in the fifth we used the definition of insecurity for a |
| 850 | PRP. |
| 851 | \end{slide} |
| 852 | |
| 853 | \begin{slide} |
| 854 | \head{PRPs are PRFs, \seq: proof (cont.)} |
| 855 | |
| 856 | Finally, we imposed no restrictions on $A$, except that it run in time $t$ |
| 857 | and make $q$ oracle queries. So our bound |
| 858 | \[ \Adv{prf}{F}(A) \le \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}} \]% |
| 859 | is true for \emph{any} such adversary $A$, and in particular, it's true for |
| 860 | the most successful adversary running with those resource bounds. |
| 861 | |
| 862 | Hence, we can maximize, showing that |
| 863 | \[ \InSec{prf}(F; t, q) \le |
| 864 | \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}} \]% |
| 865 | as required. |
| 866 | \end{slide} |
| 867 | |
| 868 | \begin{slide} |
| 869 | \topic{hash functions} |
| 870 | \resetseq |
| 871 | \head{Hash functions, \seq: properties} |
| 872 | |
| 873 | Hash functions like MD5 and SHA-1 are extremely useful primitives. What |
| 874 | properties do we expect of them? This out to be an extremely difficult |
| 875 | question to answer. |
| 876 | \begin{itemize} |
| 877 | \item One-wayness. We've seen a definition for this already. But it's not |
| 878 | enough. |
| 879 | \item Collision-resistance. This is the property usually claimed as the |
| 880 | requirement for use in digital signature systems. We'll look at this |
| 881 | later. |
| 882 | \item Randomness. What does this mean, when the function is completely |
| 883 | public? A distinguishability criterion is clearly hopeless. |
| 884 | \end{itemize} |
| 885 | \end{slide} |
| 886 | |
| 887 | \begin{slide} |
| 888 | \head{Hash functions, \seq: Merkle-Damg\aa{}rd iterated hashing |
| 889 | \cite{Damgaard:1990:DPH, Merkle:1991:FSE}} |
| 890 | |
| 891 | Let $F\colon \{0, 1\}^{k+L} \to \{0, 1\}^k$ be a \emph{compression} |
| 892 | function. Now consider the function $H\colon \{0, 1\}^* \to \{0, 1\}^k$ |
| 893 | which transforms an input string $x$ as follows: |
| 894 | \begin{enumerate} |
| 895 | \item Pad $x$ to a multiple of $L$ bits in some injective way. Divide the |
| 896 | padded message into $L$-bit blocks $x_0$, $x_1$, \ldots, $x_{n-1}$. |
| 897 | \item Fix some $k$-bit constant $I$. Let $I_0 = I$. Define $I_{i+1} = |
| 898 | F(I_i \cat x_i)$ for $0 \le i < n$. |
| 899 | \item The result $H(x) = I_n$. |
| 900 | \end{enumerate} |
| 901 | |
| 902 | Suppose we have two strings $x \ne y$, such that $H(x) = H(y)$; i.e., a |
| 903 | \emph{collision}. Then \emph{either} we can find a collision for $F$ |
| 904 | \emph{or} a string $z$ for which $F(z) = I$. (This is why initialization |
| 905 | vectors for hash functions have such obviously regular forms.) |
| 906 | \end{slide} |
| 907 | |
| 908 | \begin{proof} |
| 909 | Let $x_0, x_1, \ldots, x_{n-1}$ and $x'_0, x'_1, \ldots, x'_{n'-1}$ be |
| 910 | the $l$-bit blocks of two distinct (padded) messages, and without loss |
| 911 | of generality suppose that $n \ge n'$. Let $I_0 = I'_0 = I$, let |
| 912 | $I_{i+1} = F(I_i \cat x_i)$, and $I'_{i+1} = F(I'_i \cat x'_i)$. We |
| 913 | have $I_n = I'_{n'}$. |
| 914 | |
| 915 | We prove the result by induction on $n$. The case $n = 0$ is trivially |
| 916 | true, since there is only one zero-block message. Suppose, then, that the |
| 917 | result is true for $n$-block messages. There are three cases to consider. |
| 918 | Firstly, if $n' = 0$ then $F(I_n \cat x_n) = I$. Secondly, if $I_n \ne |
| 919 | I'_{n'}$ or $x_n \ne x'_{n'}$, then we have a collision, for $F(I_n \cat |
| 920 | x_n) = I_n = I'_{n'} = F(I'_{n'} \cat x'_{n'})$. Finally, if $I_n = |
| 921 | I'_{n'}$ and $x_n = x'_{n'}$ then we remove the final block from both |
| 922 | messages, and because the remaining messages must differ in at least one |
| 923 | block, we can apply the inductive hypothesis on these shorter messages to |
| 924 | complete the proof. |
| 925 | \end{proof} |
| 926 | |
| 927 | \begin{slide} |
| 928 | \head{Hash functions, \seq: Merkle-Damg\aa{}rd iterated hashing (cont.)} |
| 929 | |
| 930 | \vfil |
| 931 | \[ \begin{graph} |
| 932 | []!{0; <2cm, 0cm>: <0cm, 0.9cm>::} |
| 933 | *+=(1, 0)+[F]{\mathstrut I_0 = I} :[d] *+[F]{F}="f" |
| 934 | [urrr] *+=(3, 0)+[F]{\mathstrut x_0} :`d"f" "f" :[d] |
| 935 | *+=(1, 0)+[F]{\mathstrut I_1} :[d] *+[F]{F}="f" |
| 936 | [urrr] *+=(3, 0)+[F]{\mathstrut x_1} :`d"f" "f" :@{-->}[dd] |
| 937 | *+=(1, 0)+[F]{\mathstrut I_{n-1}} :[d] *+[F]{F}="f" |
| 938 | [urrr] *+=(3, 0)+[F]{\mathstrut x_{n-1}} :`d"f" "f" :[d] |
| 939 | *+=(1, 0)+[F:thicker]{\mathstrut H(x) = I_n} |
| 940 | \end{graph} \] |
| 941 | \vfil |
| 942 | \end{slide} |
| 943 | |
| 944 | \begin{slide} |
| 945 | \head{Hash functions, \seq: any-collision resistance} |
| 946 | |
| 947 | The statement usually made about a `good' hash function $h$ is that it |
| 948 | should be `difficult' to find a collision: i.e., two preimages $x \ne y$ |
| 949 | where $H(x) = H(y)$. How do we formalize this? Here's one attempt: |
| 950 | \begin{eqlines*} |
| 951 | \Succ{acr}{H}(A) = \Pr[(x, y) \gets A : x \ne y \land H(x) = H(y)]; \\ |
| 952 | \InSec{acr}(H; t) = \max_A \Succ{acr}{H}(A). |
| 953 | \end{eqlines*} |
| 954 | But this doesn't work. There clearly \emph{exists} an adversary which |
| 955 | already `knows' the a collision for $H$ and just outputs the right answer. |
| 956 | It succeeds very quickly, and with probability 1. So this definition is |
| 957 | impossible to satisfy. |
| 958 | \end{slide} |
| 959 | |
| 960 | \begin{slide} |
| 961 | \head{Hash functions, \seq: targetted collision resistance} |
| 962 | |
| 963 | The concept of targetted collision resistance is relatively new, but quite |
| 964 | promising. It replaces a single hash function with a \emph{family} of hash |
| 965 | functions. They're not really keyed, because the indices aren't kept |
| 966 | secret. |
| 967 | |
| 968 | When making a signature, an index $i$ is chosen at random, and the |
| 969 | signature for message $m$ is formed over the pair $(i, H_i(M))$. |
| 970 | |
| 971 | TCR-hash functions are the subject of ongoing research. No practical |
| 972 | designs exist at the moment. |
| 973 | \end{slide} |
| 974 | |
| 975 | \begin{slide} |
| 976 | \head{Hash functions, \seq: targetted collision resistance (cont.)} |
| 977 | |
| 978 | Consider the following experiment: |
| 979 | \begin{program} |
| 980 | $\Expt{tcr}{H}(A)$: \+ \\ |
| 981 | $(x, s) \gets A(\cookie{find})$; \\ |
| 982 | $i \getsr \keys H$; \\ |
| 983 | $y \gets A(\cookie{collide}, i, s)$; \\ |
| 984 | \IF $x \ne y \land H_i(x) = H_i(y)$ |
| 985 | \THEN \RETURN $1$; \\ |
| 986 | \ELSE \RETURN $0$; |
| 987 | \end{program} |
| 988 | The security of a TCR-hash function is measured as: |
| 989 | \[ \InSec{tcr}(H; t) = \max_A \Pr[\Expt{tcr}{H}(A) = 1] \] |
| 990 | where the maximum is taken over all adversaries running in time $t$. We |
| 991 | define $(t, \epsilon)$-security as usual. |
| 992 | \end{slide} |
| 993 | |
| 994 | \begin{slide} |
| 995 | \head{Hash functions, \seq: random oracles \cite{Bellare:1993:ROP}} |
| 996 | |
| 997 | In practice, we expect much more than just collision resistance from hash |
| 998 | functions: we expect a certain amount of `random' behaviour. But this is |
| 999 | hard to quantify. |
| 1000 | |
| 1001 | One approach is to model a hash function as a `random oracle', i.e., an |
| 1002 | oracle containing a function chosen at random, used by the construction |
| 1003 | under consideration, and made available to the adversary. The idea is that |
| 1004 | reductions can `capture' the knowledge of an adversary by examining the |
| 1005 | queries it makes to its random oracle. |
| 1006 | |
| 1007 | Hash functions \emph{aren't} random oracles. But a random oracle proof is |
| 1008 | better than nothing. |
| 1009 | \end{slide} |
| 1010 | |
| 1011 | \xcalways\subsection{Standard assumptions}\x |
| 1012 | |
| 1013 | \begin{slide} |
| 1014 | \head{Standard assumptions} |
| 1015 | |
| 1016 | There are a number of `standard' assumptions that are made about the |
| 1017 | difficulty of various problems: |
| 1018 | \begin{itemize} |
| 1019 | \item IFP, the Integer Factorization Problem; |
| 1020 | \item QRP, the Quadratic Residuosity Problem; |
| 1021 | \item DLP, the Discrete Logarithm Problem; |
| 1022 | \item RSAP, the RSA Problem; and |
| 1023 | \item CDH, the Computational Diffie-Hellman problem and its variants |
| 1024 | \end{itemize} |
| 1025 | \cite{Menezes:1997:HAC} has excellent material on the above. |
| 1026 | \end{slide} |
| 1027 | |
| 1028 | \begin{slide} |
| 1029 | \topic{integer factorization} |
| 1030 | \resetseq |
| 1031 | \head{The Integer Factorization Problem, \seq} |
| 1032 | |
| 1033 | We often assume that large integers of the form $n = p q$, where $p$ and |
| 1034 | $q$ are primes of roughly the same size, are `hard' to factor. |
| 1035 | Specifically, there is no algorithm which will factor such an $n$ in time |
| 1036 | bounded by a polynomial function of $\log n$. |
| 1037 | |
| 1038 | The difficulty of various other problems, e.g., Quadratic Residuosity, or |
| 1039 | RSA, depend on the difficulty of factoring; however, it is not yet known |
| 1040 | whether the ability to solve QRP or RSAP can be used to factor. |
| 1041 | \end{slide} |
| 1042 | |
| 1043 | \begin{slide} |
| 1044 | \head{The Integer Factorization Problem, \seq: square roots} |
| 1045 | |
| 1046 | The problem of extracting square roots modulo $n = p q$ is provably as hard |
| 1047 | as factoring. This is the basis of Rabin's public key encryption and |
| 1048 | digital signature schemes. We shall analyse these later. |
| 1049 | |
| 1050 | Suppose $Q(n, y)$ is an algorithm which returns an $x$ such that $x^2 |
| 1051 | \equiv y \pmod{n}$, provided such an $x$ exists. Then we can find a |
| 1052 | nontrivial factor of $n$ as follows: |
| 1053 | \begin{program} |
| 1054 | Algorithm $\id{find-factor}(n)$: \+ \\ |
| 1055 | \REPEAT \\ \quad\=\+\kill |
| 1056 | $x \getsr \{1, 2, \ldots, n - 1\}$; \\ |
| 1057 | $y \gets x^2 \bmod n$; \\ |
| 1058 | $x' \gets Q(n, y)$; \\ |
| 1059 | $p \gets \gcd(x + x', n)$; \\ |
| 1060 | \IF $p \notin \{1, n\}$ \THEN \RETURN $p$; \- \\ |
| 1061 | \FOREVER; |
| 1062 | \end{program} |
| 1063 | \end{slide} |
| 1064 | |
| 1065 | \begin{proof} |
| 1066 | The program attempts to find two square roots of $y$ mod $n$. It's easy to |
| 1067 | see that this might lead to factors of $n$. If $x^2 \equiv x'^2 \pmod{n}$ |
| 1068 | then $x^2 - x'^2 = k n$ for some constant $k$. Then $(x + x')(x - x')$ is |
| 1069 | a factorization of $k n$. It remains to prove the probability bound on $x |
| 1070 | + x'$ being a nontrivial factor of $n$. |
| 1071 | |
| 1072 | Let $n$ be an odd composite. Then, if $x \not\equiv \pm y \pmod{n}$ but |
| 1073 | $x^2 \equiv y^2 \pmod{n}$, then $\gcd(x + y, n)$ is a nontrivial factor of |
| 1074 | $n$. |
| 1075 | |
| 1076 | Firstly, we claim that, if $p$ is an odd prime then the congruence $x^2 |
| 1077 | \equiv y \pmod{p}$ has precisely two solutions $x$, $x'$ such that $x |
| 1078 | \equiv -x' \pmod{p}$. Let $g$ be primitive mod $p$, with $x = g^\alpha$, |
| 1079 | $x' = g^\beta$. Then $g^{2 \alpha} \equiv g^{2 \beta} \pmod{p}$, so $2 |
| 1080 | \alpha \equiv 2 \beta \pmod{p - 1}$. But $p - 1$ is even, by hypothesis, |
| 1081 | so $\alpha \equiv \beta \pmod{(p - 1)/2}$. But $g^{(p-1)/2} \equiv -1 |
| 1082 | \pmod{p}$; hence $x \equiv \pm x' \pmod{p}$, proving the claim. |
| 1083 | |
| 1084 | There must exist odd primes $p$, $q$, such that $p|n$ and $q|n$, and $x |
| 1085 | \equiv -y \pmod{p}$ and $x \equiv y \pmod{q}$, for if not, then $x \equiv |
| 1086 | \pm y \pmod{n}$ contrary to hypothesis. But then $x + y \equiv 0 |
| 1087 | \pmod{p}$, so $p|(x + y)$; but $x + y \equiv 2 x \not\equiv 0 \pmod{q}$, |
| 1088 | since $q$ is odd. Hence, $p$ divides $x + y$, but $q$ does not, so $\gcd(x |
| 1089 | + y, n)$ is a nontrivial factor of $n$, completing the proof. |
| 1090 | \end{proof} |
| 1091 | |
| 1092 | \begin{slide} |
| 1093 | \topic{quadratic residuosity} |
| 1094 | \head{The Quadratic Residuosity Problem} |
| 1095 | |
| 1096 | If there is an $x$ such that $x^2 \equiv y \pmod{n}$ then $y$ is a |
| 1097 | \emph{quadratic residue modulo $n$}, and we write $y \in Q_n$; if there is |
| 1098 | no such $x$ then $y$ is a \emph{quadratic nonresidue modulo $n$}. |
| 1099 | |
| 1100 | If $p$ is prime, then we can use the \emph{Legendre symbol} to decide |
| 1101 | whether $x$ is a quadratic residue mod $p$: |
| 1102 | \[ \jacobi{x}{p} = x^{(p-1)/2} \bmod p = |
| 1103 | \begin{cases} |
| 1104 | 0 & if $p$ divides $x$ \\ |
| 1105 | -1 & if $x$ is a quadratic nonresidue mod $p$ \\ |
| 1106 | +1 & if $x$ is a quadratic residue mod $p$ |
| 1107 | \end{cases}. \]% |
| 1108 | The \emph{Jacobi symbol} (written the same way) is defined for odd~$n$: if |
| 1109 | $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ where the $p_i$ are prime, then |
| 1110 | \[ \jacobi{x}{n} = |
| 1111 | \jacobi{x}{p_1}^{a_1} \jacobi{x}{p_2}^{a_2} \cdots |
| 1112 | \jacobi{x}{p_k}^{a_k}. \]% |
| 1113 | This can be efficiently computed without knowledge of the factors of $n$ |
| 1114 | \cite[Section~2.4.5]{Menezes:1997:HAC}. |
| 1115 | \end{slide} |
| 1116 | |
| 1117 | \begin{slide} |
| 1118 | \head{The Quadratic Residuosity Problem (cont.)} |
| 1119 | |
| 1120 | If $\jacobi{x}{n} = -1$ then $x$ is certainly \emph{not} a quadratic |
| 1121 | residue mod $n$; however, if $\jacobi{x}{n} = 1$ then $x$ might be a |
| 1122 | quadratic residue or it might not; if not, then we say that $x$ is a |
| 1123 | \emph{pseudosquare}. |
| 1124 | |
| 1125 | If $n = p q$ is a product of two primes and $x \inr (\Z/n\Z)^*$ is chosen |
| 1126 | at random, then |
| 1127 | \[ \Pr\Bigl[x \in Q_n \Bigm| \jacobi{x}{n} = 1\Bigr] = \frac{1}{2}, \] |
| 1128 | since we have |
| 1129 | \[ \jacobi{x}{p} = \jacobi{x}{q} = \pm 1 \] |
| 1130 | with each occurring with equal probability. |
| 1131 | |
| 1132 | The problem of distinguishing pseudosquares from quadratic residues is |
| 1133 | called the Quadratic Residuosity Problem (QRP). It is not known how to |
| 1134 | solve this problem without factoring $n$. |
| 1135 | \end{slide} |
| 1136 | |
| 1137 | \begin{slide} |
| 1138 | \topic{discrete logarithms} |
| 1139 | \head{The Discrete Logarithm Problem} |
| 1140 | |
| 1141 | The (Integer) Discrete Logarithm Problem asks for the solution $x$ given a |
| 1142 | congruence of the form $g^x \equiv y \pmod{n}$. This seems to be about as |
| 1143 | difficult as factoring. (The ability to solve discrete logs modulo $n$ is |
| 1144 | sufficient to factor $n$. The best known algorithms for IFP and DLP have |
| 1145 | the same running time.) |
| 1146 | |
| 1147 | The problem generalizes to other cyclic groups, e.g., elliptic curves over |
| 1148 | finite fields. |
| 1149 | \end{slide} |
| 1150 | |
| 1151 | \begin{slide} |
| 1152 | \topic{self-reducibility} |
| 1153 | \resetseq |
| 1154 | \head{Self-reducibility, \seq} |
| 1155 | |
| 1156 | The problems of square-root extraction, deciding quadratic residuosity, the |
| 1157 | RSA problem, and finding discrete logarithms share the property of being |
| 1158 | \emph{randomly self-reducible}; i.e., an instance of the problem can be |
| 1159 | transformed into many different derived instances \emph{without skewing the |
| 1160 | probability distribution of problem instances}, such that a solution to |
| 1161 | one of the derived instances yields a solution to the original one. |
| 1162 | |
| 1163 | This is a good property to have. It implies that `most' problem instances |
| 1164 | are as hard as the hardest instances. |
| 1165 | \end{slide} |
| 1166 | |
| 1167 | \begin{slide} |
| 1168 | \head{Self-reducibility, \seq: the RSA problem \cite{Rivest:1978:MOD}} |
| 1169 | |
| 1170 | The RSA problem is to compute $e$-th roots modulo $n = p q$, where $e$ is |
| 1171 | relatively prime to $n$. Suppose that the algorithm $S(n, e, y)$ returns a |
| 1172 | value $x$ such that $x^e \equiv y \pmod{n}$ for `many' choices of $y$, or |
| 1173 | the special symbol $\bot$ otherwise. The following probabilistic algorithm |
| 1174 | then solves the RSA problem for arbitrary $y$: |
| 1175 | \begin{program} |
| 1176 | Algorithm $\id{solve-rsa}(n, e, y)$: \+ \\ |
| 1177 | \REPEAT \\ \quad\=\+\kill |
| 1178 | $x' \getsr \{1, 2, \ldots, n - 1\}$; \\ |
| 1179 | \IF $\gcd(x', n) = 1$ \THEN \\ \quad\=\+\kill |
| 1180 | $y' \gets y x'^e \bmod n$; \\ |
| 1181 | $x \gets S(n, e, y')$; \\ |
| 1182 | \IF $x \ne \bot$ \THEN \RETURN $x x'^{-1} \bmod n$; \-\- \\ |
| 1183 | \FOREVER; |
| 1184 | \end{program} |
| 1185 | \end{slide} |
| 1186 | |
| 1187 | \begin{slide} |
| 1188 | \topic{the Diffie-Hellman problem} |
| 1189 | \head{The Diffie-Hellman problem \cite{Diffie:1976:NDC}} |
| 1190 | |
| 1191 | Let $G = \langle g \rangle$ be a cyclic group or order $q$. Let $\alpha$ |
| 1192 | and $\beta$ be indices, $\alpha, \beta \in \Z/q\Z$. |
| 1193 | |
| 1194 | The (computational) \emph{Diffie-Hellman} problem is, given $g^\alpha$ and |
| 1195 | $g^\beta$, to find $g^{\alpha\beta}$. |
| 1196 | |
| 1197 | The (computational) Diffie-Hellman \emph{assumption} is that there is no |
| 1198 | probabilistic algorithm which solves the computational Diffie-Hellman |
| 1199 | problem in time polynomial in $\log q$. |
| 1200 | |
| 1201 | Obviously, being able to compute discrete logs in $G$ efficiently would |
| 1202 | yield a solution to the Diffie-Hellman problem. But it may be the case |
| 1203 | that the Diffie-Hellman problem is easier than the discrete log problem. |
| 1204 | |
| 1205 | The Diffie-Hellman problem is self-reducible. |
| 1206 | \end{slide} |
| 1207 | |
| 1208 | \begin{slide} |
| 1209 | \head{The Decisional Diffie-Hellman assumption \cite{Boneh:1998:DDP}} |
| 1210 | |
| 1211 | The computational Diffie-Hellman assumption makes a statement only about |
| 1212 | algorithms which compute the \emph{entire} answer $g^{\alpha\beta}$. Since |
| 1213 | Diffie-Hellman is frequently used for key-exchange, what can we say about |
| 1214 | the ability of an adversary to guess any of the bits? |
| 1215 | |
| 1216 | The Decisional Diffie-Hellman (DDH) assumption asserts that, if you don't |
| 1217 | know $\alpha$ or $\beta$, then it's hard to tell $g^{\alpha\beta}$ from a |
| 1218 | random element of $G$; that is, that the distributions of the following |
| 1219 | experiments are computationally indistinguishable: |
| 1220 | \begin{program} |
| 1221 | $\alpha \getsr \Z/q\Z;$ \\ |
| 1222 | $\beta \getsr \Z/q\Z;$ \\ |
| 1223 | \RETURN $(g^\alpha, g^\beta, g^{\alpha\beta})$; |
| 1224 | \next |
| 1225 | $\alpha \getsr \Z/q\Z;$ \\ |
| 1226 | $\beta \getsr \Z/q\Z;$ \\ |
| 1227 | $\gamma \getsr \Z/q\Z;$ \\ |
| 1228 | \RETURN $(g^\alpha, g^\beta, g^\gamma)$; |
| 1229 | \end{program} |
| 1230 | \end{slide} |
| 1231 | |
| 1232 | \begin{slide} |
| 1233 | \head{The Decisional Diffie-Hellman assumption (cont.)} |
| 1234 | |
| 1235 | If $A$ is an algorithm attempting to solve DDH in the group $G$, then we |
| 1236 | write its advantage as |
| 1237 | \begin{eqnarray*}[rl] |
| 1238 | \Adv{ddh}{G}(A) = |
| 1239 | & \Pr[\alpha \getsr \Z/q\Z; \beta \getsr \Z/q\Z : |
| 1240 | A(g^\alpha, g^\beta, g^{\alpha\beta}) = 1] - {} \\ |
| 1241 | & \Pr[\alpha \getsr \Z/q\Z; \beta \getsr \Z/q\Z; |
| 1242 | \gamma \getsr \Z/q\Z : |
| 1243 | A(g^\alpha, g^\beta, g^\gamma) = 1] |
| 1244 | \end{eqnarray*} |
| 1245 | and the insecurity of DDH in $G$ as |
| 1246 | \[ \InSec{ddh}(G; t) = \max_A \Adv{ddh}{G}(A) \] |
| 1247 | with the maximum over all algorithms $A$ running in time $t$. |
| 1248 | \end{slide} |
| 1249 | |
| 1250 | \begin{slide} |
| 1251 | \head{The Decisional Diffie-Hellman assumption (cont.)} |
| 1252 | |
| 1253 | If you can solve the computational Diffie-Hellman problem, you can solve |
| 1254 | the decisional version. If you can compute discrete logs, you can solve |
| 1255 | both. |
| 1256 | |
| 1257 | There \emph{are} groups in which the computation problem is (believed to |
| 1258 | be) hard, but the decisional problem is easy. In particular, if the group |
| 1259 | order $q$ has small factors then the decisional problem isn't hard. |
| 1260 | \end{slide} |
| 1261 | |
| 1262 | \endinput |
| 1263 | |
| 1264 | %%% Local Variables: |
| 1265 | %%% mode: latex |
| 1266 | %%% TeX-master: "ips" |
| 1267 | %%% End: |