Structured Codes Improve the Bennett-Brassard-84 Quantum Key Rate

A central goal in information theory and cryptography is finding simple characterizations of optimal communication rates under various restrictions and security requirements. Ideally, the optimal key rate for a quantum key distribution (QKD) protocol would be given by a single-letter formula involving optimization over a single use of an effective channel. We explore the possibility of such a formula for the simplest and most widely used QKD protocol, Bennnett-Brassard-84 with one-way classical postprocessing. We show that a conjectured single-letter formula is false, uncovering a deep ignorance about good private codes and exposing unfortunate complications in the theory of QKD. These complications are not without benefit—with added complexity comes better key rates than previously thought possible. The threshold for secure key generation improves from a bit error rate of 0.124 to 0.129.