Navigating trust across federated PKI ecosystems · Academic research

A governed graph model for federated trust.

In a sea of cross-certifications, bridge CAs and trust lists, federation relationships remain implicit and hard to reason about.

Like the polar star for a navigator, PolarisChain is a fixed reference that stays outside the route. It reads the trust that others have already established and turns it into a governed graph of keys, on which each receiver computes the certification paths it admits and the one it prefers, whether its domains are traditional, hybrid or post-quantum.

Author
Jorge Pablo Trías Posa
Supervisor
Dr. Mario Aragonés Lozano
Institution
Universitat Politècnica de València
Academic context
Master’s thesis and doctoral research

Abstract. Federated PKIs link sovereign domains through cross-certificates, bridge CAs and trust lists, and RFC 5280 specifies in detail how to validate a certification path once it is given. Yet no standard says which path a verifier should choose when several of them are valid at the same time. PolarisChain models the federation as a graph of keys, compiled from the certificates themselves, and it defines for each receiving domain the paths it admits and the one it prefers.

It establishes no trust of its own, since it only reads the trust that others established and computes over it. From that single object follow three capabilities, which differ in the moment at which they answer: Govern before a cross-certificate is signed, Discover inside the mTLS handshake and Audit after the decision. The post-quantum transition needs no mechanism of its own, because it becomes a cryptographic floor that the receiver demands of every key on the path.

1Motivation

Challenges in federated PKI environments

Cross-certification and bridge CAs have made domains interoperable for years, but as trust topologies grow denser and the cryptographic transition draws closer, discovering, governing and choosing certification paths is still hard to do formally and deterministically, with an eye on the cryptography of each hop.Key idea The paths exist whether or not anyone looks at them, and what has been missing is a way to compute over them before trusting them.

The risk is far from theoretical, as the case of eMudhra showed in October 2026, when eight of its intermediate CAs turned out to hold weak ECDSA keys. Sectigo had cross-certified them, so every verifier that trusted the Sectigo root admitted those keys without ever having decided to trust eMudhra. Passive measurements had already shown that a cross-certificate can keep a trust path valid after a revocation [Hiller2020], and yet nobody had computed what those cross-certificates enabled before they were signed.The eMudhra case. The CA’s final report of 10 November 2026 corrects its first account: the HSM generated correct keys, and a program on the ceremony host cut the private value down to its leading byte [BZ2083449].

Growing complexity of trust topologies

Every new relationship multiplies the paths that lead from an identity to an anchor, and few of them were ever drawn on purpose.

Heuristic validation

Path building stops at the first chain that works, so better admissible paths are never seen.

Lack of trust governance

Trust is inherited from whole hierarchies instead of being bounded, and reaches further than anyone decided.

No crypto agility awareness

Federation rarely weighs the algorithm on each hop, just as traditional, hybrid and post-quantum material starts to coexist.

Pressures that make it worse

Operational lifecycle fatigue

Short-lived certificates, renewals, revocations and policy updates are hard to sustain across many domains at once.

Machine and AI identity explosion

Workloads and agents multiply identities, and the trust graph changes faster than people can follow.

Real-time visibility gap

Nobody sees which trust paths are active right now, which limits audit and incident response.

Software supply chain integrity

Signed artefacts cross domains, and their provenance still rests on implicit trust in foreign repositories.

2Where federation stands

Trust already crosses domains, along paths nobody chose

A PKI binds a public key to an identity, and trust in that binding climbs a chain of certificates up to an anchor that the verifier has chosen. Inside one organisation the problem is solved; the difficulty begins when sovereign domains, each with its own policies and its own cryptography, need to accept each other’s identities.Where the crossings are. Cross-certificates are issued between intermediate CAs, never from a root: the root stays offline and only certifies its own subordinates.

Four models do this today, as figure 1 shows: two of them link the domains with certificates, either through a mesh of bilateral cross-certificates or through a bridge CA in the middle, while the other two rely on a list or an agreement and bound nothing.

The four PKI federation modelsFederation splits into cryptographic approaches (bridge certification and cross-certification in a mesh) and non-cryptographic approaches (common standards and a central broker).FederationCryptographic approachesa certificate links the domainsNon-cryptographic approachesa list or an agreement links themBridge CA2n cross-certificatesFor example: Federal PKI (US)Meshn(n−1) cross-certificatesFor example: PKIoverheid (NL)Common standardsqualification, trusted listFor example: eIDAS (EU)Central brokerredistributes anchorsFor example: ICAO PKDThe four PKI federation modelsFederationCryptographica certificate links themNon-cryptographica list or an agreementBridge CA2n cross-certificatesFor example:Federal PKI (US)Meshn(n−1) cross-certificatesFor example:PKIoverheid (NL)Common standardstrusted listsFor example:eIDAS (EU)Central brokerredistributes anchorsFor example:ICAO PKD
Figure 1. The four federation models, after the World Bank taxonomy [WorldBank].

Once several domains cross-certify, the hierarchy becomes a directed graph, and one credential can have more than one valid path. The Federal PKI playbook shows the same certificate validating through three CAs or through six, with two bridges on the longer route, and which of the two applies depends only on the anchor that is installed.

One credential, two valid pathsThe same end-entity certificate validates through three CAs when the Federal Common Policy CA G2 is the installed anchor, and through six, crossing two bridges, when the Raytheon Technologies root is.Path 1Installed anchor: Federal Common Policy CA G2Federal Common Policy CA G2US Treasury Root CADepartment of Veterans Affairs CAUser (Affiliate)Path 2Installed anchor: Raytheon Technologies Root CARaytheon Technologies Root CACertiPath Bridge CA - G3Federal Bridge CA G4Federal Common Policy CA G2US Treasury Root CADepartment of Veterans Affairs CAUser (Affiliate)Trust anchorBridge CACAEnd-entity certificateOne credential, two valid pathsPath 1Anchor: Federal Common Policy CA G2Federal Common Policy CA G2US Treasury Root CADepartment of Veterans Affairs CAUser (Affiliate)Path 2Anchor: Raytheon Technologies Root CARaytheon Technologies Root CACertiPath Bridge CA - G3Federal Bridge CA G4Federal Common Policy CA G2US Treasury Root CADepartment of Veterans Affairs CAUser (Affiliate)AnchorBridgeCAEnd entity
Figure 2. One credential, two valid paths. Redrawn from the Federal PKI path discovery and validation playbook [FPKI-PDVAL].

If there are several paths, someone has to choose among them, and today nobody has written down how.

Related work

The standards and the verified validators answer a different question from the one asked here. A validator, verified or not, takes a chain and a policy and says yes or no. This work takes a federation and a receiver and says which chains exist for a certificate, which one the receiver prefers, and what would change if a cross-certificate were issued. The two are complementary: the path the model selects still has to pass a validator, and a verified one is a candidate for that final check.Verdict is the closest work to this one, although the question it answers is a different one. Its policy is a first-order predicate over one chain and its path builder is specified over the paths that repeat no certificate, so the universe searched here (paths that repeat no key) is a subset of Verdict’s.

Table 1. What the closest work does, and what it leaves open.
WorkWhat it doesWhat it leaves open
RFC 5280, section 6 [RFC5280]Validates a certification path in full detail.Its first input is the path, already built. It neither searches nor prefers.
RFC 4158 [RFC4158]Describes how to build paths and how to sort candidates heuristically.Informational. It gives no criterion that makes one valid path better than another.
SCVP, RFC 5055 [RFC5055]Lets a client delegate path construction and ask a server for the best path.Never defines what best means, and needs a certificate that already exists.
ARMOR and Verdict [ARMOR2024][Verdict2025]Formally verified validators: the acceptance decision is proved against a specification.They verify whether a chain is acceptable. They do not order the acceptable ones.

3The gap

Validating a path is specified. Choosing it is not.

RFC 5280 validates a chain in detail, but its first input is literally “a prospective certification path”: it does not search for one, and it does not prefer one. RFC 4158 describes how to build paths but is only informational, and SCVP lets a client ask a server for the best path while it never defines what makes a path better.RFC 5280 has been updated nine times since 2008, and the model follows the policy processing of RFC 9618, the noRevAvail extension of RFC 9608 and the CRL key-usage clarification of RFC 10007.

Meanwhile, constraints such as nameConstraints or pathLenConstraint are only checked once a chain has been walked, so path builders explore branches that were condemned before the walk started.Key idea A cross-certificate enables a space of names and policies below the CA it certifies, which is a much narrower thing than the CA itself.

Building a path and validating it are specified by different documentsRFC 4158 describes how candidate paths may be built but is informational. RFC 5280 section 6 validates one path it receives already built. Between them nothing fixes how to choose the admissible path, nor which of several is best. PolarisChain works in that gap.RFC 4158InformationalPath buildingDescribes the certificate graph andheuristics to order candidates.Its goal is to find a path, not toprefer one over another.candidate paths?Which one isadmissible, andwhich is best?no procedure fixedone pathRFC 5280 · section 6Proposed standardPath validationInput (a) of section 6.1.1:"a prospective certification pathof length n"Valid or not, by minimum conditions.SCVP (RFC 5055) can ask a server for id-swb-pkc-best-cert-path, but never defines "best".PolarisChain: admissible subgraph, then a preferenceconstraints decide which paths may exist; the verifier’s cost ranks those that remainBuilding a path and validating it are specified by different documentsRFC 4158 · informationalPath buildingDescribes the certificate graph andheuristics: it finds a path, prefers none.candidate paths?Which one is admissible,and which is best?one pathRFC 5280 · section 6 · proposed standardPath validationInput (a) of section 6.1.1:"a prospective certification pathof length n"SCVP (RFC 5055) can ask a server forid-swb-pkc-best-cert-path, but never defines "best".PolarisChainadmissible subgraph first, then a preference:the verifier’s cost ranks the paths that remain
Figure 3. Building and validating are specified by different documents, and nothing in between says which path to choose.

Today nobody knows what a cross-certificate enables until it has been issued and is already in use.

Before issuing

What does a cross-certificate enable before it is signed?

Constraints are audited only afterwards, when the bridge is already in production and every path it opens is live.

During the handshake

Which admissible path does the receiver prefer, under its own policy?

The vendor of each validation library decides, and it decides in the same way for every receiver that uses it.

After the decision

Why was a path accepted, or why was there none?

A trust store says yes or no, and nothing records the reason behind either answer.

4The proposal

A formal model of the federation, not another federation

Polaris is not on the ship’s route; it is a fixed reference outside it, from which navigators compute their own position. PolarisChain plays the same role, since it establishes no trust relationship and only reads the ones that others established by issuing certificates, which it turns into a graph and computes over.Key idea PolarisChain is a formal model of the federation that the domains have already built, and therefore not a fifth federation model beside the other four.

A bridge, a mesh and a trust list are ways of building roads between domains. PolarisChain is the map of the roads that already exist, with precise rules for which ones may be taken and which one to take. For this reason it works the same over a mesh, a bridge or trust lists, since it describes those models and does not compete with any of them.The precision the image needs. Once the decision moves into the handshake, each domain’s own engine is on the critical path of its own admissions. Two properties still hold, because no domain’s decision is taken by an instance it does not operate and no third party can make it admit a certificate.

PolarisChain computes over the trust that the federation has already established, and adds none of its own.

Table 2. Remove each component and see what falls.
The bridge CAThe federation falls: there is no path between domains.
The cross-certificatesThe federation falls: the hierarchies are isolated again.
The trust listVerifiers are left without anchors.
PolarisChainNothing in the federation falls. Certificates stay signed and any RFC 5280 validator still works. The only loss is knowing what each certificate enables and being able to choose among the paths.

From that single object follow three computable capabilities, and each of them is a question put to the same graph, asked at a different moment and by a different person.

Three capabilities over the same graph, ordered by timeGovern asks before a certificate is issued, Discover during the handshake and Audit after the decision. All three query the same governed graph with the same receiver policy.Governed federation graphcompiled by PolarisChain from the certificatesGovernbefore issuingDiscoverduring the handshakeAuditafter the decisionTimeThree capabilities over the same graph, ordered by timeGoverned federation graphcompiled by PolarisChain from the certificatesTimeGovernbefore issuingDiscoverduring the handshakeAuditafter the decision
Figure 4. Govern, Discover and Audit query the same graph with the same receiver policy. The axis that orders them is time.

Govern

Before a cross-certificate is signed, or a policy changes: which certificates become admissible and which stop being so, for the issuer and for third parties that trust its anchors.

Discover

Inside the handshake: whether an admissible path exists for the presented certificate from an anchor the receiver accepts and, if there are several, which one it prefers.

Audit

After the decision: not another verdict but its reason, one of seven defined outcomes, with a record that reproduces it.

5The model

One common graph, read by each receiver

The model rests on a single object: the certification graph of the federation at an instant. Every domain compiles it the same way from the same published material, and each receiver then queries it with its own policy.Key idea There is one logical graph and there are as many queries as receivers, so two receivers that query the same graph can obtain different routes, which is exactly what the model intends.

The examples use the names of the use case throughout. Domain A publishes its systems under altair.example, and the cross-certificate that Intermediate B issues to Intermediate A permits the names of ops.altair.example, its operations department, while it excludes ext.ops.altair.example, where A enrols the machines of its contractors. The client is erp.ops.altair.example, and B demands of it its own certificate policy pB, which the cross-certificate maps to the policy pA of A.

Definition 1 (key graph). The federation at the instant t is the directed multigraph

G|t = ( V, E|t, src, dst, w, Φ )(1)

whose nodes are the keys of the certification authorities and whose edges are the CA certificates between them that are valid at t.

where

t
The instant at which the federation is looked at.
V
The keys of the certification authorities, each one a node v = ⟨dn(v), pk(v), alg(v)⟩: its distinguished name, its public key and the profile of that key. Each node also carries its domain dom(v), its cryptographic level ℓ(v) and a weak-key flag weak(v).
E|t
The CA certificates between those keys that are within their validity period at t, a subset of every edge E compiled from the material.
src, dst
Two functions E → V that give, for each certificate, the key that signs it and the key it certifies. Two certificates may join the same two keys, so the graph is a multigraph.
w
The cost of each edge as common facts, a function E → ℕ × {0, 1}: the octets that depend on the algorithm, and whether the certificate crosses an administrative boundary.
Φ
The governance constraints of each certificate, a function E → 𝒞 that gives ⟨depth, name, pol⟩: its depth budget, its name constraints and its policy extensions, composed along the path as in RFC 5280, section 6.
(πd, c, t)
The query: the policy of the receiving domain d, which is not part of the graph, the certificate c it is presented and the instant t.

The expression (1) already holds the three traits of the model, and the first is that the graph is governed, because its edges carry the constraints of their certificates and a path is only good if it respects them all. It is temporal, because the set of edges depends on the instant, so a question about the past is the same question asked at another t. And it is common: none of its components depends on who queries it, so two domains that compile the same material obtain exactly the same graph.Nodes are keys. When a CA rotates its key, the new key is a new node, whether or not the algorithm changes. A cross-certificate certifies one key: what the CA signs with the next one is no longer reachable through it.

The domain of a key does not come from any X.509 field but from the scope declaration that each domain signs and publishes, and a declaration only counts for a key if that key signs it too, so no member can claim a key it does not control. A key that nobody claims gets a domain of its own, and the domain enters the cost and never the admission.

5.1 When a certificate is an edge

Not every certificate in the material is an edge, since a certificate issued with the key u for the key v is one only if it meets seven conditions, the first six taken from RFC 5280 and the last from its update in RFC 9608.

  1. The signature verifies with the key src(e), and the two signature algorithm fields agree (RFC 5280, 6.1.3 (a)(1) and 4.1.1.2).
  2. The issuer field matches the name of the CA that holds src(e) (6.1.3 (a)(4)).
  3. basicConstraints has cA set to TRUE (6.1.4 (k)).
  4. If keyUsage is present, it includes keyCertSign (6.1.4 (n)).
  5. The two ends are different keys, so the certificate is not self-signed.
  6. It carries no critical extension that the parser cannot process (6.1.4 (o)).
  7. It does not carry noRevAvail, which RFC 9608 forbids in CA certificates.

These conditions do not constrain paths: they decide whether there is an edge at all, and so they are not part of Φ. Each edge also carries four data that are not constraints: the signature algorithm of its certificate sigalg(e), the names it presents nm(e), the self-issued mark si(e), and the permission crl(e), which holds when its keyUsage carries cRLSign and decides whether the revocation lists signed by the certified key count for whoever reaches it through that edge.Why not issuer and serial number. An edge is identified by the signed content of its certificate together with the key that signs it, id(e) = SHA-256(tbsCertificate, issuer key). Uniqueness of a serial number holds inside one CA, and two unrelated CAs of a federation may share a name.

Of all the edges, the graph at t keeps those within their validity period:

E|t = { e ∈ E : t ∈ time(e) }(2)

where

E
Every edge compiled from the snapshot of the material, whatever its validity.
e
One edge, that is, one CA certificate between two keys.
time(e)
The validity period of its certificate, from the field notBefore to the field notAfter.
t
The instant of the query.

The revocation state cannot be part of the common graph. Evidence only counts if whoever signs it has authority over the certificate, and RFC 5280 binds that authority to the receiver, since the key that signs a revocation list has to validate up to the same anchor as the chain (section 6.3.3 (f)). A common verdict would have to decide that authority without knowing the anchor, and it would then be enough for a member to certify a key of its own under the name of a foreign CA to withdraw that CA’s certificates from every receiver. Each receiver d therefore resolves the state revd(x, t) of a certificate at admission, with three values, because not knowing whether a certificate is revoked is not the same as knowing it is not.

lifed(e) = { t ∈ time(e) : revd(e, t) = good }(3)

where

lifed(e)
The instants at which receiver d can traverse the edge e.
d
The receiving domain. Revocation depends on it, because the authority of the evidence is bound to its anchor.
time(e)
The validity period of the certificate of e.
revd(e, t)
The revocation state of the certificate at t for the receiver: revoked if the applicable evidence revokes it or some evidence did so irrevocably, good if the applicable evidence covers t and holds it good, and unknown otherwise.

The value is revoked if the applicable evidence revokes the certificate or any evidence did so irrevocably, good if the applicable evidence covers t and holds it good, and unknown otherwise. In this work the evidence with authority is the revocation list signed by the same key that issued the certificate, and the applicable one is the most recent issued no later than t and no older than the receiver accepts.

5.2 The policy of the receiver

πd = ( TPd, κd, τd, Adkey, Adsig, σd, Ld, Fd, Dd )(4)

where

TPd
The trust anchor entries, each with its identifier, its key, its initial state s0(d, tp), its provenance and its validity.RFC 5280, 6.1.1 (c) to (i)
κd
The octets that crossing one administrative boundary is worth to the receiver.outside the RFC
τd
The ordered list of cryptographic floors, of one or more elements, from the most to the least demanding.outside the RFC
Adkey, Adsig
The key profiles and the signature algorithms the receiver admits.outside the RFC
σd
The purposes the chain must allow, such as clientAuth.outside section 6
Ld
The largest number of CA certificates in a path.outside the RFC
Fd
The freshness demanded of the log checkpoint, Fdcp, and of the status evidence, Fdev.outside section 6
Dd
The keys the receiver excludes, by a canonical identifier kid(v) of the key material.outside the RFC

A value belongs to the policy if it changes when the verifying domain changes and no certificate is touched. The anchors with their initial state are inputs of section 6.1.1 of RFC 5280; the rest of the policy does not come from that standard.

The receiver does not search for a path from a root but from one of its anchors, and each anchor entry starts the validation in an initial state s0(d, tp) that the receiver fixes, with the names it starts from, the policies it accepts and its depth. A service that authorises by certificate policies demands them here, as the initial policy set of its anchors with explicit policy, so that every admissible path credits at least one policy accepted for that service. If that set gathers policies that grant different rights, the closing step may return different subsets depending on the path, and the service then authorises with the output of the validated path and not with the initial set.

A cryptographic floor is the least level the receiver demands of each CA on the path, the anchor included, and it is a pair that is compared component by component:

ℓ(u) ⪰ τ  ⟺  stage(u) ≥ τstage ∧ nist_category(u) ≥ τcat(5)

where

u
A key of the path, the anchor included.
ℓ(u)
Its cryptographic level, the pair (stage(u), nist_category(u)).
stage(u)
Its migration stage, ordered traditional < hybrid < post_quantum, with the names of RFC 9794.
nist_category(u)
Its NIST security category, from 1 to 5, with 0 for traditional algorithms and the category of the post-quantum component for a hybrid one.
τ
A cryptographic floor, the pair (τstage, τcat) the receiver demands.
⪰
Meets the floor: both components are at least as high. The order is partial, so two levels may not be comparable.

By (5), with τ = (hybrid, 0) the receiver admits hybrid and post-quantum keys of any category; with (post_quantum, 3), only post-quantum keys of category 3 or above, which leaves ML-DSA-44 out. Raising the floor, removing an algorithm or excluding a key takes a subgraph of the common graph, the only part the receiver walks, so those decisions can only remove paths.A list of floors expresses a preference. An adversary who breaks the algorithm of a node presents a certificate fabricated under that node, and if its only path meets the last floor of the list the receiver admits it. The guarantee against forgery is therefore that of the last floor of the list, and no higher.

5.3 The cost, and why posture is not in it

Among the paths the policy lets it consider, the receiver prefers the cheapest. The cost has two levels, the common facts on the edge and the price that one receiver puts on them with a single parameter.

b(e) = |pk(dst(e))| + |sig(e)|   wd(e) = b(e) + κd · cdist(e)
Wd(P) = Σe ∈ P wd(e)
(6)

where

b(e)
The octets of the two parts of the certificate that depend on the algorithm.
|pk(dst(e))|
The size of the public key it certifies, that of the key dst(e).
|sig(e)|
The size of the signature that closes it, made by the key src(e).
cdist(e)
1 if the two keys belong to different administrative domains, and 0 otherwise.
κd
The price receiver d puts on crossing one boundary, in octets.
wd(e)
The cost of the edge for the receiver, in octet-equivalents.
P
A path, a sequence of edges.
Wd(P)
The cost of the path, the sum of the costs of its edges.

The first term of (6), b(e), measures in octets the two parts of a certificate that depend on the algorithm: the public key it carries and the signature that closes it. The second, cdist(e), is 1 when the two keys belong to different administrative domains. The price κd says how many octets crossing one boundary is worth to the receiver, so the cost of a path is measured in octet-equivalents and computed in exact arithmetic.One parameter is enough. Selection does not change if every cost is multiplied by the same positive constant, so two weights and a scale choose exactly what κd chooses.

Table 3. Reference sizes in octets, and the level ℓ(v) of a key of each algorithm. ML-DSA sizes are those of FIPS 204; composite sizes are the sum of the two components, as in RFC 10073.
AlgorithmSignaturePublic keystagenist_category
ML-DSA-874,6272,592post_quantum5
ECDSA P-384 + ML-DSA-653,4132,049hybrid3
ML-DSA-653,3091,952post_quantum3
ECDSA P-256 + ML-DSA-442,4921,377hybrid2
ML-DSA-442,4201,312post_quantum2
RSA-4096512512traditional0
RSA-2048256256traditional0
ECDSA P-38410497traditional0
ECDSA P-2567265traditional0

The migration stage and the security category also come from the algorithm, and they could be added along the path as one more term of the cost instead of being demanded through the floor, yet the model deliberately leaves them out. A chain is accepted only if every signature verifies, so an adversary able to forge the signatures of a single CA can fabricate certificates below it, and adding the levels of the nodes would give different numbers to two routes with the same weakest link.

Since the protection of a chain is set by its weakest link, posture is not added into the cost but demanded, as a floor, of every key on the path.

5.4 What the validation carries along a path

Each certificate brings constraints, the path accumulates them in a state, and the transition computes the next state from the previous one. A state is a card with six slots, and the state space S is the set of every possible card, written as a Cartesian product because each card holds one value of each slot at once.

S = ℕ∞ × 𝒯 × 𝒯 × 𝒢pol × ℕ∞3 × 2OID
δ : S × E → S ∪ {⊥}   fint : V × S × 𝒳 → 𝒪 ∪ {⊥}
(7)

where

ℕ∞
The remaining depth, max_path_length: a natural number, or ∞ when there is no limit.
𝒯 × 𝒯
The permitted and the excluded name subtrees, permitted_subtrees and excluded_subtrees: two values of the same type.
𝒢pol
The graph of valid policies of RFC 9618, which replaces the policy tree of RFC 5280.
ℕ∞3
The three policy counters, explicit_policy, inhibit_anyPolicy and policy_mapping.
2OID
The initial set of policies the receiver accepts, any subset of the policy identifiers.
δ
The transition: from a state and an edge, the next state, or ⊥ if the edge breaks a constraint.
⊥
The failure state, which is never left.
fint
The closing step at t: from the last key, the state reached and the presented certificate, the output of the validation, or ⊥.
𝒳, 𝒪
The presented certificates and the outputs of the closing step, the valid policies restricted by the user, as RFC 9618 fixes.
  1. ℕ∞Remaining depthmax_path_length1
    1. 𝒯Permitted name subtreespermitted_subtreesops.altair.example
    2. 𝒯Excluded name subtreesexcluded_subtreesext.ops.altair.example
  2. 𝒢polGraph of valid policiesvalid_policy_graphpB, expecting pA
  3. ℕ∞3Three policy countersexplicit_policy · inhibit_anyPolicy · policy_mapping(0, ∞, ∞)
  4. 2OIDInitial policies the receiver acceptsuser-initial-policy-set{ pB }

The sign × reads “and”: a state holds one value of each slot at once, and S is the set of every combination. 𝒯 appears twice, joined by the bracket, because the permitted and the excluded names are two values of the same type.

Figure 5. The six slots of a state and the product that forms the space S, with the state of the use-case route on reaching Intermediate A.

The transition δ reads from each edge its constraints, the names it presents and its self-issued mark, and returns the next state or the failure state ⊥, which is never left. The closing step fint processes the presented certificate as the last one and returns the valid policies restricted by the user, the output RFC 9618 fixes. A path satisfies Φ for c when it never falls to ⊥ and the closing step accepts it.The only adaptation. RFC 5280 starts its counters with the length of a path that the search does not yet know. The model starts them at ∞, which gives the same decisions, because a path of n certificates applies at most n decrements and the algorithm only asks whether a counter is zero.

5.5 Admissible paths and the selected one

Definition 2 (admissible path). For the receiver d, the presented certificate c, the instant t and a floor τ, a path is admissible when it starts at a valid anchor entry of d, runs over the receiver’s subgraph inside the search universe, satisfies Φ up to and including c, and every certificate of its chain (x1, …, xh+1) is held good by its own issuer.

Padm(d, c, t, τ) = { P ∈ Pathsd,τ(t) ∩ 𝒰d :
freshd(M, t) ∧ P ⊨d,c Φ ∧ ∀i ∈ {1, …, h+1} : statust(P, i) }
(8)

where

Padm(d, c, t, τ)
The paths receiver d may accept for the presented certificate c at the instant t under the floor τ.
Pathsd,τ(t)
The paths that start at a valid anchor entry of d and run over its subgraph under τ, each edge leaving the key the previous one reached.
𝒰d
The search universe: the simple paths, with no key repeated, of at most Ld CA certificates.
freshd(M, t)
The snapshot M is recent: its checkpoint is no older than Fdcp. It guards the whole query.
P ⊨d,c Φ
The path satisfies the constraints for c: the state never falls to ⊥ and the closing step accepts it.
h
The number of CA certificates of the path; the presented certificate is the (h + 1)-th.
statust(P, i)
The i-th certificate of the chain is held good at t, as defined by (9).
statust(P, i) ⟺ exempt(xi) ∨ ( ( i = 1 ∨ crl(ei−1) ) ∧ revd(xi, t) = good )(9)

where

xi
The i-th certificate of the chain (x1, …, xh+1), the certificates of the path followed by the presented one. It is issued by the key vi−1.
exempt(xi)
Holds only for a presented certificate that carries noRevAvail.
i = 1
The first certificate, whose issuer is the anchor: the anchor entry grants it the right to sign lists.
crl(ei−1)
The permission of the certificate through which the path reaches the issuing key: its keyUsage carries cRLSign, as RFC 10007 demands.
revd(xi, t)
The revocation state for the receiver, from the list signed by the key that issued xi.
Root Banchor tpIntermediate BIntermediate AIssuing AcAerp.ops.altair.example

x1 to x3: the h = 3 CA certificates of the pathx4: the presented one, h + 1 = 4

  1. freshd(M, t)The snapshot is recent: its checkpoint is no older than Fdcp. Without it there is no query at all.
  2. Pathsd,τ(t) ∩ 𝒰dThe three CA certificates x1 to x3 are valid at t and join keys of B’s subgraph, without repeating any, and h ≤ Ld.
  3. P ⊨d,c ΦThe state moves with δ from s0 without falling to ⊥, and fint closes the path with cA.
  4. statust(P, i)The list of whoever issued each xi, entitled to sign it on this path, holds it good, from the anchor to the presented certificate, which may be exempt.
P*d(c)Among the paths that meet everything: the first floor of the list that leaves any (j*), the least cost Wd and, on a tie, the order of Sel. It is the route that goes on to explicit validation.
Figure 6. The conditions of an admissible path and the selection, over the use-case route. Hover or focus a condition to see what it checks.

The state of each certificate is resolved by induction along the path. The anchor credits with its list the first certificate, the key that this certifies credits the second, and the issuing CA credits at the end the presented certificate, so the definition ends without recursion. A list only counts if its key may sign it for whoever reaches it along P: for the keys of the path that permission is crl(ei−1), because RFC 10007 demands since June 2026 that the certificate of a list signer carry cRLSign, and for the anchor it is granted by the anchor entry. The value of revd is the same along any path and the permission is not, so two cross-certificates to the same key can give paths with different states.Two profiles of evidence. The standards admit two further signers, an OCSP responder delegated by the issuing key and another key of the same CA after a rotation. Both need an auxiliary path to the same anchor and their dependencies can close in a cycle, so this work leaves them as an extended profile, declared and not proved, and states its results for the direct profile, which is also the one of the laboratory.

The presented certificate is bound into every expression, because the constraints of a cross-certificate apply to everything that comes after it. Three clients of the same Issuing A have the same candidate path and it is admissible for only one: it serves erp.ops.altair.example, but not nominas.rrhh.altair.example, which falls outside the permitted subtree, nor portatil7.ext.ops.altair.example, which falls in the excluded one.

A path is always admissible for a particular certificate, and never towards a CA in general.

Definition 3 (selected path). Among the admissible paths under the first floor of the list that leaves any, the receiver selects the one of least cost, and Sel makes it unique by ordering paths on the key k(P).

P*d(c) = Sel( arg minP ∈ Padm Wd(P) )
k(P) = ( Wd(P), h, idtp, (id(e1), …, id(eh)) )
(10)

where

P*d(c)
The path receiver d selects for the certificate c.
arg min Wd(P)
The admissible paths of least cost, under the first floor of the list that leaves any, τdj*.
Sel
The choice of a single path among them, the first in the order of the key k.
k(P)
The selection key, compared in order: the cost Wd(P), the number of certificates h, the identifier of the anchor entry idtp and the identifiers id(e1), …, id(eh) of its certificates.
id(e)
The SHA-256 digest of the signed content of the certificate together with the key that signs it.

The search universe 𝒰d is the set of simple paths of the key graph with at most Ld CA certificates: no key is visited twice, the rule RFC 4158 recommends, which implies the no-repeated-certificate rule of RFC 5280. The universe is finite, so if any path is admissible there is an optimum and Sel makes it unique, and the search the thesis implements enumerates its admissible paths exactly, which is feasible on the topologies of the laboratory.

Admission (8) is binary and comes first, whereas preference (10) only orders the paths that were admitted. The security of admission does not depend on the cost, which decides which of the admissible paths is validated, recorded and explained, and that makes the route Audit keeps deterministic and reproducible.Two outputs that must not be confused. s* is the state the path reaches before the presented certificate; it explains the decision. o* is the output of the closing step, with the valid policies of RFC 9618, and it is the only one a service may use to authorise.

An admissible path decides whether there is a route to propose and the cost only decides which, but the certificate is not accepted until the server validates that route and TLS checks that the client holds the key.

5.6 A worked example

With admission and selection defined, a whole case can be solved. Receiver B has Root B as its anchor, demands τB = (hybrid, 0), accepts up to five CA certificates and prices a boundary at κB = 6,000 octets. The presented certificate was issued by Issuing C, an ML-DSA-65 CA of domain C, and four candidate paths lead to it. The floor removes the one through domain A at its first crossing, because Intermediate A1 is (traditional, 0). The depth budget removes the one through the bridge on an internal edge of domain C, which is only detected because the graph holds internal edges too.

Worked example: four candidate paths from R_B to the issuing CA Iss_CThe receiver B, with floor (hybrid, 0), has four candidate paths. The floor removes the path through the traditional intermediate of A. The depth budget removes the path through the bridge, inside domain C. Of the two survivors the cost selects the path through the hybrid intermediate, with 22,289 octet-equivalents against 24,046.e1 · 3e4 · 2e2 · 3e5 · 1e8 · 3e3 · 0e10 · 0e6 · 1e7 · 0e9 · 0RBP-384 + ML-DSA-65IBP-384 + ML-DSA-65IA1ECDSA P-384IC1P-384 + ML-DSA-65BrP-384 + ML-DSA-65IC3ML-DSA-87IC2ML-DSA-65IssCML-DSA-65C2 pruned: IA1 is (traditional, 0), below τB = (hybrid, 0)(the floor, at the first crossing)C3 pruned at e7: depth reaches 0(inside domain C, not at a crossing)C1 = (e1, e2, e3) 22,289 selectedC4 = (e1, e8, e9) 24,046edge label: name · pathLenConstraintcost in octet-equivalents, with κ = 6,000 per boundaryWorked example: four candidate paths from R_B to the issuing CA Iss_CRBanchor · P-384+ML-DSA-65e1 · 3IBP-384 + ML-DSA-65C1 · e2 · 3IC1P-384+ML-DSA-65e3 · 0IssCML-DSA-65C2 · e4 · 2IA1ECDSA P-384✕ (traditional, 0): belowthe floor τB = (hybrid, 0)C3 · e5 · 1BrP-384+ML-DSA-65e6 · 1IC2ML-DSA-65✕ e7: depth 0C4 · e8 · 3IC3ML-DSA-87e9 · 0IssCML-DSA-65C1 = (e1, e2, e3) 22,289 ✓C4 = (e1, e8, e9) 24,046label: path · edge · pathLenConstraint; octet-equivalents, κ = 6,000
Figure 7. Four candidate paths from Root B to Issuing C. Two fall to different constraints and the cost selects C₁, the path through the hybrid intermediate.
Table 4. Cost of the edges for receiver B, in octet-equivalents.
EdgeIssuer → subjectb(e)cdistwB
e1Root B → Intermediate B5,46205,462
e2Intermediate B → Intermediate C15,462111,462
e3Intermediate C1 → Issuing C5,36505,365
e8Intermediate B → Intermediate C36,005112,005
e9Intermediate C3 → Issuing C6,57906,579
e4Intermediate B → Intermediate A13,51019,510
e10Intermediate A1 → Issuing C2,05618,056

C₁ costs 22,289 and C₄ costs 24,046, so C₁ wins, and since both cross one boundary and differ only in 1,757 octets, it wins for any κ. It is the right result: both have the same limiting profile, (hybrid, 3), that of Root B and Intermediate B, and all the ML-DSA-87 intermediate of C₄ adds is octets. If the level entered the cost, C₄ could win for having one more post-quantum node without being any more resistant.

The policy changes the optimum in two ways that can be computed, and the first is the floor: a receiver B′ of the same domain with a traditional floor also admits C₂, which crosses two boundaries and carries 5,261 octets less than C₁. C₂ wins as soon as a boundary is worth less than that to the receiver. The example leaves a prediction the laboratory can check, that B selects C₁, and not a proof of the integration, which belongs to the experimental validation.

Cost of the three candidate paths as a function of the price of a boundaryC1 and C4 cross one boundary and rise in parallel, C4 always 1757 octets above C1. C2 crosses two boundaries and rises twice as fast: it is cheaper than C1 below 5261 octets per boundary and dearer above. With a hybrid floor C2 does not compete at all.10,00015,00020,00025,00030,00002,5005,0007,50010,000κ, octets per boundaryW(P), octet-equivalents5,261C₁C₄C₂
Floor τ of the receiver

Candidates C₁ and C₄. Selected: C₁, 22,289 octet-equivalents, against 24,046 for C₄.

Figure 8. The floor decides which paths compete; the price of a boundary decides which of them wins. Move κ and change the floor.

5.7 Three results

The exact enumeration of the example does not scale, and making the search tractable depends on three results that this work states and does not implement, so that pruning by dominance is a deployment extension and not the search of the thesis. Dijkstra’s algorithm with one label per node is not correct on this graph, because two paths can reach the same key with different accumulated states and the dearer one cannot be discarded, since its state may admit continuations the cheaper one forbids. The exact technique is a label-setting search with dominance, as in the resource-constrained shortest path problem.

Proposition 1 (dominance). A label at the key x with anchor entry tp, state s, visited keys U and selection key k dominates another at the same key and anchor with (s′, U′, k′) when s is at least as permissive as s′, U ⊆ U′, k ≤ k′ and the first carries the permission crl whenever the second does. The dominated label can be discarded without losing the selected path.

Proved by argument for the relation defined by accepted continuations. A relation that can be computed component by component and implies it remains open.

Lemma 2 (cycle elimination). If no certificate of the receiver’s subgraph carries policy mappings, or the anchor entry starts with the policy_mapping counter at zero, every walk that repeats a key and is accepted for c contains a simple path that is also accepted for c, at lower cost and with fewer certificates.

Proved by argument and checked by simulation, though it has not yet been reviewed by third parties.

Proposition 3 (complexity). Given the material, an anchor entry and a presented certificate, deciding whether a path exists that passes RFC 5280 validation is NP-complete, even when the key graph is acyclic and there are no policies, depth limits or costs.

Proved by reduction from the path with forbidden pairs problem [Gabow1976]: hardness appears with name constraints alone and paths of unbounded length, because with Ld fixed the enumeration is polynomial.

Soundness and completeness against standard validation are stated but not proved, although the safety of the design does not rest on them alone. The selected path is validated explicitly before it is accepted, so an error of the model in chaining, validity, names or policies becomes a denial and never an undue acceptance as long as the validation library is correct, and what only the engine checks depends on an independent checker.

5.8 The cone of trust and confinement

In a federation any member can publish certificates and evidence, and controlling the transitivity of trust demands knowing which of those publications can change a receiver’s decisions. The answer is stated with its cone of trust, formed by the keys of its valid anchors and every key reached from them along edges of its subgraph under the last floor of its list.

Coned(M, t) = { v : a path of Ed,τdr|t leads from vtp to v, for some tp ∈ TPd(t) }(11)

where

Coned(M, t)
The cone of trust of receiver d over the snapshot M at the instant t.
v
A key of the graph.
Ed,τdr|t
The edges of the receiver’s subgraph at t under the last floor of its list, τdr.
vtp
The key of the anchor entry tp.
TPd(t)
The anchor entries of d that are valid at t.

The cone is not the receiver’s subgraph but the part of it reached from the anchors, so a foreign key that meets the floor and the lists is in the subgraph and stays outside the cone for as long as no certificate leads to it from an anchor. Objd(M, t) names the objects of the snapshot M, certificates or evidence, whose signature verifies with a key of the cone.

The cone of trust of receiver BThree nested sets. The keys of the common graph contain the subgraph of B, the keys that meet its floor and its lists, and the subgraph contains the cone of trust, the keys B reaches from its anchor Root B: Intermediate B, Issuing B and, through the cross-certificate, Intermediate A and Issuing A. Domain M meets the floor but no certificate leads to it, so the revocation list it signs with a key named like Intermediate A changes no decision of B. Intermediate E, excluded by B, and Root F, a weak key, are outside the subgraph. With the floor (hybrid, 0) Intermediate A leaves the subgraph and the cone shrinks to B's own branch.KEYS OF THE COMMON GRAPH V · the same for every domainSUBGRAPH OF B · keys that meet its floor and its listsCONE OF TRUST OF B1Root Banchor · (hybrid, 3)Intermediate B(hybrid, 3)Issuing B(hybrid, 3)Intermediate A(traditional, 0)below the floorIssuing A(traditional, 0)cut off with iterp.ops.altair.exampleclient of A · admittedclient of A · no routeDOMAIN MRoot MKey K′named Intermediate ARevocation listsigned with K′no key of the cone signs it:no decision of B changesOUTSIDE THE SUBGRAPHIntermediate Eexcluded, in DBRoot Fweak keyIntermediate Anow joins themcone of trust of Bsubgraph of Boutside the subgraph1cross-certificate of B to A, whose constraints bound what hangs from itThe cone of trust of receiver BKEYS OF THE COMMON GRAPH VSUBGRAPH OF B1Root BanchorIntermediate B(hybrid, 3)Issuing B(hybrid, 3)Intermediate A(traditional, 0)below the floorIssuing A(traditional, 0)cut off with iterp.ops.altair.exampleadmittedno routeDOMAIN MB does not reach its keysRoot MKey K′named Int. ARevocation listsigned with K′no decision of B changesOUTSIDE THE SUBGRAPHIntermediate Eexcluded by BRoot Fweak keyIntermediate Anow joins themcone of trust of Bsubgraph of B1cross-certificate of B to A, which bounds what hangs from it
Floor τ of receiver B

With the floor (traditional, 0) the cone holds Root B, Intermediate B, Issuing B and, through the cross-certificate, Intermediate A and Issuing A, so the client erp.ops.altair.example has a route. Domain M meets the floor but stays outside the cone, and nothing it signs changes a decision of B.

Figure 9. The cone of trust of receiver B, inside its subgraph, inside the common graph. Change the floor of B and watch the cone follow it.

Proposition 4 (confinement). In the direct profile, with the same policy and the same valid anchor entries, let M and M′ be two snapshots that meet freshd at t and hold the same objects signed by keys of the cone, Objd(M, t) = Objd(M′, t). Then Padm(d, c, t, τ) is the same with both, for every presented certificate c and every floor τ of the list.

Proved by argument for the direct profile. The cones of the two snapshots coincide, every path of the receiver starts at an anchor, and in the direct profile the evidence of each certificate is signed by the key that issued it, which is a node of the path. Not reviewed by third parties nor checked by simulation; in the extended profile it is not proved.

Nothing signed by a domain the receiver does not reach from its anchors can make it admit a certificate or deny one, and inside its cone what a foreign key can get admitted is bounded by the constraints of the receiver’s own edges that lead to it.

6Threat model

Against whom the guarantees hold

The properties of the model do not hold equally against every adversary, and the assets they protect are four: the integrity of the admission decision and its availability, the confidentiality of each domain’s policy and topology, and the integrity of the record of its decisions.

Each domain trusts only what it operates: its governance plane with the compiler, its policy and anchors, the validation library with the policy checker, its TLS stack and its clock. The common log and the material of the other domains are untrusted inputs, whose content has to authenticate itself.Quorum. With n witnesses of which at most f are dishonest, a reader that demands q cosignatures needs 2q − n > f for two accepted checkpoints to share an honest witness, and q ≤ n − f for the honest ones to reach it alone.

The guarantees rest on six hypotheses, of which the first five are needed for any decision:

  1. The signature algorithms the receiver admits under the last floor of its list resist forgery.
  2. SHA-256 resists collisions.
  3. The clocks of the domains agree within the tolerance the compilation profile fixes.
  4. The dishonest witnesses of the log do not exceed the number each reader tolerates.
  5. The founding charter of the federation reaches each reader through an authentic channel.
  6. The material is published in full. This one is needed only for the negative conclusions of Govern.
Table 5. Adversaries considered and the reach of each one.
AdversaryCapabilityAchievesDoes not achieve
Network, no keysReplays public certificates and opens connections.Computation spent at the receiver.Admission: the proof of possession fails.
Holder of a valid certificatePresents it with whatever chain it likes.Its own admission, if it is admissible.Choosing the path, or widening its names or policies.
Malicious or compromised member domainIssues certificates, cross-certificates, evidence and statements, and publishes them.Admission of its subjects within what others’ constraints leave open; attracting the selection with a cheap path; denials or a longer search in the receivers that reach its keys.Fabricating others’ edges, escaping a constraint written in a cross-certificate issued to it, or influencing a receiver that does not reach its keys.
Operator of the common logOmits, delays or reorders entries, shows split views, serves an old state.Denials and, while earlier evidence is still valid, acceptance of a certificate already revoked.Forging entries.
Dishonest witnesses, up to the tolerated numberCosign any checkpoint.Nothing against a reader that demands the minimum quorum.Making two readers accept incompatible histories.
CryptanalyticSigns as any key of a broken algorithm, or as a weak key.Admission through any broken node the receiver admits; forged evidence or checkpoints signed with that algorithm.Anything through the nodes that the floor, the algorithm lists or the exclusions leave out.
Insider of the receiverChanges the policy, the anchors or the decision record.Everything.Out of scope.

The guarantee is strong against the network adversary, the certificate holder and the witnesses, whereas against a member domain or the log operator the design limits the damage without reducing it to a mere denial. The case that prevents it is the omission of evidence: whoever withholds the latest revocation list leaves the previous one in force, for as long as the receiver’s freshness bound Fd allows. Against the cryptanalytic adversary the floor reaches the keys that sign the evidence, because in the direct profile each list is signed by a key of the path itself, but it does not cover the signature of the log or the authentication of the channel. And a domain that the receiver does not reach from its anchors cannot move any of its decisions, which is the confinement of section 5.8.

7Path discovery

From a presented certificate to an admissible path

  1. 1

    Present

    A peer presents its certificate inside the mTLS handshake, and the receiver starts from its own anchors and builds the path from the graph it compiled, so neither the foreign root nor the chain that the peer sends decides anything.

  2. 2

    Admit

    The search walks only the receiver’s subgraph: every key at or above the floor τd, Φ composed edge by edge, the purposes σd allowed, and every certificate held good by the list of the key that issued it, entitled to sign it on that path.

  3. 3

    Prefer

    Among the admissible paths the receiver prefers the one of least cost Wd, measured in octet-equivalents, and Sel makes that choice unique.

  4. 4

    Validate

    The selected path is the only one validated explicitly with a standard library, and if anything is missing or differs the connection is denied, with Audit recording which of seven outcomes it was.

  5. Crossings always link intermediate CAs, so the root of the origin domain is never on the path and the relying party does not need to trust it.

Federated path discoveryadmissible path selected
Federated path discovery across three trust zonesA server in the origin domain D0 presents its certificate to a relying party in the hybrid domain Dn, whose cryptographic floor is (hybrid, 0). The discovery climbs from the certificate through the issuing and intermediate CAs of D0, crosses to an intermediate CA of D1 and then to an intermediate CA of Dn, and ends at the relying party's own root, its trust anchor. Every crossing links intermediate CAs. The root of D0 is not on the path. A candidate through a traditional RSA-2048 intermediate of D2 is pruned, because that key is below the receiver’s cryptographic floor.ORIGIN DOMAIN · D₀Post-quantum · issuer of the certificateFEDERATION TRANSIT · D₁ ‥ Dₙ₋₁Intermediate domainsRELYING-PARTY DOMAIN · DₙHybrid · floor τ = (hybrid, 0) · validatorEnd-entityserver.c.labIssuing CADOMAIN D₀ROLE End-entity issuanceALG ML-DSA-65✓ (post_quantum, 3) ⪰ τIntermediate CADOMAIN D₀ROLE Subordinate CAALG ML-DSA-65✓ (post_quantum, 3) ⪰ τRoot CADOMAIN D₀ROLE Internal rootALG ML-DSA-87not on the pathIntermediate CADOMAIN D₁ROLE Federated transitALG P-384 + ML-DSA-65✓ (hybrid, 3) ⪰ τIntermediate CADOMAIN D₂ROLE Federated transitALG RSA-2048✕ traditional, below τIntermediate CADOMAIN DₙROLE Subordinate CAALG P-384 + ML-DSA-65✓ (hybrid, 3) ⪰ τRoot CADOMAIN DₙROLE Trust anchorALG P-384 + ML-DSA-65✓ anchor of the relying party
Federated path discoveryadmissible path selected
Federated path discovery across three trust zonesA server in the origin domain D0 presents its certificate to a relying party in the hybrid domain Dn, whose cryptographic floor is (hybrid, 0). The discovery climbs from the certificate through the issuing and intermediate CAs of D0, crosses to an intermediate CA of D1 and then to an intermediate CA of Dn, and ends at the relying party's own root, its trust anchor. Every crossing links intermediate CAs. The root of D0 is not on the path. A candidate through a traditional RSA-2048 intermediate of D2 is pruned, because that key is below the receiver’s cryptographic floor.ORIGIN · D₀post-quantum · issuerTRANSIT · D₁ ‥ Dₙ₋₁intermediate domainsRELYING PARTY · Dₙhybrid · τ = (hybrid, 0)End-entityserver.c.labIssuing CAML-DSA-65✓ (post_quantum, 3) ⪰ τIntermediate CAML-DSA-65✓ (post_quantum, 3) ⪰ τRoot CAML-DSA-87not on the pathIntermediate CAP-384 + ML-DSA-65✓ (hybrid, 3) ⪰ τIntermediate CARSA-2048✕ traditional, below τIntermediate CAP-384 + ML-DSA-65✓ (hybrid, 3) ⪰ τRoot CAP-384 + ML-DSA-65✓ relying-party anchor

8Admission at the server

The decision lives where the connection is accepted

The work only ends when the path that the model computes decides whether a connection gets in. PolarisChain sits in the server side of an mTLS handshake: the enforcement point is the TLS endpoint’s own client-certificate check, and the decision point runs in the same process, with no proxy and no network in between.Key idea In TLS the chain that travels is chosen by whoever sends it, whereas the one PolarisChain selects at admission is chosen by whoever receives it and so it never travels.

Each domain splits the work in two planes that can fail separately: an asynchronous governance plane that compiles the graph, and an execution plane on the critical path of the handshake.

Every decision leaves a record with what is needed to reproduce it: the presented certificate, the instant of the decision tdec, the selected and the validated path, the closing output o* with its valid policies, the evidence known for each certificate of the path, and the versions of the graph, of the policy and of the compilation profile. Reproducing it also demands keeping the material those versions point to, because the same certificate evaluated with the same snapshot gives different results before and after it expires. A denial is classified by asking what would have to be relaxed for an admissible path to exist, so that the result does not depend on the order in which the search discarded candidates.Audit outcomes. admitted, validation_mismatch, search_incomplete, unsupported_profile, insufficient_evidence, policy_rejected and no_path, and only the last of them states that there was no route.

Two planes in the receiving domainAn asynchronous governance plane ingests material, compiles the graph and analyses policy. A frontier separates it from the execution plane, which sits on the critical path of the handshake: the PEP in the TLS endpoint, the selector and validator in the same process, and the compiled graph and policy resident in memory. Evidence of each decision feeds governance back.Domain B · own policy and deploymentGovernance plane · asynchronousIngestionCA-to-CA certificates, statusTrust lists: candidates for V, TPLocal acceptance, no edgesGraph compilationX.509 → w(e), Φ(e)G|t = (V, E|t, src, dst, w, Φ)compiled and versionedAdministrationLocal policy πBWhat-if analysis of across-certificate (Govern)Frontier · no call to governance during the handshakegraph precompiled and resident: governance may be downExecution plane · critical pathapplication layerPEP · server TLS endpointclient-certificate callbacksynchronous, returns a boolean,always evaluates, cert. requiredInternal servicesees admitted peers onlyadmitted trafficdenied if validation fails,evidence is missing orthe path differsdecision layerSelector and validator (PDP)in process, no network, no disknameConstraintspathLenConstraint ...queryverdictdata layerLocal G|t and πB, identified, in memoryload, outsidethe handshakeEvidence · feeds governance back (Audit)certificate · selected and validated paths · profile · policy and version · cost · reasonacceptance of the certificate and completion of the handshake are recorded as distinct factsClient of Astandard TLS 1.3 stackno PolarisChain agentproves possessionof its private keyOutside domain BTwo planes in the receiving domainClient of A · outside domain Bstandard TLS 1.3 stack, proves possession of its keyDomain B · own policyExecution plane · in the handshakePEP · server TLS endpointclient-certificate callback, returns a booleanqueryverdictSelector and validator (PDP)in process, no network, no diskLocal G|t and πB, in memoryInternal serviceadmitted peers onlydenied if validation fails,evidence is missing orthe path differsFrontier · no call to governance in the handshakegraph precompiled and resident: governance may be downGovernance plane · asynchronousIngestionCA-to-CA certificates, status, trust listsGraph compilationX.509 → w(e), Φ(e), compiled and versionedAdministrationlocal policy πB, what-if analysis (Govern)loadEvidence · feeds governance (Audit)selected and validated paths, policy version, reason
Figure 10. Two planes in the receiving domain. Adapted from Annex I of the thesis.

Fail closed

No answer, no path, missing evidence or a validated path that differs from the selected one: the connection is denied, with its reason.

Possession stays with TLS

The engine decides whether the issuer is admissible, while only the TLS stack decides whether the peer holds the private key.

No network in the handshake

Graph, policy and status evidence are compiled beforehand and kept in memory, so governance can be down and admission goes on for as long as the material stays within the freshness that the receiver demands. Under a time budget a deployment may admit with the first path that passes validation and note that the optimum was not certified; the thesis enumerates exactly.

Selection, not authority

A standard library validates the selected path, and only that path, and a final checker repeats the receiver’s own limits, so that an error of the engine becomes a denial and never an undue acceptance.

The handshake, step by step
mTLS admission governed by PolarisChainA TLS 1.3 handshake in which the server requests a client certificate. When the client presents it, the PEP callback fires and calls the PDP in the same process. The PDP selects a path on the admissible subgraph, validates it with an existing library and checks that the validated path is the selected one. The PEP applies the boolean; TLS still verifies proof of possession. Only then does the internal service see the request.Domain ADomain BClient of Astandard TLS stackPEPserver TLS endpointPDPPolarisChain engineInternal serviceafter the handshakeGovernanceoutside the handshakePreparation · outside the critical pathPhase 1 · key exchangePhase 2 · server parametersPhase 3 · authenticationAdmission decision · PEP and PDP in the same processmTLS session, end to end0b certificate required; callback setfrom here on, everything is encrypted8 no application data to an unauthenticated peer11 callback fires, with or without platform errors13 filter by Φ, τB, σB; order by wB; tie-break by certificatevalidate with the library under the declared profile; compare paths16 TLS checks proof of possession, the other gate0a load compiled G|t and πB1 ClientHello2 ServerHello4 EncryptedExtensions5 CertificateRequest6-7 Certificate, CertificateVerify, Finished10 Certificate (c_A), CertificateVerify, Finished12 ResolvePath(c_A, π_B, context)15 verdict: selected = validated, policy met17 otherwise: TLS alert and close18 POST /v1/resource (same TLS session)20 200 OKmTLS admission governed by PolarisChainDomain ADomain BClientPEPPDPServiceGov.Preparation · outside the handshake0a load compiled G|t and πB0b client certificate required; callback setKey exchange and parameters1 ClientHello2-5 ServerHello … CertificateRequestAuthentication6-7 Certificate, CertificateVerify, Finished8 no application data to an unauthenticated peer10 Certificate (c_A), CertificateVerify, FinishedAdmission · PEP and PDP in one process11 callback fires, with or without platform errors12 ResolvePath(c_A, π_B, context)13 filter by Φ, τB, σB; order by wB; validate; compare15 verdict: selected = validated16 TLS checks proof of possession, the other gate17 otherwise: TLS alert and closemTLS SESSION18 POST /v1/resource (same session)20 200 OK
Figure 11. mTLS admission governed by PolarisChain, with the PEP at the server endpoint and a local PDP. Adapted from Annex II of the thesis.

9The common log

Everyone compiles the same material

For every domain to reason over the same federation, they need a common place to read the material from and a way to check it has not been altered. PolarisChain adopts the architecture of Certificate Transparency[RFC6962], with another object recorded: certificates between CAs, trust lists, and the signed manifests of each version a domain activates.Material, never decisions. Everything a domain publishes means the same to every reader, whereas its policy and the version it activates belong to it alone and are never published.

Entries are leaves of a Merkle tree, and signed checkpoints allow proofs of inclusion and of consistency. The operator can omit an entry but cannot forge one without some proof failing; witnesses and monitors make a split view detectable. The log cannot give freshness by itself, because an old checkpoint still passes every proof, and that is why each receiver bounds its age in its own policy.

The log works like a minute book with numbered pages, in which one can only ever write at the end.

The federation’s common log: who publishes, who verifies, who decidesDomains publish signed material into a single append-only log organised as a Merkle tree, as in Certificate Transparency. The operator orders entries and signs checkpoints. Each domain’s compiler reads a snapshot up to a checkpoint, verifies it and compiles its own graph. Witnesses co-sign checkpoints and monitors check inclusion and consistency.Domains · publishCA-to-CA certificatestrust lists and statusa signed scope declarationversion manifests (CMS)material, never decisionsOperatoraccepts signed entries only,orders them, signs checkpointscan omit, cannot forgeCommon log · append-only Merkle treeR = I(N12, N34)N12 = I(h1, h2)N34 = I(h3, h4)h1=L(m1)m1cross-certIB → IA, by Bh2=L(m2)m2trust listby Ch3=L(m3)m3manifestB-47, by Bh4=L(m4)m4manifestC-19, by CL(m) = H(0x00 || enc(m))I(a, b) = H(0x01 || a || b)the prefixes separate a leaf from an internal nodeCheckpoint"At date D this log has N entries and root R."Signed by the log, co-signed by witnesses. It fixes the snapshot M.Compiler of Breads M up to a checkpoint,with inclusion andconsistency proofscompiles its own G|tpublishes the manifest m3Witnesses, monitorsco-sign checkpoints; checkinclusion, consistency andsignatures; compare viewsMirrorsserve static, cacheable tilesThe federation’s common logDomains · publishCA-to-CA certificates, trust lists and status,a signed scope declaration, version manifestsmaterial, never decisionsCommon log · append-only Merkle treeR = I(N12, N34)N12 = I(h1, h2)N34 = I(h3, h4)h1=L(m1)m1cross-certby Bh2=L(m2)m2trust listby Ch3=L(m3)m3manifestB-47h4=L(m4)m4manifestC-19L(m) = H(0x00 || enc(m))I(a, b) = H(0x01 || a || b)Checkpoint"At date D, N entries, root R."Signed by the log, co-signed by witnesses: it fixes M.Compiler of Breads M up to a checkpoint, with inclusion andconsistency proofs, and compiles its own G|tWitnesses, monitorsco-sign checkpoints; check inclusion, consistencyand signatures; compare what they seeOperatororders, signs checkpointscan omit, cannot forgeMirrorsserve static,cacheable tiles
Figure 12. Who publishes, who verifies and who decides. Adapted from Annex III of the thesis. The log is specified; its implementation is ongoing work.

10Post-quantum migration

Migrating is traversing an edge

As each domain migrates at its own pace, traditional, hybrid and post-quantum domains will coexist for years. Because one key is one node and each key carries its level, a mixed path can be read on the graph edge by edge, with no extra mechanism.Key idea A domain never accepts a route through a certification authority below its cryptographic floor, anchor included, whether the other domains migrate at the same time or not.

A CA that changes algorithm holds two keys, linked by the certificates of RFC 9810: new with old, and old with new. Each is an edge with its own cost, and the two directions do not cost the same, because the return certificate carries the ML-DSA signature, which is the larger part.

Migrating is traversing an edgeA CA that moves from ECDSA P-384 to ML-DSA-65 occupies two nodes. The link certificate new-with-old carries the ML-DSA-65 key under an ECDSA signature and takes 2,056 octets. The link certificate old-with-new carries the ECDSA key under an ML-DSA-65 signature and takes 3,406. Both touch the traditional key, so with a traditional floor both are admissible and with a hybrid floor neither is.One CA, two keys, two nodes · same domainnew with oldb(e) = 1,952 + 104 = 2,056 octets · ML-DSA-65 key, ECDSA P-384 signatureCA, traditional keyECDSA P-384old keyCA, post-quantum keyML-DSA-65new keyold with newb(e) = 97 + 3,309 = 3,406 octets · ECDSA P-384 key, ML-DSA-65 signatureLink certificates as in RFC 9810, section 4.4. They keep the CA name, so they are self-issued and consume no depth budget (RFC 5280, 6.1.4 (h) and (l)).Both edges touch the traditional key: a traditional floor admits both, a hybrid floor admits neither, since the floor binds every key on the path.Migrating is traversing an edgeOne CA, two keys, two nodesCA, traditional keyECDSA P-384 · old keyCA, post-quantum keyML-DSA-65 · new keynew with old2,056 octetsold with new3,406 octetsLink certificates as in RFC 9810, section 4.4: self-issued,they consume no depth budget. Both touch the traditionalkey: a hybrid floor admits neither.
Figure 13. A CA that migrates from ECDSA P-384 to ML-DSA-65. Entering the post-quantum key takes 2,056 octets and going back 3,406. Both edges touch the traditional key.

Under a strict floor, then, a link certificate signed with the traditional key does not lead to the new one. The certificates that the migrating CA signs become admissible again only when a CA that meets the floor certifies its post-quantum key directly, and Govern can announce that before the receiver raises the floor. The floor also binds the receiver’s own branch, anchor included: a domain cannot demand of others a level its own chain does not have.A list of floors. With τB = ⟨(post_quantum, 0), (hybrid, 0)⟩ the receiver asks for the strongest without running out of routes, and Audit records under which floor each path was admitted.

A receiver governs its own migration simply by raising τd, and it does so without reissuing a single certificate.

Using ML-DSA certificates does not make the channel post-quantum, since the thesis acts on the certificates and on the path decision while the key exchange and the handshake signatures of the channel are separate layers.

11Use cases

Where a governed path matters

One scenario runs through the whole thesis, in which a client of domain A connects over mTLS to a service of domain B. B trusts only its own root, and its intermediate has cross-certified the intermediate of A. Inside the handshake, B has to decide whether an admissible path exists under its policy, and which one is best.The candidate path in this scenario is Root B → Intermediate B → Intermediate A → Issuing A. B starts with a traditional floor, so that it admits the clients of A; raising it is the migration variant.

The use case that runs through the thesisThree domains, each with a root and an intermediate CA. Domain B trusts its own root. Its intermediate has issued a cross-certificate to the intermediate of domain A, which issued the client certificate. The candidate path is root B, intermediate B, intermediate A, closed by the client certificate.Domain A · traditionalDomain B · receiverDomain CRA root CARB root CAanchorTPBRC root CAIA intermediateIB intermediateIC intermediatecA client cert.cross-cert.issued by IBB decides, inside the handshake,whether an admissible path existsand which one is best.a third domain: it entersthe variants of the use caseHighlighted: the candidate path RB → IB → IA, closed by cA. Cross-certificates are issued between intermediates, never from a root.The use case that runs through the thesisDomain AB · receiverDomain CRAroot CAanchor of BRBroot CARCroot CAIAintermediateIBintermediateICintermediatecA clientcross-certificateissued by IB to IAenters thevariantsB decides, inside the handshake, whether anadmissible path exists and which one is best.In colour: the candidate path RB → IB → IA, closed by cA.Cross-certificates link intermediates, never a root.
Figure 14. The use case of the thesis. Its variants (a key rotation, a revocation, a higher floor) are all told on this same scenario.

In the thesis

Machine-to-machine mTLS

A service of one domain admits, at connection time, a client certificate issued in another, with Discover working inside the handshake. It is also the case that the laboratory implements from end to end, with real certificates.

Beyond

Long-term signature validation

A PAdES signature made years ago in another domain has to be judged against the trust in force when it was signed, which needs the graph as it was at that moment and belongs to the ongoing doctoral research.

Beyond

Coalition S/MIME

Participants join and leave during an exercise and every arrival brings a new cross-certificate, which makes this the scenario where Govern is used most often.

12Laboratory

Three real PKI domains, one reproducible laboratory

Three EJBCA Community Edition instances on Proxmox, each a PKI domain with its own cryptographic profile, cross-certified with one another. Certificates are issued for real, and every constraint of Φ is read from real extensions, never simulated.How to read this section. The rows that carry a date were run on that day, and everything else is described as planned work.

Table 6. Reference profile of each domain of the laboratory.
DomainPostureAlgorithmsReference floor τd
ATraditionalRSA, ECDSA(traditional, 0)
BHybridComposite ECDSA + ML-DSA, RFC 10073(hybrid, 0)
CPost-quantumML-DSA-44, -65, -87(post_quantum, 0)

The engine runs on .NET with Kestrel, over EJBCA for issuance and OpenSSL 3.5 underneath the platform validator, deployed with Ansible on Linux containers and with no proprietary licences. In the use case B starts with a traditional floor, so that it admits the clients of A, and raising it to its reference profile is the migration variant.

Table 7. What the platform validator can do, checked before building the laboratory.
RunSubjectResult
12 Nov 2026OpenSSL 3.5 on LinuxValidates ML-DSA chains. Knows no composite signature algorithm. An intermediate as the only anchor needs the partial-chain option.
13 Nov 2026.NET 11 X509Chain, Linux and WindowsValidates ECDSA P-384 and ML-DSA-65 chains and detects an altered signature in both. An intermediate as the only anchor gives PartialChain, which does not affect the use case: its anchor is the self-signed root of B.
13 Nov 2026.NET 11 X509Chain, composite chainOn Linux it throws an OpenSSL exception when reading the composite public key and gives no verdict. On a preview build of Windows 11 the same program validates the chain.

The third row has a direct consequence, because every route of domain B starts at its root, which is composite, so on Linux the platform validator cannot give B its explicit validation. Domain B has to change format, validation library or system, and that decision is open (section 13).

The evaluation measures and describes, and it claims no improvement in performance over existing validators. The selected path is checked against exhaustive enumeration on small topologies and against a reference validation library, and a negative result counts as a result.

13Limits and open work

What is proved, what is stated and what is open

The model went through a scientific audit and a critical review in November 2026, and their findings were applied before this page was written. The table separates what has a proof from what is only stated, because the two are easy to confuse in an overview.The audit was run on 12 November 2026 over the model and the thesis, and it left 26 findings that range from the definition of the graph to the status of each proof. The review of 15 November took revocation out of the common graph, restricted the proofs to the direct profile of evidence and added the cone of trust.

Table 8. Status of the formal claims.
ClaimStatusScope and what is missing
Dominance (Proposition 1)Proved by argumentFor the relation defined by accepted continuations, with the CRL permission in the label. A computable relation that implies it is open, with delicate cases in RFC 9618, section 5.4.
Cycle elimination (Lemma 2)Proved by argumentChecked by simulation. The policy part rests on the argument alone. Not reviewed by third parties.
NP-completeness (Proposition 3)Proved by reductionFrom the path with forbidden pairs problem. Tractability as a function of the number of constrained certificates is open.
Confinement (Proposition 4)Proved by argumentFor the direct profile of evidence. Not reviewed by third parties nor checked by simulation, and not proved for the extended profile.
Soundness and completeness against RFC 5280StatedNot proved. Safety does not depend on them: the selected path is validated explicitly and failure is closed.
Third-party bound of Govern, policy partStatedThe bound holds for names and depth. For policies it depends on a condition that is not proved, and Govern labels it fragile.
Selection against exhaustive enumerationPlannedTo be checked on the small topologies of the laboratory and against a reference validation library.

Open work

A validator for composite chains
On Linux, .NET 11 X509Chain over OpenSSL 3.5 validates ECDSA and ML-DSA chains and cannot read a composite public key, so the library that validates domain B is still an open decision.
The common log, built
The log is fully specified, while its implementation, several independent logs and a post-quantum signature for it are ongoing work.
A tamper-evident decision record
In the thesis it is a structured file, enough to reproduce and re-evaluate a decision, but proving one to a third party needs entries that are signed and anchored in the log.
Time, in full
The model has to separate when a datum is valid from when it becomes known, since a revocation published later with an earlier invalidity date gives a re-evaluation and leaves the reproduced decision as it was.
The extended profile of evidence
Delegated OCSP responders and lists signed by another key of the CA after a rotation need an auxiliary path to the same anchor. The thesis declares them and proves its results only for lists signed by the issuing key.
Search at scale
Pruning by dominance and admission under a time budget are deployment extensions. The thesis enumerates the admissible paths exactly, which is feasible on the topologies of the laboratory.
Ordering by policy before cost
Two admissible routes may end with different valid policies, and until this is solved a service that authorises by policy must demand it in the initial state of its anchors.
A post-quantum channel
ML-DSA certificates do not make the channel post-quantum, because the key exchange and the handshake signatures are separate layers that the thesis does not touch.
Counting domains instead of crossings
It would measure the dependence on other organisations better, but it is not additive and is therefore left as a variant.

End matter

References

  1. [Hiller2020]Hiller, J., Amann, J. and O. Hohlfeld, "The boon and bane of cross-signing: Shedding light on a common practice in public key infrastructures", ACM CCS 2020, pp. 1289-1306.
  2. [BZ2083449]Jackson, D. et al., "eMudhra: Private key compromise of Intermediate Certificates", Mozilla Bugzilla, bug 2083449, October 2026; final incident report in comment 82, 10 November 2026.
  3. [WorldBank]Tullis, C. and D. Black, "Public Key Infrastructure: Implementing High-Trust Electronic Signatures", Digital Public Infrastructure Policy Note Series, World Bank, December 2024.
  4. [FPKI-PDVAL]General Services Administration, "Path Discovery and Validation", Federal PKI Playbooks, IDManagement.gov.
  5. [RFC5280]Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R. and W. Polk, "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 5280, May 2008.
  6. [RFC4158]Cooper, M., Dzambasow, Y., Hesse, P., Joseph, S. and R. Nicholas, "Internet X.509 Public Key Infrastructure: Certification Path Building", RFC 4158, September 2005.
  7. [RFC5055]Freeman, T., Housley, R., Malpani, A., Cooper, D. and W. Polk, "Server-Based Certificate Validation Protocol (SCVP)", RFC 5055, December 2007.
  8. [ARMOR2024]Debnath, J., Jenkins, C., Sun, Y., Chau, S. Y. and O. Chowdhury, "ARMOR: A formally verified implementation of X.509 certificate chain validation", IEEE Symposium on Security and Privacy 2024, pp. 1462-1480.
  9. [Verdict2025]Lin, Z. et al., "Towards practical, end-to-end formally verified X.509 certificate validators with Verdict", 34th USENIX Security Symposium, 2025, pp. 5035-5052.
  10. [RFC9618]Benjamin, D., "Updates to X.509 Policy Validation", RFC 9618, August 2024.
  11. [RFC9608]Housley, R., Okubo, T. and J. Mandel, "No Revocation Available for X.509 Public Key Certificates", RFC 9608, June 2024.
  12. [RFC10007]Bonnell, C., Ito, T. and T. Okubo, "Clarification to Processing Key Usage Values During Certificate Revocation List (CRL) Validation", RFC 10007, June 2026.
  13. [FIPS204]National Institute of Standards and Technology, "Module-Lattice-Based Digital Signature Standard", FIPS PUB 204, August 2024.
  14. [RFC10073]Ounsworth, M., Gray, J., Pala, M., Klaußner, J. and S. Fluhrer, "Composite Module-Lattice-Based Digital Signature Algorithm (ML-DSA) for Use in X.509 Public Key Infrastructure", RFC 10073, November 2026.
  15. [Gabow1976]Gabow, H. N., Maheshwari, S. N. and L. J. Osterweil, "On two problems in the generation of program test paths", IEEE Transactions on Software Engineering, vol. SE-2, no. 3, pp. 227-231, 1976.
  16. [RFC6962]Laurie, B., Langley, A. and E. Kasper, "Certificate Transparency", RFC 6962, June 2013.
  17. [RFC9810]Brockhaus, H., von Oheimb, D., Ounsworth, M. and J. Gray, "Internet X.509 Public Key Infrastructure -- Certificate Management Protocol (CMP)", RFC 9810, July 2025.

Academic context

Credits

Author

Jorge Pablo Trías Posa

Master’s Degree in Cybersecurity and Cyberintelligence
Universitat Politècnica de València

Thesis supervisor

Dr. Mario Aragonés Lozano

Universitat Politècnica de València

Project

PolarisChain

Ongoing research since 2026, born as a master’s thesis and continuing as doctoral research.