"Thirty-Year-Old Encryption Formula Can Resist Quantum-Computing Attacks That Defeat All Common Codes"

[David-Sarah Hopwood]

Alec Muffett wrote:
> This may[1] be relevant to your interests; alas I am not fit to review the math...
> 
>   http://www.popsci.com/technology/article/2010-08/quantum-computer-proof-data-encryption-researchers-look-formulat-created-1978

You're really better off reading the abstract:

<http://arxiv.org/abs/1008.2390v1>

The paper's actual title is "The McEliece Cryptosystem Resists Quantum Fourier
Sampling Attacks", which already explains its content much more clearly,
concisely, and accurately than the "popsci" article.

(I would argue, it does so even for an audience who doesn't know what the
McEliece cryptosystem or a quantum fourier sampling attack is. At least
they'll know that they don't know! Both are easy to look up on the web.)

Note that the result is about a variant of McEliece proposed by Janwa and
Moreno in 1996, not the original 1978 version.

I'll spare you all a more extensive rant about popular science journalism.
The actual result is not particularly surprising. It doesn't prove the
security of the Janwa/Moreno variant (either against quantum or classical
attacks), but it does prove that the presumed-hard problem on which that
variant is based, is not solvable by a class of quantum algorithms that
includes the Deutsch-Jozsa, Simon, and Shor algorithms (see
<http://en.wikipedia.org/wiki/Quantum_algorithm#Algorithms_based_on_the_quantum_Fourier_transform>).

This supports continued study of variants of McEliece as potential
"post-quantum" public key cryptosystems, but it doesn't do much more than
that.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20100821/0b7e3a4c/attachment.pgp>