CS 4830: Introduction to Cryptography

One-Way Function Examples The Discrete Logarithm There is an algorithm that runs in $O(\log^2q \cdot \log x)$ and computes $h = g^x \mod q$ for $g \in \mathbb{Z}/q\mathbb{Z}$. We can define $x$ to be the base-$g$ discrete logarithm of $h$ modulo $q$ if $g^x = h \mod q$. We usually assume that DLOG is hard: $$\Pr_{q \sim \mathbb{P}_n, g \sim \mathbb{Z}/q\mathbb{Z}, x \sim \mathbb{Z}/q\mathbb{Z}} [x^\prime \leftarrow \mathcal{A}(q, g, g^x \mod q) \ : \ g^{x^\prime} = g^x \mod q] \leq \varepsilon(n).$$ ...

Some Definitions Our definition of many-message semantic security from last lecture was pretty complex, so we can study the definition within a more restricted context. A one-way function is a function $f : \{0, 1\}^* \to \{0, 1\}^*$ which has the following two properties: It is easy to compute: there exists PPT $\mathcal{B}$ such that for any $x \in \{0, 1\}^*$, $\mathcal{B}(x) = f(x)$. It should be hard to invert: for any PPT $\mathcal{A}$, there exists negligible $\varepsilon$ such that $$\text{Pr}_{x \sim \{0, 1\}^n} [x^\prime \leftarrow \mathcal{A}(1^n, f(x)), f(x^\prime) = f(x)] \leq \varepsilon(n)$$ ...

Perfect Indistinguishability It can be proven that if you have an encryption scheme that is perfectly indistinguishable, then $|K| \geq |M|$. To prove this, we can choose an $m \in M$ and $c \in C$ such that $c$ is valid, e.g. $$\text{Pr}[\text{Enc}(k, m) = c] > 0.$$ We can define $M_c := \{ m^\prime \in M : \exists k^\prime \in K \text{ s.t. } \text{Dec}(k^\prime, c) = m^\prime \}$, which is the set of messages that can encrypt to $c$. Importantly, $|M_c| \leq |K|$ since each key for which there is a message $m^\prime \in M_c$ can correspond to at most one such message. ...

Logistics This is a theoretical course. It is about math, definitions, and theorems, not real world practical security and programming. There are 6 (plus one extra) problem sets, and the lowest score is dropped. They are due roughly every other Thursday. Cryptography Fun Examples In Yao’s millionaires problem, you have two millionaires, each with a net worth. They want to find out who is richer but “without revealing any other information” such as the actual net worths, as simply telling each other their net worths is boring. ...