Hacker News Reader

Comment by Deukhoofd | Hacker News Reader

As far as I'm aware, Shor's Algorithm is still unfeasible because it requires far more qubits than currently available to execute in any reasonable time. It'd require several million qubits, while the most cutting-edge devices currently only have a couple of hundreds at best.

I wouldn't worry too much about post-quantum algorithms for any production code in the next couple of years (decades?) myself.

View on HN

Quantum factoring may not be quite as far distant as you might think

Most importantly, Shor is not the algorithm of choice for first-gen hardware where the central challenge is likely to be circuit depth due to error correction overhead. The current front-runner is a probably proposal by Regev [0] with a space-optimization by Ragavan et al. [1], which factors an n-bit integer with O(n log n) logical qubits and a circuit depth of O(n).

What you should be looking for when studying quantum computing press releases is "fault tolerance": A central problem in QC is that the underlying hardware needs to be better than an (architecture-specific) threshold, before error-correction can be applied without introducing more errors than it corrects.

Nobody has really crossed the threshold yet with scalable hardware, and when someone does, the overhead will be abysmal (2 or 3 layers of error correction, each with a factor ~100 overhead in space and time). Still, there are two reasons to be optimistic:

One reason is that once a system crosses the threshold, any improvement in hardware will result in exponential improvements in the encoded operations, meaning that there will be a Moore-style exponential development.

Another reason is that there are several "dark mode" VC-funded companies working towards intrinsically scalable systems based on optical QC: If any of these achieve fault tolerance, they will be scalable from day one.

[0]: http://arxiv.org/abs/2308.06572 [1]: http://arxiv.org/abs/2310.00899

I'd probably be looking at a shorter timeline, just because of the Harvest Now, Decrypt Later strategy[0].

[0]: https://en.wikipedia.org/wiki/Harvest_now,_decrypt_later

I'd say it ultimately depends on the information you're encrypting. Information and secrecy around it often has some sort of temporal/time relationship tied to the information and surrounding context. If it's something you wish to protect indefinitely or for a long time into the future, it's important to consider now. If n the other hand it's some rotating fairly randomly generated password that expires monthly, quarterly, whatever or say session information that expires after a period then you don't need to worry so much about this. Context of the information you're protecting is important to determine time periods you wish to protect it for and you should already be considering this today when choosing protection strategies, IMO.

If it's a password, sure, rotating it every once in a while should secure your account if someone has stored a copy of the encrypted (usually hashed) version; that said, rotating passwords is no longer a recommended practice, and second, it's more important for encrypted data, like hard drives, online e2e-encrypted chats, internet usage, images/files, etc. You can change the password / key on those too, but if someone already has a copy of the old password encrypted data it may be cracked later on.

In practice this is probsbly reserved for important people I suppose.

That's an approach that makes sense in theory, but in practice you're almost certainly better off assuming a long time horizon for protecting everything.

For one thing, it's not always obvious what's short term vs long term information and you could end up applying short term protection to information that has long term value in a scenario you didn't consider. For example, encrypted session information that expires might not be useful in gaining access to an account, but it could potentially be used to track you in historical data.

The other problem is that most systems (and people) aren't great at segregating information that needs short term vs long term protection, so it's hard in practice to have a strategy based on applying different cryptographic protection to different information. Most encrypted protocols and systems deal with a mix of information that ranges from inconsequential if revealed even now to requiring long term confidentiality because it's much harder to try to deal with that information separately. There's also the practical argument that once I have a protocol or system to protect high value, long term info, why wouldn't I just use that for everything? Modern HTTPS is ridiculous overkill for the vast majority of things it protects, but there's really no reason to use something worse even if you could get away with doing so.

This is basically the premise of HTTPS everywhere and similar encrypt all the things concepts. It makes a lot more sense to just protect everything instead of trying to figure out what needs protection and what doesn't and hoping you didn't get it wrong or that nothing changes over the years. Same goes for post-quantum crypto. You might be OK not adopting it for things you think don't need protection beyond the time a practical quantum computer comes around (good luck guessing that time horizon btw), but it's both easier and less error prone to just post quantum all the things.

You also probably want post-quantum crypto if you're making anything that can be updated, and there's a chance the thing may sit in a drawer for 10 years before being connected to the internet. The crypto you use to authenticate an update's origin needs to still be secure at take-out-of-drawer time.

True - on the other hand, that fear/principle could be applied to all algorithms that could theoretically be broke in the future. There's a lot of uncertainty concerning the scalability of quantum computers and quantum error corrections. In the neare future it seems more likely that the post-quantum algorithms might be broken (even on normal computers) compared to quantum computers cracking RSA/ECC (so one should at least combine to get the best of both worlds)

This exact sentiment is why passwords are still hashed Unding md5. While I wouldn't exactly worry about Post-Quantum right now, it's important to implement and be ready to switch.

Encrypted data is almost certainly being recorded now in anticipation of quantum computers being able to break it later.

The NSA's Utah datacenter has to store something!

I think the fear people have is an attacker storing captured encrypted data and decrypting it later. It may be five or ten years out of date by the time it is decrypted, but even then it could still prove to be fruitful for the attacker.

I'm sure many oppressive regimes would love to know what their citizens where privately talking about, even if it was ten years ago. I think its a valid concern that quantum computing might take off, and in ten years you could run shores algo on an AWS instance. Long con attackers could MITM chats for juicy blackmail in the future.

> I wouldn't worry too much about post-quantum algorithms for any production code in the next couple of years (decades?) myself.

For data in transit that's probably fine, but for data at rest, you have to consider how long that data might remain at rest. If you have 30 year old encrypted data that is now breakable, is that a problem? It depends on the use case.

Also keep in mind that any data in transit could be tapped and saved and become data at rest.

So really you have to ask yourself, is it critical that this data remain encrypted in 20 years?

I'd agree. I'd say adversaries are unlikely to steal data now, wait a decade or two, and then decrypt on a quantum computer for _most_ private company ip. It's only relevant to government at this stage, yet Congress is, unsurprisingly, out-of-touch (or perhaps age?) in this regard.

Fun fact: I emailed my senator, chair of the foreign relations committee, on concerns over China's heavy investment here. I got a reply from an overworked intern about banning Tiktok !

This recently released page might be of a lot of interest to this discussion regarding crypto algorithms and the size of the quantum hardware needed. (Disclaimer, I work on the Azure Quantum team that builds this).

https://quantum.microsoft.com/en-us/experience/quantum-crypt...

Also, some interpretations of Quantum Mechanics, like Dioshi-Penrose objective collapse interpretation, imply a physical limit on the number of qubits.

However, whether you should worry about post-quantum crypto or not is a risk assessment question, not a physical one.

Do any interpretations not have such a limit?

Many-worlds etc. does not have such a limit. There are interpretations that posit that collapse is triggered by the system reaching a certain size (also GRW theory etc.). Such interpretations would preclude big quantum computers. Note that such interpretations aren't purely interpretations because they actually do posit measurable new physical phenomena. But since the relevant experiments are not currently possible to carry out and since they do have significant interpretational consequences, they are often called intepretations.

Reply on news.ycombinator.com