F-rPKE — Replayable CCA encryption

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

F-PKE with one clause changed, and the change is the whole idea of RCCA: an adversary is allowed to produce a different ciphertext that decrypts to the same plaintext. Full CCA security forbids that, and forbidding it turns out to be more than applications need — mauling a ciphertext into another encryption of the same message gains an attacker nothing, so a definition that rules it out is stronger than necessary and rules out otherwise-good schemes.

The relaxation is line 20. Where F-PKE lets the adversary answer an unknown decryption with any plaintext, this box lets it answer either with a plaintext or with a pointer to a ciphertext the functionality already issued — and in the second case the functionality looks the plaintext up itself, so the adversary causes a replay without learning what was replayed.

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 message domain; \(\mathtt{Rec}\) maps a ciphertext to its plaintext; \(\alpha\) is the adversary’s tag, either \(\textsf{plaintext}\) or \(\textsf{ciphertext}\).

Functionality \(\mathcal{F}_{\mathsf{rPKE}}\)

\(\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′

3. \(e \gets \mathcal{A}\bigl(\mathit{id}.\mathsf{KeyGen}\bigr)\)// the adversary supplies the key
4. \(\textbf{if}\ \mathtt{e} = \square\ \textbf{then}\)
5. \(\mathtt{e} \gets e\);  \(\mathtt{R} \gets \mathit{id}.P\)// only the first activation is recorded
6. \(\textbf{return}\ e\)

id.Encrypt(e', m)from id′

7. \(\textbf{require}\ m \in D\)
8. \(\textbf{if}\ e' \neq \mathtt{e}\ \textbf{then}\)
9. \(\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
10. \(c \gets \mathcal{A}\bigl(\mathit{id}.\mathsf{Encrypt}, e', \mathit{id}.P\bigr)\)// the plaintext is withheld
11. \(\textbf{require}\ \mathtt{Rec}[c] = \square\)// a repeated tag is an error
12. \(\mathtt{Rec}[c] \gets m\)
13. \(\textbf{return}\ c\)

id.Decrypt(c)from id′

14. \(\textbf{require}\ \mathit{id}.P = \mathtt{R}\)// the key's owner, and only it
15. \(\textbf{if}\ \mathtt{Rec}[c] \neq \square\ \textbf{then}\)
16. \(\textbf{return}\ \mathtt{Rec}[c]\)
17. \((\alpha, v) \gets \mathcal{A}\bigl(\mathit{id}.\mathsf{Decrypt}, c\bigr)\)
18. \(\textbf{if}\ \alpha = \mathsf{plaintext}\ \textbf{then}\)
19. \(\textbf{return}\ v\)
20. \(\textbf{require}\ \alpha = \mathsf{ciphertext} \ \wedge\ \mathtt{Rec}[v] \neq \square\)// no such ciphertext: the source halts
21. \(\textbf{return}\ \mathtt{Rec}[v]\)// a replay decrypts, and the adversary never learns to what

id.Leak()from id′

22. \(\textbf{if}\ \mathit{id}.P = \mathtt{R}\ \textbf{then}\)
23. \(\textbf{return}\ (\mathtt{e}, \mathtt{Rec})\)
24. \(\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, §3.1, p. 10 (PDF page 12). The source defines this functionality as a delta: “identically to \(\mathcal{F}_{\textsc{pke}}\) from Figure 2 except that step 2 of the Decryption stage is re-defined as follows”. Everything above line 17 is therefore Figure 2, p. 7, transcribed exactly as on F-PKE; lines 17 to 21 are §3.1. The rendered pages are at _src/canetti2003-p9.png and _src/canetti2003-p12.png.

A note on presenting a delta as a whole box. The source prints only the changed clause. A page that printed only the clause would not be a functionality, so the box above is the composition — and the honest way to read it is that lines 1–16 and 22–24 carry no independent authority beyond F-PKE’s. If the two pages ever disagree outside Decrypt, this page is wrong.

Line 21 is the relaxation, and the parenthesis in the source is the point. The adversary names a ciphertext \(v\); the functionality finds the recorded pair and returns its plaintext — “without letting the adversary know what this value is”, as the source puts it. So the adversary gains the ability to make an unknown ciphertext decrypt to the same thing as a known one, and gains no information in doing so. That asymmetry is what makes the relaxation safe for applications: the attacker can replay, and replaying tells it nothing.

Line 20 refuses where the source halts. The printed clause says “if no such \(c_{0}\) is found then halt” — the functionality stops, which in the older framework means the whole execution ends. A long-lived box cannot halt, so the condition becomes a require and the call is refused. The observable difference is confined to the adversary: it learns that its pointer was invalid, where the source would have ended the run. Since the adversary chose the pointer, this hands it nothing it did not already know.

Line 19 is F-PKE’s line 17, unchanged. The adversary may still answer with an outright plaintext. RCCA does not remove that power; it adds the pointer form beside it. A reader expecting the relaxation to constrain the adversary has it backwards — the functionality is weaker than F-PKE, which is why more schemes realize it.

Known realizations

The equivalences are the paper’s subject. It defines three notions — UC-RCCA (realizing this box), IND-RCCA and NM-RCCA, the latter two as relaxed CCA games — and proves them equivalent for encryption schemes with super-polynomial message domains. So this functionality is not an isolated UC artefact: it has a game-based characterisation, which is what makes it usable by anyone not working in this framework.

Definition 3 in the source is the statement to cite: a scheme \(S\) is UC-RCCA secure if \(\pi_{S}\) securely realizes this functionality with respect to non-adaptive adversaries. The restriction is not incidental — adaptive corruption raises the same non-committing-encryption obstruction that F-aPKE exists to address.

Why it matters practically. The paper’s motivation is that CCA security is stronger than applications need, and RCCA is the weakest relaxation that still supports them. On this site the clearest downstream use is F-SMT, whose entry already cites this paper for exactly that: secure channels can be built from RCCA-secure encryption.

Properties

• Correctness, with probability exactly \(1\). Lines 15–16, unchanged from F-PKE.
• Confidentiality, unconditionally, for the registered key. Line 10 withholds the plaintext, and line 21 returns a recorded plaintext to the decryptor — never to the adversary.
• Replay is permitted and is the only added power. Line 21 is reachable exactly when the adversary can name a previously issued ciphertext. It cannot invent a pairing: the plaintext returned is one the functionality itself recorded.
• Strictly weaker than F-PKE. Every environment distinguishing a realization of this box from the ideal one also distinguishes for F-PKE, since F-PKE’s decryption behaviour is the \(\alpha = \textsf{plaintext}\) branch. The converse fails, which is the entire content of the relaxation.

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. §3.1, p. 10 (PDF page 12), the redefined decryption clause transcribed above, and its parenthesis on what the adversary does not learn; Figure 2, p. 7, for the remaining sixteen lines; Definition 3 for the non-adaptive restriction; §3.2 for IND-RCCA and NM-RCCA and the equivalence. Authors, venue and page range confirmed against DBLP.