F-PKE — Public-key encryption

F-PKE (Public-key encryption) is part of Public-Key Primitives in the UC functionality encyclopedia. Status: a canonical, well-established UC functionality.

Encryption as a table, not as an algorithm. The adversary hands over the key and hands over every ciphertext; the functionality’s only job is to remember which ciphertext it gave for which plaintext, and to answer a decryption from that memory. Confidentiality is then not a computational claim but the plain observation that line 10 does not pass \(m\) to the adversary — and the entire security of the notion is the difference between line 10 and line 9, which does.

That shape is deliberate. The source says it is “written in a way that allows realizations consisting of three non-interactive algorithms without any communication”, which is why an encryption scheme rather than a protocol can realize it.

Functionality

Reading the box: \(\mathcal{A}(\cdot)\) is a call on the adversary slot whose answer is used; require refuses the call, and the framework answers \(\textsf{rej}\), so no return is written for it; \(\square\) marks a value never set; \(D\) is the parameter, a message domain; \(\mathtt{Rec}\) maps a ciphertext to the plaintext it was recorded for.

Functionality \(\mathcal{F}_{\mathsf{PKE}}\)
\(\mathit{pid}\),   \(\mathbf{P}\),   \(\mathbf{N}\),   \(\mathbf{U} := \{(\mathcal{A},\mathsf{serves})\}\),   \(\mathit{par} := D\)
Initialize():
  1. \(\mathtt{e} \gets \square\);  \(\mathtt{R} \gets \square\)// the recorded key and its owner
  2. \(\mathtt{Rec}[*] \gets \square\)// ciphertext to plaintext
id.KeyGen()from id′
  1. \(e \gets \mathcal{A}\bigl(\mathit{id}.\mathsf{KeyGen}\bigr)\)// the adversary supplies the key
  2. \(\textbf{if}\ \mathtt{e} = \square\ \textbf{then}\)
  3. \(\mathtt{e} \gets e\);  \(\mathtt{R} \gets \mathit{id}.P\)// only the first activation is recorded
  4. \(\textbf{return}\ e\)
id.Encrypt(e', m)from id′
  1. \(\textbf{require}\ m \in D\)
  2. \(\textbf{if}\ e' \neq \mathtt{e}\ \textbf{then}\)
  3. \(\textbf{return}\ \mathcal{A}\bigl(\mathit{id}.\mathsf{Encrypt}, e', \mathit{id}.P, m\bigr)\)// wrong or absent key: \(m\) goes too, nothing is recorded
  4. \(c \gets \mathcal{A}\bigl(\mathit{id}.\mathsf{Encrypt}, e', \mathit{id}.P\bigr)\)// the plaintext is withheld
  5. \(\textbf{require}\ \mathtt{Rec}[c] = \square\)// a repeated tag is an error
  6. \(\mathtt{Rec}[c] \gets m\)
  7. \(\textbf{return}\ c\)
id.Decrypt(c)from id′
  1. \(\textbf{require}\ \mathit{id}.P = \mathtt{R}\)// the key's owner, and only it
  2. \(\textbf{if}\ \mathtt{Rec}[c] \neq \square\ \textbf{then}\)
  3. \(\textbf{return}\ \mathtt{Rec}[c]\)
  4. \(\textbf{return}\ \mathcal{A}\bigl(\mathit{id}.\mathsf{Decrypt}, c\bigr)\)// never encrypted here: the adversary answers
id.Leak()from id′
  1. \(\textbf{if}\ \mathit{id}.P = \mathtt{R}\ \textbf{then}\)
  2. \(\textbf{return}\ (\mathtt{e}, \mathtt{Rec})\)
  3. \(\textbf{return}\ \mathtt{e}\)// the key is public

The box is transcribed from Canetti, Krawczyk and Nielsen, Relaxing chosen-ciphertext security, ePrint 2003/174, revision 20030819:195126, Figure 2, p. 7 (PDF page 9) — “the public-key encryption functionality”. Printed page numbers run two behind the PDF’s paging; _src/sources.json records both. The rendered page is at _src/canetti2003-p9.png.

A provenance note, and it is the finding on this page. This functionality is printed in at least two places that do not agree. Canetti, Halevi and Katz reproduce it in the appendix of Adaptively-secure, non-interactive public-key encryption and say it is “taken almost verbatim” from the paper above — but the two differ in two respects, and one of them is load-bearing:

  • The version above ends its encryption clause with “if the tag \(c\) already appears in a previously recorded pair then return an error message” — line 11. The reproduction drops that clause. Without it a realization may reuse a ciphertext for two different plaintexts, and a later decryption is answered from whichever pair was recorded first.
  • The reproduction binds the decryptor into the session identifier, \(\mathit{sid} = (\mathit{sid}_{0}, R^{*})\), and ignores a key generation from anybody else. The version above lets any party generate, records the first, and then lets only that party decrypt — which is line 5 and line 14 here.

This page takes the earlier, stronger version, because it is the one the later paper attributes to and because the uniqueness clause is a real requirement rather than an editorial flourish. A protocol proved against the reproduction is not proved against this box.

Line 9 is where confidentiality is given up, on purpose. If the key is not the recorded one, the plaintext goes to the adversary and nothing is recorded. That is the functionality saying: encryption under a key nobody registered protects nothing. It is also what makes the box realizable — a simulator that does not know the decryption key cannot produce a consistent ciphertext without seeing the message.

Line 11 is the uniqueness clause and it is a require, so a repeated tag refuses the call. The source returns an error message to the encryptor, which is the same observable outcome in this framework.

Line 17 is the decryption oracle, and it is the whole reason RCCA exists. A ciphertext the functionality never issued is decrypted by asking the adversary. That is maximally permissive — the adversary may answer anything — and it is exactly the clause the same paper’s F-rPKE refines. Read the two boxes side by side; they differ in one operation.

Leak splits by role, and the source’s corruption clause is where it comes from (lines 18–20). The key is public, so everybody’s leak carries it; the recorded table is the decryptor’s secret, so only the decryptor’s leak carries that.

Known realizations

Non-adaptively, from CCA-secure encryption. The source’s framing is that a scheme \(S\) becomes a protocol \(\pi_{S}\) in the obvious way, and the notion “UC-CCA” is that \(\pi_{S}\) realizes this functionality. The equivalence with the game-based definition is the paper’s subject: standard CCA security corresponds to realizing this box, and the relaxation of both is what the paper introduces.

Adaptively, it needs more than encryption. Adaptive corruption is what F-aPKE is about, and the reason it is a separate entry is that this box is unrealizable adaptively by a scheme with short ciphertexts — the standard non-committing-encryption obstruction, the same one that appears on F-SMT.

Properties

  • Correctness, with probability exactly \(1\). Line 12 records and line 16 reads the same cell. No adversary line can revise a recorded pair.
  • Confidentiality, unconditionally, for the registered key. Line 10 passes the caller’s identity and not \(m\). There is no path from \(m\) to the adversary when \(e' = \mathtt{e}\).
  • Ciphertext uniqueness, with probability exactly \(1\) (line 11) — in this printing of the functionality, and not in the reproduction discussed above.
  • No integrity for unknown ciphertexts. Line 17 hands the answer to the adversary, so a ciphertext the box never issued decrypts to whatever the adversary likes. This is not CCA security failing; it is where the model puts the adversary’s power, and constraining it is the subject of the sibling entry.

Formal artifacts

No machine-checked formalization yet.

References:

  • Canetti, Krawczyk, and Nielsen. Relaxing chosen-ciphertext security. In Advances in Cryptology – CRYPTO 2003, pages 565–582, 2003. Read at ePrint revision 20030819:195126. Figure 2, p. 7 (PDF page 9), the definition transcribed above, including the ciphertext-uniqueness clause; §3.1, p. 10, for the RCCA modification that F-rPKE takes; the discussion above Figure 2 for the three-algorithm realizability remark. Authors, venue and page range confirmed against DBLP.
  • Canetti, Halevi, and Katz. Adaptively-secure, non-interactive public-key encryption. In 2nd Theory of Cryptography Conference (TCC), pages 150–168, 2005. Read at ePrint revision 20041124:031924. Appendix B.1, p. 33 (PDF page 35), the reproduction described above, which drops the uniqueness clause and binds the decryptor through the session identifier. Its own functionality is the subject of F-aPKE. Authors, venue and page range confirmed against DBLP.