Boyer, Liss, and Mor (2022) gave a self-contained, algebraic proof of composable unconditional security for four BB84-like quantum key distribution protocols (BB84-INFO-z, standard BB84, efficient BB84, and modified efficient BB84) against the most general attacks, recovering the state-of-the-art 11% asymptotic error threshold and finite-key bounds that closely match the best known results. One defect survives in their bounds: a multiplicative factor m (the final key length) in the secrecy terms, produced by the hybrid triangle-inequality argument of their Proposition 6 and carried through Theorem 7 into the final finite-key bounds. The authors call this factor superfluous, note that state-of-the-art analyses contain no such factor, and state their intention to remove it in a future version; they also confine their method to BB84-like protocols and leave generalizations to broader protocol families for future research. The open problem is two-fold and unified by one objective - bringing this elementary proof method to full state-of-the-art parity in both tightness and scope: (1) prove the composable, general-attack security of the same protocols with finite-key bounds free of the m factor while preserving the proof's self-contained algebraic character, and (2) extend the same algebraic technique to at least one protocol family or practical-imperfection model outside the BB84-like class. No published removal of the m factor and no generalization of the method beyond BB84-like protocols is known: the problem remains open.

Background

Quantum key distribution (QKD) lets two parties, Alice and Bob, grow a shared secret key whose security rests on quantum mechanics rather than computational assumptions. The first QKD protocol, BB84 (Bennett and Brassard, 1984), encodes each raw key bit in a qubit prepared and measured in one of two conjugate bases (two orthonormal bases related the way position and momentum are, so that measuring in the wrong basis destroys the information). An eavesdropper, Eve, who couples to the transmitted qubits necessarily disturbs them; Alice and Bob estimate this disturbance by publicly comparing a random subset of their data (the TEST bits) and then apply error correction and privacy amplification - a public random hash that compresses Alice's corrected string, of which Eve has partial information, to a shorter final key of m bits about which Eve has essentially no information (the remaining bits are the INFO bits).

A satisfactory security proof must meet two demands. First, it must hold against the most general (unconditional) attacks: Eve may keep an arbitrarily large quantum memory and postpone her measurement until after the key is used. Second, it must be composable: the key must remain secure when used as a component inside a larger cryptographic task, not only when Eve measures immediately. Composable security is formalized by demanding that the joint quantum state of Alice, Bob, and Eve at the end of the protocol be close, in trace distance 12tr∣ρ−σ∣\frac{1}{2}\mathrm{tr}|\rho-\sigma| (the standard operational measure of how distinguishable two quantum states are), to the ideal state in which the parties hold a uniform key uncorrelated with Eve. Early BB84 proofs (Mayers 2001; Biham, Boyer, Boykin, Mor, and Roychowdhury - BBBMR - 2006) were not composable in this sense, and the BBBMR proof additionally supported only a 7.56% asymptotic error threshold: the error rate on tested bits above which the protocol must abort, in the limit of infinitely many transmitted qubits. Later proofs reached the 11% threshold (Shor and Preskill 2000; Renner, Gisin, and Kraus 2005), and modern finite-key analyses - bounds valid at a finite number nn of qubits rather than only asymptotically - give essentially optimal explicit key lengths (Tomamichel, Lim, Gisin, and Renner 2012; Hayashi and Tsurumaru 2012; Tomamichel and Leverrier 2017). These bounds are expressed through the binary entropy H2(x)=−xlog⁡2x−(1−x)log⁡2(1−x)H_2(x)=-x\log_2 x-(1-x)\log_2(1-x) and concentration inequalities such as Hoeffding's, which bounds the probability that an average of bounded random variables deviates far from its mean.

BBBMR's proof style is distinctive: purely algebraic manipulations of Eve's quantum state and trace distances, avoiding the entropic or decoupling machinery of other proofs, and self-contained apart from the BBBMR paper itself. Boyer, Liss, and Mor (2022) upgraded this technique in three ways: they replaced BBBMR's mutual-information estimates with trace-distance estimates, making the proof composable and unconditional against general attacks; they extended it to a class of generalized BB84 protocols - BB84-INFO-z (previously analyzed by the same authors against collective attacks only, i.e., attacks where Eve applies the same operation to every qubit), standard BB84, efficient BB84 of Lo, Chau, and Ardehali (where the two bases are chosen with non-uniform probabilities), and a simplified modified efficient BB84; and they recovered the 11% asymptotic threshold together with finite-key bounds that, in their words, match the state of the art 'pretty closely' - except for one defect. Their Proposition 6 bounds the trace distance between Eve's states for two candidate final keys kk and k′k' by chaining the triangle inequality across mm single-bit changes between kk and k′k', incurring a factor 2m2m that propagates through Theorem 7 into the final bounds, schematically

⟨ΔEve(k,k′)⟩  ≤  2mPr⁡[INFO-error rate≥t/n]+2 n[H2(t/n)−(n−r−m)/n],\langle\Delta_{Eve}(k,k')\rangle \;\le\; 2m\sqrt{\Pr[\text{INFO-error rate}\ge t/n] + 2^{\,n[H_2(t/n)-(n-r-m)/n]}},

where rr is the number of bits revealed during error correction. The authors state this mm factor is superfluous - state-of-the-art bounds carry no key-length prefactor, and since the factor multiplies only an exponentially small term it degrades finite-size tightness but not the asymptotic threshold - and that they intend to remove it in a future version. They further state that their method 'is currently limited to BB84-like protocols' and that further generalizations 'for future research' are left open. The proof also relies on two BB84-specific devices that any extension must replace: a symmetrization step (averaging Eve's attack over the basis choices so her attack takes a structured form) and an 'inverted-INFO-basis' comparison protocol.

Problem Statement

As left open by Boyer, Liss, and Mor (2022), the problem has two linked components serving one objective - bringing the self-contained algebraic composable proof to full state-of-the-art parity in both tightness and scope.

(1) Remove the superfluous key-length factor from the finite-key composable bounds. Prove composable, unconditional security of the generalized BB84 protocols (BB84-INFO-z, standard BB84, efficient BB84, and modified efficient BB84) against general attacks, within the paper's algebraic framework, with final finite-key bounds in which the secrecy terms carry no multiplicative factor m (the final key length). This requires replacing the hybrid triangle-inequality argument of Proposition 6 - which chains over the m key bits and produces the factor 2m2m in Theorem 7 and in bounds of the schematic form

⟨ΔEve(k,k′)⟩≤2mPr⁡[INFO-error rate≥t/n]+2 n[H2(t/n)−(n−r−m)/n]\langle\Delta_{Eve}(k,k')\rangle \le 2m\sqrt{\Pr[\text{INFO-error rate}\ge t/n] + 2^{\,n[H_2(t/n)-(n-r-m)/n]}}
  • by a direct argument, while preserving composability (trace-distance closeness to an ideal key state), validity against general attacks, and the proof's self-contained algebraic character. The resulting bounds should match the state-of-the-art finite-key form of Tomamichel-Lim-Gisin-Renner (2012), Hayashi-Tsurumaru (2012), and Tomamichel-Leverrier (2017) up to constants, and must contain no multiplicative factor mm in any secrecy term.

(2) Extend the algebraic method beyond BB84-like protocols. Using the same algebraic, composable trace-distance technique, prove unconditional composable security against general attacks, with explicit finite-key bounds, for at least one QKD protocol family or practical-imperfection model that lies demonstrably outside the 'generalized BB84' class defined in Section 3 of the source (i.e., not describable as the paper's random partition of qubits into INFO and TEST bits prepared in the two BB84 bases).

The source leaves the concrete targets of component (2) to future research, so a complete answer must identify its target explicitly and show it falls outside the source's class; the two BB84-specific devices of the source (attack symmetrization over basis choices and the inverted-INFO-basis comparison) must be replaced by corresponding arguments for the target. Neither component may be satisfied by weakening the security notion - restricting to collective attacks, dropping composability, or limiting the attack model otherwise - relative to the source.

References

  1. Michel Boyer, Rotem Liss, and Tal Mor, Composable Security of Generalized BB84 Protocols Against General Attacks, arXiv:2208.12154 (2022), doi:10.48550/arXiv.2208.12154, https://arxiv.org/abs/2208.12154
  2. Eli Biham, Michel Boyer, P. Oscar Boykin, Tal Mor, and Vwani Roychowdhury, A Proof of the Security of Quantum Key Distribution, Journal of Cryptology 19(4):381-439 (2006), doi:10.1007/s00145-005-0011-3, https://doi.org/10.1007/s00145-005-0011-3
  3. Charles H. Bennett and Gilles Brassard, Quantum cryptography: Public key distribution and coin tossing, Theoretical Computer Science 560:7-11 (2014 reprint of the 1984 conference paper), doi:10.1016/j.tcs.2014.05.025, https://doi.org/10.1016/j.tcs.2014.05.025
  4. Dominic Mayers, Unconditional security in quantum cryptography, Journal of the ACM 48(3):351-406 (2001), doi:10.1145/382780.382781, https://doi.org/10.1145/382780.382781
  5. Peter W. Shor and John Preskill, Simple Proof of Security of the BB84 Quantum Key Distribution Protocol, Physical Review Letters 85:441-444 (2000), doi:10.1103/PhysRevLett.85.441, https://doi.org/10.1103/PhysRevLett.85.441
  6. Renato Renner, Nicolas Gisin, and Barbara Kraus, Information-theoretic security proof for quantum-key-distribution protocols, Physical Review A 72:012332 (2005), doi:10.1103/PhysRevA.72.012332, https://doi.org/10.1103/PhysRevA.72.012332
  7. Hoi-Kwong Lo, H. F. Chau, and M. Ardehali, Efficient Quantum Key Distribution Scheme and a Proof of Its Unconditional Security, Journal of Cryptology 18(2):133-165 (2005), doi:10.1007/s00145-004-0142-y, https://doi.org/10.1007/s00145-004-0142-y
  8. Marco Tomamichel, Charles Ci Wen Lim, Nicolas Gisin, and Renato Renner, Tight finite-key analysis for quantum cryptography, Nature Communications 3:634 (2012), doi:10.1038/ncomms1631, https://doi.org/10.1038/ncomms1631
  9. Masahito Hayashi and Toyohiro Tsurumaru, Concise and tight security analysis of the Bennett-Brassard 1984 protocol with finite key lengths, New Journal of Physics 14:093014 (2012), doi:10.1088/1367-2630/14/9/093014, https://doi.org/10.1088/1367-2630/14/9/093014
  10. Marco Tomamichel and Anthony Leverrier, A largely self-contained and complete security proof for quantum key distribution, Quantum 1:14 (2017), doi:10.22331/q-2017-07-14-14, https://doi.org/10.22331/q-2017-07-14-14
  11. Michel Boyer, Rotem Liss, and Tal Mor, Composable security against collective attacks of a modified BB84 QKD protocol with information only in one basis, Theoretical Computer Science 801:96-109 (2020), doi:10.1016/j.tcs.2019.08.014, https://doi.org/10.1016/j.tcs.2019.08.014