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.
Navigating trust across federated PKI ecosystems · Academic research
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.
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.
1·Motivation
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].
Every new relationship multiplies the paths that lead from an identity to an anchor, and few of them were ever drawn on purpose.
Path building stops at the first chain that works, so better admissible paths are never seen.
Trust is inherited from whole hierarchies instead of being bounded, and reaches further than anyone decided.
Federation rarely weighs the algorithm on each hop, just as traditional, hybrid and post-quantum material starts to coexist.
Short-lived certificates, renewals, revocations and policy updates are hard to sustain across many domains at once.
Workloads and agents multiply identities, and the trust graph changes faster than people can follow.
Nobody sees which trust paths are active right now, which limits audit and incident response.
Signed artefacts cross domains, and their provenance still rests on implicit trust in foreign repositories.
2·Where federation stands
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.
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.
If there are several paths, someone has to choose among them, and today nobody has written down how.
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.
| Work | What it does | What 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. |
3·The gap
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.
Today nobody knows what a cross-certificate enables until it has been issued and is already in use.
Before issuing
Constraints are audited only afterwards, when the bridge is already in production and every path it opens is live.
During the handshake
The vendor of each validation library decides, and it decides in the same way for every receiver that uses it.
After the decision
A trust store says yes or no, and nothing records the reason behind either answer.
4·The proposal
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.
| The bridge CA | The federation falls: there is no path between domains. |
|---|---|
| The cross-certificates | The federation falls: the hierarchies are isolated again. |
| The trust list | Verifiers are left without anchors. |
| PolarisChain | Nothing 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.
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.
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.
After the decision: not another verdict but its reason, one of seven defined outcomes, with a record that reproduces it.
5·The model
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
whose nodes are the keys of the certification authorities and whose edges are the CA certificates between them that are valid at t.
where
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.
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.
basicConstraints has cA set to TRUE (6.1.4 (k)).keyUsage is present, it includes keyCertSign (6.1.4 (n)).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:
where
notBefore to the field notAfter.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.
good }(3)where
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.
where
clientAuth.outside section 6A 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:
where
traditional < hybrid < post_quantum, with the names of RFC 9794.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.
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.
where
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.
| Algorithm | Signature | Public key | stage | nist_category |
|---|---|---|---|---|
| ML-DSA-87 | 4,627 | 2,592 | post_quantum | 5 |
| ECDSA P-384 + ML-DSA-65 | 3,413 | 2,049 | hybrid | 3 |
| ML-DSA-65 | 3,309 | 1,952 | post_quantum | 3 |
| ECDSA P-256 + ML-DSA-44 | 2,492 | 1,377 | hybrid | 2 |
| ML-DSA-44 | 2,420 | 1,312 | post_quantum | 2 |
| RSA-4096 | 512 | 512 | traditional | 0 |
| RSA-2048 | 256 | 256 | traditional | 0 |
| ECDSA P-384 | 104 | 97 | traditional | 0 |
| ECDSA P-256 | 72 | 65 | traditional | 0 |
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.
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.
where
max_path_length: a natural number, or ∞ when there is no limit.permitted_subtrees and excluded_subtrees: two values of the same type.explicit_policy, inhibit_anyPolicy and policy_mapping.max_path_length1permitted_subtreesops.altair.exampleexcluded_subtreesext.ops.altair.examplevalid_policy_graphpB, expecting pAexplicit_policy · inhibit_anyPolicy · policy_mapping(0, ∞, ∞)user-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.
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.
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.
where
good )(9)where
noRevAvail.keyUsage carries cRLSign, as RFC 10007 demands.x1 to x3: the h = 3 CA certificates of the pathx4: the presented one, h + 1 = 4
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).
where
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.
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.
| Edge | Issuer → subject | b(e) | cdist | wB |
|---|---|---|---|---|
| e1 | Root B → Intermediate B | 5,462 | 0 | 5,462 |
| e2 | Intermediate B → Intermediate C1 | 5,462 | 1 | 11,462 |
| e3 | Intermediate C1 → Issuing C | 5,365 | 0 | 5,365 |
| e8 | Intermediate B → Intermediate C3 | 6,005 | 1 | 12,005 |
| e9 | Intermediate C3 → Issuing C | 6,579 | 0 | 6,579 |
| e4 | Intermediate B → Intermediate A1 | 3,510 | 1 | 9,510 |
| e10 | Intermediate A1 → Issuing C | 2,056 | 1 | 8,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.
Candidates C₁ and C₄. Selected: C₁, 22,289 octet-equivalents, against 24,046 for C₄.
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.
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.
where
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.
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.
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.
6·Threat model
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:
| Adversary | Capability | Achieves | Does not achieve |
|---|---|---|---|
| Network, no keys | Replays public certificates and opens connections. | Computation spent at the receiver. | Admission: the proof of possession fails. |
| Holder of a valid certificate | Presents 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 domain | Issues 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 log | Omits, 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 number | Cosign any checkpoint. | Nothing against a reader that demands the minimum quorum. | Making two readers accept incompatible histories. |
| Cryptanalytic | Signs 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 receiver | Changes 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.
7·Path discovery
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.
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.
Among the admissible paths the receiver prefers the one of least cost Wd, measured in octet-equivalents, and Sel makes that choice unique.
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.
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.
8·Admission at the server
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.
No answer, no path, missing evidence or a validated path that differs from the selected one: the connection is denied, with its reason.
The engine decides whether the issuer is admissible, while only the TLS stack decides whether the peer holds the private key.
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.
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.
9·The common log
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.
10·Post-quantum migration
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.
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.
11·Use cases
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.
In the thesis
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
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
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.
12·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.
| Domain | Posture | Algorithms | Reference floor τd |
|---|---|---|---|
| A | Traditional | RSA, ECDSA | (traditional, 0) |
| B | Hybrid | Composite ECDSA + ML-DSA, RFC 10073 | (hybrid, 0) |
| C | Post-quantum | ML-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.
| Run | Subject | Result |
|---|---|---|
| 12 Nov 2026 | OpenSSL 3.5 on Linux | Validates 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 Windows | Validates 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 chain | On 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.
13·Limits and open work
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.
| Claim | Status | Scope and what is missing |
|---|---|---|
| Dominance (Proposition 1) | Proved by argument | For 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 argument | Checked by simulation. The policy part rests on the argument alone. Not reviewed by third parties. |
| NP-completeness (Proposition 3) | Proved by reduction | From the path with forbidden pairs problem. Tractability as a function of the number of constrained certificates is open. |
| Confinement (Proposition 4) | Proved by argument | For 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 5280 | Stated | Not proved. Safety does not depend on them: the selected path is validated explicitly and failure is closed. |
| Third-party bound of Govern, policy part | Stated | The 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 enumeration | Planned | To be checked on the small topologies of the laboratory and against a reference validation library. |
End matter
Academic context
Author
Master’s Degree in Cybersecurity and Cyberintelligence
Universitat Politècnica de València
Thesis supervisor
Universitat Politècnica de València
Project
Ongoing research since 2026, born as a master’s thesis and continuing as doctoral research.