In a new paper Peter Shor extends his quantum algorithm to solving a variant of the Closest Lattice-Vector Problem in polynomial time. With some future tweaking it can be used against the entire family of Lattice based crypto.
While an error in the calculations has been pointed out and the paper will be withdrawn, this isn't reassuring since a revised version where this still holds is probable.
Its available on arxiv until Monday so grab a copy before then:
https://arxiv.org/pdf/1611.06999.pdf
Without Lattice crypto we're stuck with some very ugly choices as Isis pointed out. McEliece is huge. SIDH is slow and brittle. The PQ future looks grim fam :(
On 11/26/2016 07:50 AM, bancfc@openmailbox.org wrote:
While an error in the calculations has been pointed out and the paper will be withdrawn, this isn't reassuring since a revised version where this still holds is probable.
Where was this discussed or announced? I'm curious what the issue was. It will be very groundbreaking if Eldar and Shor can fix it.
3) on Scott Aaronson's blog post and the discussion in the comments is the most information I've seen. |http://www.scottaaronson.com/blog/?p=2996
On Sat, Nov 26, 2016 at 9:36 AM Jesse V kernelcorn@torproject.org wrote:
On 11/26/2016 07:50 AM, bancfc@openmailbox.org wrote:
While an error in the calculations has been pointed out and the paper will be withdrawn, this isn't reassuring since a revised version where this still holds is probable.
Where was this discussed or announced? I'm curious what the issue was. It will be very groundbreaking if Eldar and Shor can fix it.
-- Jesse
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
On 2016-11-26 18:36, Jesse V wrote:
On 11/26/2016 07:50 AM, bancfc@openmailbox.org wrote:
While an error in the calculations has been pointed out and the paper will be withdrawn, this isn't reassuring since a revised version where this still holds is probable.
Where was this discussed or announced? I'm curious what the issue was. It will be very groundbreaking if Eldar and Shor can fix it.
It seems the flaw found was fatal to the whole algorithm rather than a minor error. Unfortunately no details were posted by the cryptographer who found them - only a statement that lattice crypto was still safe:
https://groups.google.com/forum/?_escaped_fragment_=topic/cryptanalytic-algo...
" Dear all,
Yesterday Lior Eldar and I found a flaw in the algorithm proposed in the arXiv preprint. I do not see how to salvage anything from the algorithm. The security of lattice-based cryptography against quantum attacks therefore remains intact and unchanged.
Regards, Oded "
-
bancfc＠openmailbox.org -
Jesse V -
zaki＠manian.org