arXiv CSopen access

Optimizing Credential Blast Radius Through Trust Boundaries and Delegation Under Post-Quantum Authentication Costs

Optimizing Credential Blast Radius Through Trust Boundaries and Delegation Under Post-Quantum Authentication Costs

arXiv:2609.04566v1 [cs.CR] 3 Sep 2026

Pauli Taipale and Harri Lainio Abstract—Partitioning interacting services into independently rooted trust domains limits issuer-compromise reach while increasing calls across trust boundaries. Post-quantum replacements for public-key authentication and key-establishment mechanisms can increase crossing latency on constrained or lossy paths. We formulate the joint selection of trust domains and credential-derivation structures under policy and latency constraints, linking separate service-interaction and credential-derivation graphs through domain assignment. Credential blast radius measures weighted service impact after compromise. A linear upper bound supports optimization, while a joint event model gives exact expected impact. For shared issuers, the bound is exact under nonoverlapping credential reach and otherwise requires explicit propagation. While the general problem is NP-hard, scalarized two-domain direct issuance reduces to a weighted minimum cut. Joint optimization yields lower blast radius than choosing boundaries first in 195 of 230 exhaustive synthetic comparisons, especially under chained delegation. A trace-derived replay used measured post-quantum costs, synthetic risk inputs, a fixed derivation family, and one to six trust domains. The best design found reduced expected impact by up to 36% relative to one domain within the latency budget. The framework turns risk assumptions and measured crossing costs into candidate trust-domain and credential-derivation designs. Index Terms—access control, authentication, graph theory, optimization, public key

National Institute of Standards and Technology (NIST) 1 INTRODUCTION Credential compromise can propagate through two dis- has standardized several PQC algorithms, while transition tinct mechanisms: compromise of a domain root exposes guidance gives a timeline for retiring quantum-vulnerable every principal in its domain, while compromise of a dele- public-key algorithms in NIST standards. [7–10] High-rate systems already amortize classical publicgated principal exposes the descendants reachable through key authentication. Google’s Application Layer Transcredential derivation. Trust boundaries limit the first mechport Security uses resumption and long-lived remoteanism. Derivation structure limits the second. Zero-trust procedure-call channels to preserve workload authentiguidance describes trust and identity controls architeccation while reducing repeated cryptographic work. [11] turally. [1] We study how to choose trust boundaries and At the constrained-device extreme, smart-card expericredential-derivation structures jointly when boundary ments found hybrid post-quantum payment transactions crossings carry a performance cost. Post-quantum cryptography (PQC) makes this joint de- to be dominated by transmitting larger certificate chains cision consequential. Classical public-key key establish- over the card interface rather than by cryptographic comment and signatures are vulnerable to Shor’s algorithm, putation. [12] Certificate-size reduction efforts for postwhereas Grover’s generic search gives a quadratic quan- quantum HTTPS address the same communication bottum speedup against symmetric keys. [2, 3] Thus, a 256-bit tleneck. [13] These cases motivate deciding where indesymmetric key retains approximately 128 bits of key-search pendently rooted authentication boundaries justify their strength in the idealized query model. Classical RSA- path-dependent cost. Figure 1 summarizes the two arand elliptic-curve-based boundary mechanisms require re- chitecture decisions and the quantities used to evaluate placement. Post-quantum migration changes key establish- them. We model operational principals in separate servicement and authentication separately. ML-KEM can replace interaction and credential-derivation graphs. The serviceor augment classical key establishment, while ML-DSA interaction graph assigns a calibrated crossing cost to calls and SLH-DSA replace signatures used for peer authenticathat cross trust domains. Within each domain, a contion and certificate chains. On some platforms, implemenstrained credential-derivation tree determines how comtations of post-quantum key-establishment and signature promise of a delegating principal reaches downstream schemes can match or outperform their classical counterprincipals. The design chooses both under policy and parts, so PQC does not impose a uniform computational slowdown. Larger public keys, ciphertexts, signatures, latency constraints, including fanout and depth limits. and certificates can nevertheless increase handshake byte Domain-root compromise remains confined to its domain. The tree model does not cover every credential system. volume and the number of transport packets or segments, In shared-issuer JSON Web Token (JWT) or OpenID Conamplifying delay on constrained or lossy paths. [4–6] A nect (OIDC) deployments, services in several nominal boundary that improves containment can therefore condomains may accept credentials from one issuer, creatsume a measurable latency or bandwidth budget whose ing compromise paths that bypass the domain roots. We dominant source depends on the deployment. The U.S. model these acceptance relationships separately. A structural condition identifies when issuer risk is represented • Corresponding author: Pauli Taipale ([email protected]). exactly by the additive score. Otherwise, candidate de• Pauli Taipale and Harri Lainio are with OP Lab, OP Pohjola, Gebsigns must be evaluated by tracing issuer reachability exhardinaukio 1, FI-00510 Helsinki, Finland.

1

Performance inputs call edges E with rates ruv sensitivities ℓuv and crossing costs cpqc (u, v)

Domain assignment D

Boundary objective Lat( D )

defines Vi

Risk inputs weights w(v) and marginals p( x ) optional joint event model

Blast-radius analysis optimize BRnode evaluate BRexact when specified

Derivation trees { Hi }

Figure 1: Two coupled architecture decisions and their evaluation. Performance inputs describe service calls and path-dependent crossing costs. Risk inputs describe service impact, marginal compromise probabilities, and optional event dependence. Domain assignment D defines Vi = D −1 (i ), the services in domain i. Credential-derivation tree Hi is built on Vi and determines compromise reach within that domain. Rightward arrows show objective dependence. Performance inputs and D determine boundary latency Lat( D ). Risk inputs, D, and { Hi } determine the conservative linear blast-radius score BRnode . Given a joint compromise model, BRexact gives exact expected impacted weight. Joint optimization trades boundary latency against compromise reach.

plicitly. This work contributes:

We consider hybrid architectures that replace the quantum-vulnerable public-key mechanism at these crossings with PQC while retaining symmetric protection and derived credentials within domains. A compromised domain root can mint for its entire domain. A compromised service or delegator can impersonate the descendants enabled by its credential authority. Boundary placement controls the former reach. Derivation design controls the latter. Services holding identities with different scopes can be split into separate principals before optimization, as described in Supplementary Sec. S5. Compromise probabilities p( x ) are marginal scenario inputs over a fixed planning horizon T, a chosen time interval such as a detection or rotation window. Service weights w(v) encode impact. Here compromise means credential theft or loss of control over credential authority, not quantum cryptanalysis. PQC enters through the cost of replacing quantum-vulnerable boundary mechanisms. We assume that verifiers and boundary enforcement follow the modeled policy. Verifier compromise, software supplychain compromise, denial of service, and non-credential lateral movement are outside scope. The model is conditional on its ( p, w) scenario and does not estimate compromise probabilities.

• A two-layer optimization model that chooses trust domains and credential-derivation trees under policy and latency constraints. The optimizer uses a conservative linear objective. When a joint compromise model is available, candidates are evaluated by exact expected impact. • Hardness and tractable regimes for the model, including a condition for exact additive scoring of shared issuers. The solver map distinguishes results proved for this formulation from guarantees inherited from established optimization algorithms. • An operational evaluation that measures named Transport Layer Security (TLS) profiles across network paths, applies the resulting costs to trace-derived optimization, and validates selected crossings on held-out measurements. It also tests whether additive sharedissuer scoring agrees with explicit issuer-reachability evaluation.

Given explicit workload, compromise, criticality, and credential-semantics assumptions, the planning method returns containment–performance tradeoffs and states 3 FORMAL MODEL which guarantees apply. Proofs and supporting experi- Let G = (V, E) be the directed service-interaction graph, ments appear in the supplementary material. where V is the set of services or principals and (u, v) ∈ E means that u calls v. Each edge has an interaction rate 2 BACKGROUND AND THREAT MODEL ruv ≥ 0 and system-level latency sensitivity ℓuv ≥ 0. A trust domain is a set of principals that derive session The interaction rate, latency sensitivity, and calibrated keys or credentials from a common issuer, signing key, crossing cost together determine boundary-authentication or key-management root ρi . We study key-establishment overhead rather than payload-cryptography work. Policydomains: after establishment, intra-domain payload inter- forbidden calls are removed or assigned zero weight. A actions use symmetric protection or already-issued dele- design uses k ≥ 1 nonempty trust domains. A domain gated credentials, whereas a crossing connects indepen- assignment dently rooted credential systems and invokes public-key D : V → {1, . . . , k } authentication or key establishment. This is a deployment assumption rather than a universal definition of a trust induces Vi = {v : D (v) = i }. An interaction crosses a domain. It need not coincide with a subnet or administra- boundary when D (u) ̸= D (v). Credential derivation in domain i is tive boundary: one network segment can contain several isolated issuers, while separate segments can still trust Hi = (Vi ∪ {ρi }, Ai ), (1) one shared issuer. We therefore distinguish the serviceinteraction graph, the trust-domain assignment, and cre- where virtual root ρ represents the issuer or master secret i dential propagation. and A is the set of directed derivation arcs. The relation i

2

( x, y) ∈ Ai means compromise of x enables credentials for y. The core model restricts Hi to a rooted directed arborescence: every service has exactly one incoming derivation arc and is reachable from ρi . This captures direct issuance, delegation chains, and shallow subissuer layouts. Because each service has one parent, every root-to-service compromise path is explicit. The separate acceptance model below handles issuer entry points not represented by these roots.

This form makes the design pressure explicit: highprobability principals should control little descendant weight. Give each derivation arc entering a non-root vertex x length p( x ), and let d Hi (ρi , v) be the resulting root-to-v distance. Then Eq. (4) is equivalently " # k

BRnode = ∑ p(ρi )W (Vi ) + ∑ w(v)d Hi (ρi , v) ,

4 PROBLEM DEFINITION

(5)

v∈Vi

i =1

Let Aallow ⊆ (V ∪ {ρ1 , . . . , ρk }) × V denote the permitted where W (S) = ∑v∈S w(v). For a fixed service set S, let derivation arcs. When this relation is omitted, every root- H (S) be the derivation trees on S ∪ {ρi } that satisfy (C3)– i to-service arc and every service-to-service arc between (C4), including Ai ⊆ Aallow , and the applicable domaindistinct vertices is eligible. The inputs are G, r, ℓ, service policy constraints. Define Φi (S) as the minimum brackweights w, compromise probabilities p, domain count k, eted term over this family. For fixed D, each domain can atderivation limits (∆, h), Aallow , optional domain-policy tain Φ (V ) independently. The outer assignment remains i i constraints, and the effective crossing-cost function cpqc coupled because it determines both V and the interaction i defined in Sec. 6. The decision variables are D and { Hi }. A cut. design is feasible, written ( D, { Hi }) ∈ F , when it satisfies: Let Ex denote compromise of x. The exact expected impacted weight is (C1) Partition. Every service belongs to exactly one nonempty domain.   k

BRexact = ∑ ∑ w(v) Pr

(C2) Policy. Required must-link pairs share a domain and cannot-link pairs do not.

i =1 v∈Vi

(C3) Derivation. Each Hi is a rooted directed arborescence spanning Vi , with Ai ⊆ Aallow .

∆ = 1, ∆ > 1.

(2)

This condition is necessary under (C3)–(C4). It is also sufficient when derivation eligibility is complete and no additional policy constraint applies. Capacity and latency constrain k jointly with ∆ and h. A heterogeneous root risk must be attached to a concrete issuer label, and policy determines which services may use that issuer. Interchangeable roots use homogeneous risk, whose root contribution is assignment-independent (Supplementary Sec. S3).

For each interaction (u, v), let ruv be its rate, ℓuv its systemlevel latency sensitivity, and cpqc (u, v) the effective cost of invoking the boundary mechanism. For a predicate P, 1[ P] is 1 when P is true and 0 otherwise. The boundary objective is

For S ⊆ Vi ∪ {ρi }, let Reach Hi (S) be the services reachable from S in Hi and define deterministic impact as

∑

Lat( D ) =

w ( v ).

∑

p( x ) BRi ({ x }, Hi ).

(3)

i =1 x ∈Vi ∪{ρi }

For an arborescence, let Anc Hi (v) be the vertices on the root-to-v path. Swapping the sums gives k

BRnode = ∑ ∑ w(v) i =1 v∈Vi

∑

p ( x ).

ruv ℓuv cpqc (u, v)1[ D (u) ̸= D (v)].

(7)

Equation (7) is a linearized boundary-overhead proxy, not a general end-to-end or tail-latency model. The formal results require only nonnegative edge coefficients and do not depend on PQC specifically. PQC supplies the motivating calibration regime. Accordingly, cpqc (u, v) is a deployment-specific coefficient. It is a measured or estimated profile for a selected cryptographic suite, protocol stack, hardware platform, network path, and reuse policy, and different edges may use different profiles. The product ruv cpqc (u, v) represents key-establishment or authentication work after session reuse, credential caching, and key-update policy. Represent reuse through either an

Our primary objective sums this impact over possible compromise points: k

∑

(u,v)∈ E

v∈Reach Hi (S)

BRnode ( D, { Hi }) = ∑

(6)

x ∈Anc Hi (v)

6 LATENCY COST

5 BLAST-RADIUS OBJECTIVE

BRi (S, Hi ) =

Ex  .

The union bound gives BRexact ≤ BRnode under any dependence structure. Under independence the probability is 1 − ∏ x (1 − p( x )), so the bound is first-order tight when probabilities are small. We optimize the conservative linear form because it avoids an assumed dependence model and preserves additive structure. When probabilities are large or strongly dependent, candidates should be rescored under an explicit joint model. Worst-case single-compromise and issuer-only summaries are diagnostics rather than additional propagation models. Alternative risk summaries appear in Supplementary Sec. S3. A surrogate-regret check appears in Supplementary Table S2.

(C4) Operational limits. Every derivation out-degree is at most ∆ and every root-to-leaf depth is at most h. In particular, (C3)–(C4) imply ( h, |Vi | ≤ ∑dh=1 ∆d ,

[

(4)

x ∈Anc Hi (v)

3

Domain 1

Domain 2

a

d

(∆, h). Supplementary Sec. S1 gives a three-service counterexample. For architecture decisions we use a latency budget B: min

b

e

c

f

( D,{ Hi })∈F

s.t.

BRnode ( D, { Hi }) (10) Lat( D ) ≤ B.

Varying B traces the containment–latency frontier without mixing units. Additional linear constraints, such as a boundary-byte cap, can be imposed in the same form. A raw-unit linear scalarization is

interaction edge (E) boundary edge (D (u) ̸= D (v))

min

( D,{ Hi })∈F

Figure 2: The two red service-call arrows cross the fixed domains, and their ruv ℓuv cpqc (u, v) contributions sum to Lat( D ) = 220 in the unit-normalized toy calibration. Blue arrows remain within a domain. Supplementary Sec. S1 gives the derivation-tree comparison at this fixed cut.

BRnode ( D, { Hi }) + λ Lat( D ),

λ ≥ 0. (11)

Here λ has units of impact per millisecond. To sample tradeoffs independently of reporting units, candidate generation uses

event-equivalent rate or an amortized per-interaction cost, Lat( D ) BR ( D, { Hi }) α + (1 − α) node , α ∈ [0, 1], (12) not both. The cost may include key establishment, signaL0 R0 ture verification, parsing, proxy work, and communication. Since the indicator is symmetric, antiparallel directed inter- where L0 = ∑(u,v)∈E ruv ℓuv cpqc (u, v) is the cost if evactions can be summed when an undirected cut or labeling ery modeled interaction crossed a boundary and R = 0 algorithm is used. ∑v∈V w(v) is total modeled impact. If either scale is At this fixed cut, raising the fanout bound from ∆ = 2 zero, its identically zero term is omitted. For positive to 3 permits direct root issuance and reduces BRnode from L , R and α < 1, Eq. (12) is equivalent to Eq. (11) with 0 0 0.06 to 0.03 without changing the boundary latency. λ = αR0 /((1 − α) L0 ). Thus changing milliseconds to miStateful stacks can be retained without changing the croseconds or multiplying all service weights by a common optimizer by calibrating constant leaves candidate ordering unchanged. Linear scalarization generates supported candidates. warm cold cold ceff (u, v) = cuv + Puv cuv , (8) For each budget B, the implementation refines retained scalarized and traffic-structured candidates using moves where cwarm is the reused-session cost, ccold uv uv is the addicold tional setup penalty, and Puv is the probability of incur- that preserve Lat( D ) ≤ B. It then selects the feasible canring that penalty under the workload and reuse policy. didate with minimum blast radius. This ε-constraint reRequest-class mixtures and critical-path weights similarly finement addresses Eq. (10) and can recover unsupported alter edge coefficients. Supplementary Sec. S5 gives these points. It remains heuristic in the general regimes. extensions. 8 SHARED-ISSUER VALIDATION AND RESCORING Our named TLS measurements evaluate three cryptoShared-issuer acceptance adds deployment-specific propagraphic profiles on five controlled network paths. Under gation to the core design problem. The domain assignment mutual authentication, 20 requests per connection, and a and derivation trees remain the architecture variables, 0.05 full-handshake probability, the hybrid X25519+MLwhile the observed issuer-minting and verifier-acceptance KEM-768/ML-DSA-65 profile spans 0.0338–15.5815 ms per relations ( M, J ) determine whether a candidate’s blast racrossing call from the unshaped local path to the condius can be evaluated by the core score. When these relastrained lossy path. These values are architecture inputs tions create additional entry points, final candidate selecrather than algorithm rankings: changing the implemention must use explicit issuer reachability. tation, platform, path, or reuse policy changes the edge Let I be issuers with compromise probabilities p( a), weights. Supplementary Table S7 gives the profiles, path Eauth ⊆ E protected calls, M ⊆ V × I caller–issuer mintconditions, and measured costs. ing, and J ⊆ I × V verifier acceptance. Issuer events in I are distinct from service and domain-root events. A phys7 OPTIMIZATION PROBLEM The design object is ( D, { Hi }) ∈ F , and its Pareto objective ical principal occupying several roles is represented by one compromise event, with its reachable targets unioned is
min Lat( D ), BR ( D, { H }) . (9) before scoring. A redesign remains authenticatable only if ( D,{ Hi })∈F

node

i

∀(u, v) ∈ Eauth ,

Boundary placement changes root exposure and boundary latency. The derivation structures determine delegatedprincipal propagation inside each domain. Fixing D separates the derivation-tree best responses. A latency-first optimization can miss the optimum because the assignment changes Φi (Vi ) and can change feasibility through

∃ a ∈ I : (u, a) ∈ M ∧ ( a, v) ∈ J.

Compromise of issuer a reaches R H,J ( a) =

[ ( a,v)∈ J

4

{u ∈ VD(v) : v ⇝ u in HD(v) }.

(13)

Equation (13) conservatively treats successful impersonation at an accepted target v as access to every downstream credential capability represented below v in HD(v) . Because verifier-acceptance relations are fixed deployment inputs rather than optimization variables, feasible redesigns preserve required/allowed acceptance pairs and enforce intended issuer isolation through (C2). For issuer a and domain i, Ti ( a) = {v ∈ Vi : ( a, v) ∈ J } is the set of accepted targets. Define WHi (S) =

∑

9 COMPLEXITY AND STRUCTURAL REGIMES

The joint problem ranges from standard cut primitives to coupled NP-hard cases. Write n = |V |. The scalarized direct-issuance k = 2 slice is a minimum cut. For k ≥ 3, multiway-cut variants are NP-hard. [14] Derivation constraints can preserve hardness even when boundary latency vanishes. Theorem 9.1 (Coupled NP-hardness (chains)) Let E = ∅, impose (∆, h) = (1, |V |) with complete derivation eligibility, and set p(ρi ) = 0 for every domain. Minimizing BRnode over feasible designs is NP-hard for every fixed k ≥ 3, and strongly NP-hard when k is part of the input.

w ( u ).

u:∃s∈S, s⇝u in Hi

Issuer a contributes p( a)WHi ( Ti ( a)) in domain i. The full first-order score is therefore

The reduction is from Pk ∥ ∑ j w j Cj , where Cj is job completion time: domains are machines, chain order is job order, and p(v j ) is a scaled processing time. The full proof appears in Supplementary Sec. S2.2. Under direct issuance, where each Hi is a star, delegatedprincipal ancestor coupling disappears and the boundary problem can collapse to cut or labeling structure. An anchor is a service fixed to a specified domain label.

BRexplicit ( D, { Hi }, J )

= BRnode ( D, { Hi })

(14)

k

+ ∑ p( a) ∑ WHi ( Ti ( a)). a∈ I

i =1

An additive alternative assigns issuer risk separately to each accepted target and contributes p( a) ∑v∈Ti (a) WHi ({v}). We call the result the additive issuer score. It can count the same descendant through several accepted targets. Such overlap is absent when the targets form an antichain, meaning that no accepted target is an ancestor of another. A star refers to the derivation arborescence Hi , where ρi is the parent of every service. The interaction graph G remains arbitrary.

Proposition 9.2 (Two-domain min-cut regime) Consider Eq. (11) with k = 2, label-specific root probabilities independent of D, and star derivations feasible and optimal in both domains. Exact optimization under (C1) is the minimum over ordered anchor pairs of s–t cuts with service-label costs w(v) p(ρi ) and edge-disagreement costs λruv ℓuv cpqc (u, v), and remains polynomial time. Supplementary Sec. S2.3 gives the construction. The proposition maps the architecture variables to cut costs. Polynomial-time optimization then follows from the standard minimum-cut algorithm. The two-domain supportedpoint procedure varies the scalarization parameter and collects the resulting cut solutions. Supplementary Corollary S2.1 states the corresponding parametric-flow result. A hub is a selected depth-one node in a depth-two derivation tree. The solver routes require both semantic and topological eligibility. Direct root-to-workload issuance gives a star Hi . A root–intermediate–workload hierarchy gives depth two, and sequential delegation gives a chain. Shared verifier acceptance requires the explicit-propagation model rather than an arborescence shortcut. Table 1 summarizes the applicable solver choices. The chain route uses exact ratio ordering, while the multiway-cut, metric-labeling, and parametric rows inherit guarantees from established algorithms. [14–16] The corresponding reductions and bounded-treewidth statement appear in Supplementary Sec. S2. SPIRE documents single-authority, nested-intermediate, and federated trust-domain deployments, while OAuth 2.0 Token Exchange represents impersonation and delegation chains. [17–19] These specifications establish implementability. Deployment prevalence remains unknown. Service-call traces contain interaction topology and omit credential semantics. The replay therefore does not estimate regime prevalence.

Proposition 8.1 (Additive issuer-score upper bound) For fixed ( D, { Hi }) and nonnegative p, w, the additive issuer score upper-bounds the first-order explicit issuer-reachability score. Equality holds if, for every issuer and domain, the accepted targets form an antichain in Hi . The bound follows because weighted union size is at most the sum of weighted set sizes. Antichain targets in an arborescence have disjoint descendant sets. A full proof appears in Supplementary Sec. S2.5. Corollary 8.2 (Star-overlay exactness) For star Hi , the additive issuer score is exact for any number of accepted targets. Corollary 8.3 (Chain-overlay exactness) For chain Hi , the additive issuer score is exact when each issuer has at most one accepted target per domain, using peff (v) = p(v) +

∑

p ( a ).

a:( a,v)∈ J

The objectives therefore agree on any candidate family satisfying this condition. Both specializations follow in the proof of Proposition 8.1 in Supplementary Sec. S2.5. For a fixed deeper tree, removing any accepted target reachable from another accepted target leaves explicit reach unchanged. This deduplication depends on Hi and cannot be represented by a candidateindependent transformation to peff . If accepted targets overlap by ancestry, the additive issuer score is only a screening upper bound and final selection requires explicit scoring.

10 OPERATIONAL SOLVER

The implementation follows four steps. 5

Table 1: Solver guarantees by structural regime. Coupled chain and multiway cases are hard, while the listed two-domain, bounded-width, and fixed-partition cases admit exact methods under their stated assumptions. The antichain condition makes additive shared-issuer scoring exact. Supporting statements appear in Supplementary Sec. S2.

Applicable structure

Method

Guarantee

What it provides

Hard. NP-hard for fixed k ≥ 3 and strongly NP-hard when k varies. Exact. O(n2 ) anchor pairs.

Coupled hardness boundary.

Ratio ordering

Exact. O(n log n).

Optimal derivation order.

Root-to-service arcs Capacitated assignment

Exact. No inner search. Exact after fixed-∆ hub enumeration.

Derivation star. Small-fanout assignment.

Explicit reachability and antichain test

Conditional. An antichain makes additive scoring exact.

Determines when explicit rescoring is required.

Coupled partition and derivation (D, H) Chain, k ≥ 3 Parallel-machine scheduling reduction Direct issuance, k = 2

Anchored min-cut and parametric flow Direct issuance with equal root Multiway cut risk and k anchors Direct issuance with Graph labeling label-specific root risk (Potts/metric labeling)

Fixed partition (optimize Hi ) Chain with unrestricted ordering Direct issuance Depth two with fixed hubs Issuer overlay validation Shared-issuer acceptance

Boundary and supported Pareto-point optimization. Hard. NP-hard with a Anchored boundary (2 − 2/k)-approximation. optimization. Conditional. Exact for fixed k on Label-aware boundary bounded-treewidth interaction optimization. graphs. Specified anchors enforce nonempty labels. A 2-approximation applies only when labels may be unused.

1) Build the instance: Construct G from policy-gated call telemetry, calibrate crossing costs on the deployed cryptographic stack, specify w and p for a planning horizon, and encode domain policy, derivation eligibility, fanout, and depth constraints. Retain ( I, M, J ) when shared-issuer acceptance creates entry points not represented by the domain roots. 2) Generate candidates: Use exact structural solvers when their assumptions hold. The joint routes are the twodomain cut for direct issuance and bounded-treewidth dynamic programming for eligible low-width graphs. After fixing the domain assignment, use an exact chain, directissuance, or fixed-hub depth-two routine when applicable. Supplementary Tables S3 and S5 report the tested low-width dispatch and the treewidth increase caused by scoped refinement. Otherwise initialize D from traffic structure using spectral or multilevel partitioning, [20] construct a feasible derivation tree in each domain, and alternate risk-aware boundary moves with derivation updates. [21, 22] The default general-tree construction sorts by p(v)/w(v) and fills a ∆-ary tree breadth first. It is exact for chains and heuristic otherwise. 3) Refine under the budget: Weighted-sum solutions and deterministic traffic partitions form the initial candidate set. For each latency budget B, apply only moves and swaps that preserve feasibility and satisfy Lat( D ) ≤ B, then retain the candidate with the lowest blast-radius score. This hard-budget stage can recover designs omitted by linear scalarization. Increasing the density of the α grid alone cannot provide that coverage. Supplementary Table S1 isolates the contribution of this stage. 4) Validate semantics and cost: Use the additive issuer

score directly when the antichain condition guarantees exactness. Otherwise, trace issuer reachability for each retained candidate before selection. Exact enumeration provides reference solutions on small instances. Larger instances use additive or proxy scores to build a shortlist, then evaluate that shortlist using explicit reachability. For chain derivations, the proxy orders services using peff and evaluates the resulting order under both derivation and acceptance paths. After choosing B from measured latency constraints, rank designs that satisfy it by blast radius and inspect the edge and compromise-point contributions. Then remeasure the selected crossing edges in separate validation blocks. Reject a design whose observed boundary latency exceeds B, update the calibration or reserve, and rerun the budgeted selection. The reserve is a planning control rather than a statistical guarantee. Control-plane issuer inventories, trust stores, and delegation metadata determine plausible Hi and J. Where these are uncertain, solve several defensible scenarios rather than treating one inferred graph as ground truth. Supplementary Sec. S5 gives the extraction and refinement details. Guarantees and limits: For a fixed domain assignment, the implementation contains exact chain, direct-issuance, and fixed-hub depth-two derivation routines. It also contains exact two-domain direct-issuance/min-cut and anchored low-treewidth assignment routines. The general candidate search assumes complete within-domain derivation eligibility. Restricted relations can be represented and checked, while optimizing over them requires a separate eligible-tree routine. The implementation uses anchored αexpansion as a graph-labeling heuristic and generates supported points through repeated exact two-domain solves.

6

The 2-approximation and parametric-flow guarantees in Table 1 refer respectively to the algorithms of Kleinberg– Tardos and Gallo–Grigoriadis–Tarjan. [15, 16] The implementation applies one propagation model to the whole instance and does not yet combine different models or solvers across local graph regions. General guarantees for explicit propagation and such locally mixed strategies remain open.

dependencies. Reported wall-clock measurements remain machine dependent. Supplementary Sec. S4.1 gives parameters and source records. Q1: Does joint optimization change the design?: Table 2 compares joint optimization with the staged baseline on controlled n = 9, k = 3 instances. For each instance and budget, the exact reference evaluates every feasible assignment of the nine services to three nonempty labeled domains. The staged baseline minimizes the direct-issuance blast-radius score under the latency budget. Each seed assigns the three domain labels deterministic heterogeneous root priors drawn uniformly from [0.01, 0.07). These priors remain fixed across partitions, budgets, and risk settings. If several assignments tie, the baseline receives the one with the lowest chain or depth-two score. This tie rule favors the staged baseline by giving it information that a practical sequential procedure would not have. Joint optimization minimizes the chain or depth-two score directly under the same budget. The staged score is higher in nearly every chain case: 117 of 120. It is also higher in most depth-two cases: 78 of 110. The larger chain regret shows that a partition chosen under direct issuance can be poorly matched to the delegated compromise paths introduced later. The depth-two effect is smaller and remains present in most feasible cases. Supplementary Sec. S4.1 reports the adaptive supported-point solver-call check, hard-budget refinement, low-width dispatch, and heuristic comparisons with exact small-instance references. Q2: Workload, risk, and crossing cost: A reference replay first tests sensitivity to the service-risk scenario. At B = 0.10 ms, both scenarios select k = 6. The resulting BR/BR0 is 0.685 under the heterogeneous baseline and 0.743 under cluster skew. Under each scenario, the corresponding domain count recurs in at least 80% of edgecount resamples and 80% of solver seeds (Supplementary Sec. S4.3). The operational comparison keeps the bounded breadthfirst derivation family fixed and changes only how the domain assignment is selected. Risk-aware search optimizes the conservative score under the measured latency budget. For each k ∈ {1, . . . , 6}, latency-first search applies the restart-limited latency-only search and retains its lowestlatency partition. It then scores these partitions with the fixed breadth-first derivation family and selects the lowestscore candidate satisfying the budget. Traffic clustering partitions the interaction graph without risk input, and the single-domain design provides the baseline. All methods use the same edge-specific calibration-block maxima with a 5% budget reserve. Their selected crossings are then measured in held-out blocks. On N0, latency-first search has a mean exact expectedimpact ratio of 0.884 at both budgets. Risk-aware search lowers these ratios to 0.693 and 0.638, respectively. Every risk-aware design satisfies its held-out budget in these runs. The broader five-path sensitivity, including absolute C0/K1/A1 costs and incremental A1-minus-C0 migration costs, appears in Supplementary Fig. S3 and Table S8. Table 3 reports five independent graph-replay runs on each of N0 and N2 that separated calibration blocks

11 EVALUATION

We ask three questions: whether the coupled objective changes the design relative to a staged baseline, whether designs selected using measured crossing costs retain their benefit and latency compliance on held-out measurements, and when shared-issuer relationships require explicit rescoring. Setup: The main trace replay applies the optimization to a Train-Ticket service-interaction graph with 32 services and 72 directed edges, extracted from 1157 public Jaeger traces. [23] Edge multiplicities determine normalized calls/request. The baseline uses ℓuv = 1. Supplementary Sec. S4.3 defines the scenario inputs w(v) and p( x ). The heterogeneous-baseline scenario retains these priors. The cluster-skew scenario triples p(v) in the largest supplied service cluster, capped at 0.25. The formal problem treats the number of domains k as an input. Replay searches k ∈ {1, . . . , 6} under a computational cap. A value of k = 6 means the largest tested count, not an optimum over larger k. Replay root priors are zero and no fixed per-domain management charge is applied, so these experiments isolate delegated-principal risk and crossing cost. An equal nonzero root prior would add the same partition-invariant term to every candidate. Unless stated otherwise, replay assumes complete within-domain derivation eligibility, and candidate partitions satisfy the domain-size condition induced by (∆, h) = (3, 3). Each partition is scored with the deterministic breadth-first construction used for candidate generation. Within each domain, services are ordered by p(v)/w(v) and attached in that order to the earliest parent with remaining fanout, level by level to depth h. Thus, these replay results optimize one feasible family under complete eligibility. Global optimization over all admissible arborescences and replay under deploymentspecific eligibility remain outside the evaluation. The controlled solver-transfer and baseline replay experiments retain cpqc = 0.03 ms per crossing call and 20 calls per top-level request so that only the tested algorithmic factor changes. The deployment study instead uses 12000 TLS observations from 3 named cryptographic profiles and 5 network paths, then optimizes with those measured profiles and validates selected crossings on held-out blocks. We denote classical X25519/ECDSA-P256 by C0, hybrid X25519+ML-KEM-768/ECDSA-P256 by K1, and hybrid X25519+ML-KEM-768/ML-DSA-65 by A1. Paths N0–N4 denote the unshaped local, datacenter, regional, edge or mobile, and constrained lossy profiles. In the replay text and tables, BR abbreviates the conservative BRnode score, and BR0 is its k = 1 value under the same workload, risk scenario, derivation method, and feasibility filter. Candidate selections use fixed seeds and pinned numerical 7

Table 2: Joint optimization lowers the chain or depth-two blast-radius score relative to the staged baseline in 195 of 230 feasible comparisons. Each comparison enumerates every feasible nonempty domain assignment. Regret is the staged score minus the exact joint optimum, divided by that optimum. H is the heterogeneous-baseline risk setting and S triples service risk in the largest supplied cluster with clipping at 0.25. Each setting contains 20 seeds and three budgets. Five depth-two cases per setting have no feasible k = 3 design at the tightest budget and are omitted.

Derivation Chain Chain Depth two Depth two

Risk H S H S

Cases 60 60 55 55

Staged worse (%) 98 97 64 78

Mean regret (%) 29.38 32.73 2.47 2.67

(a) Exact expected impact

Max regret (%) 66.41 64.67 10.75 14.72

(b) Budget use (must not exceed 1)

N0: Risk-aware N0: Latency-first N0: Traffic clustering N0: Single domain N2: Risk-aware N2: Latency-first N2: Traffic clustering N2: Single domain

0.6

0.7 0.8 0.9 Ratio to single-domain baseline

1

B = 0.10 ms

0

0.2 0.6 0.8 0.4 1 Held-out boundary latency / budget

B = 0.20 ms

Figure 3: Risk-aware search produces the largest reduction in exact expected impacted weight on N0. On N2, its observed range overlaps that of traffic clustering. N0 is the unshaped local path. N2 has 35-ms round-trip time, 100-Mbit/s rate, and 0.1% packet loss. Panel (a) reports exact expected impacted weight under independent root and service compromise events. Candidate selection uses the conservative linear score. Panel (b) divides held-out boundary latency by the budget B in ms/request. The dashed line marks the budget limit. Points are means over five independently calibrated runs and bars span the observed range. The comparison tests domain selection within one fixed derivation family. It does not establish global optimization over all derivation arborescences.

Table 3: Held-out budget compliance across five independent runs and two budgets per path. Both block-maximum rules meet every check with a 5% reserve. Point estimates and unmodified maxima fail on some paths. N0 is unshaped. N2 has 35-ms round-trip time, 100-Mbit/s rate, and 0.1% packet loss. B is in ms/request. Standalone uses a path-level profile, graph-weighted uses one call-weighted coefficient, and edge-specific retains per-edge coefficients. Block maxima are taken across calibration blocks. Reserve rows inflate them by 1/(1 − 0.05).

Calibration

N0

N2

Standalone profile Graph-weighted mean Edge-specific means Graph block maximum Edge-specific block maxima Graph maximum + 5% reserve Edge maxima + 5% reserve

2/10 1/10 1/10 7/10 10/10 10/10 10/10

10/10 10/10 9/10 10/10 8/10 10/10 10/10

the isolated issuer auth to payments and orders leaves boundary latency unchanged and adds explicit propagation paths. The discrepancy comes from semantics: arborescence-only scoring omits issuer entry paths that the deployment accepts. On the larger candidate sets derived from traces, ranking by the additive issuer score alone identifies the best explicitly evaluated candidate in 11 of 12 comparisons and misses by at most 5.86%. Explicitly evaluating the three candidates ranked highest by the reachability-aware proxy recovers the best generated candidate in all 12 comparisons. When the antichain condition holds, the additive score can select the final design. In all other cases, final selection uses explicit issuer reachability over the shortlist. 12 LIMITATIONS

The model is a credential-architecture planning abstraction. It does not cover every enterprise compromise path. Its conclusions are conditional on the supplied workload, criticality, compromise, and cost scenarios.

from held-out validation blocks and checked two budgets per run. Reserving 5% of the budget under either block-maximum rule meets all 20 path-budget checks per rule. Finite held-out success does not establish a pathindependent guarantee, so remeasurement and rejection remain necessary. Additional solver-scaling, protocol, and calibration diagnostics appear in Supplementary Sec. S4. Q3: Explicit-rescoring conditions: The hand-constructed shared-issuer reachability example in Fig. 4 uses unitnormalized interaction coefficients. Its edge labels are illustrative toy costs rather than measured latency. Keeping that interaction cut fixed while adding acceptance from

• Propagation is limited to credential authority. Verifier compromise, software supply-chain compromise, and non-credential exploitation paths are not modeled. Compromise probabilities are exogenous, although segmentation may change real exposure. • The core assumes single-parent derivation. Multiparent or threshold issuance requires a directed acyclic graph (DAG) model. Explicit issuer accep-

8

r·ℓ·c=140 r=70 ℓ=2 c=1

client H₂

r·ℓ·c=300 r=100 ℓ=3 c=1

gateway H₂

r·ℓ·c=160 r=80 ℓ=2 c=1

management (IAM) policy synthesis change access structure to reduce credential-connected components, unnecessary permissions, or compromise impact while limiting operational disruption. [24, 25] Their decision variables stop at access structure. The credential-authority arborescence among operational principals remains fixed. Logical-key-hierarchy research chooses rooted auxiliarykey trees using update probabilities, communication cost, and network topology. [26–29] Those models use rekeying keys as internal vertices under a shared controller, and their objective is update or recovery communication. Each domain has an independently compromised root. The hierarchy’s internal vertices are operational principals, and steady-state service calls incur cost when they cross roots. Hierarchical key assignment and delegation systems provide authority-structure context while optimizing different objectives. [30–32] Zero-trust identity guidance defines relevant issuer relationships. [1, 33] Risk-optimized and role-based microsegmentation methods synthesize access boundaries from policy or flow evidence while treating credential-derivation structure as fixed. [34, 35] The comparison turns on four elements used together in this formulation: an independent-root partition, an operational derivation forest, steady-state crossing cost, and a modelspecific condition for exact additive issuer scoring.

payments H₂ J

auth H₁ J r·ℓ·c=60 r=60 ℓ=1 c=1

orders H₂

Figure 4: Shared-issuer reachability example showing why boundary placement alone does not capture issuer propagation. The H1 /H2 labels identify the credential-derivation trees containing each principal. Black arrows are service interactions. Solid arrows stay within H2 , whereas the thick dashed gateway→auth arrow is the sole boundary crossing and contributes the full toy cut cost r ℓc = 160. Gray dotted arrows are verifier-acceptance pairs J , not derivation arcs. Because payments and orders in H2 accept credentials from auth in H1 , issuer compromise reaches both services without changing Lat( D ).

tance is handled separately. General complexity guarantees and globally coordinated mixtures of core and explicit-propagation scoring remain open.

• The mapping from trust boundaries to crossing cost assumes key-establishment domains in which intradomain payload protection uses established symmetric keys or derived credentials. Deployments that perform independent public-key operations within a domain must represent those operations as additional 14 CONCLUSION We formulate trust-boundary placement and credential weighted events or refine the domain assignment. delegation as one design problem: limit compromise • Boundary latency is linearized from measured or esti- reach without exceeding the latency budget for crossmated effective crossing costs. Static edge coefficients boundary authentication. The model separates domaincan absorb path-specific mean effects. They do not authority compromise, delegated-principal compromise, directly model correlated packet loss, retries, shared and shared-issuer acceptance. The formal results establish congestion, queueing, or end-to-end tail latency. The NP-hardness and identify exact cases for scalarized twocontrolled TLS measurements expose path-specific domain direct issuance. For bounded-width interaction retransmission and handshake effects only through graphs, exactness holds with specified anchors or fixed k. effective coefficients. The graph replay estimates how The results also state when the additive score represents several calibration and reserve rules transfer across shared-issuer risk. Other regimes inherit guarantees from N0 and N2. Finite held-out success cannot establish a established scheduling, graph-labeling, and parametricpath-independent guarantee. Operational use there- flow algorithms. fore requires iterative calibration, optimization, and The evaluation shows where the formulation changes remeasurement of the selected crossing edges. design decisions. Joint optimization lowers the chain or depth-two blast-radius score in 195 of 230 exact compar• Trace results use one deterministic bounded-breadthisons, with the larger effect under chain delegation. Meafirst derivation family and finite local-search budgets. sured path conditions change the domain count selected The reported designs are best found within this search. under the same latency budget. On N0, risk-aware search Global optimality over all feasible arborescences reyields a large impact reduction. The five N2 runs leave the mains unverified. Supplementary Tables S1 and S4 ordering of risk-aware search and traffic clustering unrequantify observed gaps against exhaustive references solved. A 5% reserve meets every held-out check for both on small instances. tested block-maximum rules. The reserve remains a plan• Two public trace-derived workloads, synthetic fami- ning rule that requires deployment remeasurement. The lies, and controlled stack measurements do not estab- additive issuer score can misrank designs when accepted lish production-wide generality. Control-plane uncer- services have overlapping credential reach. In deployment, tainty should be represented by several plausible Hi use the optimization to generate candidate architectures, trace shared-issuer reach where required, and remeasure and J scenarios. selected crossings before accepting a design. 13 RELATED WORK DATA AND CODE AVAILABILITY

The formulation combines a segmentation decision with credential-derivation design. Its compromise semantics differ from the two closest decision problems. Authentication-graph partitioning and identity and access

Code and processed data may be made available by the corresponding author upon reasonable request, subject to organizational approval. 9

ACKNOWLEDGMENT

[17] The SPIFFE Authors, “Scaling SPIRE,” SPIFFE deployment guidance, 2026, version 1.15.1, accessed 2026-07-17. [Online]. Available: https://spiffe.io/docs/latest/planning/scaling spire/

The authors thank K. Halunen for feedback on an earlier version of this manuscript. The views expressed in this paper are those of the authors and do not necessarily reflect the views and policies of their respective employers.

[18] ——, “SPIFFE Federation,” SPIFFE specification, 2026, version 1.15.1, accessed 2026-07-17. [Online]. Available: https://spiffe.io/ docs/latest/spiffe-specs/spiffe federation/

REFERENCES [1] S. Rose, O. Borchert, S. Mitchell, and S. Connelly, “Zero trust architecture,” National Institute of Standards and Technology, Tech. Rep. NIST Special Publication 800-207, Aug. 2020, accessed 2026-02-07. [Online]. Available: https://csrc.nist.gov/pubs/sp/ 800/207/final

[19] M. Jones, A. Nadalin, B. Campbell, J. Bradley, and C. Mortimore, “OAuth 2.0 Token Exchange,” Internet Engineering Task Force (IETF), RFC 8693, Jan. 2020. [Online]. Available: https://www. rfc-editor.org/rfc/rfc8693 [20] G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” SIAM Journal on Scientific Computing, vol. 20, no. 1, pp. 359–392, 1998.

[2] P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124–134.

[21] B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell System Technical Journal, vol. 49, no. 2, pp. 291–307, 1970.

[3] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 212–219.

[22] C. M. Fiduccia and R. M. Mattheyses, “A linear-time heuristic for improving network partitions,” in Proceedings of the 19th Design Automation Conference, 1982, pp. 175–181.

[4] M. Sosnowski, F. Wiedner, E. Hauser, L. Steger, D. Schoinianakis, S. Gallenmüller, and G. Carle, “The performance of post-quantum TLS 1.3,” in Companion of the 19th International Conference on Emerging Networking Experiments and Technologies, 2023, pp. 19–27.

[23] M. Steidl, “Anomalies in microservice architecture (train-ticket) based on version configurations,” Zenodo dataset, 2022.

[5] P. Kampanakis and W. Childs-Klein, “The impact of data-heavy, post-quantum TLS 1.3 on the time-to-last-byte of web connections,” in Proceedings 2024 Workshop on Measurements, Attacks, and Defenses for the Web. Internet Society, 2024. [6] M. Sim, G. Song, M. Lee, S. Yoon, A. Baksi, and H. Seo, “Integrating and benchmarking KpqC in TLS/X.509,” 2025, accessed 2026-02-07. [Online]. Available: https://eprint.iacr.org/2025/1245 [7] D. Moody, R. Perlner, A. Regenscheid, A. Robinson, and D. Cooper, “Transition to post-quantum cryptography standards,” National Institute of Standards and Technology, Tech. Rep. NIST IR 8547 (Initial Public Draft), Nov. 2024, accessed 2026-02-07. [Online]. Available: https://csrc.nist.gov/pubs/ir/8547/ipd [8] National Institute of Standards and Technology, “Modulelattice-based key-encapsulation mechanism standard,” National Institute of Standards and Technology, Tech. Rep. FIPS 203, Aug. 2024, accessed 2026-02-07. [Online]. Available: https: //csrc.nist.gov/pubs/fips/203/final

[24] A. S. Pope, D. R. Tauritz, and A. D. Kent, “Evolving bipartite authentication graph partitions,” IEEE Transactions on Dependable and Secure Computing, vol. 16, no. 1, pp. 58–71, 2019. [25] M. Kazdagli, M. Tiwari, and A. Kumar, “Using constraint programming and graph representation learning for generating interpretable cloud security policies,” arXiv:2205.01240, 2022. [Online]. Available: https://arxiv.org/abs/2205.01240 [26] C. K. Wong, M. Gouda, and S. S. Lam, “Secure group communications using key graphs,” ACM SIGCOMM Computer Communication Review, vol. 28, no. 4, pp. 68–79, 1998. [27] D. Wallner, E. Harder, and R. Agee, “Key management for multicast: Issues and architectures,” RFC Editor, Tech. Rep. RFC 2627, Jun. 1999, accessed 2026-02-07. [Online]. Available: https://www.rfc-editor.org/rfc/rfc2627 [28] A. Chan, R. Rajaraman, Z. Sun, and F. Zhu, “Approximation algorithms for key management in secure multicast,” in Computing and Combinatorics, ser. Lecture Notes in Computer Science. Springer, 2009, vol. 5609, pp. 148–157. [29] H. Sakai and H. Yamamoto, “Asymptotically optimal tree-based group key management schemes,” arXiv:cs/0507001, 2005. [Online]. Available: https://arxiv.org/abs/cs/0507001

[9] ——, “Module-lattice-based digital signature standard,” National Institute of Standards and Technology, Tech. Rep. FIPS 204, Aug. 2024, accessed 2026-02-07. [Online]. Available: https: //csrc.nist.gov/pubs/fips/204/final

[30] M. J. Atallah, M. Blanton, N. Fazio, and K. B. Frikken, “Dynamic and efficient key management for access hierarchies,” ACM Transactions on Information and System Security, vol. 12, no. 3, pp. 1–43, 2009, article 13.

[10] ——, “Stateless hash-based digital signature standard,” National Institute of Standards and Technology, Tech. Rep. FIPS 205, Aug. 2024, accessed 2026-02-07. [Online]. Available: https: //csrc.nist.gov/pubs/fips/205/final [11] Google Cloud Security and Privacy Team, “Securing communications between Google services with application layer transport security,” Google Online Security Blog, Dec. 2017, accessed 2026-08-10. [Online]. Available: https://security.googleblog.com/ 2017/12/securing-communications-between-google.html [12] L. Bettale, M. De Oliveira, and E. Dottax, “Post-quantum protocols for banking applications,” Fourth NIST PQC Standardization Conference, 2022, accessed 2026-08-10. [Online]. Available: https://csrc.nist.gov/csrc/media/Events/2022/ fourth-pqc-standardization-conference/documents/papers/ post-quantum-protocols-for-banking-applications-pqc2022.pdf [13] Chrome Secure Web and Networking Team, “Cultivating a robust and efficient quantum-safe HTTPS,” Google Online Security Blog, Feb. 2026, accessed 2026-03-23. [Online]. Available: https://security. googleblog.com/2026/02/cultivating-robust-and-efficient.html [14] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, “The complexity of multiway cuts (extended abstract),” in Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, 1992, pp. 241–251. [15] J. Kleinberg and É. Tardos, “Approximation algorithms for classification problems with pairwise relationships,” Journal of the ACM, vol. 49, no. 5, pp. 616–639, 2002. [16] G. Gallo, M. D. Grigoriadis, and R. E. Tarjan, “A fast parametric maximum flow algorithm and applications,” SIAM Journal on Computing, vol. 18, no. 1, pp. 30–55, 1989.

10

[31] A. Birgisson, J. G. Politz, Ú. Erlingsson, A. Taly, M. Vrable, and M. Lentczner, “Macaroons: Cookies with contextual caveats for decentralized authorization in the cloud,” in Proceedings of the Network and Distributed System Security Symposium (NDSS). Internet Society, 2014. [32] M. P. Andersen, S. Kumar, M. AbdelBaky, G. Fierro, J. Kolb, H.-S. Kim, D. E. Culler, and R. A. Popa, “WAVE: A decentralized authorization framework with transitive delegation,” in 28th USENIX Security Symposium (USENIX Security 19). Santa Clara, CA: USENIX Association, Aug. 2019, pp. 1375–1392. [Online]. Available: https://www.usenix.org/conference/usenixsecurity19/ presentation/andersen [33] R. Ward and B. Beyer, “BeyondCorp: A new approach to enterprise security,” ;login:, vol. 39, no. 6, pp. 6– 11, 2014. [Online]. Available: https://research.google/pubs/ beyondcorp-a-new-approach-to-enterprise-security/ [34] S. Noel, V. Swarup, and K. Johnsgard, “Optimizing network microsegmentation policy for cyber resilience,” The Journal of Defense Modeling and Simulation: Applications, Methodology, Technology, vol. 20, no. 1, pp. 57–79, 2023. [35] S. K. Mani, K. Hsieh, S. Segarra, R. Chandra, Y. Zhou, and S. Kandula, “Securing public cloud networks with efficient role-based Micro-Segmentation,” in 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25). Philadelphia, PA: USENIX Association, Apr. 2025, pp. 1033–1048. [Online]. Available: https://www.usenix.org/conference/nsdi25/ presentation/mani

Supplementary Information: Optimizing Credential Blast Radius Through Trust Boundaries and Delegation Under Post-Quantum Authentication Costs Pauli Taipale and Harri Lainio The worked example makes trust-domain assignment and within-domain credential derivation concrete. The remaining sections give structural results and proofs, define secondary risk summaries, report solver, workload, crossing-cost, and shared-issuer diagnostics, and describe deployment considerations. S1 WORKED EXAMPLE

We illustrate how feasibility constraints and intra-domain derivation structure affect blast radius and latency. Throughout this example, the domain assignment D is fixed and maps each service to one of two domains. The quantity Lat( D ) is the total calibrated cost of interactions that cross between those domains. Fixing D isolates derivation-side changes in blast radius at constant boundary latency. Let V = { a, b, c, d, e, f } and k = 2 with D ( a) = D (b) = D (c) = 1 and D (d) = D (e) = D ( f ) = 2. Let the interaction edges include a → b, b → c, c → d, b → e, and e → f . Assume only c → d Domain 1

Domain 2

a

d

b

e

c

f interaction edge (E) boundary edge (D (u) ̸= D (v))

Figure S1: Fixed domains separate boundary latency from derivation risk. All arrows are service calls. Red arrows mark the two crossing calls, whose ruv ℓuv cpqc (u, v) contributions sum to Lat( D ) = 220 in the unit-normalized toy calibration. Changing only the derivation trees leaves this boundary latency fixed while allowing a different blast radius.

and b → e cross the domain boundary. Let ruv denote the interaction rate, ℓuv its path-sensitivity weight, and cpqc (u, v) its effective crossing cost. Using a unit-normalized toy crossing cost on the crossing edges (not a literal classical or PQC deployment measurement), together with rcd = 100, ℓcd = 2, cpqc (c, d) = 1 and rbe = 20, ℓbe = 1, cpqc (b, e) = 1, we have Lat( D ) = 100 · 2 · 1 + 20 · 1 · 1 = 220.

(S1)

Let Hi denote the credential-derivation tree rooted at issuer ρi , let ∆ bound the number of children of any tree vertex, and let h bound the root-to-service depth. In this example, Aallow contains every root-to-service arc and only the service-to-service arcs b → c and e → f . With ∆ = 2 and h = 2, these constraints require ρ1 → a, ρ1 → b, and b → c in domain 1, and ρ2 → d, ρ2 → e, and e → f in domain 2. Let w(v) = 1 for all v ∈ V, and assume compromise probabilities p(b) = 0.02 and p(e) = 0.01 with all other p( x ) = 0. Writing Reach Hi ({ x }) for the services reachable from a compromised vertex x in Hi , including x itself, gives Reach H1 ({b}) = {b, c} and Reach H2 ({e}) = {e, f }. The conservative score BRnode sums each compromise probability times the total weight reached, so BRnode ( D, { Hi }) = 0.02 · 2 + 0.01 · 2 = 0.06.

(S2)

Increasing the degree bound to ∆ = 3 permits each root to issue directly to all three services. Then Reach H1 ({b}) = {b} and Reach H2 ({e}) = {e}, reducing the conservative blast-radius score to 0.02 · 1 + 0.01 · 1 = 0.03 without changing Lat( D ). This demonstrates why derivation eligibility and fanout limits can change blast radius even when trust boundaries are fixed. In this example the derivation structures are simple depth-two arborescences with the arcs listed above. • Corresponding author: Pauli Taipale ([email protected]). • Pauli Taipale and Harri Lainio are with OP Lab, OP Pohjola, Gebhardinaukio 1, FI-00510 Helsinki, Finland.

11

S1.1 Why latency-first optimization can fail

Consider three unit-weight principals a, b, c, two nonempty domains, zero root risk, and chain derivations (∆, h) = (1, 2). Let p( a) = 0.01 and p(b) = p(c) = 0.9. The only interaction coefficients are 1 on a → b and 2 on b → c. For singleton a, b, or c, respectively, the best-chain triples (Lat, BRnode , BRnode + 12 Lat) are (1, 2.71, 3.21), (3, 1.82, 3.32), and (2, 1.82, 2.82). A latency-first design therefore selects { a} | {b, c}, whereas joint scalarized optimization selects { a, b} | {c}. Equivalently, under budget B = 2, the latter reduces blast radius from 2.71 to 1.82. The difference arises because grouping b and c forces one high-risk principal above the other, while grouping a and b places the low-risk principal first. S2 FORMAL RESULTS AND PROOFS

The formal results distinguish model-specific reductions from guarantees inherited from cited algorithms. This section states domain-assignment and fixed-domain derivation results before their supporting proofs. S2.1 Secondary structural results

Corollary S2.1 (Parametric cut sweep) Consider two nonempty domains with fixed label-specific root probabilities independent of D, where direct issuance is feasible and optimal. An anchor is a service fixed to a specified domain. Varying the latency weight λ ∈ [0, ∞) in BRnode + λLat( D ) traces the supported tradeoff between boundary latency and blast radius. For each fixed ordered anchor pair, applying the parametric maximum-flow/min-cut algorithm of Gallo–Grigoriadis–Tarjan computes all breakpoints and a nested representative optimal cut for every parameter interval in polynomial time, rather than solving an independent cut on a dense parameter grid. [16] Without fixed anchors, enumerating ordered anchor pairs and taking the lower envelope still gives a polynomial-time sweep. Representatives selected from different anchor pairs need not be globally nested. To match the cited parametric-flow family, exchange labels so that δ = p(ρ2 ) − p(ρ1 ) ≥ 0, subtract constants, divide the λ > 0 objective by λ, and set µ = 1/λ. The interaction capacities are then fixed and the source capacities µδw(v) are monotone in µ. Corollary S2.2 (Interval-robustness) Consider interval uncertainty in boundary-edge coefficients and compromise probabilities. For each interaction edge (u, v) ∈ E, let auv ∈ [ auv , auv ], and for each compromise point x (service or root) let p( x ) ∈ [ p( x ), p( x )]. Let auv and p( x ) denote the upper endpoints, and write p for the collection { p( x )} x . Then for any fixed design ( D, { Hi }), max Lat( D ) = { auv }

∑

auv ,

(u,v)∈ E:D (u)̸= D (v)

max BRnode ( D, { Hi }) = BRnode ( D, { Hi }) p= p .

{ p( x )}

Consequently, the robust counterparts of the scalarized objective (minimize worst-case scalarized objective) and the budgeted objective (minimize worst-case BRnode subject to worst-case budget feasibility) reduce to the same problems with auv and p( x ) replaced by their upper bounds. In particular, under the assumptions of the two-domain min-cut regime, the interval-robust scalarized problem remains reducible to a minimum s–t cut (using capacities auv and root-risk terms evaluated at p), and the parametric sweep in Corollary S2.1 still applies. The endpoint substitution follows directly because every uncertain coefficient has a nonnegative multiplier in both objectives. Corollary S2.3 (Multiway-cut regime) Under the same star-derivation assumptions, with k ≥ 3 and uniform root compromise probability p(ρi ) = p0 for all i, the BRnode term becomes constant. If, in addition, k anchor vertices t1 , . . . , tk ∈ V are required to lie in distinct domains (a policy constraint in (C2)), then optimizing the scalarized objective over D is equivalent to a minimum multiway cut instance on the underlying undirected interaction graph (ignoring directions, equivalently summing antiparallel weights) with terminals {t1 , . . . , tk }. This problem is NP-hard and admits a (2 − 2/k )-approximation algorithm. [14] Proposition S2.4 (Star regime: treewidth dynamic programming) Under the same star-derivation assumptions, for general k ≥ 2 and arbitrary root compromise probabilities p(ρi ), the scalarized objective reduces (up to additive constants) to a uniform metric labeling objective, also called a Potts maximum-a-posteriori (MAP) objective. [15] min

∑ cv,D(v)

D:V →[k ] v∈V

+

∑

buv 1[ D (u) ̸= D (v)].

(u,v)∈ E

where cv,i = w(v) p(ρi ) and buv = λ ruv ℓuv cpqc (u, v). Since 1[ D (u) ̸= D (v)] is symmetric, one may equivalently view the edge-disagreement term as living on the underlying undirected graph with weights obtained by summing antiparallel directed interactions. The displayed formulation permits unused labels and is therefore the at-most-k relaxation of (C1). If distinct anchors t1 , . . . , tk are fixed to labels 1, . . . , k, the anchors enforce (C1). Given an O(n)-bag width-τ tree decomposition, dynamic programming (DP) then finds an exact optimum in O(nkτ +1 ) time. Without fixed anchors, exact (C1) optimization follows by minimizing over all (n)k = n!/(n − k)! ordered anchor tuples, in O((n)k nkτ +1 ) time and hence polynomial time for fixed k. 12

Proof in Supplementary Sec. S2.8. Corollary S2.5 (At-most-k star-regime approximation) The at-most-k relaxation in Proposition S2.4 is a uniform metric labeling instance. It admits a polynomial-time 2-approximation algorithm. [15] This inherited guarantee does not by itself apply to the exact-k nonempty-domain constraint (C1). Corollary S2.6 (Treewidth under refinement) Let G be the underlying undirected interaction graph and suppose tw( G ) = τ. Form a refined graph G ′ by replacing each vertex v ∈ V by between one and s scoped principals (e.g., public vs. privileged). Add edges only between refined endpoints of original edges. The standard bag-expansion construction gives tw( G ′ ) ≤ s(τ + 1) − 1. Consequently, in the star regime, the bounded-treewidth dynamic program in Proposition S2.4 applies verbatim to G ′ with the same label set [k ]. Its running time is O(|V ′ | ks(τ +1) ). Proof in Supplementary Sec. S2.9. Remark S2.7 (Tightness) The dependence on s and τ is tight up to constants. For τ ≥ 1, let G be a clique on τ + 1 vertices and replace each vertex by an independent set of s refined principals, with all cross-fiber edges induced by the original clique. The resulting complete (τ + 1)-partite graph has equal part size s and treewidth sτ, within an additive s − 1 of the upper bound s(τ + 1) − 1. We now fix the domain assignment and optimize one derivation tree at a time. For a fixed domain, write its contribution as (i ) BRnode ( Hi ) = ∑ w(v) (S3) ∑ p ( x ). v∈Vi

x ∈Anc Hi (v)

Corollary S2.8 (Exact chain ordering (∆ = 1)) Fix a domain Vi with weights w(v) ≥ 0 and compromise probabilities p(v) ≥ 0. Assume (C3)–(C4) with ∆ = 1, h ≥ |Vi |, and complete derivation eligibility on Vi ∪ {ρi }. Any feasible Hi is a directed chain rooted at ρi and therefore induces an ordering (permutation) σ of Vi . Then a minimizer of the domain objective in Eq. (S3) is obtained by sorting services by nondecreasing ratio p(v)/w(v) (with the convention p(v)/0 = +∞ when w(v) = 0). This optimal chain can be computed in O(|Vi | log |Vi |) time. Proof in Supplementary Sec. S2.4. Proposition S2.9 (Star optimality (∆ ≥ |Vi |)) Fix a domain Vi with weights w(v) ≥ 0 and compromise probabilities p(v) ≥ 0, and assume ∆ ≥ |Vi |, h ≥ 1, and eligibility of every arc ρi → v for v ∈ Vi . Then the star arborescence with arcs ρi → v for all (i )

v ∈ Vi minimizes BRnode ( Hi ) among all feasible Hi . Proof in Supplementary Sec. S2.6. Proposition S2.10 (Depth-two case (h = 2)) Fix a domain Vi with n = |Vi |, assume complete derivation eligibility and h = 2, and let ∆ ≥ 1 (so feasibility requires n ≤ ∆ + ∆2 ). If n > ∆, there exists an optimal Hi in which exactly ∆ services are attached directly to ρi (depth 1), and all remaining services have depth 2. Fix any depth-1 set U ⊆ Vi with |U | = ∆ and define leaves L = Vi \ U. An optimal depth-two arborescence consistent with hub set U is obtained by solving the assignment problem below (up to additive constants in Eq. (S3)): min ∑ ∑ p(u) w(v) xuv { xuv }

s.t.

u ∈U v ∈ L

∑ xuv = 1

∀v ∈ L

∑ xuv ≤ ∆

∀u ∈ U

(S4)

u ∈U v∈ L

xuv ∈ {0, 1}. Because costs factor as p(u)w(v), an optimal assignment attaches the largest w(v) to the smallest p(u) (fill the lowest-p hub up to capacity ∆, then proceed in increasing p). If ∆ is a fixed constant, enumerating all (∆n ) hub sets and solving the corresponding assignment yields an exact algorithm running in O(n∆ poly(n)) time. Proof in Supplementary Sec. S2.7.

13

S2.2 Proof of coupled NP-hardness (chains)

Proof. We give a polynomial-time reduction from the scheduling problem Pk ∥ ∑ j w j Cj on k identical parallel machines.1 Skutella and Woeginger show that the problem is strongly NP-hard and admits a polynomial-time approximation scheme (PTAS). [?] Fix k ≥ 3 and take an instance with jobs J = {1, . . . , n}, processing times t j > 0, and weights w j ≥ 0. Construct our instance as follows. We may assume n ≥ k: if n < k, an optimal schedule assigns each job to a distinct machine and can be found in polynomial time, so hardness is witnessed on instances with n ≥ k. Let V contain one vertex v j per job j. Set E = ∅ so that Lat( D ) = 0 for all assignments. Set the feasibility parameters (∆, h) = (1, |V |). Set all root compromise probabilities to zero: p(ρi ) = 0 for i = 1, . . . , k. Assign node compromise probabilities by scaling the processing times into (0, 1): let T = 1 + ∑ j∈ J t j and define p(v j ) = t j /T. Set criticality weights w(v j ) = w j . This defines an instance satisfying the theorem’s restrictions. Because eligibility is complete, ∆ = 1, and (C3) requires an arborescence, each feasible Hi is a directed chain rooted at ρi spanning Vi , i.e., any linear order of the vertices assigned to domain i is feasible. Consider any feasible design ( D, { Hi }) and interpret each vertex v j as job j, assigned to machine D (v j ) and processed in the chain order induced by HD(v j ) . For a job j scheduled on a machine with preceding jobs j1 , . . . , jm , the completion time is m

Cj =

∑ t jℓ + t j .

ℓ=1

In our objective, for the corresponding vertex v j , the ancestor set along the chain (excluding the root, which has p(ρi ) = 0) is exactly {v j1 , . . . , v jm , v j }, so

∑

x ∈Anc H

D (v j )

 Cj 1 m t jℓ + t j = . ∑ T ℓ=1 T

p( x ) = (v j )

Therefore, summing Eq. (S3) over all domains and using p(ρi ) = 0, BRnode ( D, { Hi }) = ∑ w j · j∈ J

Cj 1 = w j Cj , T T j∑ ∈J

so an optimizer of BRnode yields an optimizer of Pk ∥ ∑ j w j Cj (and vice versa), up to the positive scaling factor 1/T. Non-empty domains vs. unused machines.: Constraint (C1) requires each domain Vi to be non-empty, corresponding to schedules that use all k machines. When n ≥ k, this restriction does not change the scheduling optimum: given any schedule with an idle machine, select a machine with at least two jobs and move its last job to the idle machine. This weakly decreases that job’s completion time and leaves all other completion times unchanged, so ∑ j w j Cj does not increase. By repeating, there exists an optimal schedule that uses all machines. Therefore the scheduling optimum equals the optimum among schedules that use all machines, and our reduction is valid under (C1). It follows that our coupled optimization is NP-hard for any fixed k ≥ 3, and strongly NP-hard when k is part of the input. □ S2.3 Proof of the two-domain min-cut regime

Proof. Let k = 2. Under the assumptions of the proposition, for any partition D we may restrict attention to star derivations within each domain (Proposition S2.9). In a star, each service v has ancestors Anc(v) = {ρ D(v) , v}, so BRnode ( D, { Hi⋆ }) =

∑ w ( v ) p ( v ) + ∑ w ( v ) p ( ρ D ( v ) ),

v ∈V

v ∈V

where the first term is constant over all D. Let auv = ruv ℓuv cpqc (u, v) so that Lat( D ) = ∑(u,v)∈E auv 1[ D (u) ̸= D (v)]. Dropping additive constants, the scalarized objective reduces to minimizing over D the objective

∑ c D (v) ( v ) + ∑

v ∈V

buv 1[ D (u) ̸= D (v)],

(u,v)∈ E

where ci (v) = p(ρi )w(v) and buv = λauv . Build a directed s–t network with vertices {s, t} ∪ V. For each v ∈ V, add arcs s → v of capacity c2 (v) and v → t of capacity c1 (v). For each interaction edge (u, v) ∈ E, add arcs u → v and v → u, each of capacity buv . For any s–t cut (S, T ) (with s ∈ S, t ∈ T), define a partition D by assigning D (v) = 1 if v ∈ S and D (v) = 2 if v ∈ T. Then the cut capacity equals the objective above: a vertex v contributes c1 (v) iff v ∈ S (via v → t crossing), and c2 (v) iff v ∈ T (via 1 In the standard three-field notation, C

j denotes the completion time of job j on its assigned machine.

14

s → v crossing). For each (u, v) ∈ E, neither symmetric arc crosses when D (u) = D (v). When D (u) ̸= D (v), exactly one crosses and contributes buv . Thus, minimizing the scalarized objective is equivalent to a minimum s–t cut and is solvable in polynomial time. Enforcing non-empty domains.: Constraint (C1) requires that both domains contain at least one service vertex. If two anchors a, b ∈ V are specified and must satisfy D ( a) = 1 and D (b) = 2, enforce these constraints by adding arcs s → a and b → t with capacity larger than any finite feasible cut (equivalently, treat a and b as fixed terminals on the s and t sides). If no anchors are specified, enforce non-emptiness by taking the minimum over all ordered pairs ( a, b) of distinct vertices: for each pair, solve the anchored min-cut instance above and return the best solution. This adds a factor of O(|V |2 ) to the runtime and remains polynomial. □ S2.4 Derivation of Corollary S2.8

Proof. Complete derivation eligibility and constraints (C3)–(C4) with ∆ = 1 make every ordering of Vi a feasible chain. For chain order (v1 , . . . , vn ), its objective is n

n

t

t =1

t =1

j =1

p ( ρ i ) ∑ w ( v t ) + ∑ w ( v t ) ∑ p ( v j ). The first term is constant, and the second is ∑ j w j Cj with processing times p(v j ). For adjacent services u and v, placing u before v rather than v before u changes this term by w(v) p(u) − w(u) p(v). Thus u before v is no worse whenever p(u)/w(u) ≤ p(v)/w(v), using the convention in the corollary. Repeatedly removing inversions proves that sorting by this ratio is optimal and takes O(n log n) time. □ S2.5 Proof of the additive issuer-score upper bound

Proof. Fix a domain i and an issuer a, and abbreviate T = Ti ( a). For each accepted target v ∈ T, let Desc Hi (v) = {u ∈ Vi : v ⇝ u in Hi } denote the descendants unlocked from v. The explicit issuer contribution in domain i is therefore p( a) u∈

S

∑

w(u) = p( a) WHi ( T ).

v∈ T Desc Hi ( v )

The additive score instead counts each accepted target separately and contributes p( a) ∑

∑

v∈ T u∈Desc H (v)

w(u) = p( a) ∑ WHi ({v}). v∈ T

i

Because w ≥ 0, the weight of a union is at most the sum of the individual weights: u∈

S

∑

w(u) ≤

∑

∑

w ( u ).

v∈ T u∈Desc H (v)

v∈ T Desc Hi ( v )

i

Multiplying by p( a) ≥ 0 preserves the inequality, so the additive contribution of issuer a in domain i is an upper bound on the explicit contribution. Summing over all issuers and all domains, and then adding back the unchanged service-compromise and root terms, proves the pointwise upper bound on the full first-order objective. Now assume that no accepted target in Ti ( a) is an ancestor of another. In an arborescence, descendant sets of incomparable vertices are disjoint. Hence the sets {Desc Hi (v)}v∈T are pairwise disjoint, so the union-weight inequality above is tight. Therefore the additive and explicit contributions agree exactly issuer-by-issuer and domain-by-domain, and thus the full scores are equal. In a star, each service has only itself as a service descendant, so accepted targets always form an antichain. In a chain, all distinct services are comparable, so the antichain condition permits at most one target per issuer and domain. For a target at position j, explicit propagation and the corresponding increase to peff both contribute p( a) ∑m □ t= j w ( vt ). These observations give the star- and chain-overlay corollaries. S2.6 Proof of Proposition S2.9

Proof. Because ∆ ≥ |Vi |, h ≥ 1, and every root-to-service arc is eligible, the star with arcs ρi → v for all v ∈ Vi is feasible under (C3)–(C4). In any feasible Hi , write Eq. (S3) as BRnode ( Hi ) = p(ρi ) ∑ w(v) + (i )

v∈Vi

+

∑

∑

∑ w(v) p(v)

v∈Vi

w ( v ) p ( u ).

v∈Vi u∈Anc H (v)\{ρi ,v} i

The last double sum is nonnegative (since w, p ≥ 0) and is identically zero for the star, because Anc(v) = {ρi , v} in a (i )

(i )

star. Therefore, for any feasible Hi , BRnode ( Hi ) ≥ BRnode ( Hi⋆ ), proving optimality. 15

□

S2.7 Proof of Proposition S2.10

Proof. Let n = |Vi | and assume h = 2. For any feasible Hi , define the depth-1 set (children of the root) U = {u ∈ Vi : (ρi → u) ∈ Ai }. By the out-degree bound in (C4), |U | ≤ ∆. Every v ∈ Vi \ U has depth two and therefore has a parent in U. Step 1 (saturating the root degree). Assume n > ∆ and take any feasible Hi with |U | < ∆. Pick any leaf v ∈ Vi \ U and let u ∈ U be its parent. Form Hi′ by replacing the arc u → v with ρi → v. This preserves indegree one for all vertices, increases deg+ (ρi ) by one (still ≤ ∆), decreases deg+ (u) by one, and does not increase depth. Thus Hi′ is feasible. Only the ancestor set of v changes: u is removed from Anc(v), while all other services have the same ancestors. Therefore, the objective decreases by exactly p(u)w(v) ≥ 0. Repeating this promotion until |U | = ∆ shows that some optimum satisfies |U | = ∆ and all remaining nodes have depth two. Step 2 (assignment formulation for fixed hubs). Fix a hub set U ⊆ Vi with |U | = ∆ and define L = Vi \ U. In any depth-two arborescence consistent with U, each leaf v ∈ L chooses a parent u ∈ U and each u may have at most ∆ children. Let xuv ∈ {0, 1} indicate whether v attaches to u. Then each v ∈ L has exactly one parent (∑u∈U xuv = 1) and each hub satisfies the degree constraint (∑v∈ L xuv ≤ ∆). For such a structure, hub nodes have ancestors {ρi , u}, and leaves have ancestors {ρi , u, v}, yielding BRnode ( Hi ) = p(ρi ) ∑ w(v) + (i )

v∈Vi

+

∑ w(v) p(v)

v∈Vi

∑ ∑ p(u)w(v)xuv .

u ∈U v ∈ L

(i )

The first two terms are constant given Vi , so minimizing BRnode over depth-two structures with hub set U is equivalent to the assignment problem in Eq. (S4). Step 3 (greedy optimality). Order hubs so that p(u1 ) ≤ · · · ≤ p(u∆ ) and order leaves so that w(v1 ) ≥ · · · ≥ w(vn−∆ ). We first observe that some optimal solution fills hubs in this order: if some u a has remaining capacity while a leaf v is assigned to ub with p(ub ) > p(u a ), moving v from ub to u a does not increase cost, and decreases it when w(v) > 0. Given this, consider any feasible assignment and any two leaves v, v′ assigned to hubs u a , ub with p(u a ) ≤ p(ub ) while w(v) < w(v′ ). Swapping the parents of v and v′ preserves feasibility (each hub keeps the same number of children) and changes the objective by

p(u a )w(v′ ) + p(ub )w(v) − p(u a )w(v) + p(ub )w(v′ )

= ( p(ub ) − p(u a )) (w(v) − w(v′ )) ≤ 0. Thus repeated exchanges yield an optimal assignment in which larger weights are assigned to smaller-p hubs, which is exactly the stated greedy rule (fill u1 up to capacity ∆ with the largest leaves, then u2 , and so on). Step 4 (exactness for constant ∆). If ∆ is constant, enumerating all (∆n ) = O(n∆ ) hub sets and computing the optimal assignment for each (e.g., by the greedy rule above, or by min-cost flow) yields an exact algorithm in O(n∆ poly(n)) time. □ S2.8 Proof of Proposition S2.4

Proof. In a star, each service contributes the assignment-dependent unary term w(v) p(ρ D(v) ). The latency term supplies the pairwise disagreement costs displayed in the proposition. This is the stated Potts objective. For a fixed anchored instance, let each bag table contain one entry for every assignment of its vertices to [k]. An entry stores the minimum cost in the processed subgraph conditional on that bag assignment, with each unary and pairwise term charged when its last required vertex is processed. Introduce, forget, and join transitions preserve this invariant, while anchor violations receive infinite cost. A bag contains at most τ + 1 vertices, so it has at most kτ +1 entries, and each transition takes O(kτ +1 ) time. The O(n) bags therefore give total time O(nkτ +1 ). Hard unary constraints fix anchor ti to label i, so every feasible assignment uses all k labels. Conversely, every assignment satisfying (C1) contains at least one ordered tuple of representatives (t1 , . . . , tk ) with D (ti ) = i. Taking the minimum over all (n)k tuples therefore recovers the exact (C1) optimum and gives the stated runtime. □ S2.9 Proof of Corollary S2.6

Proof. Take any tree decomposition of the underlying undirected graph G with bags { Bt } of size at most τ + 1. For each original vertex v, let Sv denote its refined principal set with |Sv | ≤ s. Replace each bag by Bt′ =

[

Sv .

v∈ Bt

Every refined edge lies within some bag Bt′ because its endpoints come from the refined endpoints of an original edge whose endpoints co-occur in some bag of the original decomposition. The connectedness condition for each refined 16

vertex follows from the connectedness condition for its parent vertex v. Hence { Bt′ } is a valid tree decomposition of the refined graph G ′ . Each refined bag has size at most s(τ + 1), so tw( G ′ ) ≤ s(τ + 1) − 1. Applying Proposition S2.4 to G ′ yields the stated runtime bound O(|V ′ | ks(τ +1) ). □ S3 ALTERNATIVE RISK SUMMARIES

For any set X of compromise points, define its deterministic total impact by k

BR( X, D, { Hi }) = ∑

∑

w ( v ).

i =1 v∈Reach H ( X ∩(Vi ∪{ρi })) i

The worst-case single-compromise impact is BRmax ( D, { Hi }) = max BR({ x }, D, { Hi }), x

When only domain-root compromise is retained, the issuer summary is BRissuer ( D ) = ∑ p(ρi ) i

∑

w ( v ).

v:D (v)=i

If root risks are equal, this expectation is constant in D. Segmentation then appears in worst-case or heterogeneous-risk summaries. S4 SUPPORTING EVALUATION DIAGNOSTICS

This supplement reports experimental settings, calibration data, solver-quality diagnostics, workload variants, and explicit-propagation checks supporting the evaluation. S4.1 Evaluation protocol

Candidate designs come from local search over normalized risk–latency tradeoffs and from deterministic traffic partitions. Each study states its scalarization grid. The principal trace replay uses nine equally spaced α values on [0, 1]. The reference scales are the all-crossing latency L0 and total impact R0 . For each latency budget, budget-constrained moves and swaps refine every feasible candidate before the minimum-blast-radius design is selected. All runs use fixed computational budgets. Replay experiments assume complete within-domain derivation eligibility, use (∆, h) = (3, 3), and visit only nonempty partitions that satisfy the domain-size capacity bound implied by (C3)–(C4). Within each domain, services are ordered by p(v)/w(v) and attached in that order to the earliest parent with remaining fanout, proceeding breadth first to depth h. Each partition is therefore scored with one deterministic feasible derivation family. Optimization over all admissible intra-domain arborescences lies outside these experiments. The replay experiments set ℓuv = 1, enumerate k ∈ {1, . . . , 6}, set all domain-root compromise priors to zero, and apply no fixed per-domain management charge. The upper limit on k is a common computational planning cap, not a value inferred from latency or the derivation-capacity bound. A row selecting k = 6 is therefore right-censored at the largest tested count. Across the replay text and tables, BR abbreviates the conservative BRnode score, and BR0 denotes its k = 1 value under the same workload, risk setting, derivation method, and feasibility filter. Synthetic selections are generated from fixed seeds and pinned NumPy dependencies. The generation scripts record a SHA-256 manifest for the resulting outputs. Reported wall-clock measurements were collected on spark (aarch64) using Python 3.13.14 and NumPy 2.5.2. Each study states its specific settings alongside its results. S4.2 Q1: Solver validity and transfer

The exact coupling ablation in Table 2 fixes n = 9 and k = 3, then evaluates 20 clustered-graph seeds under the heterogeneous-baseline (H) and cluster-skew (S) risk settings at latency budgets B ∈ {0.20, 0.30, 0.40} ms. For each feasible assignment, the reference computes both the direct-issuance score and the chain or depth-two score. The staged baseline minimizes the direct-issuance score under B and then selects the smallest chain or depth-two score among all tied optima. Each seed assigns the three domain labels deterministic heterogeneous root priors drawn uniformly from [0.01, 0.07). These priors remain fixed across assignments, budgets, and the H and S risk settings. This favorable tie rule isolates the loss caused by choosing boundaries under the simpler issuance structure. The two-domain transfer test uses clustered synthetic graphs with n ∈ {20, 40} and seeds 0–5. Each instance is evaluated at 11 equally spaced α values. The grid method solves every value independently. The adaptive supportedpoint sweep starts from α = 0 and 1, then adds exact solves only where the current solutions imply another supported tradeoff. Both methods solve the same scalarized two-domain direct-issuance problem with nonempty domains and no fixed anchors. The recursion may omit tied designs on a collinear supported segment, so the comparison checks objective equality at the grid values rather than recovery of every tied design. Across the 12 instances, the sweep matched every one of the 132 grid objective values. Depending on n, it required 4.7–5.0 exact solves per instance on average, compared with 11 independent solves for the grid. This solver-call comparison leaves runtime unmeasured and does not cover unsupported hard-budget optima. 17

Mean frontier-search runtime (s)

101

100.5

102

103 Services n

Figure S2: Fixed-schedule frontier search remains within the tens-of-seconds range on the tested sparse family. Increasing n from 50 to 1000 raises mean runtime from 1.95 to 17.03 seconds, a 8.7× increase for 20× more services. Points are means over two seeded instances per size, and bars span the observed minimum and maximum. Fixed restart, scalarization, and iteration limits cap the work, so the curve measures throughput for this schedule rather than worst-case scaling or solution quality. Table S1: Across 60 small-instance and budget combinations, budget repair lowers the miss rate, and adding traffic-based starts eliminates misses in all tested cases. The rows add one search stage at a time. Supported points retain only exact scalarization-supported designs. Scalarized search uses the reduced local-search schedule. Budget repair applies feasible moves and swaps to those candidates. Traffic starts + repair also adds deterministic graph partitions. Miss rate and gap are measured against exhaustive budget optima.

Method Supported points Scalarized search Budget repair Traffic starts + repair

Miss (%) 23.3 51.7 3.3 0.0

Mean gap (%) 1.44 3.74 0.04 0.00

Max gap (%) 18.44 20.31 1.90 0.00

The scaling study uses a clustered synthetic family with n ∈ {50, 100, 200, 500, 1000}, expected average out-degree 12, k ≤ 6, four restarts, α ∈ {0, 0.25, 0.5, 0.75, 1}, at most 250 iterations, and (∆, h) = (6, 3). The scaling-quality check compares the reduced schedule with exhaustive optimization for n ∈ {8, 9, 10}. It matches all 60 small-instance budget optima across five seeds and four latency budgets per size. In a separate exact-chain check on clustered n = 9, k ≤ 4 instances (seeds 0–4), exhaustive enumeration of nonempty partitions and exact chain ordering provides the reference for the budget-refined search. The heuristic and exact solutions choose the same k in both observed miss cases. The remaining failure mode is within-k partition quality under tight budgets, where local search can still leave more budget unused than the exact solution (at B = 0.10, mean slack 0.018 vs. 0.002 ms among misses). The miss at B = 0.60 is a near-tie with a very small objective gap. This supports the surrogate on the tested probability ranges, not under arbitrary dependence or larger priors. Topology alone does not establish semantic eligibility for a formal solver. Central issuance maps to a star, one intermediate layer to depth two, and sequential delegation to a chain. Shared verifier acceptance instead requires explicit propagation. SPIRE documents single-authority, nested-intermediate, and federated layouts, while OAuth 2.0 Token Exchange represents impersonation and delegation chains. [17–19] The two-domain cut additionally requires a binary split, and fixed-anchor results require policy-pinned services. Issuer, trust-bundle, certificate-chain, delegation, Table S2: Optimizing the linear BRnode surrogate produces zero or small regret under the tested independent-event model. Across eight exhaustive n = 9 instances, the largest observed BRexact regret is 1.22%. H denotes the heterogeneous-baseline risk scenario. S additionally triples service priors in the designated cluster. In the second block, every service prior is first tripled. All scaling is clipped at 0.25. Entries report mean ± normal-approximation 95% confidence half-width and maximum regret. B is in ms/request.

B

H scenario

S scenario

Mean regret (%)

Maximum (%)

Mean regret (%)

Maximum (%)

Baseline service priors 0.10 0.00±0.00 0.20 0.00±0.00 0.40 0.00±0.00

0.00 0.00 0.00

0.15±0.30 0.00±0.00 0.03±0.03

1.22 0.00 0.14

All service priors ×3.0 (clipped at 0.25) 0.10 0.00±0.00 0.00 0.20 0.00±0.00 0.00 0.40 0.01±0.02 0.07

0.12±0.16 0.01±0.02 0.00±0.00

0.59 0.09 0.00

18

Table S3: The min-fill heuristic produces tree decompositions of width at most 6 for the tested interaction graphs. Under the configured candidate-generation schedule, exact dynamic programming is faster on five workloads. On Train-Ticket, generating the candidate pool with anchored α-expansion takes 0.09× the exact-DP time. The final column reports this ratio before both methods undergo the same budget-refinement step. It measures the configured schedule rather than isolated solver complexity.

Workload

Min-fill width α-expansion / exact-DP time

Fintech proxy Online Boutique Retail proxy Sample architecture socialNetwork Train-Ticket

3 2 3 4 2 6

1.46× 3.42× 1.98× 1.06× 2.73× 0.09×

Table S4: Local search recovers the exact assignment in 43% of the tested chain cases and reaches a maximum objective gap of 84.30%, despite its lower measured runtime. The exact method enumerates anchor-consistent assignments and applies exact ratio ordering within each domain. The experiment tests an eligible chain family and does not estimate the prevalence of chain delegation.

Method Exact Local

Cases 96 96

Mean gap (%) 0.00 9.36

Max gap (%) 0.00 84.30

Exact assignment (%) 100 43

Time (ms) 2.61 0.07

and verifier metadata can recover these conditions. Service-call traces cannot. Thus, the 6 replay graphs establish interaction-graph widths up to 6, and the standards establish realizability. Deployment prevalence remains unmeasured. The chain regime provides an exact best response and a hardness boundary. It is not treated as a default architecture. Across the 36 heterogeneous-root cases, anchored α-expansion and anchored local search match the exact-DP-seeded budget selection. The homogeneous-root control has zero blast-radius gap for every method because blast radius is partition-invariant under direct issuance. The joint-chain transfer uses six seeded n = 8, k = 3 clustered instances, four fixed-anchor starts per seed, heterogeneous concrete root priors, and α ∈ {0.2, 0.4, 0.6, 0.8}. The exact reference enumerates all labeled assignments consistent with the anchors and applies exact ratio ordering within every domain. The refinement stress test uses scope sizes 2–4 and width caps 4, 6, 8. Table S5: Scoped refinement increases min-fill width and exact bounded-treewidth solver runtime in the tested families. Larger scopes require higher width caps, and scope size four remains solvable only for the tested tree family. “Width ratio” compares refined and base min-fill widths. The last two columns report the smallest tested cap that solves every refined instance for that family and scope, followed by the refined-to-base runtime ratio at that cap. A dash means that no tested cap succeeds.

Graph family

Scope size

Banded Banded Banded Clustered Clustered Clustered Tree Tree Tree

2 3 4 2 3 4 2 3 4

Width ratio 2.50 4.00 5.50 2.50 4.00 5.50 3.00 5.00 7.00

Exact solver at minimum successful cap Width cap

Runtime ratio

6 8 – 6 8 – 4 6 8

67.8× 3992.0× – 60.9× 3539.8× – 9.6× 121.7× 1453.6×

Supplementary Table S5 quantifies Corollary S2.6 and Remark S2.7. Search reliability.: The stability-screen transfer uses four workloads, 20 count resamples, 10 solver seeds, and a reduced schedule of four restarts, five α values, and 250 iterations, compared with a 12 × 9 × 800 reference schedule. We flag the reference-run domain count when its support falls below a chosen threshold under either count resampling or solver-seed variation. The returned candidate set contains that count and any count selected in at least 10% of either perturbation family.

19

Table S6: Stability-screen threshold ablation. At the retained 80% threshold, the screen catches all 6 schedule disagreements, and the returned sets contain the reference count in 5 of those cases. Entries report flagged cases out of all cases, caught disagreements out of all disagreements, remaining disagreements out of unflagged cases, and disagreements for which the returned candidate set contains the reference domain count. Support is measured across count resamples and solver-seed perturbations. The screen is a review rule, not a correctness guarantee.

Support threshold 60% 70% 80% 90%

Flagged cases 8/32 12/32 13/32 20/32

Caught mismatches 5/6 6/6 6/6 6/6

Unflagged mismatches 1/24 0/20 0/19 0/12

Reference-k coverage 5/6 5/6 5/6 5/6

S4.3 Q2: Workload, risk, and crossing-cost effects

Train-ticket instantiation.: The workload uses 1157 unique public Jaeger traces from seven Train-Ticket configurations. [23] Cross-service CHILD OF relations produce a directed parent-to-child call graph. Retaining the largest weakly connected component leaves 32 services and 72 edges. Aggregated edge counts are rescaled to the stated calls per top-level request. Let m(v) be the sum of incoming and outgoing trace-call multiplicities incident to service v, and let mmax = maxv m(v). The planning scenarios set w(v) = 1.4 + 1.6 log(1 + m(v))/ log(1 + mmax ). Let h(v) ∈ [0, 1] be the first 32 bits of the SHA-256 hash of the service name scaled by 232 − 1, let o (v) be its outgoing call count, and let omax = maxv o (v). Let a(v) indicate that the name contains admin, and let q(v) indicate an auth, user, payment, security, or assurance term. The baseline compromise prior is the scenario construction   log(1 + o (v)) clip[0.005,0.08] 0.015 + 0.020h(v) + 0.006a(v) + 0.005q(v) + 0.004 . log(1 + omax )

(b) Best generated domains (k ≤ 6)

(a) Measurement-derived effective cost

6

10

5 1

4 3

0.1 0.03

2 N0

N1 N2 N3 Network path profile B = 0.10 ms latency budget

N4

N0

B = 0.20 ms latency budget

N1 N2 N3 Network path profile

Number of domains

Effective cost (ms/crossing call)

The reported w(v) and p(v) values are rounded to three decimal places and define a reproducible heterogeneous planning scenario. No empirical service-compromise frequencies are used. Role-derived cluster labels affect only the skewed-risk multiplier. Recommendation stability.: Recommendation stability uses 100 multinomial edge-count resamples with fixed solver seeds, separated from 20 solver seeds on the observed edge counts. The shared reference-run value k = 6 is recovered in at least 80% of count resamples and 80% of solver seeds across the two risk scenarios at B = 0.10 ms. The reported k = 6 is right-censored at the tested upper limit. The count experiment perturbs aggregate edge frequencies and does not model within-trace dependence. For the critical-path sensitivity check, we extract the longest-duration root-to-leaf span chain from each of the 1157 traces. For edge (u, v), let suv be the fraction of its observed calls appearing on those chains. Its multiplier is (0.5 + 3suv ) normalized to call-weighted mean one. Reweighting leaves the selected domain count unchanged in all 4 risk–budget rows. At B = 0.10 ms, it raises BR/BR0 from 0.685 to 0.711 under the heterogeneous baseline. Under cluster skew, the ratio rises from 0.743 to 0.780. At B = 0.20 the change is at most 0.011.

N4

Search cap reached (k = 6)

Figure S3: Higher measured crossing costs reduce the number of domains in the best generated Train-Ticket designs. Panel (a) shows the effective mutualauthentication cost of X25519+ML-KEM-768 with ML-DSA-65 across five path profiles. Bars span stored bootstrap 5th to 95th percentile estimates. Panel (b) applies each estimate uniformly to all interaction edges under two boundary-latency budgets. Vertical bars span the selected domain counts across the three cost estimates. N0–N4 denote the path profiles whose round-trip time, rate, and loss appear in Table S7. B is the latency budget in ms/request, and k is the selected number of trust domains. Only N0 at B = 0.10 changes across its interval, from five to six domains. Triangles mark results that reach the k = 6 search cap.

Named PQC calibration.: The measurement matrix contains 12000 observations from 4 randomized blocks per condition on an ARM64 host using OpenSSL 3.6.3. C0 uses X25519 with ECDSA-P256 authentication, K1 uses hybrid X25519+ML-KEM-768 with ECDSA-P256 authentication, and A1 uses hybrid X25519+ML-KEM-768 with ML-DSA-65 20

authentication. Each profile is measured with fresh and resumed sessions under server-only and mutual authentication across the five network paths in Table S7. The displayed effective costs use mutual authentication, 20 requests per connection, and a 0.05 full-handshake probability. The architecture replay separately assumes 20 calls per top-level request. Table S7: For A1, the measured crossing-cost range across network paths exceeds the largest within-path spread among C0, K1, and A1. In the center-estimate A1 replay, the two lower-cost paths select more domains than the three higher-cost paths at both budgets. C0 uses X25519 with ECDSA-P256 authentication. K1 uses hybrid X25519+ML-KEM-768 key exchange with ECDSA-P256 authentication. A1 uses the same hybrid key exchange with ML-DSA-65 authentication. RTT is round-trip time, and a dash in the rate column denotes an unshaped path. B is the latency budget in ms/request. Design cells report the conservative risk ratio BRnode /BR0 , normalized to the single-domain baseline BR0 , with the selected trust-domain count k in parentheses. N0 is the unshaped local path. Across the stored bootstrap estimates, only N0 at B = 0.10 changes, from five to six domains. A reported k = 6 reaches the search cap.

Path

Network conditions RTT (ms) Rate (Mbit/s)

N0 N1 N2 N3 N4

0 1 35 70 200

Crossing cost (ms/crossing call)

A1 design: BR/BR0 (k)

Loss (%)

C0

K1

A1

B = 0.10

B = 0.20

0 0 0.1 1 3

0.0209 0.0678 1.8809 3.9460 13.3346

0.0194 0.0726 1.8230 3.6150 14.5419

0.0338 0.0814 1.9756 4.1041 15.5815

0.683 (5) 0.722 (6) 0.944 (2) 0.968 (2) 0.968 (2)

0.619 (6) 0.662 (6) 0.925 (4) 0.944 (2) 0.968 (2)

– 1000 100 20 1

The architecture replay applies each profile/path coefficient uniformly to all interaction edges. Absolute profile costs represent the full measured crossing cost. Incremental costs represent migration headroom relative to C0. The profiles are deployment calibration inputs rather than comparative algorithm benchmarks. Their mean effective costs are not end-to-end tail-latency guarantees. Table S8: Across the ten path–budget cells, center-estimate C0, K1, and A1 costs select the same domain count in eight cells. Incremental A1-minus-C0 costs select more domains than absolute A1 costs in six cells. The comparison uses Train-Ticket and the fixed bounded breadth-first derivation family. C0 uses X25519 with ECDSA-P256 authentication. K1 adds ML-KEM-768 to the key exchange, and A1 also uses ML-DSA-65 authentication. The ∆A1 column uses cA1 − cC0 as the per-crossing migration cost. N0–N4 denote the path profiles listed by round-trip time, rate, and loss in Table S7. B is the latency budget in ms/request. Each design cell reports the selected trust-domain count k followed by the conservative risk ratio BRnode /BR0 , normalized to the single-domain baseline BR0 . All columns use the same optimizer schedule. A reported k = 6 reaches the search cap.

Path profile Budget B N0 N1 N2 N3 N4

0.10 0.20 0.10 0.20 0.10 0.20 0.10 0.20 0.10 0.20

C0

K1

A1

∆A1

6 / 0.657 6 / 0.610 6 / 0.704 6 / 0.662 2 / 0.944 3 / 0.904 2 / 0.968 2 / 0.944 2 / 0.968 2 / 0.968

6 / 0.630 6 / 0.607 6 / 0.704 6 / 0.673 2 / 0.944 3 / 0.904 2 / 0.968 2 / 0.944 2 / 0.968 2 / 0.968

5 / 0.683 6 / 0.619 6 / 0.722 6 / 0.662 2 / 0.944 4 / 0.925 2 / 0.968 2 / 0.944 2 / 0.968 2 / 0.968

6 / 0.614 6 / 0.608 6 / 0.613 6 / 0.606 6 / 0.722 6 / 0.687 5 / 0.783 6 / 0.722 2 / 0.944 4 / 0.925

Held-out graph replay.: For A1, five independent N0 runs and five independent N2 runs measure every Train-Ticket edge and session mode in 20 calibration trials, optimize at B ∈ {0.10, 0.20} ms, and then remeasure only the selected crossing edges in 10 held-out trials. Budget compliance is determined from the separately observed boundary latency. Without a reserve, the edge-specific block maxima pass every N0 check and 8 of the 10 N2 checks. The graph block maximum passes 7 of the 10 N0 checks and every N2 check. With a 5% budget reserve, each rule passes all 20 path–budget checks. These checks support the reserve for the tested paths and budgets. Deployment therefore remains iterative: calibrate, optimize, remeasure the selected crossings, reject violations, and update costs or reserve before rerunning. S4.4 Q3: Explicit shared-issuer rescoring

In the induced Train-Ticket cases, every generated candidate is evaluated with explicit issuer reachability to provide the reference. The additive score and a reachability-aware proxy are then compared as candidate-ranking rules. The J → peff reduction is exact under the antichain condition. When accepted services have overlapping descendant sets, the additive score remains an upper bound and final selection uses explicit evaluation. Across the induced comparisons, the additive score identifies the best explicitly evaluated candidate in 11 of 12 cases and misses by at most 5.86%. Evaluating the three candidates ranked highest by the reachability-aware proxy recovers the best generated candidate in all 12 cases. The reported gaps are relative to the explicit best among generated candidates under the same budget. Global optimality lies outside this comparison.

21

S5 DEPLOYMENT CONSIDERATIONS

The model isolates credential authority (who can mint or derive which identities) as the mechanism that determines blastradius propagation under compromise. The deployment class treats each trust domain as a key-establishment domain rooted in a common issuer or key-management authority. After establishment, intra-domain payload interactions use symmetric protection or already-issued delegated credentials. Communication between independently rooted domains invokes public-key authentication or key establishment. Deployments can add structure around that core through scoped credentials (role-based access control (RBAC) or attribute-based access control (ABAC)), policy-gated reachability, and finite compromise windows due to detection and rotation. These effects can be represented as refinements without changing the cut-and-reachability structure. S5.1 Network segmentation vs. trust domains

A recurring deployment mistake is to equate network segmentation with cryptographic trust segmentation. Network segmentation and trust domains describe different objects. The model keeps them separate: • the interaction graph G records which services communicate and therefore where latency-relevant crossings can occur, • the domain assignment D records which services share a cryptographic trust boundary, and • the derivation graphs Hi record how compromise propagates once an issuer, root, or delegated credential source is lost. This distinction matters even on a tiny topology such as client → gateway → orders → payments → ledger, with an auxiliary issuer auth. Several readings of the same service graph are possible: • Gateway TLS only / collapsed internal segment. TLS terminates at the gateway and internal services share one credential root or one implicit trusted segment. This yields low boundary latency. The internal segment behaves like one collapsed trust domain. • Gateway plus isolated issuer. The runtime topology is unchanged. Placing auth in its own trust domain prevents compromise of an internal service from automatically granting the issuer’s authority. This adds a boundary crossing and can reduce blast radius. • Per-service identities / service-to-service mutual TLS (mTLS). Distinct service identities under one accepted trust bundle do not by themselves create distinct trust domains: compromise of their common authority retains shared minting power. Per-service trust domains require independently rooted credential systems, with cross-root authentication or key establishment on service interactions. This can reduce root-compromise reach while increasing boundary latency. A VLAN, subnet, or gateway boundary should not be collapsed into one black-box node when the analysis target is credential blast radius. Even if network topology is unchanged, moving a trust root or changing which services share an issuer can change propagation sharply. JSON Web Token (JWT) issuer systems make this distinction explicit. The service-interaction graph may remain unchanged. Acceptance of one issuer by multiple services makes that issuer a shared propagation root regardless of network segmentation. Sec. 8 distinguishes restricted one-target-per-domain overlays, which admit the additive peff chain reduction, from multiple accepted targets inside one domain, which require explicit scoring. S5.2 Extracting derivation structure from control-plane data

For deployment, reconstruct Hi from identity and key-management control planes rather than from network traces alone. Audited control planes can expose the dominant trust roots and delegation layers. Useful sources include service meshes, workload-identity systems, JWT/OIDC issuer configuration, and managed certificate authority (CA) or key management system (KMS) platforms. In legacy or mixed-vendor environments, an exact reconstruction may be unavailable. Evaluate a small set of plausible Hi candidates instead. These control-plane sources map to the model as follows: • SPIFFE/SPIRE, service-mesh CA, workload identity. Determine which workloads receive identities from each trust bundle or issuer and whether namespace- or cluster-level subissuers exist. This fixes roots, initial domain membership, and root-to-workload issuance edges. A star is appropriate when workloads receive credentials directly from a root. A depth-two approximation is appropriate when the control plane contains one intermediate issuer layer. • JWT/OIDC issuer and verifier configuration. Use issuer, audience, and scope configuration to determine which services accept each issuer and whether a token-minting service is a shared propagation root. Restricted one-targetper-domain overlays admit the additive peff chain reduction. Multiple accepted targets inside one domain require explicit scoring. 22

• CA/KMS and hardware security module (HSM) inventory and signing-service metadata. Use key-custody and signing metadata to identify who signs for whom and whether intermediate or tenant issuers exist. This determines derivation edges and whether a star, chain, or depth-two abstraction is appropriate. • Authorization and mesh policy. Remove interactions or delegation edges that cannot be exercised. This gates both E and Hi before optimization. • RBAC and administrative scopes. Use privileged-role inventories to decide which services should be split into scoped principals with separate w and p values. The extraction sequence is to inventory dominant roots, map issuance or delegation edges, intersect them with verifier-acceptance and policy data, and collapse the result to the coarsest defensible planning abstraction before optimization. Audited control planes support a direct reconstruction. Legacy systems require sensitivity analysis across plausible Hi and J families. S5.3 Practitioner instantiation checklist

This checklist maps common observability and security tooling to model inputs. Deployment-specific estimation is still required. 1. Services/principals (V). Decide the granularity: services only, or also explicit issuers/verifiers, sidecars, and gateways if they hold independent credentials. 2. Interaction edges and rates (E, ruv ). Use distributed tracing, such as OpenTelemetry or Jaeger, to extract a directed call graph and per-edge call counts or rates. When interpreting Lat( D ) as milliseconds per request, normalize these values to calls per top-level request. If cpqc is a raw per-event cost, convert the call rates to event-equivalent rates using the observed reuse and reauthentication policy. Do not apply this conversion when the cost is already amortized per interaction. Request classes or critical-path labels may provide additional edge weights. 3. Latency sensitivity (ℓuv ). Start with ℓuv = 1. Refine using path criticality (edges on paths critical to a service-level objective (SLO)), slack within traced request dependency graphs, or downstream fanout/queuing sensitivity when available. 4. Crossing cost (cpqc (u, v)). Microbenchmark the deployed cross-root key-establishment or authentication stack on representative hardware. Represent protocol amortization through either event-equivalent rates or effective per-interaction costs, not both. cold ccold . Here cwarm is the reusedTo model session state, estimate a cold/warm mixture ceff (u, v) = cwarm + Puv uv uv uv cold session cost, ccold uv is the additional setup penalty, and Puv is inferred from telemetry. Relevant factors include connection lifetime, request limits, stream limits, idle timeouts, and burst fanout.

5. Criticality weights (w(v)). Choose weights from business or mission impact or data sensitivity (e.g., assign greater weight to services handling personally identifiable information (PII) or payments). Normalize so ∑v w(v) is interpretable. 6. Compromise probabilities (p T ( x )). Pick an explicit planning horizon T (e.g., expected detection/rotation window) and set p T ( x ) via exposure tiers or a hazard model. Represent uncertainty with intervals and design against upper endpoints. 7. Policy gating. If service-mesh authorization (mTLS + policy) or network reachability forbids some interactions, gate them by removing edges from E (or setting ruv ℓuv = 0). Similarly, remove derivation edges that cannot be exercised operationally. 8. Scoped credentials (vertex refinement). If a service holds multiple identities (e.g., normal service vs. admin/minting), split v into scoped principals (v, s), allocate weights/priors per scope, and distribute each base edge’s traffic across scoped edges according to which scopes are exercised. 9. Derivation constraints (Aallow , ∆, h). Extract eligible derivation arcs from issuer policy and credential-control-plane metadata. Set fanout and depth from the intended key-management mechanism. Treat the remaining coupled optimization as a design-space search under these constraints. The same graph optimizer can be retained by refining the linear edge coefficients by request class: Latmean ( D ) =

∑

(u,v)∈ E

cold 1[ D (u) ̸= D (v)] ∑ ωq nuv,q τuv,q + Puv,q κuv,q . q∈Q

23

(S5)

Here nuv,q is traced use of edge (u, v) under request class q, ωq is a class weight, τuv,q is the warm crossing cost, and κuv,q is the additional cold-setup penalty. These quantities are combined into weighted graph edges instead of being optimized over as a separate request-level directed acyclic graph (DAG) model. Handshake flights, certificate growth, session reuse, retry behavior, and path limits enter through the calibrated edge coefficients and cold/warm mixture above. Explicit protocol state machines, packet failure probabilities, and request-level precedence are outside the graph formulation. S5.4 Operational refinements

Scoped principals.: Services may hold credentials with different scopes, use rates, and risk. Represent them by replacing each base vertex v ∈ V with scoped principals Sv and forming V ′ = {(v, s) : v ∈ V, s ∈ Sv }. Assign w′ (v, s) and p′ (v, s) per scope, then distribute each base edge’s traffic among scoped edges while preserving its total weight. Latency still depends only on whether an edge crosses domains, so the same procedures apply to (V ′ , E′ ). Constantsize refinement multiplies instance size by |S| and preserves bounded-treewidth tractability under direct issuance by a standard bag-expansion argument. Refinement can isolate highly privileged principals behind stricter boundaries or separate issuers at low latency cost when their interaction rate is small. Policy gating and reachability.: Policy and network reachability determine which interactions can occur. Remove disallowed interactions from E, set ruv ℓuv = 0, or replace G with an effective interaction graph Geff derived from reachability and authorization policy. If compromise of x cannot exercise a derivation edge, remove that edge from the modeled relation or reduce its effective compromise probability. The resulting model remains a cut-and-reachability problem with policy-conditioned graphs. Finite compromise windows.: Our compromise probabilities p( x ) are marginals over a planning horizon. To make that horizon explicit, one can parameterize p T ( x ) by an exposure window T (e.g., mean time to detect/rotate), using a simple hazard model such as p T ( x ) = 1 − exp(−λ x T ). Uncertainty in λ x or T can be handled with interval bounds and robust design as in Supplementary Corollary S2.2, yielding worst-case containment guarantees over plausible deployment regimes.

24