Certifying Hidden Paths: Scalable Topology Assurance for QKD Networks

1 Introduction

• Customers need assurance that a certified path meets node, link, and hop requirements, but private QKD customers cannot be expected to access the provider’s topology.An independent auditor may certify the infrastructure, while the provider answers requests without disclosing the audited graph.Source: §1 · pp. 1–2

1.1 Our Contributions

• The construction certifies nodes and edges independently, so proof size and cryptographic work for a selected route depend on that route rather than the full network.Certification storage and route discovery remain graph-dependent, and graph updates require explicit epoch management.Source: §1.1 · p. 2
• Dedicated padding loops hide actual path length without requiring a maximum fixed at certification; proof cost depends on the padding chosen for each presentation.The padding extension can also be combined with proofs of several hidden node-disjoint paths.Source: §1.1 · p. 2

1.2 Technical Overview

• A provider proves knowledge of signatures for a valid path whose adjacent node and edge identifiers match, while the proof hides the route and its actual length.A shorter route is padded by repeating its destination node using a certified self-loop until it reaches the public number of node positions.Source: §1.2 · p. 3

1.3 Related Work

• Prior topology-hiding QKD approaches have graph-size-dependent costs, while this work builds assurance from independently authenticated graph components.The related-work discussion distinguishes a-priori assurance of path existence from a-posteriori validation of a path already used for transmission.Source: §1.3 · pp. 3–4

2.1 Notation

• The notation distinguishes the network graph from the pairing groups and separates public presentation inputs from the prover’s private route witness.The witness contains certified route components and signatures; endpoints, policies, a padded-length bound, and request context are public.Source: §2.1 · p. 4

2.2 Cryptographic Building Blocks

• Multi-message signatures authenticate node and edge vectors, while non-interactive zero-knowledge proofs let the provider show that the components form a valid route without disclosing it.The signed vectors include graph identifiers and a fresh graph-wide binding tag, as well as node or edge identifiers and attributes.Source: §2.2 · p. 5
• The proof context is bound to the statement and proof and can be used to ensure freshness; the public request remains visible while the route witness stays hidden.For a fixed request, the proof should not disclose which certified route supplied its witness.Source: §2.2 · p. 5
• Unforgeability relies on signature security, while the reduction also needs fresh-statement weak simulation extractability to recover a valid witness after simulated presentation replies.Ordinary soundness or zero knowledge alone does not provide the extractability used in that reduction.Source: §2.2 · pp. 5–6

3 Syntax and Security Model

• The scheme formalizes an accepting token as evidence of a certified compliant route, while hiding the selected route and internal topology beyond the public request.The graph identifier designates the audited graph or epoch, and public predicates test node and edge attributes.Source: §3 · p. 6

3.1 Syntax

• Six algorithms cover parameter and key generation, issuance, certificate validation, presentation, and verification; verification needs neither the graph nor the route.Correctness requires honest certificates and tokens for feasible requests to pass, except with negligible probability; context binds a token to a request but does not supply freshness.Source: §3.1 · p. 6
• The public bound ℓ fixes padded witness positions, while issuer-certified destination loops conceal the actual route length.A real route uses at most ℓ−1 genuine edges, and padding loops are exempt from the genuine-link predicate.Source: §3.1 · p. 6

3.2 Security Model

• Unforgeability requires that a valid presentation cannot be produced for an unqueried request unless a corrupted certificate satisfies its route requirements.The adversary may obtain credentials on chosen graphs and request presentations from uncorrupted certificates.Source: §3.2 · p. 7
• Graph hiding compares challenge presentations for two valid candidate graphs under the same public request, testing whether the token reveals which certified witness was used.The public request deliberately exposes endpoints, policies, graph identifier, bound, and context; equal padding bounds avoid exposing route length through witness shape.Source: §3.2 · p. 8

4 Topology Certification from Multi-Message Signatures

• Independent signatures on nodes and directed edges support a zero-knowledge proof that selected signed components form a route, without revealing the graph to the verifier.The issuer certifies the complete graph once; the provider later proves a customer-specific path statement.Source: §4 · p. 8

4.1 A Generic Construction

• A shared random binding tag ties signed components to one certification run, while edge signatures bind ordered endpoint identifiers.The issuer rejects malformed graphs and adds destination loops with a special attribute tuple for padding.Source: §4.1 · pp. 9–10, §4 · p. 9
• Exactly ℓ node-signature checks and ℓ−1 edge-signature checks make proof-core work depend on padded route positions and attributes, not total network size.Issuing signatures and discovering a route still depend on graph size and structure; padding hides the number of genuine edges beneath ℓ.Source: §4.1 · pp. 10–11

4.2 Security of the Generic Construction

• Unforgeability follows if node and edge signatures are EUF-CMA secure and the proof system is zero-knowledge and fresh-statement weakly simulation extractable.Graph hiding follows if the non-interactive proof system is zero-knowledge.Source: §4.2 · p. 11

4.3 BBS Signatures and Composed Proofs

• The BBS instantiation uses separately keyed multi-message signatures and linked Schnorr-style proofs to hide signatures while checking route components and predicates.An OR proof handles each edge’s genuine-policy or padding branch, under the stated proof-system assumptions and in the random-oracle model for the Fiat–Shamir argument.Source: §4.3 · pp. 11–12

4.4 Extensions

• For node-disjoint routes, context-specific pseudonyms let a verifier detect shared intermediate nodes without learning their identifiers.Repeated destination occurrences used for padding must be excluded from the comparison.Source: §4.4 · p. 12
• Within a graph epoch, new nodes or links can be certified without resigning unchanged components, while removals require a fresh epoch; component identifiers also enable constant-size non-connectivity proofs.Merging components requires re-certifying affected nodes.Source: §4.4 · pp. 12–13

5 Evaluation

• The evaluation measures certificate size, presentation size, and presentation runtime, but excludes route discovery and other graph-management operations.Those operations may depend on the size and structure of the underlying QKD network.Source: §5 · p. 13

5.1 Certificate Size

• The certificate transformation yields 2|V| + 2|E| graph objects, and BBS signatures alone account for 160(|V|+|E|) bytes.The estimate excludes message vectors, graph data, encoding overhead, and the binding tag; issuance, validation, and route search can scale with |V| + |E|.Source: §5.1 · p. 13

5.2 Presentation Size

• At fixed ℓ, n, m, and predicates, cryptographic presentation size is independent of graph size; disclosure-rate effects vary with the relative node and edge attribute counts.The evaluation uses equality-based predicates as a representative policy class, with disclosure rates denoting attributes constrained to public values.Source: §5.2 · pp. 13–14, §5 · p. 13
• Below 300 KiB, presentation size remains practical at ℓ = m = n = 50, the largest parameter setting considered.Table 1 covers presentation sizes across path lengths, attribute dimensions, and disclosure rates.Source: §5.2 · p. 14, Table 1 · p. 14

5.3 Runtime

• At m = n = 8, increasing ℓ from 2 to 64 raises generation from 7.2 to 353 ms and verification from 8.5 to 275 ms.The authors attribute approximately linear growth to constant proof work added at each position.Source: §5.3 · p. 15, Figure 3 · p. 15
• At ℓ = 32, increasing m = n from 2 to 16 raises generation from 136 to 217 ms and verification from 113 to 174 ms.The experiments use 50% disclosure and show roughly linear hidden-attribute proof work.Source: §5.3 · p. 15, Figure 4 · p. 15

6 Conclusions

• Providers can prove that a policy-compliant route exists without revealing the route in an individual presentation.Presentation size and cryptographic proof work for a selected route depend on that route, while certificate storage and route discovery remain graph-dependent.Source: §6 · p. 15
• The construction also supports hidden path lengths and sketches extensions to node-disjoint multi-path and non-connectivity proofs.Updates require explicit epoch management.Source: §6 · p. 15
• Future work includes an efficient post-quantum instantiation and end-to-end integration with practical QKD management and path selection.The integration should include an independently enforced binding between the proved existence statement and the route actually used for key material.Source: §6 · p. 15

A Formal Proof-System Security Games

• The formal security-game section expands the five definitions from Section 2.2 with algorithms, correctness conditions, and security games.It uses the notation of Section 2.1.Source: A Formal Proof-System Security Games · p. 17

A.1 Cryptographic Building Blocks

• A multi-message signature authenticates a vector of messages so a verifier can check that the signer issued a signature on exactly that vector.The scheme is defined by parameter generation, key generation, signing, and verification algorithms.Source: Multi-message signatures · p. 18
• Signature verification takes a verification key, message vector, and signature, and returns 1 exactly when the signature is valid on that vector.Correctness requires honestly generated signatures to verify; EUF-CMA security rules out efficient production of a valid signature on a message vector never signed before.Source: Multi-message signatures · p. 18
• A non-interactive zero-knowledge proof lets a prover establish that a statement belongs to a language without revealing its witness.For path presentations, the public statement includes the complete request and context.Source: Non-Interactive Zero-Knowledge Proofs · p. 18
• The defined NIZK proof system comprises PPT parameter-generation, proving, and verification algorithms; for every (x,w) with R(x,w)=1, correctness requires honestly generated proofs to verify correctly.Source: Non-Interactive Zero-Knowledge Proofs · pp. 18–19
• Fresh-statement weak simulation extractability requires an extractor to recover a witness from an accepting proof of a statement not previously simulated.The extractor may rewind the adversary and use its random tape, random-oracle transcript, and proof-simulation transcript; the construction's unforgeability game makes the final statement fresh.Source: Non-Interactive Zero-Knowledge Proofs · p. 19

B Full Proofs of the Generic Construction

• The generic proofs establish the stated theorems, while the concrete BBS/Schnorr proof core separately requires proof that its full composition satisfies the assumed extractability property.The concrete instantiation uses BBS multi-message signatures, Schnorr-based zero-knowledge proofs with Fiat-Shamir, and efficient Schnorr OR proofs.Source: B Full Proofs of the Generic… · p. 20, C Full Concrete Instantiation · p. 22

B.1 Unforgeability

• A successful generic-construction forgery yields either a violation of fresh-statement weak simulation extractability or EUF-CMA security of a deployed multi-message signature scheme.Extraction recovers the binding tag, node and edge signatures and attributes, and identifiers needed to satisfy the path relation; the proof then uses cases for fresh, uncorrupted, and corrupted tags.Source: §B.1 · pp. 20–21

B.2 Graph Hiding

• The resulting π′ is independent of challenge bit b and the certificate, graph, signatures, binding tag, and node and edge attributes selected by b; therefore, the adversary guesses b correctly with probability exactly 1/2.Source: §B.2 · p. 22

C.1 BBS Signatures

• The BBS multi-message signature scheme is EUF-CMA secure under the q-strong Diffie-Hellman assumption in the underlying bilinear groups.The cited proof of this lemma is in.Source: §C.1 · p. 23

C.2 Schnorr-based Zero-knowledge Proofs for BBS Signatures

• The presentation proof demonstrates possession of a valid BBS signature without revealing the signature or its signed messages, and can combine with zero-knowledge arguments that the hidden messages satisfy a public policy.The proof relation pairs signature validity with satisfaction of the policy.Source: §C.2 · p. 23
• The policy is an efficiently decidable predicate on the signed message vector, and the proof relation requires both signature verification and policy satisfaction.The Schnorr representation protocol is special honest-verifier zero knowledge.Source: §C.2 · p. 23
• The prover forms a Fiat-Shamir proof from randomized signature elements and a representation witness, then combines standard Schnorr proofs with policy proofs.The policy-proof techniques are assumed special honest-verifier zero knowledge and special sound; verification checks the pairing equation and verifies the policy proof.Source: §C.2 · p. 24
• An extracted Schnorr representation witness, together with the verifier's pairing equation, reconstructs a valid BBS signature except with negligible probability under the corresponding discrete-logarithm representation assumptions.AND composition with other special-sound protocols preserves special soundness.Source: §C.2 · p. 24

C.3 Efficient OR Composition of Zero-Knowledge Proofs

• The OR prover executes the Σ-protocol for a branch with a known witness and simulates an accepting transcript for the other branch.The branch challenges combine into a common Fiat-Shamir challenge, with the real branch's challenge determined from it.Source: §C.3 · pp. 25–26
• The standard OR composition is special sound when both underlying Σ-protocols are special sound.The complete interactive presentation protocol inherits special soundness when its Schnorr representation and supported-policy protocols are special sound.Source: §C.3 · p. 26
• For a valid certified edge, branch exclusivity ensures that the complete path relation interprets it as either a policy-compliant genuine edge or an issuer-added padding loop.The exclusivity is not needed for special soundness of the OR protocol itself.Source: §C.3 · p. 26
• If the complete interactive presentation protocol is special sound and special honest-verifier zero knowledge with challenge space Zp, its Fiat-Shamir transform is zero knowledge and fresh-statement weakly simulation extractable in the random-oracle model.Extraction applies to an accepting proof for a statement not previously submitted to the proof simulator.Source: §C.3 · pp. 26–27

• A shared intermediate repeater can compromise key material on multiple paths, so the relevant condition is node-disjointness, not merely link-disjointness.With t-out-of-t secret sharing, an adversary must compromise at least one node on every path; link-disjoint routes can still share a central repeater.Source: §D.1 · p. 27
• Stable per-node secrets yield context-specific pseudonyms, letting verifiers check that paths share no intermediate nodes without learning their identities.The same secret is assigned to a node throughout a graph epoch; proofs establish that each pseudonym derives from its certified secret.Source: §D.1 · pp. 27–28
• For padded paths, each position after the first is proved either to repeat the previous node or to be a genuine policy-compliant node with a valid pseudonym.A padding occurrence can use a random group element instead of a pseudonym, preventing repeated padding from falsely appearing to violate disjointness.Source: §D.1 · p. 28
• Padded-path support costs substantially more: a straightforward OR proof can make the node-related proof cost approach twice that of the unpadded construction.The overhead depends on the proof system and whether common subrelations can be shared between branches.Source: §D.1 · p. 28

• New nodes or edges can be added without re-certifying the entire graph, supporting monotonic growth of certified networks.Source: §D.2 · p. 28
• The issuer adds new components by signing them under the existing graph identifier and binding tag with their node or edge identifiers and attributes.Source: §D.2 · p. 28
• Removing certified nodes or edges requires the graph to be certified again, unlike monotonic additions.Source: §D.2 · p. 28

D.3 Proving Non-Connectivity

• Non-connectivity can be proved by showing valid signatures for both nodes and proving their certified component identifiers differ.The proof requires only an inequality proof over two certified attributes, with constant-size overhead independent of graph size.Source: §D.3 · p. 28
• Adding an edge between previously disconnected components merges them and requires affected nodes to be re-certified with a common component identifier.Source: §D.3 · p. 28

E On the Use of Generative AI

• The manuscript reports using GPT-5 and GPT-6 ChatGPT models for language editing, consistency checks, and discussion of selected technical arguments; authors independently verified incorporated suggestions.The tools were not treated as authoritative sources, and the authors take responsibility for the research and final technical results.Source: E On the Use of Generative AI · p. 29