Definitions

Cryptosystems

• Cryptographic system: A single parameter family \(\{S_K\}_{K \in \{K\}}\) of invertible transformations: \[S_K: \{P\} \to \{C\}, \] from a set of messages \(\{P\}\) to a set of ciphertexts \(\{C\}\). If \(\{P\}=\{C\}\), we denote them as \(\{M\}\).

Definitions

Cryptosystems

• Symmetric Cryptography: The same key is used for both encryption and decryption of the data. This means that both the sender and receiver must share the secret key securely beforehand.
• Asymmetric Cryptography: A pair of keys is used — a public key for encryption and a private key for decryption. The public key can be shared openly, while the private key remains confidential, allowing secure communication without the need to share the secret key beforehand.

Definitions

Security

• Computational security: Breaking the system is theoretically possible, but requires infeasible computation.
  • Computationally infeasible: A problem whose time and/or spatial cost is finite but incredibly large.
• Unconditional security: Impossible to break, regardless of computational resources (e.g., one-time pad).

Definitions

Attack models

• Ciphertext only attack: Only ciphertexts available.
• Known plaintext attack: Ciphertext-plaintext pairs known.
• Chosen plaintext attack: Can encrypt arbitrary plaintexts.

Challenge

how can two parties securely communicate over an insecure channel with no prior shared secret?

Contributions

1. Public key cryptosystems (asymmetric encryption)
2. Public key distribution systems (securely establishing secrets over open channels)
3. Digital signatures (authenticated, non-refutable communication)

Contributions

Definitions

All previous models rely on the computational difficulty of the cryptanalyst/adversary to derive a plaintext from a ciphertext without the key.

Cryptography goals

• Privacy: Preventing eavesdroppers from learning the message.
• Authentication: Ensuring a message comes from the claimed sender.

Classic cryptographic system

• Transmitter & receiver pre-share a secret key \(K\), defining a reversible transformation \(S_K\).
• Message \(P\) encrypted as \(C = S_K(P)\).
• Receiver decrypts \(C\) to obtain \(P = S_K^{-1}(C)\).

Public key cryptography

Till then, preparation in advance was needed for secure communication.

Our goal is to enable two parties communicating over a public channel and using only publicly known techniques to create a secure connection.

This goal can be achieved with a system like this:

Public key cryptosystem

• Each user generates a pair of keys \((E, D)\):

  • \(E\): Public encryption key.
  • \(D\): Private decryption key, hard to infer from \(E\).

• Anyone can send secure messages by encrypting with \(E\).

• Only the intended recipient can decrypt using \(D\).

Public key distribution system

A system that allows two users \(A,B\) to securely exchange a key over an insecure channel.

Initially studied by Merkle [6], however, the proposed solution has several issues [4, pp. 648–649].

Groups

A group is a set \(G\) with an operation \(\circ\) satisfying:

1. Closure: \(a \circ b \in G\)
2. Associativity: \((a \circ b) \circ c = a \circ (b \circ c)\)
3. Identity: \(\exists e \in G : a \circ e = a\)
4. Inverse: \(\forall a \in G, \exists a^{-1} \in G : a \circ a^{-1} = e\)

Cyclic groups

A group is cyclic if there exists a generator/primitive element \(g\) such that \[\forall x \in G, \exists k : x = g^k.\]

Discrete logarithm problem

let \(\mathbb G=(\mathbb{Z}_p^{*}, \times \mod p)\) a cyclic group of the non-zero integers modulo a prime \(p\) under multiplication.

Diffie-Hellman Key Exchange

A ‘public key distribution system’ implementation

1. It requires only a single key exchange—unlike Merkle’s method [6].
2. The effort for a cryptanalyst to break it increases exponentially compared to the effort required by regular users.

It relies on the computational difficulty of the discrete logarithm problem.

DHKE Protocol

1. Each user secretly and independently generates a random number \(X_i \in \left\{ 1,2, \dots, p-1 \right\}=\mathbb{Z}_p^{*}\), where \(p\) is a prime and \(g\) is the generator.

2. The user computes \(Y_i = g^{X_i} \mod p\) and publishes it.

3. When users \(i\) and \(j\) wish to communicate, they use the key \(K_{ij}=g^{X_i X_j} \mod p\).

   • User \(i\) derives the key using \(Y_j = g^{X_j} \mod p\): \[K_{ij}=Y_j^{X_i}=\left( g^{X_j} \right)^{X_i} = g^{X_j X_i}=g^{X_i X_j}\mod p.\]

One-way authentication/Digital signatures

A system where a digital signature can be easily recognized as authentic, but cannot be forged by anyone other than the actual signer.

Since every digital signal can be copied, a digital signature must be identifiable without being disclosed.

One-way functions

A function \(f\) is called a one-way function when for every \(x\) in its domain, we can easily compute \(f(x)\), but for almost all \(y\) in its range, it is computationally infeasible to solve for \(y = f(x)\).

Example: Polynomials. Finding the root \(x_0\) of \(p(x) = y\) is difficult, whereas evaluating \(x_0\) as a solution is straightforward.

Trap Doors / Trap-Door One-Way Functions

Functions that appear one-way but can be easily inverted due to specific information.

Given only an algorithm for the forward function from \(x \to f(x)\), it is computationally infeasible to find an easily computable inverse.

Only with specific trap-door information can we compute the inverse.

Claim 1

A cryptosystem secure against a known plaintext attack can produce a one-way function

Let \(S_K\) be such a cryptosystem. We define \(P=P_0\) and a function \(f:\{K\}\to \{C\}\) such that \(f(X)=S_X(P_0)\).

The function \(f\) is one-way since solving for \(X\) given \(f(X)\) is equivalent to cryptanalyzing the key recovery problem from a specific plaintext-ciphertext pair. Thus, knowing \(f\) is equivalent to knowing \(\{S_K\}, P_0\).

Claim 2

A public key cryptosystem can create a one-way authentication system

If user \(A\) wants to send a signed message \(M\) to user \(B\), then

1. \(A\) sends \(D_A(M)\), where \(E_A,D_A\) are \(A\)’s keys in the PKC.
2. User \(B\) verifies \(E_A(D_A(M))=M\), confirming it was signed by \(A\).
   • \(B\) retains \(D_A(M)\) as proof.

Given \(E\), we have an algorithm to convert plaintext into cryptograms. In other words, a PKC is a set of trap-door one-way functions.

Claim 3

A trap-door cryptosystem can generate a public key distribution system

1. \(B\) publishes the trap-door cryptosystem while keeping the trap-door information secret.
2. \(A\) selects a random key and sends a plaintext-cryptogram pair to \(B\), who uses the trap-door to retrieve the key, which both now possess.