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