Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.21469

Limits of adaptive two-way linear postprocessing in six-state quantum key distribution

Toyohiro Tsurumaru

quant-phSubmitted Oct 15, 2026• Announced Oct 16, 2026• 0 citations• Revised Oct 16, 2026 (v2)
v1 · Oct 15, 2026v2 · Oct 16, 2026
arXivHTMLPDF

Abstract

Two-way classical communication improves the noise tolerance of quantum key distribution, but the limits of adaptive parity processing remain unclear. For the six-state protocol with equal three-basis error rate $p\in[p_*,1/2]$, where $p_*=(5-\sqrt5)/10\simeq27.64\%$, we construct a single compatible collective attack that defeats a broad class of linear postprocessing. Each public message may be a linear function of the sender's raw key, chosen adaptively from the public history. For every finite input length and every accepted transcript of positive probability, Eve's optimal probability of recovering any linear function of Alice's raw key is at least Bob's. Consequently, reliable agreement on a linear final key is incompatible with secrecy. The same conclusion holds for arbitrary publicly seeded privacy amplification after reliable recovery of a linear candidate. The proof conditions on the complete transcript, which restricts the two raw keys to affine subspaces. A local degradation of Eve's state, a known Rényi-entropy comparison, and a coset-probability inequality then give the recovery comparison. Both inequalities are proved in self-contained appendices. The result allows block splitting, regrouping, nonzero-syndrome selection, and adaptive linear reconciliation.

AI Summary

Can adaptive two-way parity processing raise the six-state QKD noise threshold beyond $p_*=(5-\sqrt5)/10\simeq27.64\%$? This paper establishes a converse for a specified class of linear postprocessing, addressing part of the gap between that achievable threshold and the $1/3$ intercept–resend limit. For equal three-basis QBER $p\in[p_*,1/2]$, it constructs one compatible collective attack, independent of the postprocessing protocol. Public messages may be linear functions of either party’s original raw key, with the sender and matrices chosen adaptively from public history. Alice’s candidate is also a history-dependent linear function; Bob may use his complete raw key and any decoder. For every finite input length and every positive-probability accepted transcript $t$, the result is $p_{\mathrm{guess}}(K\mid E,t)\ge p_{\mathrm{guess}}(K\mid B,t)$. Thus reliable linear-key agreement cannot be secret. For a fixed $\ell$-bit output with conditional agreement error $\epsilon_B$, the conditional secrecy distance satisfies $\Delta_{\mathrm{acc}}\ge1-\epsilon_B-2^{-\ell}$. Arbitrary publicly seeded privacy amplification is also excluded after reliable recovery of a linear candidate. The proof fixes the complete transcript, expressing compatible inputs as affine subspaces. A local degradation gives Eve the error pattern and a pure-state alphabet; a known Rényi-entropy comparison and code-coset weight inequalities then compare recovery probabilities. The converse permits adaptive regrouping and syndrome selection, but does not establish zero unrestricted secret-key capacity or settle the full linear-code threshold conjecture. Secret noisy preprocessing, secret local randomness, and directly shared nonlinear outputs remain outside its scope; rare acceptance also weakens acceptance-weighted secrecy implications.

Little sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
21 pages, no figure. v2: Minor improvements to the exposition; no changes to the technical content

Related papers

Information Reconciliation for Quantum Key Distribution

David Elkouss, Jesús Martínez-Mateo, Vicente Martín Ayuso +1 more

Quantum key distribution (QKD) relies on quantum and classical procedures in order to achieve the growing of a secret random string -the key- known only to the two parties executing the protocol. Limited intrinsic efficiency of the protocol, imperfect devices and eavesdropping produce errors and information leakage from which the set of measured signals -the raw key- must be stripped in order to distill a final, information theoretically secure, key. The key distillation process is a classical one in which basis reconciliation, error correction and privacy amplification protocols are applied to the raw key. This cleaning process is known as information reconciliation and must be done in a fast and efficient way to avoid cramping the performance of the QKD system. Brassard and Salvail proposed a very simple and elegant protocol to reconcile keys in the secret-key agreement context, known as Cascade, that has become the de-facto standard for all QKD practical implementations. However, it is highly interactive, requiring many communications between the legitimate parties and its efficiency is not optimal, imposing an early limit to the maximum tolerable error rate. In this paper we describe a low-density parity-check reconciliation protocol that improves significantly on these problems. The protocol exhibits better efficiency and limits the number of uses of the communications channel. It is also able to adapt to different error rates while remaining efficient, thus reaching longer distances or higher secure key rate for a given QKD system.

•Oct 1, 2010•50 citations

Information Reconciliation for Quantum Key Distribution

David Elkouss, Jesús Martínez-Mateo, Vicente Martín

Quantum key distribution (QKD) relies on quantum and classical procedures in order to achieve the growing of a secret random string -the key- known only to the two parties executing the protocol. Limited intrinsic efficiency of the protocol, imperfect devices and eavesdropping produce errors and information leakage from which the set of measured signals -the raw key- must be stripped in order to distill a final, information theoretically secure, key. The key distillation process is a classical one in which basis reconciliation, error correction and privacy amplification protocols are applied to the raw key. This cleaning process is known as information reconciliation and must be done in a fast and efficient way to avoid cramping the performance of the QKD system. Brassard and Salvail proposed a very simple and elegant protocol to reconcile keys in the secret-key agreement context, known as Cascade, that has become the de-facto standard for all QKD practical implementations. However, it is highly interactive, requiring many communications between the legitimate parties and its efficiency is not optimal, imposing an early limit to the maximum tolerable error rate. In this paper we describe a low-density parity-check reconciliation protocol that improves significantly on these problems. The protocol exhibits better efficiency and limits the number of uses of the communications channel. It is also able to adapt to different error rates while remaining efficient, thus reaching longer distances or higher secure key rate for a given QKD system.

arXiv:1007.1616•Jul 9, 2010•5 citations

EFFICIENT RECONCILIATION WITH RATE ADAPTIVE CODES IN QUANTUM KEY DISTRIBUTION

David Elkouss, Jesús Martínez-Mateo, Vicente Martín +1 more

Quantum key distribution (QKD) relies on quantum and classical procedures in order to achieve the growing of a secret random string —the key— known only to the two parties executing the protocol. Limited intrinsic efficiency of the protocol, imperfect devices and eavesdropping produce errors and information leakage from which the set of measured signals —the raw key— must be stripped in order to distill a final, information theoretically secure, key. The key distillation process is a classical one in which basis reconciliation, error correction and privacy amplification protocols are applied to the raw key. This cleaning process is known as information reconciliation and must be done in a fast and efficient way to avoid cramping the performance of theQKD system. Brassard and Salvail proposed a very simple and elegant protocol to reconcile keys in the secretkey agreement context, known as Cascade, that has become the de-facto standard for all QKD practical implementations. However, it is highly interactive, requiring many communications between the legitimate parties and its efficiency is not optimal, imposing an early limit to the maximum tolerable error rate. In this paper we describe a low-density parity-check reconciliation protocol that improves significantly on these problems. The protocol exhibits better efficiency and limits the number of uses of the communications channel. It is also able to adapt to different error rates while remaining efficient, thus reaching longer distances or higher secure key rate for a given QKD system.

•Jan 1, 2010•1 citation

Symmetric Extendability of Quantum States and the Extreme Limits of Quantum Key Distribution

Sumeet Khatri

We investigate QKD protocols with two-way classical post-processing that are based on the well-known six-state and BB84 signal states. In these QKD protocols, the source (Alice) sends quantum signals to the receiver (Bob), who measures them, leaving only classical data on both sides. Our goal is to find the highest value of the quantum bit-error rate (QBER) $Q$ for which two-way classical post-processing protocols on the data can distill secret keys. Using the BB84 signal states, such protocols currently exist for $Q<\\frac{1}{5}$. On the other hand, for $Q\\geq\\frac{1}{4}$ no such protocol can exist as the observed data is compatible with an intercept-resend attack. This leaves the interesting question of whether successful two-way protocols exist in the interval $\\frac{1}{5}\\leq Q<\\frac{1}{4}$. For the six-state signal states, the corresponding interval is known to be $\\frac{5-\\sqrt{5}}{10}\\leq Q<\\frac{1}{3}$. \n\t \n\tWe search for two-way protocols because it turns out that within these intervals Alice and Bob's correlations are symmetrically extendable, meaning that Bob and the eavesdropper (Eve) are completely indistinguishable from Alice's point of view, making any one-way Alice-to-Bob post-processing protocol insecure. A two-way protocol might be able to break the symmetry between Bob and Eve, and it must do so in order to distill a secret key because any two-way protocol will necessarily terminate with a one-way communication step, at which point the symmetric extendability of Alice and Bob's updated correlations must be checked again. \n \nWe first show that the search for two-way protocols breaking the symmetric extendability of Alice and Bob's correlations can be restricted to a search over post-selection protocols if all we care about is whether secret key can at all be distilled and not about the rate of distillation. We then provide strong analytical and numerical evidence to suggest that no two-way classical post-processing protocol exists within the gap when the six-state signal states are used. \n\t \n\tUnder quantum entanglement distillation protocols, it is known that secret key can be distilled right up to the intercept-resend bounds of $\\frac{1}{4}$ and $\\frac{1}{3}$ for the BB84 and six-state signal states, respectively. We therefore want to know whether classical post-processing protocols are just as good at distilling secret keys as quantum ones. Our results appear to indicate that they are not.

•Oct 13, 2016•3 citations

Numerical evidence for bound secrecy from two-way postprocessing in quantum key distribution

Sumeet Khatri, Norbert Lütkenhaus

Bound secret information is classical information that contains secrecy but from which secrecy cannot be extracted. The existence of bound secrecy has been conjectured but is currently unproven, and in this work we provide analytical and numerical evidence for its existence. Specifically, we consider two-way postprocessing protocols in prepare-and-measure quantum key distribution based on the well-known six-state signal states. In terms of the quantum bit-error rate $Q$ of the classical data, such protocols currently exist for $Q<\frac{5\ensuremath{-}\sqrt{5}}{10}\ensuremath{\approx}27.6%$. On the other hand, for $Q\ensuremath{\ge}\frac{1}{3}$ no such protocol can exist as the observed data are compatible with an intercept-resend attack. This leaves the interesting question of whether successful protocols exist in the interval $\frac{5\ensuremath{-}\sqrt{5}}{10}\ensuremath{\le}Q<\frac{1}{3}$. Previous work has shown that a necessary condition for the existence of two-way postprocessing protocols for distilling secret keys is breaking the symmetric extendability of the underlying quantum state shared by Alice and Bob. Using this result, it has been proven that symmetric extendability can be broken up to the $27.6%$ lower bound using the advantage distillation protocol. In this work, we first show that to break symmetric extendability it is sufficient to consider a generalized form of advantage distillation consisting of one round of postselection by Bob on a block of his data. We then provide evidence that such generalized protocols cannot break symmetric extendability beyond $27.6%$. We thus have evidence to believe that $27.6%$ is an upper bound on two-way postprocessing and that the interval $\frac{5\ensuremath{-}\sqrt{5}}{10}\ensuremath{\le}Q<\frac{1}{3}$ is a domain of bound secrecy.

arXiv:1612.07734•Physical Review A•Apr 14, 2017•17 citations

One Key Good, L Keys Better: List Decoding Meets Quantum Privacy Amplification

Prateek P. Kulkarni

We introduce list privacy amplification (LPA), a relaxation of the final step of quantum key distribution (QKD) in which Alice and Bob extract a list of $L$ candidate keys from a raw string correlated with an eavesdropper Eve, with the guarantee that at least one key is perfectly secret while Eve cannot identify which. This parallels list decoding in error-correcting codes: relaxing unique decoding to list decoding increases the decoding radius; analogously, list extraction increases achievable key length beyond the standard quantum leftover hash lemma (QLHL). Within the abstract cryptography framework, we formalise LPA and prove the \emph{Quantum List Leftover Hash Lemma} (QLLHL): an $L$-list of $\ell$-bit keys can be extracted from an $n$-bit source with smooth min-entropy $k$ iff \[ \ell \le k + \log L - 2\log(1/ε) - 3, \] yielding a tight additive $\log L$ gain over QLHL. This gain arises because the index of the secure key is chosen after hashing and hidden from Eve, effectively contributing $\log L$ bits of entropy. Applying QLLHL to BB84-type QKD, a list size $L = 2^{αn'}$ increases the tolerable phase-error threshold from $h^{-1}(1 - h(e_b))$ to $h^{-1}(1 - h(e_b) + α)$, exceeding the standard $\approx 11\%$ bound for any $α> 0$. We prove tightness via a matching intercept-resend attack, establish composability with Wegman--Carter authentication, and present two constructions: a polynomial inner-product hash over $\mathbb{F}_{2^m}$ and a Toeplitz-based variant, running in $O(nL)$ and $O(nL \log n)$ time.

quant-pharXiv:2603.18097•Mar 19, 2026•0 citations
Two-way classical communication improves the noise tolerance of quantum key distribution, but the limits of adaptive parity processing remain unclear. For the six-state protocol with equal three-basis error rate p∈[p∗,1/2]p\in[p_*,1/2]p∈[p∗​,1/2], where p∗=(5−5)/10≃27.64%p_*=(5-\sqrt5)/10\simeq27.64\%p∗​=(5−5​)/10≃27.64%, we construct a single compatible collective attack that defeats a broad class of linear postprocessing. Each public message may be a linear function of the sender's raw key, chosen adaptively from the public history. For every finite input length and every accepted transcript of positive probability, Eve's optimal probability of recovering any linear function of Alice's raw key is at least Bob's. Consequently, reliable agreement on a linear final key is incompatible with secrecy. The same conclusion holds for arbitrary publicly seeded privacy amplification after reliable recovery of a linear candidate. The proof conditions on the complete transcript, which restricts the two raw keys to affine subspaces. A local degradation of Eve's state, a known Rényi-entropy comparison, and a coset-probability inequality then give the recovery comparison. Both inequalities are proved in self-contained appendices. The result allows block splitting, regrouping, nonzero-syndrome selection, and adaptive linear reconciliation.
Can adaptive two-way parity processing raise the six-state QKD noise threshold beyond p∗=(5−5)/10≃27.64%p_*=(5-\sqrt5)/10\simeq27.64\%p∗​=(5−5​)/10≃27.64%? This paper establishes a converse for a specified class of linear postprocessing, addressing part of the gap between that achievable threshold and the 1/31/31/3 intercept–resend limit.
For equal three-basis QBER p∈[p∗,1/2]p\in[p_*,1/2]p∈[p∗​,1/2], it constructs one compatible collective attack, independent of the postprocessing protocol. Public messages may be linear functions of either party’s original raw key, with the sender and matrices chosen adaptively from public history. Alice’s candidate is also a history-dependent linear function; Bob may use his complete raw key and any decoder. For every finite input length and every positive-probability accepted transcript ttt, the result is pguess(K∣E,t)≥pguess(K∣B,t)p_{\mathrm{guess}}(K\mid E,t)\ge p_{\mathrm{guess}}(K\mid B,t)pguess​(K∣E,t)≥pguess​(K∣B,t). Thus reliable linear-key agreement cannot be secret. For a fixed ℓ\ellℓ-bit output with conditional agreement error ϵB\epsilon_BϵB​, the conditional secrecy distance satisfies Δacc≥1−ϵB−2−ℓ\Delta_{\mathrm{acc}}\ge1-\epsilon_B-2^{-\ell}Δacc​≥1−ϵB​−2−ℓ. Arbitrary publicly seeded privacy amplification is also excluded after reliable recovery of a linear candidate.
The proof fixes the complete transcript, expressing compatible inputs as affine subspaces. A local degradation gives Eve the error pattern and a pure-state alphabet; a known Rényi-entropy comparison and code-coset weight inequalities then compare recovery probabilities.
The converse permits adaptive regrouping and syndrome selection, but does not establish zero unrestricted secret-key capacity or settle the full linear-code threshold conjecture. Secret noisy preprocessing, secret local randomness, and directly shared nonlinear outputs remain outside its scope; rare acceptance also weakens acceptance-weighted secrecy implications.
Quantum key distribution (QKD) relies on quantum and classical procedures in order to achieve the growing of a secret random string -the key- known only to the two parties executing the protocol. Limited intrinsic efficiency of the protocol, imperfect devices and eavesdropping produce errors and information leakage from which the set of measured signals -the raw key- must be stripped in order to distill a final, information theoretically secure, key. The key distillation process is a classical one in which basis reconciliation, error correction and privacy amplification protocols are applied to the raw key. This cleaning process is known as information reconciliation and must be done in a fast and efficient way to avoid cramping the performance of the QKD system. Brassard and Salvail proposed a very simple and elegant protocol to reconcile keys in the secret-key agreement context, known as Cascade, that has become the de-facto standard for all QKD practical implementations. However, it is highly interactive, requiring many communications between the legitimate parties and its efficiency is not optimal, imposing an early limit to the maximum tolerable error rate. In this paper we describe a low-density parity-check reconciliation protocol that improves significantly on these problems. The protocol exhibits better efficiency and limits the number of uses of the communications channel. It is also able to adapt to different error rates while remaining efficient, thus reaching longer distances or higher secure key rate for a given QKD system.
Quantum key distribution (QKD) relies on quantum and classical procedures in order to achieve the growing of a secret random string -the key- known only to the two parties executing the protocol. Limited intrinsic efficiency of the protocol, imperfect devices and eavesdropping produce errors and information leakage from which the set of measured signals -the raw key- must be stripped in order to distill a final, information theoretically secure, key. The key distillation process is a classical one in which basis reconciliation, error correction and privacy amplification protocols are applied to the raw key. This cleaning process is known as information reconciliation and must be done in a fast and efficient way to avoid cramping the performance of the QKD system. Brassard and Salvail proposed a very simple and elegant protocol to reconcile keys in the secret-key agreement context, known as Cascade, that has become the de-facto standard for all QKD practical implementations. However, it is highly interactive, requiring many communications between the legitimate parties and its efficiency is not optimal, imposing an early limit to the maximum tolerable error rate. In this paper we describe a low-density parity-check reconciliation protocol that improves significantly on these problems. The protocol exhibits better efficiency and limits the number of uses of the communications channel. It is also able to adapt to different error rates while remaining efficient, thus reaching longer distances or higher secure key rate for a given QKD system.
Quantum key distribution (QKD) relies on quantum and classical procedures in order to achieve the growing of a secret random string —the key— known only to the two parties executing the protocol. Limited intrinsic efficiency of the protocol, imperfect devices and eavesdropping produce errors and information leakage from which the set of measured signals —the raw key— must be stripped in order to distill a final, information theoretically secure, key. The key distillation process is a classical one in which basis reconciliation, error correction and privacy amplification protocols are applied to the raw key. This cleaning process is known as information reconciliation and must be done in a fast and efficient way to avoid cramping the performance of theQKD system. Brassard and Salvail proposed a very simple and elegant protocol to reconcile keys in the secretkey agreement context, known as Cascade, that has become the de-facto standard for all QKD practical implementations. However, it is highly interactive, requiring many communications between the legitimate parties and its efficiency is not optimal, imposing an early limit to the maximum tolerable error rate. In this paper we describe a low-density parity-check reconciliation protocol that improves significantly on these problems. The protocol exhibits better efficiency and limits the number of uses of the communications channel. It is also able to adapt to different error rates while remaining efficient, thus reaching longer distances or higher secure key rate for a given QKD system.
We investigate QKD protocols with two-way classical post-processing that are based on the well-known six-state and BB84 signal states. In these QKD protocols, the source (Alice) sends quantum signals to the receiver (Bob), who measures them, leaving only classical data on both sides. Our goal is to find the highest value of the quantum bit-error rate (QBER) QQQ for which two-way classical post-processing protocols on the data can distill secret keys. Using the BB84 signal states, such protocols currently exist for Q<frac15Q<\\frac{1}{5}Q<frac15. On the other hand, for Qgeqfrac14Q\\geq\\frac{1}{4}Qgeqfrac14 no such protocol can exist as the observed data is compatible with an intercept-resend attack. This leaves the interesting question of whether successful two-way protocols exist in the interval frac15leqQ<frac14\\frac{1}{5}\\leq Q<\\frac{1}{4}frac15leqQ<frac14. For the six-state signal states, the corresponding interval is known to be frac5−sqrt510leqQ<frac13\\frac{5-\\sqrt{5}}{10}\\leq Q<\\frac{1}{3}frac5−sqrt510leqQ<frac13. \n\t \n\tWe search for two-way protocols because it turns out that within these intervals Alice and Bob's correlations are symmetrically extendable, meaning that Bob and the eavesdropper (Eve) are completely indistinguishable from Alice's point of view, making any one-way Alice-to-Bob post-processing protocol insecure. A two-way protocol might be able to break the symmetry between Bob and Eve, and it must do so in order to distill a secret key because any two-way protocol will necessarily terminate with a one-way communication step, at which point the symmetric extendability of Alice and Bob's updated correlations must be checked again. \n \nWe first show that the search for two-way protocols breaking the symmetric extendability of Alice and Bob's correlations can be restricted to a search over post-selection protocols if all we care about is whether secret key can at all be distilled and not about the rate of distillation. We then provide strong analytical and numerical evidence to suggest that no two-way classical post-processing protocol exists within the gap when the six-state signal states are used. \n\t \n\tUnder quantum entanglement distillation protocols, it is known that secret key can be distilled right up to the intercept-resend bounds of frac14\\frac{1}{4}frac14 and frac13\\frac{1}{3}frac13 for the BB84 and six-state signal states, respectively. We therefore want to know whether classical post-processing protocols are just as good at distilling secret keys as quantum ones. Our results appear to indicate that they are not.
Bound secret information is classical information that contains secrecy but from which secrecy cannot be extracted. The existence of bound secrecy has been conjectured but is currently unproven, and in this work we provide analytical and numerical evidence for its existence. Specifically, we consider two-way postprocessing protocols in prepare-and-measure quantum key distribution based on the well-known six-state signal states. In terms of the quantum bit-error rate QQQ of the classical data, such protocols currently exist for $Q<\frac{5\ensuremath{-}\sqrt{5}}{10}\ensuremath{\approx}27.6%$. On the other hand, for $Q\ensuremath{\ge}\frac{1}{3}$ no such protocol can exist as the observed data are compatible with an intercept-resend attack. This leaves the interesting question of whether successful protocols exist in the interval $\frac{5\ensuremath{-}\sqrt{5}}{10}\ensuremath{\le}Q<\frac{1}{3}$. Previous work has shown that a necessary condition for the existence of two-way postprocessing protocols for distilling secret keys is breaking the symmetric extendability of the underlying quantum state shared by Alice and Bob. Using this result, it has been proven that symmetric extendability can be broken up to the 27.627.6%27.6 lower bound using the advantage distillation protocol. In this work, we first show that to break symmetric extendability it is sufficient to consider a generalized form of advantage distillation consisting of one round of postselection by Bob on a block of his data. We then provide evidence that such generalized protocols cannot break symmetric extendability beyond 27.627.6%27.6. We thus have evidence to believe that 27.627.6%27.6 is an upper bound on two-way postprocessing and that the interval $\frac{5\ensuremath{-}\sqrt{5}}{10}\ensuremath{\le}Q<\frac{1}{3}$ is a domain of bound secrecy.
We introduce list privacy amplification (LPA), a relaxation of the final step of quantum key distribution (QKD) in which Alice and Bob extract a list of LLL candidate keys from a raw string correlated with an eavesdropper Eve, with the guarantee that at least one key is perfectly secret while Eve cannot identify which. This parallels list decoding in error-correcting codes: relaxing unique decoding to list decoding increases the decoding radius; analogously, list extraction increases achievable key length beyond the standard quantum leftover hash lemma (QLHL). Within the abstract cryptography framework, we formalise LPA and prove the \emph{Quantum List Leftover Hash Lemma} (QLLHL): an LLL-list of ℓ\ellℓ-bit keys can be extracted from an nnn-bit source with smooth min-entropy kkk iff ℓ≤k+log⁡L−2log⁡(1/ε)−3, \ell \le k + \log L - 2\log(1/ε) - 3, ℓ≤k+logL−2log(1/ε)−3, yielding a tight additive log⁡L\log LlogL gain over QLHL. This gain arises because the index of the secure key is chosen after hashing and hidden from Eve, effectively contributing log⁡L\log LlogL bits of entropy. Applying QLLHL to BB84-type QKD, a list size L=2αn′L = 2^{αn'}L=2αn′ increases the tolerable phase-error threshold from h−1(1−h(eb))h^{-1}(1 - h(e_b))h−1(1−h(eb​)) to h−1(1−h(eb)+α)h^{-1}(1 - h(e_b) + α)h−1(1−h(eb​)+α), exceeding the standard ≈11%\approx 11\%≈11% bound for any α>0α> 0α>0. We prove tightness via a matching intercept-resend attack, establish composability with Wegman--Carter authentication, and present two constructions: a polynomial inner-product hash over F2m\mathbb{F}_{2^m}F2m​ and a Toeplitz-based variant, running in O(nL)O(nL)O(nL) and O(nLlog⁡n)O(nL \log n)O(nLlogn) time.