Hacker News Reader

Comment by ggm | Hacker News Reader

I asked some people a few years back if some equivalent to Moores law on the qbit size, and what it meant for cryptography applied. Their answer was that there wasn't good evidence of a direct linkage at the qbit density we had now, to achievable breaks in RSA, but that also the fundamental metric was probably wrong right now. Yes, how many qbits is interesting. But also how stable they are, how many states you can demonstrate, which specific solutions you target in open questions which QC can address.

View on HN

My area of research is primarily post-quantum cryptography, not strict quantum mechanics. That said, based on my understanding of the implementation details of quantum computers (as opposed to e.g. quantum complexity), I’m pessimistic about quantum computers being productively used against real world RSA in the next 20 years. I’d conservatively estimate that it could happen in 50 with a series of breakthroughs.

I think quantum computers will be useful for some applications (maybe even many) and commercially available within the next decade or two, I just don’t think cryptographic breaks will be possible on them until they advance well beyond whatever is first brought to market. You need logical qubits for polynomial-time cryptanalysis of RSA, and many of them. To get these logical qubits, you need so many more physical qubits that it’s not really productive to map our current records (~50 qubits) to what we’d need. In fact, I predict we’ll get to quantum cryptanalysis via a paradigm shift that approaches the problem in a fundamentally different way long before we master the requisite error correction to have enough physical and logical qubits necessary under the current paradigm.

Are quantum computers useful for cryptanalysis in the case where you don't quite have the necessary number of qubits? Like let's say you want to factor an integer N, which would require n qubits, but you have a QC with only n/2 qubits. Could you use the QC to narrow down the search space and then finish with a classical computer, or is the QC completely useless in this case?

The article mentions this problem, and there seems to be a concept emerging that is called "volume": Basically, how complex the algorithm can be you can run on a quantum computer, taking into account the number of qubits, their error rate, the stability, ...

I hope that we see some analysis done on this subject in the near future, because the rising uncertainty regarding current public-key tech is starting to get difficult for certain businesses.

This is a very active area of research in theoretical cryptography, and has been for over a decade. It’s an area that I myself work in. The uncertainty is not quite what you think: researchers more or less know what will happen to public-key cryptography, and to which cryptosystems. We also have credible proposals for encryption, key exchange and digital signatures. The uncertainty is when quantum computers will be practical, not what will happen when they are.

Contemporary research is predominantly concerned with improving computability efficiency or security proofs for underlying complexity characteristics.

> The uncertainty is when quantum computers will be practical, not what will happen when they are.

That's what I meant above; I apologize for I should have been more clear in my wording.

Ah, no worries. Post-quantum cryptography has a reputation for being somewhat excessively theoretical (which to be fair is a reasonable argument). But there are benefits other than post-quantum security. For example, lattice problems can provide security according to worst-case hardness, whereas factoring problems can only provide average-case hardness.

In other words, for some lattice problems, we can prove that breaking the cryptosystem is equivalent to breaking every instance of the lattice problem, but factoring problems only guarantee that breaking the cryptosystem is equivalent to breaking a subset of problems from some distibution. The former is a much stronger security assumption (though in practice this comes with its own set of challenges).

It’s an exciting area of research.

There is a Public crypto system based off error correcting codes that is quantumly secure. It's the McEliece cryptosystem, it's about as old as RSA. However, the key sizes are in 10's of thousands to 100's of thousands of bits.

From my reading most crytographers think it's is secure. So if you need it now. You could probably get away with using it. However, one should have a decent explanation to why use a less well known algorithm. It's probably had less eyes looking at so a major flaw/attack could exists, but it's not if one does exist.

McEliece has had significant cryptanalytic attention since the 70s, when it was first invented. In fact, it’s probably the most well studied post-quantum proposal, and it’s not really waiting on any further cryptanalysis. It’s currently considered secure (with binary Goppa codes) and has modes for both encryption and digital signatures via Neiderreiter, but it doesn’t support key exchange.

The real issue, as you touched on, is key size. There are production deployments of the cryptosystem, but it’s actually a bit worse than your numbers if you’re looking for post-quantum resistance. In the post-quantum secure setting, McEliece uses public keys that have an upper bound of over 1MB (around 8.5 million bites specifically) in order to achieve 128-bit security.

Fortunatly McEliece is not the only proposal we have, and error correcting codes aren’t the only computational problem being studied. We also have credible proposals from lattices, hashes, multivariate polynomial equations and (most recently) supersingular elliptic curve isogenies.

From my research so far it looks like SIDH is the most promising candidate to upgrade existing protocols (relatively congruent to ECDH; "small" key sizes).

For proprietary protocols the "newiness" of pq-crypto doesn't seem to be a big problem per se, just use curve hardening (kdf(ECDH || pq-kex)) in case the pq-crypto is broken (either due to implementation defects or cryptanalysis).

It depends on the application. SIDH is attractive because it doesn’t throw out decades of elliptic curve mathematics because of the spectre of quantum computers. The mathematics is a bit more familiar if you squint at it, though working with isogenies themselves is still very different from normal elliptic curve cryptography. But more importantly, a codebase that implements elliptic curve arithmetic can port much of that functionality to implement SIDH.

And yes - SIDH is also attractive because of the small key sizes. But it’s also significantly slower than lattice-based key exchange using something like Learning With Errors (LWE). In practice the decision comes down to time versus space constraints: if your application is space-poor and time-rich, SIDH is a good proposal for key exchange. This looks especially nice in the context of IoT devices. But if your application is space-rich and time-poor, SIDH looks less attractive in favor of other options.

Reply on news.ycombinator.com