Public Key Security from Trapdoor Permutations

A recap of Public Key Encryption

Here’s a simple application for a non-interactive scenario - email encryption. We encrypt a message to Alice using her public key, she decrypts using her private key.

We saw session set up, Bob chooses a random key, encrypts it with Alice’s public key and sends it to her. Now the random key can be used as a shared key.

This is commonly used on the web, where public key encryption is used to set up a shared key between a browser and a server.

The standard notion of security for public key encryption is chosen ciphertext security. The attacker can get the decryptions of any cipher text they choose, except the challenge cipher text. The goal is to distinguish the challenge cipher text as encrypting from two messages, as usual.

Trapdoor Functions

A trapdoor function \(X \rightarrow Y\) is a triple of efficient algorithms.

• \(G()\) A randomized algoirthm outputting a key pair \((pk,sk)\)

• \(F(pk, \cdot )\) A deterministic algorithm that defines a function \(X \rightarrow Y\)

• \(F^{-1}(sk, \cdot )\) a function \(Y \rightarrow X\) that inverts \(F(pk, \cdot)\)

  The trapdoor function is secure if \(F(pk, \cdot )\) is a ‘one way’ function. It can be evaluated but not inverted without the secret key.

Public-key encryption from TDFs

let \((G,F,F^{-1})\) be a secure TDF from \(X \rightarrow Y\)

Let \((E_S,D_S)\) be a symmetric auth encyrption defined over \((K,M,C)\)

Let \(H: X \rightarrow K\) be a hash function.

We construct a public key encyrption system \((G,E,D)\).

\(G\) is the same \(G\) as for the TDF.

Note that the trapdoor function itself is only applied to a random value in \(X\), which yields a value y. That value is appended to the body of the cipher text and can then the shared key can be recovered by inverting the trapdoor function with the secret key, and applying the same hash function.

There is an ISO standard defining this.

Incorrect use of trapdoor

Do not encrypt by appying \(F\) directly to plain text.

Problems - deterministic (cannot be semantically secure).

Many attacks exist.