[145709] in cryptography@c2.net mail archive
Re: "Thirty-Year-Old Encryption Formula Can Resist Quantum-Computing
daemon@ATHENA.MIT.EDU (David-Sarah Hopwood)
Sat Aug 21 19:07:00 2010
Date: Sat, 21 Aug 2010 23:26:26 +0100
From: David-Sarah Hopwood <david-sarah@jacaranda.org>
To: cryptography@metzdowd.com
In-Reply-To: <D3A21710-9438-4642-A0B8-E56CB3AB2AE9@gmail.com>
This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--------------enigA9B9D29C2B23000F229ACC57
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Alec Muffett wrote:
> This may[1] be relevant to your interests; alas I am not fit to review =
the math...
>=20
> http://www.popsci.com/technology/article/2010-08/quantum-computer-pro=
of-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 Fo=
urier
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=
=2E
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_q=
uantum_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.
--=20
David-Sarah Hopwood =E2=9A=A5 http://davidsarah.livejournal.com
--------------enigA9B9D29C2B23000F229ACC57
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.12 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iF4EAREIAAYFAkxwUuUACgkQWUc8YzyzqAf4JgD/V3JiWHWq1f15G+KDEhltiCwN
tby7BXOUt5fOjmhpUv0A/iF93YvVZSA6SY3k+elhWyrpIptrOJ6ngwo1oua7NptP
=Ms5b
-----END PGP SIGNATURE-----
--------------enigA9B9D29C2B23000F229ACC57--
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
