Java implementation of a quantum computing resistant cryptographic algorithm | Hacker News Reader

Java implementation of a quantum computing resistant cryptographic algorithm

github.com

267 pointsmooreds55 comments

Hello everyone! I'm thrilled to see my project trending here on Hacker News. It's a pure toy implementation inspired by the paper and its reference. While it aligns with all the provided test cases, I wrote it primarily for fun and to see it work seamlessly with the standard JCE interfaces. If you have any questions or feedback, please don't hesitate to ask. Thanks for checking it out! Best regards, the author. :-)

Heya, what would it take to productionize it? Are you aware of any java libs for quantum proof cryptography that are production ready?

I'm not aware of any production-grade libs of these algorithms, but they might exist. While NIST did pick Dilthium as among the winners in summer 2022, it still hasn't been fully standardized yet. The mathematical principles are final, of course, but they still need to be documented in the form of a standard, with many other details specified, such as the ASN.1/binary encodings of keys, signatures, etc., so they can be used in the context of a broader PKI and certificates. Some of this is specified in the Dilithium submission (primarily because some of the values need to be encoded and processed as part of the algorithms themselves), but it doesn't cover everything and doesn't specify other details like OIDs, etc. This specification is also necessary before validation programs like FIPS 140-2 can get off the ground.

It looks great piece of work, and you even took the extra effort for JCE integration, congratulations.

Thanks a lot! :)

Most of the "meat" of this toy implementation of Dilithium can be found at https://github.com/mthiim/dilithium-java/blob/main/src/main/...

Here's the Dilithium specifications too: https://pq-crystals.org/dilithium/data/dilithium-specificati...

Is it a good idea to use quantum resistant crypto algorithm on-top of more established/widespread algorithms like RSA/ECDSA? I don't feel comfortable using quantum resistant crypto due to how cutting edge it all is.

It seems that's exactly what the community is doing.

Cloudflare recently enabled post-quantum cryptography, in which they're using X25519+Kyber [0]. Similarly, Signal's post-quantum cryptography also uses the same [1].

I'm guessing this spawned from the fact that a post-quantum algorithm was broken on classical computers a few years ago [2].

So now any attacker would have to break both the classical algorithm and the post-quantum algorithm.

[0] https://blog.cloudflare.com/post-quantum-to-origins/

[1] https://signal.org/blog/pqxdh/

[2] https://www.quantamagazine.org/post-quantum-cryptography-sch...

I've probably missed an important detail here, but if the post-quantum algo can be broken on classical computers, what use is it, vs. a combination of classical and quantum computers?

That algorithm was never chosen as a final candidate, unlike Dilithium and Kyber. Nevertheless, it remains intriguing because it advanced significantly in the competition until this vulnerability was identified, which allows for it to be cracked in just a few minutes on a standard computer. This underscores the inherent risk of rapidly introducing new algorithms, whether quantum or not. While RSA might become vulnerable to future quantum computers, its resilience since its public introduction in 1977 (aside from the need to increase key sizes) is quite an achievement. This is why new algorithms should always be paired with trusted classical algorithms to get the best of both worlds: if the new post-quantum component is flawed, at least you're not worse off than if you had used classical algorithms. On the other hand, if quantum computers capable of breaking practical sizes of RSA or ECC emerge, there's still the hope that the post-quantum element remains intact.

Isn't it possible to decouple the two components, that is break the post-quantum one on classical computer and the classical one on a quantum computer, essentially making this combination null?

Yes absolutely: If both security elements fail (quantum computers that break classical crypto appear, and the supposed post-quantum element turns out to be insecure as well) then you're screwed. By combining you get a chain is as strong as the strongest link - but not stronger! The motivation with combining is to avoid a scenario where you start using a new post-quantum algorithm which turns out to be really insecure (like happened to SPHINCS+) so you're actually worse off.

The algorithm that was broken is of course no longer used.

The point is: Many of these algorithms are rather new. The fact that multiple post quantum algorithms have been broken that were seen as promising shows that there is a risk with these new algorithms.

However, it should be said that the broken algorithms were in, let's say, more experimental subfields of post quantum cryptography.

At this point quantum computers aren't breaking anything. Adding protections against them is nice because we're theoretically safe in the future. We don't want to compromise our safety now by choosing algorithms that are less battle tested though, so it's best to layer them.

If it turns out that both the classical and quantum hard algorithms are weak we're just screwed, yes. That said, at this point it's not even clear, as far as I know, that many classical algorithms are event going to be broken under QC.

Agreed. While manufacturers do show an impressive increase in the number of noisy qubits, we still have yet to see a demonstration of quantum error correction at anywhere near the levels needed to pull of a QC that breaks e.g. RSA.

It's also unclear (to me, perhaps not to others!) if the conversion from O(2^n) -> O(2^n/2) means it will be faster in practice on quantum hardware.

https://eprint.iacr.org/2017/811

> Reassessing Grover's Algorithm

The proposal of this paper is that Grover's does not mean we need to double the size of symmetric keys to account for QM but that just a few extra bits are enough to prevent it from being efficient.

Of course, there may be new QM algorithms that don't suffer and, again, it's best to start preparing now and not later. But I think it's noteworthy for the discussion about quantum preparedness.

This conversion O(2^n) -> O(2^n/2) only applies to Grover's algorithm which can be used to break symmetric crypto (AES etc.). This is not the usual concern in the context of quantum computers because it just corresponds to halving the key space (in bits) which you can protect against by doubling the key size. So use AES-256 instead of AES-128. And the benefit by Grovers can only be had once. And as the paper you link to point out, maybe even that benefit is in question.

However, the main concern with quantum computers vs cryptography is Shor's algorithm which works on RSA and ECC. Shor's has the potential to take the problem from exponential (or at least close to exponential but sub, in the case of RSA) to polynomial O(n^3) which is much more powerful (essentially taking a log of the running time!). That is still assuming, of course, that workable quantum computers of required since will appear and that all the associated problems with that (noisy qbits etc.) are solved. Other challenges could also show up (difficulties scaling for longer computations, more passes through quantum gates, larger super-positions or even that the quantum laws governing e.g. probability amplitudes don't hold with full accuracy at such scales).

Yeah, my point was more that there's a lot of "this QM version of the algorithm destroys that crypto scheme" when it may be a lot more nuanced. I used Grover's as an example of that - on its face Grover's implies that you need to double the key size to be safe but there's reason to believe that that's not true in practice. I assume that may be the case with Shor's as well.

The best thing to do is to layer them, as is standard.

Secure transports are built out of asymmetric key agreement and symmetric bulk encryption, glued together with symmetric hashes. The symmetric cryptography isn't meaningfully threatened by any QC we're yet aware of. Hybrid PQC/classical schemes do two key agreements (an ECC kex and a LWE kem), and then plug both results into HKDF (conceptually: a symmetric hash) to derive a shared secret.

In that scheme, you have to compromise both the PQC and ECC key agreements, independently.

It was “a” post quantum proposed algorithm, not “the” post quantum algo. Don’t judge an entire field because of one proposal that didn’t work.

It was broken because of a mathematical breakthrough using theory lurking in the dark corners of math. The protocol itself was also using some somewhat dark corner of math.

Which is why having as many eyes as possible is important.

Now it's very well possible that it comes back with mitigations.

And even the still OK candidates are using a young area of math.

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.

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.

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.

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.

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.

Yes, the current generally-but-not-universally-accepted standard is "hybrid encryption" (not the same "hybrid" as KEM/DEM, though you'd generally use hybrid encryption with a hybrid KEM/DEM cryptosystem), which ensures that you'd have to break both classical and post-quantum algorithms to get at your plaintext. Whether you simply wrap encryptions or use a hybrid KEM combiner (see, e.g., Campagna and Petcher for examples) is a more subtle question better suited for more subtle minds than mine.

If quantum computers become more practical in our lifetimes, we don't want our current secrets vulnerable to that analysis. Scaling a quantum computer definitely isn't as simple as the evolution from valves and transistors was to integrated circuits ... but estimates from experts on the difficulty vary from "this is very very very difficult" to "this will remain physically impossible". Either way that's still more likely than brute-forcing an encryption key with modern standards; so there's a rationale for prioritizing post-Quantum security today.

That said, you are right to be wary; if there is a side-channel or implementation vulnerability in a PQ algorithm ... then you are much worse off using it. Worst-case; imagine an RCE in the PQ implementation. So it's a good idea to be cautious and check the code rigorously.

There’s no real risk to schemes that use both post-quantum and conventional crypto in such a way that a break in either is insufficient to bring down the combination. For key exchanges that’s quite easy; you can just XOR or concatenate the outputs depending on the scheme.

Yes, I think so. More widespread algorithms have been far more thoroughly studied; they've been studied for longer and stood the test of time. Their weaknesses, and how to counter them, are better understood. They're busted by general-purpose large scale quantum computers, though, if those ever happen. Combining their strengths sounds like the best approach where data is very sensitive and the overhead is acceptable.

The readme mentions a dependency on Bouncy Castle - note that BC already contains several Java-based PQC signature schemes, see https://doc.primekey.com/bouncycastle/interoperability#Inter... and https://github.com/bcgit/bc-java

A few days ago Daniel Bernstein warned about effort by NSA to spread flawed implementations of post quantum crypto (can't find the link)

Here is the article you mentioned, although it addresses Kyber, not Dilithium.

https://news.ycombinator.com/item?id=37756656

There have been two posts by djb in the month of October on this topic. I'm not sure which slim was talking about but the newest one was published today:

https://blog.cr.yp.to/20231023-clumping.html

I believe there is an HN submission on it already.

I wrote/ported a single file Java implementation of another of the post quantum signature schemes - sphincs+ here:

https://github.com/Peergos/sphincsplus

> The cryptographic algorithms RSA and ECC have long been known to be vulnerable to attacks using quantum computers via Shor's algorithm.

If this is true and quantum computers of that size do come into existence how does it impact Bitcoin?

They would get migrated before it became an issue. And even if it happened, they'd just fork it with a quantum resistant encryption at the point of first known attack.

How on earth would they patch all the historical blocks?

It could be as simple as just creating a special fork block that contains a sequence of every old block's new hash.

> This is a "for fun" implementation written in a couple of days. It's not intended to be production-grade code. No warranty or support of any kind is provided. However, it can be useful for diving into and experimenting with post-quantum algorithms. Use it at your own risk. If you don't like those terms, you must refrain from using this software.

Thought it was gonna be OTP ;)

Reply on news.ycombinator.com