G-PKI — Global, non-encapsulated PKI

G-PKI (Global, non-encapsulated PKI) is part of Idealized Setup and Resources in the UC functionality encyclopedia. Status: an idealized setup assumption or shared resource.

A single, shared directory binding a verification key to the party that registered it, closing the gap F-Sig deliberately leaves open (its Verify takes a key unconnected to any caller, since keys are not assumed authenticated on their own). Global in Canetti’s sense: at most one copy exists in any system, and every session reaches that one instance, since a second directory would mean a second notion of who owns which key.

Functionality

Reading the box: \(\mathsf{San}[\mathsf{Clean}](\cdot)\) resamples until the named predicate holds, with \(\mathsf{Clean}_{\mathsf{reg}}\) written out at the end of the box; \(\mathbf{C}\) is the set of corrupted parties; \(A\) and \(Z\) are the adversary’s and environment’s name components, so a test on \(\mathit{id}'.F\) asks who is really placing the call. The process id is pinned to a constant and \(\mathbf{N}\) admits every standard, adversarial and environment id — that is what makes the directory global.

Functionality \(\mathcal{G}_{\mathsf{PKI}}\)

\(\mathit{pid} := (\mathsf{GPKI},0,0)\),   \(\mathbf{P}\),   \(\mathbf{N} := \mathbf{Std} \cup \mathbf{A} \cup \mathbf{Z}\),   \(\mathbf{U} := \varnothing\),   \(\mathit{par} := \bot\)

Initialize():

1. \(\mathtt{VK} : \mathcal{G}_{\mathsf{PKI}}.\mathbf{P} \to \mathcal{K} \cup \{\square\}\)
2. \(\mathtt{VK}[*] \gets \square\)

id.Register(vk)from id′

3. \(\textbf{if}\ \mathit{id}'.F \in \{A,Z\} \ \wedge\ \mathit{id}.P \notin \mathbf{C}\ \textbf{then}\)
4. \(\textbf{return}\ \mathtt{VK}[\mathit{id}.P]\)// a peek, not a write
5. \(\textbf{if}\ \mathtt{VK}[\mathit{id}.P] \neq \square\ \textbf{then}\)
6. \(\textbf{return}\ \mathtt{VK}[\mathit{id}.P]\)
7. \(\mathit{vk} \gets \mathsf{San}[\mathsf{Clean}_{\mathsf{reg}}](\mathit{vk}; \mathtt{VK})\)
8. \(\mathtt{VK}[\mathit{id}.P] \gets \mathit{vk}\)
9. \(\textbf{return}\ \mathit{vk}\)

id.Retrieve(P)from id′

10. \(\textbf{return}\ \mathtt{VK}[P]\)

id.Leak()from id′

11. \(\textbf{return}\ \mathtt{VK}\)

Clean_reg(vk; VK):

12. \(\textbf{return}\ \mathit{vk} \in \mathcal{K} \ \wedge\ \neg\exists\, P : \mathtt{VK}[P] = \mathit{vk}\)

The box is transcribed from UC for Gamers (§16.1, p. 152), line numbering and all. The state is a single table, and Register is the only operation that writes to it; the other three read.

Three lines carry the whole design:

• Line 3 turns Register into a read whenever an outsider — the adversary or the environment — calls on behalf of an honest party: it gets a peek at what is on file and never a write. Registering on behalf of a corrupt party falls through and proceeds freely, which is why the guarantees below are about what the directory enforces, not about what an honest-looking key means.
• Line 5 makes the first successful registration permanent: a party with a key on file gets that key back, whatever it offers. There is no test of who offered it and no way to overwrite, so a corrupt party’s later attempt to swap its own key is indistinguishable from a repeat call.
• Line 7 sanitizes the offered key to be one no other party has claimed. This is the only condition \(\mathsf{Clean}_{\mathsf{reg}}\) imposes beyond membership in \(\mathcal{K}\), and it is exactly what makes the binding property hold.

Retrieve answers any caller with whatever is on file, or \(\square\) if nobody has registered — a directory is public by nature — which is why Leak costs nothing: the whole table is no more than Retrieve already gives out one entry at a time.

There is deliberately no Deregister: a key once bound stays bound. Revocation would be a genuine addition to this functionality, not a gap left open by oversight.

Known realizations

An idealization of a certificate authority or append-only public directory; realized in practice by any PKI whose issuance policy amounts to “first claim wins, no two parties share a key.”

Properties

Both proven with probability exactly \(0\) against every occupant of the adversary slot:

• Fixity. A party’s registered key never changes once set — every later registration by that party returns the same key, whatever is offered.
• Binding. No two distinct parties ever hold the same key on file.

Registering on behalf of a corrupt party proceeds freely (the adversary supplies whatever key it likes for a party it controls), so binding and fixity are guarantees about what the directory itself enforces, not about what an honest-looking key means.

Formal artifacts

No machine-checked formalization yet.

References:

• Canetti, Shahaf, and Vald. Universally composable authentication and key-exchange with global PKI. In Public-Key Cryptography (PKC), Part II, volume 9615 of LNCS, pages 265–296, 2016.
• UC for Gamers, this site’s own book draft on composable security. Chapter “Public-Key Infrastructure” gives the functionality above and both properties in full.