Cryptography concepts

Class notes! Wahoo

Polynomial function

For complexity theory’s sake, we say a function $f(n)$ is polynomial if there exists a value $c$ such that $f(n) < n^c$.

The notation $poly(n)$ or $P(n)$ represents some unspecified polynomial function of n.

It’s closed under multiplication.

• $poly(n) * poly(n) \in poly(n)$.

Negligible function

“a function which approaches 0 faster than the reciprocal of every polynomial”

With big-o notation we’d say a function $f(n)$ is negligible if $f(n) \in O(\frac{1}{poly(n)})$ for any arbitrary polynomial function.

For example $\frac{1}{2^n}$ is negligible. This specific negligible function comes up a lot because it represents the probability of an adversary guessing a secret $n$-bit key.

The notation $\epsilon(n)$ represents some unspecified negligible function of n.

Important properties:

• $\epsilon_1(n) + \epsilon_2(n) \in \epsilon(n)$
• $\epsilon(n)poly(n) \in \epsilon(n)$

Indistinguishability experiment

Given in the slides with some weird $PrivK^{eav}_{\pi, A}$ notation, where $A$ is the attacker and $\pi$ is the encryption scheme under test.

There are two parties in an indistinguishability experiment, the attacker A and the encryptor B.

• A picks two messages $m_1$ and $m_2$ and passes them to B.
• B encrypts one of the messages and returns the ciphertext to A.
• A guesses which message was encrypted.

The experiment is a success (as in, the funny $PrivK$ function returns 1) if A guesses correctly, and a failure if A guesses incorrectly. Usually there is a constraint that $m_1$ and $m_2$ are the same length so that A can’t simply make a guess informed by the length of the ciphertexts. Or just having A not make such a guess in its algorithm.

And we typically talk about the probability of an indistinguishability experiment succeeding.

Perfect secrecy and indistinguishability

In a perfectly secret system, seeing ciphertext gives absolutely no information about the message it encrypts. The notation in the slides is $Pr[M=m | C=c] = Pr[M=m]$ and I think how you interpret this (from the perspective of like, an eavesdropper or attacker):

• there is a true message being sent, $M$, and we want to guess what it is. our guess is called $m$
• we see the ciphertext $c$
• we can’t change our probability that $M = m$. we have learned no information at all

In a perfectly indistinguishable system, $Pr[PrivK^{eav}_{\pi, A} = 1] \leq \frac{1}{2}$. Or in English, the probability that an indistinguishability experiment succeeds is no better than chance.

These are two views into the same idea. All perfectly secret schemes are perfectly indistinguishable. Supposedly there’s a proof in the book. Maybe I should actually look at the book!

Perfectly secret schemes:

• A one-time pad, as long as the pad is truly random.
• A shift cipher, as long as it’s used to only encrypt one letter.
  • because of “false-positive” key guesses; there always exists a key which decrypts the ciphertext to either plaintext

Key-guessing and perfect secrecy

Ok I’m going to now overlook the idea of “false-positive” keys and silliness like using a shift cipher to encrypt 1 letter.

I’m pretty sure any encryption scheme with a finitely-sized keyspace cannot be perfectly secret. A can use this algorithm:

• Simply$^{\text{tm}}$ guess the key.
  • Unlikely that this is successful but the probability is not 0 because there are a finite number of keys.
• Try decrypting the ciphertext.
• If it succeeds and corresponds to a message, output that message, otherwise just guess randomly.

The probability A guesses correctly is something like $\frac{1}{2} + Pr[\text{A guessed the key correctly}]$ and that’s not $\leq \frac{1}{2}$.

Brute-forcing and perfect secrecy

There’s also this, for finitely sized keyspaces:

• For every possible key $k$:
  • try decrypting the message with $k$.
  • If it works, output that message.

Again this is kind of silly becase if there are $2^{\text{a lot}}$ keys this algorithm will loop up to $2^\text{a lot}$ times. But it will always succeed and give the right answer with probability 1 (again discounting the idea of “false-positive” keys)

Computational secrecy

We introduce a security parameter, $n$, the key length. (The slides say “for now think of this as the key length”. Hmm.) Then we make two tweaks:

• we raise the $Pr[PrivK = 1]$ threshold by $\epsilon(n)$
• we model the attacker $A$ as having $poly(n)$ computing power
  • this is called “probabilistic polynomial time” or “PPT”

Complexity theory AND probability theory together, ooh.

The idea is to formalize the notion of “silly impracitcal algorithms” and eliminate them from consideration. Guessing the key has probability $\frac{1}{2^n}$, which is a negligible function of $n$. Bruteforcing the keys takes $O(2^n)$ time which is not in $poly(n)$.

Later in the class we’ve seen interactive algorithms where A can repeatedly use B as an encryption oracle; the $poly(n)$ limit also places an upper bound on the amount of times A can interact with B.

In real life, to use a computationally secret scheme we just raise the key length until realistic polynomials of $n$ are still beaten out by $2^n$, then we’re secret enough for the real world. Even if the attacker can bruteforce $99999999999n^{99999999}$ keys per zeptosecond that’ll still get beaten out by $2^n$ for a long enough key. We know that the best algorithm the attacker can use is just guessing.