Public-key cryptography and trapdoor functions

Why a second key solves what symmetric cryptography leaves open, the six requirements a public-key cryptosystem must meet, and the two hard problems every scheme in this module builds on.

Explain what problem public-key cryptography solves that symmetric cryptography leaves open.
State which key encrypts and which decrypts for confidentiality, and the reverse pairing for origin authentication.
List the six requirements a public-key cryptosystem must satisfy, and define a trapdoor one-way function from them.
State the discrete logarithm problem and the RSA problem, and name which scheme each one underpins.

14 min read

Intuition

Symmetric cryptography — everything in module 5 — needs both sides to already hold the same secret key before a single message can be sent. That leaves a real problem unsolved: how do two parties who have never met agree on a secret over a channel an eavesdropper can read? Public-key cryptography answers this with two mathematically related keys instead of one shared key, so nothing secret has to travel over the channel at all.

Mechanism

Each participant generates a pair of keys: a public key, placed in a publicly accessible file, and a private key, kept confidential. Every other participant can see everyone’s public key; nobody but the owner ever sees a private key. The two keys are used in two different ways, and the lecture is careful that these are conceptually separate uses, not something a real system does with the same key pair at once:

Confidentiality. Bob encrypts with Alice’s public key. Only Alice can decrypt, because only she holds the private key that matches it.
Origin authentication. Bob encrypts with his own private key. Anyone can decrypt it with Bob’s public key, and anyone who does knows the message came from Bob — only he could have produced a ciphertext his own public key opens correctly. Digital signatures build on exactly this.

Every scheme this unit covers fits into one, or both, of these two roles:

Algorithm	Encryption / decryption	Digital signature	Key exchange
RSA	Yes	Yes	Yes
Diffie-Hellman	No	No	Yes
DSS	No	Yes	No
Elliptic Curve	No	No	Yes

RSA is the only one of the four the lecture marks for encryption. Diffie-Hellman and Elliptic Curve are marked for key exchange only in this table, and DSS for signatures only.

Mechanism

For an algorithm to work as a public-key cryptosystem, the lecture sets six requirements. Let $B$ be the receiver, with public key $P_{Ub}$ and private key $P_{Rb}$ :

It is computationally easy for $B$ to generate the key pair $(P_{Ub}, P_{Rb})$ .
It is computationally easy for a sender $A$ , knowing $P_{Ub}$ and a message $M$ , to compute $C = E(P_{Ub}, M)$ .
It is computationally easy for $B$ to recover $M$ from $C$ : $M = D(P_{Rb}, C) = D(P_{Rb}, E(P_{Ub}, M))$ .
It is computationally infeasible for an adversary who knows $P_{Ub}$ to determine $P_{Rb}$ .
It is computationally infeasible for an adversary who knows $P_{Ub}$ and a ciphertext $C$ to recover $M$ , without knowing $P_{Rb}$ .
The two keys can be applied in either order: $M = D(P_{Ub}, E(P_{Rb}, M)) = D(P_{Rb}, E(P_{Ub}, M))$ .

The sixth is useful — it is what lets the same key pair serve both roles above — but the lecture notes it is not essential for every public-key application.

Taken together, requirements 1 through 5 describe a single idea: a trap-door one-way function.

Formula

Trapdoor one-way function

Y = f_k(X) \implies \text{easy}, \qquad X = f_k^{-1}(Y) \implies \text{easy with } k, \text{ infeasible without } k

$X, Y$: input and output values
$f_k$: the function, parameterised by k
$k$: the trapdoor — the private key

Mechanism

Start from a plain one-way function: easy to compute forwards, $Y = f(X)$ , but infeasible to invert, $X = f^{-1}(Y)$ , even though the inverse is unique. A trapdoor one-way function adds one condition: given an extra piece of information, the trapdoor, the inverse becomes easy again. Without the trapdoor it stays infeasible. The public key is the function; the private key is the trapdoor.

Two problems are believed to have this shape, and every scheme in this module rests on one of them:

The Discrete Logarithm Problem (DLP). Given a prime $p$ , a primitive root $g$ of $p$ , and $y = g^x \bmod p$ , find $x$ . Diffie and Hellman (1976) proposed this as computationally infeasible for certain $p$ . The full treatment — primitive roots, and how to compute a discrete log by hand for a small $p$ — is on discrete logarithms and primitive roots. Diffie-Hellman key exchange rests on this problem directly.

The RSA problem. Given $c$ , $e$ and $n$ where $c = m^e \bmod n$ , find $m$ — the $e$ -th root of $c$ modulo $n$ . This is believed computationally infeasible for certain $n$ . RSA rests on this problem.

Both problems share the same trapdoor shape: “computationally infeasible” turns into “easy to compute” the moment one extra piece of information — the private key — is available.

Exam detail

Getting confidentiality and origin authentication backwards is the single easiest mistake on this page. Confidentiality encrypts with the receiver’s public key — anyone can lock the box, only the receiver has the key that opens it. Origin authentication encrypts with the sender’s own private key — only the sender could have locked it, so anyone who can open it with the sender’s public key has proof of who sent it. The two are mirror images of each other, and a question that names one is testing whether you reach for the right mirror.

Compare

Easy forwards, infeasible to invert — full stop. No amount of extra information the function’s designer controls makes the inverse tractable again.

Easy forwards, infeasible to invert unless you hold the trapdoor. The trapdoor is exactly what turns “infeasible” into “easy” — and it is exactly what a private key is.

Pitfall

Requirement 6 (either order recovers $M$ ) is convenient, not defining. RSA happens to have this property, which is why the same RSA key pair can, in principle, do both encryption and signatures — but the lecture is explicit that a scheme failing requirement 6 can still be a perfectly valid public-key cryptosystem, provided it meets requirements 1 through 5.

Source

Week 5 notes PDF