Public-key encryption and key encapsulation
Anyone can encrypt a message to a recipient's public key, or encapsulate a fresh shared key under it, and only the holder of the matching secret key can recover it.
What it is
A public-key encryption (PKE) scheme has three algorithms. KeyGen outputs a public key and a secret key. Enc encrypts a message under the public key, and Dec recovers it with the secret key. A key encapsulation mechanism (KEM) replaces Enc and Dec by Encaps, which outputs a ciphertext together with a fresh shared key, and Decaps, which recovers that key from the ciphertext. Correctness may hold only with overwhelming probability: lattice- and code-based schemes have a small decryption-failure probability. Security asks that ciphertexts hide the message, or that the encapsulated key look random, under chosen-plaintext or chosen-ciphertext attack. The public-key idea comes from , which gave public key distribution rather than encryption.
Core notions
- IND-CPA: an adversary that picks two messages cannot tell which one a challenge ciphertext encrypts. This indistinguishability notion and semantic security go back to . Encryption must be randomized: deterministic schemes such as textbook RSA () cannot be IND-CPA.
- IND-CCA1 and IND-CCA2: the adversary also gets a decryption oracle, before the challenge only (CCA1) or also afterwards on every ciphertext except the challenge (CCA2, adaptive chosen-ciphertext attack). IND-CCA2 implies non-malleability. ElGamal () is IND-CPA under DDH but malleable, so not IND-CCA2.
- KEM/DEM hybrid encryption: a KEM establishes a key and a symmetric data encapsulation mechanism (DEM), typically an AEAD scheme, encrypts the message. An IND-CCA KEM combined with a one-time IND-CCA DEM gives an IND-CCA hybrid PKE.
- Proof model: standard model or random-oracle model (ROM); for post-quantum security, the quantum ROM (QROM), where hash queries may be in superposition.
- Fujisaki–Okamoto (FO) transform: turns a weakly secure PKE into an IND-CCA scheme in the ROM by deriving the encryption randomness from a hash of the message and re-encrypting during decryption to reject malformed ciphertexts (). Modern KEM variants split it into a derandomization step and a KEM step with explicit or implicit rejection (); decryption failures enter the security bound.
- Post-quantum assumptions: module-LWE for Kyber and ML-KEM; hardness of decoding for code-based schemes such as McEliece (); learning parity with noise (LPN), where the noise rate matters.
Main approaches
- Trapdoor permutations with randomized encodings: RSA () with OAEP padding, whose original ROM chosen-ciphertext argument had a generic gap ().
- Discrete-logarithm encryption: ElGamal (), and a practical IND-CCA2 scheme in the standard model under DDH and a hash assumption ().
- Code-based encryption: a disguised decodable code plus a bounded error vector (), and LPN-based schemes at low noise (, ).
- Module-lattice KEMs: Kyber, an FO-type KEM over module-LWE (), standardized with three parameter sets as ML-KEM ().
- Hybrid frameworks: HPKE composes a KEM, a key-derivation function, and an AEAD scheme in base, pre-shared-key, authenticated, and authenticated-PSK modes ().
Notation used in the comparison table
Parameters below occur in efficiency or security bounds. Each meaning is scoped to its stated regime. Measured quantities are named in words; protocol objects are defined where used. Source aliases do not equate different regimes.
| Symbol | Meaning | Regime | Paper aliases |
|---|---|---|---|
| λ | Computational security parameter. | PKE/KEM security. | No paper spelling asserted. |
| n | Length of the LPN secret vector. | LPN-based PKE. | No paper spelling asserted. |
| m | Number of LPN samples (rows of the sample matrix). | LPN-based PKE. | No paper spelling asserted. |
| μ | Bernoulli noise rate. | LPN-based PKE. | No paper spelling asserted. |
| ε | Positive constant slack in an asymptotic exponent. | LPN noise regimes. | No paper spelling asserted. |
| δ | Decryption-failure/correctness error probability in the specified experiment. | FO/KEM reductions. | No paper spelling asserted. |
| Q | Total oracle-query count. | ROM/QROM adversaries. | writes q; writes q |
| d | Sequential oracle-query depth. | QROM reductions. | writes d |
| η | Injectivity parameter of the stated derandomization notion. | KSSSS FO reduction. | writes η |
| c | Positive constant in the sparse 3LIN sample/noise tradeoff. | Sparse 3LIN; not the dense-LPN sample count. | No paper spelling asserted. |
| dG | Sequential query depth to the encryption-coins oracle. | QROM multiplicative-loss bound. | No paper spelling asserted. |
| dH | Sequential query depth to the key-derivation oracle. | QROM multiplicative-loss bound. | No paper spelling asserted. |
This topic covers ordinary PKE, KEMs, generic transforms that change ciphertext security, and hybrid-encryption frameworks, with Diffie–Hellman key agreement as a foundational neighbour. Attribute-based encryption has its own topic; identity-based, functional, searchable, proxy, threshold, and multi-recipient encryption are out of scope. Hybrid classical/post-quantum KEM combiners are not yet covered.