Exponentiation by Squaring Suppose we want to calculate $a^n$ where $n$ is very large, like $n \approx 2^{1000}$. A naive multiplication would take $\mathcal{O}(n)$ multiplications. We will ignore...

In symmetric key encryption, we assumed that the two parties already share the same key. We will see how this can be done. In symmetric key settings, a user has to agree and store every key for ev...

Hash functions are functions that take some input an compress them to produce an output of fixed size, usually just called hash or digest. A desired property of hash function is collision resistanc...

Previously, we focused on semantic security against passive adversaries, that only eavesdrop on the ciphertext. But in the real world, there are active adversaries that interfere with the communica...

Number theory is a branch of mathematics devoted primarily to the study of the integers. Modular arithmetic is heavily used in cryptography. Divisibility Definition. Let $a, b, c \in \mathbb{Z...

Message authentication codes (MAC) were designed to provide message integrity. Bob receives a message from Alice and wants to know if this message was not modified during transmission. For MACs, th...

CPA Security Secret keys are hard to manage and it would be efficient if we could use the same key multiple times. So we need a stronger notion of security, that the adversary is given several cip...

Block Cipher Overview We need confusion and diffusion Confusion: relationship between ciphertext and key is complex Diffusion: relationship between message and ciphertext is co...

Pseudorandom Functions (PRF) Definition. A pseudorandom function $F$ over $(\mathcal{K}, X, Y)$ is an efficiently computable algorithm $F : \mathcal{K} \times X \rightarrow Y$. We consider a ...

Symmetric Encryption Alice and Bob use the same key for encryption and decryption. This was the only type of encryption before the invention of public-key cryptography. Requirements A s...