Integrity from Algebraic Manipulation Detection in Trusted-Repeater QKD Networks

Technical Summary: Integrity from Algebraic Manipulation Detection in Trusted-Repeater QKD Networks

1. Problem Statement

Quantum Key Distribution (QKD) enables secure communication without computational assumptions but is currently limited to short distances due to hardware constraints. To extend QKD over long distances, trusted-repeater networks are employed, where QKD links exist between neighboring nodes, and messages are forwarded via a relay protocol (decrypt-re-encrypt) between non-neighboring nodes.

While these networks are being deployed, a critical security gap exists: no existing protocol provides provable guarantees of integrity against manipulation by both external adversaries and corrupted intermediate nodes.

• Confidentiality is often achieved via multi-path relaying and secret sharing (e.g., splitting a secret into shares sent over disjoint paths), ensuring that an adversary must corrupt a "qualified" set of paths to learn the secret.
• Integrity (the ability to detect if a message has been tampered with) is lacking. Existing solutions, such as the SECOQC protocol, rely on Message Authentication Codes (MACs) that require pre-shared identical keys, leading to circular reasoning. Other approaches using hash functions or checksums fail to provide security against computationally unbounded adversaries or rely on unproven assumptions.

The core challenge is to design a protocol that ensures Information-Theoretic Security (ITS) for integrity in a setting where intermediate nodes are trusted only to forward data but may be corrupted, and where the adversary has full control over the network topology and communication.

2. Methodology

The authors propose a protocol that combines Algebraic Manipulation Detection (AMD) codes with multi-path relaying over trusted repeater networks.

Core Components:

1. Secret Sharing: The sender (Alice) splits a secret $s$ into $n$ shares using a linear secret-sharing scheme (e.g., additive sharing). These shares are transmitted over $n$ disjoint paths to the receiver (Bob).
2. AMD Encoding: Before splitting, Alice encodes the secret using an AMD code construction (based on Cramer et al., 2008). This maps the secret $s$ to a group element such that any non-trivial algebraic shift (manipulation) of the encoded value is detected with high probability by the decoder.
3. Relaying: Each share is relayed over its respective path using One-Time Pad (OTP) encryption with QKD-generated keys shared between adjacent nodes. Intermediate nodes decrypt and re-encrypt the data.

Protocol Flow (Listing 1):

• Alice: Encodes $s$ using an AMD encoder, splits the result into shares $\vec{S}$, and encrypts the first share of each path with the local QKD key.
• Relay Nodes: Decrypt the incoming ciphertext, subtract the incoming key, add the outgoing key, and forward the result. This effectively relays the share while maintaining the additive structure required for the secret sharing scheme.
• Bob: Decrypts the final shares from all paths, reconstructs the encoded secret using the secret sharing recovery function, and finally decodes using the AMD decoder. If the decoding fails (output $\perp$), Bob rejects the protocol, indicating tampering.

Security Model:
The authors adapt the game-based security model (Brickell et al., 2007) to the trusted repeater context. They assume:

• The network topology is static.
• The adversary can corrupt an arbitrary set of nodes but is limited to an unqualified set of paths (i.e., cannot reconstruct the secret).
• The adversary is computationally unbounded.
• QKD keys provide statistical privacy against quantum side information.

3. Key Contributions

1. First Provable Integrity Protocol: This work presents the first protocol that provably provides both confidentiality and integrity in trusted-repeater QKD networks against computationally unbounded adversaries.
2. Shift-Robustness Definition: The authors introduce a new security notion called $\delta$-shift-robustness. Unlike standard robust secret sharing where an honest shareholder recovers the secret, this definition accounts for external recovery (Bob) where the adversary can induce shifts on uncorrupted shares via the malleability of OTP encryption.
3. Formal Security Proof: The authors prove that their protocol achieves:
   • Confidentiality: Bounded by $n\ell\epsilon$ (where $n$ is paths, $\ell$ is path length, $\epsilon$ is QKD privacy).
   • Integrity: Bounded by $n\ell\epsilon + \delta$, where $\delta$ is the AMD code's manipulation detection probability.
4. Optimal Overhead: The protocol achieves the optimal overhead for strong robustness ($2 \log(1/\delta)$ bits) when relaying arbitrary messages.
5. Efficiency: The protocol is non-interactive (Alice sends, Bob receives) and requires only $n\ell$ non-authenticated messages between neighbors, improving upon interactive solutions like SECOQC.

4. Results

• Theoretical Guarantees: The protocol is proven secure through a sequence of games. The first game hop replaces QKD keys with uniform random elements (indistinguishable with probability $n\ell\epsilon$). The second hop reduces the integrity guarantee to the security of the shift-robust secret sharing scheme (probability $\delta$).
• Implementation: The authors provide a concrete implementation demonstrating that the method is efficient. For a field of size $q$, the encoding maps a value to $F^d \times F \times F$, and additive secret sharing adds no overhead.
• Comparison: Unlike the SECOQC protocol, which relies on circular reasoning for MACs and allows for cheater identification (which the authors show can be broken via algebraic manipulation), this protocol prioritizes provable integrity without circular assumptions.

5. Significance and Claims

The paper claims to fill a critical gap in the security of deployed QKD networks. While confidentiality is often assumed via multi-path relaying, integrity has been an unaddressed vulnerability. The authors assert that their protocol is the first to provide provable integrity in this specific setting.

Limitations and Assumptions:
The authors are modest regarding the practicality of their current model:

• Static Topology: The protocol assumes a fixed network topology and fixed keys. It does not currently support dynamic networks where paths or endpoints change, which limits immediate real-world deployment flexibility.
• Node Authentication: The protocol assumes node authentication is handled by the static nature of the network or an external mechanism. It does not solve the problem of authenticating endpoints in a dynamic, partially trusted network.
• No Cheater Identification: Unlike some previous proposals, this protocol detects tampering but does not identify which intermediate node was malicious.

Future Directions:
The authors identify three specific avenues for future work:

1. Investigating external difference families to achieve weak robustness with minimal tag size, which is sufficient for key relaying.
2. Developing a protocol that can identify cheaters (malicious nodes) rather than just detecting tampering.
3. Extending the trusted repeater model to represent dynamic networks, moving beyond the static assumptions required for the current proof.