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 …

[Dan 55]

Reasonably efficient quantum attack on the primitive (which supports 3000-10000 bits as public key)

Are we meant to assume from dates that this happened that they now own TLS which manages 1024-2048 bits for the public key or just that they're not very good at rolling their own security?

[Anonymous Coward]

The maths is trivial

If you're a (very) hard core maths researcher indeed ... average, ordinary post-doctorate researchers may want to stay away unless you've a few years to do the background research AND have an academic maths department to back you up AND a major cryptography background built up over many years. If it takes three researchers several years to work on this level of abstraction, most mere mortals aren't going to do it within a couple of lifetimes ...

[amanfromMars 1]

I Kid U Not

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.

It is naive to not imagine that another/other projects which supremely attack and overwhelm quantum communications with primitive algorithms is not the AI which Stephen Hawking alludes to in the passing of his thoughts by machine and as commented on here …… http://forums.theregister.co.uk/forum/1/2014/12/02/hawking_gets_replacement_comms_system/#c_2376863 ……. and that the likes of a GCHQ/CESG, to name but one small wannabe cog in a giant intelligence machine, are not slabbering at the bit to be leading everything with IT efficiently.

And yes, it can be beautifully easily used and abused and misused to deliver practically anything virtually anonymously.

[Dan 55]

Re: I Kid U Not

I knew you wouldn't let us down.

[TRT]

My brain started whistling about half-way through that. :(

[The elephant in the room]

"...like blowing up a balloon?"

We've had the Science Officer technobabble; now we need the simplistic analogy!

[John Savard]

Interesting

This article prompted me to do some searching. Apparently this cryptographic primitive belongs to the Goldreich-Goldwasser-Halevi family. Since it uses the Closest Vector Problem, and works by disguising an easy lattice as a hard one, it seems to me that it might have the same basic flaw that torpedoed the knapsac ciphers - the underlying problem is hard, but disguising an 'easy' knapsack as a 'hard' one was the key, the disguises weren't proven hard to see through.

[Wzrd1]

News at 11, *live*ish

Scientists review their work an then reconsidered the poor timing chosen press release.

[Sheep!]

"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."

You lost me at "The.."

[Dr Patrick J R Harkin]

"3000-10000 bits"

How many Olympic swimming pools is that?