GCHQ boffins quantum-busted its own crypto primitive

While the application of quantum computers to cracking cryptography is still, for now, a futuristic scenario, crypto researchers are already taking that future seriously.

It came as a surprise to Vulture South to find that in October of this year, researchers at GCHQ's information security arm the CESG abandoned work on a security primitive because they discovered a quantum attack against it.

Presented to the ETSI here, with the full paper here, the documents outline the birth and death of a primitive the CESG called Soliloquy.

Primitives are building blocks in the dizzyingly-complex business of assembling a cryptosystem: individual modules that are expected to be very well-characterised before they're accepted into security standards (and, in the case of crypto like RC4, dropped when they're no longer safe).

Given that improving computer power is one of the ways a primitive can be broken, there's a constant background research effort into both creating the primitives of the future, and testing them before they're adopted – and that's where Soliloquy comes in.

As the CESG paper states, Soliloquy was first proposed in 2007 as a cyclic-lattice key exchange primitive supporting between 3,000 and 10,000 bits for the public key. Between 2010 and 2013 – presumably as part of their effort to case-harden the primitive before releasing it into the wild – the boffins (Peter Campbell, Michael Groves and Dan Shepherd) developed what they call “a reasonably efficient quantum attack on the primitive”, and as a result, they cancelled the project.

The quantum algorithm they describe would work by creating a quantum fingerprint of the lattice Soliloquy creates; “discreteise and bound” the control space needed; and run a quantum Fourier transform over that control space, iteratively to get lots of samples approximating the lattice.

That's where the quantum attack is complete: after that, the samples would get fed into a classical lattice-based algorithm to recover the values you want – in other words, the key.

The main challenge, the authors write, is to define “to define a suitable quantum fingerprinter” that could handle the control space.

As the researchers drily note in their conclusion, “designing quantum-resistant cryptography is a difficult task”, and while researchers are starting to create such algorithms for deployment, “we caution that much care and patience will be required” to provide a thorough security assessment of any such protocol. ®