1. 8

  2. 10

    The authors of the paper estimate that attacking a terabyte-size key using Shor’s algorithm would require around 2^100 operations on a quantum computer

    What the hell? Aaronson’s objection is exactly right; this is a silly idea. Impractically large keys, stupidly long encrypt/decrypt times, all to get a mediocre constant-factor benefit over the current best factoring algorithm. It would be easier, faster, and cheaper to send a one time pad via courier.

    Why quantum computers actually might not break asymmetric crypto is that (so far) we’ve only figured out how to get exponential quantum advantages on certain kinds of abelian group structures. Unfortunately, this includes reduced residue sets and elliptic curves, so RSA and ECDSA are out.

    1. 2

      Since all (currently available) asymmetric crypto relies on algorithms (RSA & ECDSA) that are in BQP I would say that quantum computers are able to break asymmetric cryptography. As far as I know there are no popular algorithms in NP that lend themselves to asymmetric cryptography (although I heard about one that is patented in a side remark), so really the only thing keeping the current status alive is the problem of scaling quantum computers to process real world key sizes.

      But yeah, that article really suggests a solution that will simply not hold up in the long run, since a quantum computer can still solve the problem in polynomial time, no matter how long the key is.

      1. 6

        There are several asymmetric schemes not known to be in BQP. Lattice-based cryptography is promising

        1. 3

          Yeah unfortunately it isn’t really used so far, but maybe it will change if BQP becomes computable with a feasible amount of money and effort.

          Still, lattice-based cryptography is the only asymmetric crypto I’ve heard of before and I am not sure how well tested or verified this approach or the others are. To be fair; I haven’t really been keeping up with the topic so my opinion isn’t all that up to date.

          1. 4

            There’s some mentioned here by category:


            NTRU is commercialized and probably deployed for that reason:


            There’s been recent work improving Merkle Trees where you can do a ton of signatures with them. Such a scheme might work for one-to-many distribution or one-to-one integrated into an IM. One already uses McEliece but I have no idea of its implementation quality.