Skip to content

Public Key Encryption

links: AC2 TOC - Intro Public Key Encryption - Index

In the static application of Diffie-Hellman, the values (\(a\), \(A\)) can be considered as an Alices key pair.

  • Public Key: \(A\) can be published on a website or directory, or sent over an insecure channel.
  • Private Key: \(a\) must be kept secret.

The paper by Diffie and Hellman invented the principle of public key encryption based on public/private keys. But they didn't describe an actual scheme.

The first scheme was published by R. Rives, A. Shamir and L. Adleman (RSA) in 1977.

The scheme

The public-key encryption scheme consists of a message space \(M\) and three randomised polynomial-time algorithms.

  • Key generation: (\(pk\), \(sk\)) \(\leftarrow keyGen()\)
  • Encryption: \(c \leftarrow enc_{pk}(m)\)
  • Decryption: \(m := dec_{sk}(c)\)

such that \(dec_{sk}(enc_{pk}(m)) = m\) holds for all messages \(m \in M\), and all key-pairs

  • \(K\) called key space is the set of all pairs generated by \(keyGen()\)
  • \(C\) called ciphertext space is the set of all ciphertexts generated by \(enc_{pk}(m)\)
\[enc : K_{pk} \times M \rightarrow C \qquad dec: K_{sk} \times C \rightarrow M\]

Private Communication

The most important application of public-key encryption is private communication over an insecure channel.

  1. Alice generates a key pair (\(pk\), \(sk\)) and sends \(pk\) to Bob (over an authenticated channel)
  2. Bob computes the ciphertext \(c \leftarrow enc_{pk}(m)\) and sends \(c\) over an insecure channel to Alice

  3. Alice computes the plaintext \(m := dec_{sk}(c)\)

  4. Eve (Eavesdropper) can't learn anything about \(m\) (or \(sk\))

  5. If the \(pk\) is transmitted without authentication, this approach is vulnerable to man-in-the-middle attacks (similar to Diffie-Hellman).

Hardness Assumptions

Discrete logarithm assumption (and stronger):

Integer factorisation assumption (and stronger)

  • RSA encryption/signature scheme
  • Rabin encryption scheme
  • Pailler encryption scheme
  • Goldwasser-Micali encryption scheme
  • Blum-Blum-Shub pseudorandom number generator

links: AC2 TOC - Intro Public Key Encryption - Index