Modern Cryptography Lecture Flashcards

Vocabulary flashcards covering core definitions, syntactic specifications, and security games from Modern Cryptography lecture slides.

Cryptology

The overarching field that comprises both cryptography and cryptanalysis.

Cryptography

The practice of protecting the confidentiality, integrity, or authenticity of data.

Cryptanalysis

The study and practice of breaking cryptographic protections.

Steganography

The practice of concealing the existence of data, dating back to at least $440$\,BC.

Insecure Channel

A communication channel where the adversary carries the message and can read, reorder, replay, drop existing messages, or create new messages.

Cryptographic Protocol

A set of message exchanges that leverages or augments a channel's security properties to protect data in transit.

Kerckhoff's Desideratum

The cryptographic principle stating that a system should be secure even if everything about it is public knowledge, except for a secret key.

Private Key Encryption Scheme

A triple of algorithms $(\text{Gen}, \text{Enc}, \text{Dec})$ where \text{Gen} : \begin{mathbb}N\text{\}end{mathbb} \rightarrow K, $\text{Enc} : K \times M \rightarrow C$, and $\text{Dec} : K \times C \rightarrow M$, satisfying $\text{Dec}_k(\text{Enc}_k(m)) = m$ for all $k \times K$ and $m \times M$.

PrivK-eav Game

A security experiment $\text{PrivK}^{\text{eav}}_{A,\top}(n)$ testing encryption indistinguishability against a passive eavesdropping adversary $A$.

PrivK-cpa Game

A security experiment $\text{PrivK}^{\text{cpa}}_{A,\top}(n)$ testing encryption security against an adversary $A$ with access to a chosen-plaintext encryption oracle.

PrivK-cca Game

A security experiment $\text{PrivK}^{\text{cca}}_{A,\top}(n)$ testing encryption security against an adversary $A$ with access to both an encryption oracle and a decryption oracle (for any ciphertext except the challenge ciphertext $c^*$).

Public Key Encryption Scheme

A triple of algorithms $(\text{Gen}, \text{Enc}, \text{Dec})$ where \text{Gen} : \begin{mathbb}N\text{\}end{mathbb} \rightarrow PK \times SK, $\text{Enc} : PK \times M \rightarrow C$, and $\text{Dec} : SK \times C \rightarrow M$, with $\text{Dec}_{sk}(\text{Enc}_{pk}(m)) = m$ holding with all but negligible probability.

Message Authentication Code (MAC)

A triple of algorithms $(\text{Gen}, \text{Mac}, \text{Vrfy})$ where $\text{Vrfy}_k(\text{Mac}_k(m), m) = 1$ for all keys $k \times K$ and messages $m \times M$.

Mac-forge Game

A security experiment $\text{Mac-forge}_{A,\top}(n)$ where an adversary queries a MAC oracle for messages $m_i$ and attempts to forge a valid tag $t$ for an unqueried message $m$.

Digital Signature Scheme

A triple of algorithms $(\text{Gen}, \text{Sign}, \text{Vrfy})$ where \text{Gen} : \begin{mathbb}N\text{\}end{mathbb} \rightarrow PK \times SK, \text{Sign} : SK \times M \rightarrow \begin{mathcal}\text{S}\text{\}end{mathcal}, and \text{Vrfy} : PK \times M \times \begin{mathcal}\text{S}\text{\}end{mathcal} \rightarrow \begin{matrix}0, 1\text{\}end{matrix}, satisfying $\text{Vrfy}_{pk}(m, \text{Sign}_{sk}(m)) = 1$.

Secure Hash Function

A pair of algorithms $(\text{Gen}, H)$ with $\text{Gen} : \rightarrow S$ and $H : S \times M \rightarrow T$ where the message space size exceeds the image size ($|M| > |T|$).

Hash-coll Game

A security experiment $\text{Hash-coll}_A(n)$ where an adversary $A$ attempts to find two distinct inputs $m \neq m'$ such that $H_s(m) = H_s(m')$.

Key Exchange Scheme

An algorithm \text{Run} : \begin{mathbb}N\text{\}end{mathbb} \rightarrow T \times K producing a transcript space $T$ and shared key space $K$ so both parties agree on a secret key via interaction.

Perfect Secrecy

A security definition where an adversary learns no information about the plaintext from the ciphertext, formally expressed as $\text{Pr}[\text{PrivK}^{\text{eav}}_A(n) = 1] = \frac{1}{2}$ or $\text{Pr}[M = m \text{ | } C = c] = \text{Pr}[M = m]$.

Vernam Cipher (One-Time Pad)

A perfectly secret encryption scheme over M = C = K = \begin{matrix}0, 1\text{\}end{matrix}^n defined by $\text{Enc}_k(m) = m \bigoplus k$ and $\text{Dec}_k(c) = c \bigoplus k$.

Negligible Function

A function $f$ that grows slower than the reciprocal of any polynomial: \forall \text{poly}(\times) : \begin{mathcal}\text{E}\text{\}end{mathcal} n_0 : \forall n > n_0 : f(n) < \frac{1}{\text{poly}(n)}.

Efficient Algorithm

An algorithm $A(x)$ that completes execution in time bounded by at most $\text{poly}(|x|)$.

Pseudorandom Function (PRF)

A keyed function F : \begin{matrix}0, 1\text{\}end{matrix}^n \times \begin{matrix}0, 1\text{\}end{matrix}^n \rightarrow \begin{matrix}0, 1\text{\}end{matrix}^n that cannot be distinguished from a truly random function by any efficient adversary with non-negligible probability.