[Ach] "New algorithm shakes up cryptography"

[Aaron Zauner]

Hanno Böck wrote:
> On Sun, 18 May 2014 18:55:28 +0200
> Aaron Zauner <azet at azet.org> wrote:
> 
>> Hanno Böck wrote:
>>> I had mail contact with one of the authors today and also talked to
>>> someone who was at the talk, it's basically "just" the final
>>> version of the paper that was preprint-released last year.
>> It seems to extend it a bit though?
> 
> From what I'm aware of no. I had some jabber discussions about it with
> Tanja Lange, who was at the Eurocrypt conference in the presentation. It
> is the same algorithm, it just contains some fixes for errors that were
> spottet in last years version of the paper.
> 
> I'm aware not all people here speak german, but for the ones who do, I
> wrote a text about the whole thing yesterday:
> http://www.golem.de/news/kryptographie-schnellerer-algorithmus-fuer-das-diskrete-logarithmusproblem-1405-106547.html
Going to read that in a minute.

> Possible but from what I heared not very likely. See e.g. Schneier:
> https://www.schneier.com/blog/archives/2013/08/the_cryptopocal.html

I've read that before. I'm not a mathematician so it's hard for me to
see if papers such as this one are going to trigger further research in
that direction that may eventually become relevant to real-world crypto.
Of course we can always increase keylenghts. But some of the proposed
post-quantum crypto systems (e.g. lattice based crypto) are just not
feasible nowadays because they use such huge keysizes; theoretically:
once that overlaps - you can safely which (at this point post-quantum
crypto still lacks the cryptanalysis that factoring and DLP based crypto
has gone through in the last 30 years).

> I heared a number of times recently when physicists said things like
> "maybe in 10 years", so I'm a bit more worried about quantum computers.
I've sat through a talk by D-Wave last autumn (here are some of the
slides I managed to take pictures of: https://imgur.com/a/h2TxL). What
they currently do is to /simulate/ a quantum computer. Not very
efficiently. They are very far from a point where they can even think
about implementing shor's algorithm. SC is a great conference and some
of the best people in physics and maths are going there - as such the
Q/A was really interesting, because a lot of very skeptical physicists
were asking questions about the design and applicability.

On the way back to europe I got to read a general article about quantum
computing in CACM, there are some 10 different approaches to this, with
D-Wave taking only one and no clear path on which one will eventually be
useful, It's a good read:
http://cacm.acm.org/magazines/2013/10/168172-a-blueprint-for-building-a-quantum-computer/abstract
(this CACM issue also features a couple of extremely interesting
articles on HFT, btw)


Aaron

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: OpenPGP digital signature
URL: <http://lists.cert.at/pipermail/ach/attachments/20140518/7ae77bc5/attachment.sig>