⚛️ quantum physics

Transcript-Bound Combiners for Downgrade-Resilient Hybrid Post-Quantum Key Establishment: Definition, Proof, and Embedded-Device Cost

This paper defines and proves that binding hybrid post-quantum key establishment session keys to the handshake transcript is essential for preventing downgrade attacks, demonstrating that this security enhancement incurs negligible energy costs on embedded devices while requiring no additional network overhead.

Original authors: Bhanwar Gupta, Sanjeev Rana

Published 2026-09-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bhanwar Gupta, Sanjeev Rana

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the coming decades, the computers we use today may face a threat they cannot withstand. A new kind of machine, powered by the strange rules of quantum physics, could one day solve mathematical puzzles that currently protect our digital secrets. These puzzles are the foundation of the locks that keep our bank accounts, private messages, and national infrastructure safe. If a powerful quantum computer arrives, it could unlock everything we have encrypted today, a risk that has led security experts to rush toward "post-quantum" cryptography. These are new digital locks designed to resist both current computers and future quantum ones. However, simply swapping an old lock for a new one is not always safe. The transition period is dangerous because attackers can trick systems into using the old, weak locks instead of the new, strong ones. This is known as a downgrade attack, where a malicious actor intercepts a conversation, deletes the option for the new security, and forces both sides to agree on the vulnerable method, all without either party realizing they have been tricked.

Researchers Bhanwar Gupta and Sanjeev Rana have identified a specific weakness in how these new security systems are being combined and have proposed a simple, low-cost fix. Their work focuses on "hybrid" key establishment, a strategy where two parties use both a classical lock and a new post-quantum lock at the same time to create a single session key. The idea is that as long as one of the two locks holds, the connection remains secure. While this approach is already being adopted in major internet protocols, the researchers found that the method used to decide which locks to use is often left unverified. In many current designs, the actual negotiation—where the two sides agree on which security methods to employ—is not tied to the final secret key. This gap allows an attacker to strip away the new post-quantum option during the handshake, leaving the two parties to settle for a purely classical, vulnerable connection. The researchers proved that without a specific check, this attack is guaranteed to succeed.

To solve this, the team introduced a method called "transcript binding." In their proposed design, the final secret key is not just a mixture of the two shared secrets; it is also mathematically tied to a record of the entire conversation that took place to agree on those secrets. This record, or transcript, includes every message exchanged, specifically the lists of security options each side offered. If an attacker tries to delete the post-quantum option from the list, the two parties will end up with different records of what was said. Because their records do not match, the math used to generate the final key will produce two different results. When the parties try to verify they share the same secret, the check will fail, and the connection will simply stop. The attacker is blocked not by a complex new algorithm, but by the fact that the key itself refuses to be generated unless the conversation history is exactly as it should be.

The researchers did not just theorize this; they built and tested a working version of the system. They demonstrated that without this binding, a simulated attacker could force a downgrade to a weak classical system in every single trial. With the binding in place, the system aborted the connection every time an attempt was made to strip the post-quantum option. The security proof shows that the chance of an attacker bypassing this check is so small it is effectively zero, provided the hash function used to record the conversation is strong. This approach makes the safety of the negotiation a local property of the key-generation process itself, meaning it works even if the surrounding software does not have its own protection against such tampering.

A major concern for security on small devices, such as sensors or medical implants, is energy and processing power. The researchers calculated the cost of adding this protection using a detailed model based on measurements from a common microchip used in constrained devices. They found that the extra work required is minimal. The additional computation adds about 11.8 percent to the processing time of the handshake. However, because the actual transmission of data over the radio consumes far more energy than the calculation itself, the total energy cost of the entire process increases by only 1.5 percent. Crucially, this protection requires no extra messages to be sent, no additional data to be transmitted over the network, and no extra round trips between the devices. The only change is a single mathematical operation performed by each device to hash the conversation history.

The study confirms that this method is a practical and robust way to secure the transition to post-quantum cryptography. It closes a specific loophole where attackers could silently downgrade security without detection. By binding the final key to the history of the negotiation, the system ensures that any attempt to alter the agreed-upon security settings is immediately detected and rejected. For the constrained devices that will rely on these new standards, the cost of this protection is negligible compared to the energy already spent on sending the large post-quantum data packets. The result is a self-contained guarantee that the security chosen by the users is the security they actually get, regardless of what an attacker might try to do in the middle.

Technical Summary: Transcript-Bound Combiners for Downgrade-Resilient Hybrid Post-Quantum Key Establishment

1. Problem Statement

Hybrid key establishment, which runs a post-quantum Key Encapsulation Mechanism (KEM) alongside a classical Diffie–Hellman primitive, is the current standard for securing the transition to quantum-resistant cryptography (e.g., in TLS 1.3, SSH, and IKE). While hybrid KEMs secure the derived session key against the compromise of either component, they often fail to secure the integrity of the negotiation that selects which primitives are used.

In configurable deployments, devices advertise supported suites, and peers select a mutually supported one. An active man-in-the-middle (MITM) attacker can intercept these advertisements, strip the post-quantum option, and force both parties to negotiate a purely classical handshake. This "downgrade attack" results in a session key that lacks post-quantum security, even if both parties intended to use hybrid security.

While full protocols like TLS 1.3 and EDHOC mitigate this by authenticating the entire handshake transcript, a significant gap exists when hybrid KEMs are deployed as standalone drop-in primitives or within minimal, bespoke handshakes that lack transcript authentication. In these scenarios, the combiner (the logic merging the two secrets) is blind to the negotiation parameters, making downgrade attacks succeed with certainty.

2. Methodology

The authors propose a modification to the hybrid key schedule to make downgrade resilience a local property of the combiner, independent of the surrounding protocol's authentication mechanisms.

The Solution: The paper introduces a transcript-bound combiner. Instead of deriving the session key $K$ $K$ solely from the shared secrets ( $K_{pq}$ $K_{pq}$ and $K_{ec}$ $K_{ec}$ ), the key derivation function (KDF) and the key-confirmation tag are bound to a hash of the handshake transcript ( $\tau$ $τ$ ).
- Plain Combiner: $K = \text{KDF}(K_{pq} \parallel K_{ec})$
- Bound Combiner: $K = \text{KDF}(\ell \parallel K_{pq} \parallel K_{ec} \parallel H(\tau))$
- Here, $\tau$ is the ordered concatenation of all handshake messages (including advertised suite lists and the selected suite) as observed by the local party.
Mechanism: If an attacker rewrites the negotiation (e.g., deleting post-quantum entries), the initiator and responder assemble different transcripts ( $\tau_I \neq \tau_R$ ). Consequently, they derive different session keys ( $K_I \neq K_R$ ). The initiator's verification of the responder's confirmation tag fails, causing the handshake to abort.
Implementation: The authors implemented both the plain and bound combiners using ML-KEM-768 (FIPS 203) and X25519. They utilized a calibrated cost model based on published Cortex-M4 measurements (pqm4 and Lenngren's implementations) to evaluate engineering costs on constrained devices.

3. Key Contributions

The paper makes five specific contributions:

Definition: A game-based definition of downgrade resilience at the combiner layer, modeling an active MITM adversary capable of rewriting advertised suite lists.
Two-Sided Separation Proof:
- Lower Bound: A plain combiner that ignores the transcript is downgraded with probability 1.
- Upper Bound: A transcript-bound combiner limits the downgrade advantage to $q_H/2^n + \text{Adv}^{\text{euf-cma}}_{\text{MAC}}$ , where $n$ is the transcript hash length (256 bits) and $q_H$ is the adversary's random-oracle query budget. This bound is information-theoretic up to collision and forgery terms.
Strongest-Link Security: An explicit IND-CCA security bound for the concrete combiner, reducing to the security of the component KEMs in the random-oracle model. The bound includes an explicit constant ( $q_H/2^\gamma$ ) and is corroborated by an exposed-component distinguisher with $R^2 = 0.98$ .
Engineering Cost Analysis: A detailed cost model for constrained devices (Cortex-M4). The analysis shows that transcript binding adds exactly one hash evaluation per party, with no additional messages, round trips, or wire bytes.
Validation: A released harness with a 30-check validation gate that ensures all reported numbers (correctness, downgrade outcomes, and distinguisher success rates) are reproducible and consistent.

4. Results

Correctness: Over 2,000 honest handshakes, the bound combiner derived matching session keys with zero mismatches.
Downgrade Resilience: Under active attack, the plain combiner was silently downgraded to the classical suite in 100% of trials. The transcript-bound combiner aborted the handshake in 100% of trials when the transcript was altered.
Security Bound Verification: An empirical distinguisher confirmed that the key-recovery success rate tracks the analytic term $q/2^\gamma$ ( $R^2 = 0.98$ ). Extrapolated to full parameters, the success probability is below $2^{-190}$ .
Performance Overhead (Cortex-M4):
- Computation: Transcript binding adds 0.47 million cycles, representing an 11.8% increase in handshake computation.
- Energy: In a radio-inclusive energy budget (including 802.15.4 transmission), the binding overhead accounts for only 1.5% of the total energy. This is because the dominant cost is transmitting the larger ML-KEM-768 payload, not the hash computation.
- Communication: Zero additional bytes are added to the wire.
- Memory: Peak stack usage remains at ~6.5 KB, dominated by ML-KEM-768, fitting within Class-2 constrained-node budgets.

5. Significance and Claims

The paper claims that transcript binding provides a minimal, local, and self-contained mechanism to close the downgrade gap in hybrid key establishment.

Independence: Unlike full protocol fixes, this mechanism works even when the hybrid KEM is used as a standalone primitive or in a custom handshake lacking transcript authentication.
Cost-Benefit: The authors emphasize that the cost is negligible in the context of side-channel-hardened deployments (where masked ML-KEM decapsulation costs an order of magnitude more than the binding hash) and in radio-constrained environments (where transmission energy dominates).
Relation to Existing Work: The authors clarify that this is not a new cryptographic primitive but a specialization of the transcript-binding principle (previously applied at the protocol layer by Bhargavan et al.) down to the combiner layer. It complements fixed-combiner designs like X-Wing by adding negotiation integrity to the key schedule.

The paper concludes that for constrained post-quantum deployments where protocol-level transcript authentication is absent or unreliable, binding the session key to the negotiation transcript is the most efficient way to ensure downgrade resilience.