Happy days + learning cryptography

I'm pretty happy today since I managed to solve 3 problems in codeforces and had the idea for problem D (a binary search based solution) but could not figure out the implementation details in time.

I am trying to learn some cryptography so that I can better understand blockchain technology. I am following Prof. Shafi Goldwasser's (a legend in computer science) lectures to do this. I will use this post to record some notes on the first lecture.

First some important notation is introduced. We define an encryption scheme as a triple $(G,E,D)$ where

• $G(1^k)$ outputs a secret key of length $k$.
• $E(sk, m)$ takes a secret key and a message and outputs ciphertext.
• $D(sk, m')$ takes a secret key and a ciphertext and outputs plaintext.

We also assume a message space $M$ which defines a probability distribution over all possible messages, a key space $K$, and a ciphertext space $C$, which is just a probability distribution which is dependent on $M$ and $K$.

Note that $G$ must be probabilistic in the sense that its output must define a probability distribution. If not our adversary could easily decrypt any ciphertext since there exists only one secret key for each $k$. If we allow $E$ to be probabilistic then we could have many possible ciphertexts for the same message. Similarly, if $D$ is probabilistic, we allow for a ciphertext to have many possible plaintexts. For this to make sense, we demand that w.h.p the decryption is correct.

By correctness, we mean the following: $D(sk, E(sk, m))=m$. Additionally, we need security, i.e. it should be hard for our adversary to decrypt the ciphertext. Usually, this is done by reduction to some "hard" problem.

Shanon secrecy is demanding that $\mathbb{P}[M=m]=\mathbb{P}[M=m \mid C=c]$, where $c=E(sk, m)$. This basically says that the attacker does not learn anything new about the message by looking at the ciphertext.

The notion of perfect indistinguishability is the condition that $\mathbb{P}[C=c \mid M=m]=\mathbb{P}[C=c \mid M=m']$. This says that for any pair of messages, by looking at the ciphertext, we cannot learn/distinguish between which message, $m$ or $m'$, was sent.

It turns out that these two concepts are equivalent. The lecture concludes by giving an example encryption scheme which achieves Shanon secrecy. This scheme is called the one-time pad:

• $G(1^k)$ outputs a random string from $\{0,1\}^k$.
• $E(sk, m)$ outputs $m \oplus sk$.
• $D(sk, m')$ outputs $m' \oplus sk$.

This works because $(m \oplus sk) \oplus sk = m$. Additionally, it can be shown that one-time pads achieve Shanon secrecy, however, a one-time pad can only send one message with the same secret key, if it sends two we no longer have Shanon secrecy.