A Tricky Path to Quantum-Safe Encryption

Quantum computers, once seen as a remote theoretical possibility, are now widely expected to work within five to 30 years. By exploiting the probabilistic rules of quantum physics, the devices could decrypt most of the world’s “secure” data, from National Security Agency secrets to bank records to e-mail passwords. Aware of this looming threat, cryptographers have been racing to develop “quantum-resistant” schemes efficient enough for widespread use. But last October, cryptographers at the Government Communications Headquarters (GCHQ), Britain’s electronic surveillance agency, posted an enigmatic paper online that called into question the security of some of the most efficient lattice-based schemes.

The findings hinted that vulnerabilities had crept in during a decade-long push for ever-greater efficiency. As cryptographers simplified the underlying lattices on which their schemes were based, they rendered the schemes more susceptible to attack. Building on the GCHQ claims, two teams of cryptanalysts have spent the past year determining which lattice-based schemes can be broken by quantum computers, and which are safe -- for now.