Adding support for Post-Quantum algorithms?

[mouse07410]

NIST is supposed to announce the new Post-Quantum standards for Key Encapsulation Mechanism and Digital Signature by the end of this January.

Any plans or efforts underway to support those algorithms in ring package?

[josephlr]

I mean the algorithms haven't even been released yet, and I thought standardization wasn't on track until 2024?

[mouse07410]

The results of the NIST PQC are to be announced by the end of January of 2022. Those will be the first standards: KEM and Signature. In the following two years more algorithms may be added to the standards - but those announced this January will remain "in force", regardless of whether other algorithms would be added or not.

[saolof]

Quick input as someone who has been following post quantum cryptography closely:

Regardless of which one gets accepted, all of the three generalized LWE based KEMs (NTRU, Kyber, Saber) and all SIS-based digital signature schemes (DiLithium, Falcon) use NTT multiplication of polynomial rings modulo a polynomial of the form x^k + 1 as one of the key fundamental operations necessary to make them run fast. So this would be a very useful primitive to provide.

So writing an optimized implementation of NTT fast polynomial multiplication with a Rust API would be a very useful concrete way to contribute for anyone willing to start working on post-quantum encryption for Ring, and should be useful regardless of what specific system gets picked. Here's a good recent reference on optimized implementations: https://eprint.iacr.org/2020/1397.pdf

Also, this would mean working a lot with rings, which would definitely add a layer of puns to this library. Having good ring multiplication implementations automatically makes implementing the various cryptosystems fairly straightforward.

Other things that are general-purpose but useful for some of the schemes includes cryptographically secure RNG for Gaussian and for Binomial distributions. Those are substantially harder than a uniform distribution RNG, and some of the schemes that use Gaussians can be attacked if their noise source is non-Gaussian, and this is arguably the hardest part to implement for those schemes.

[briansmith]

Of course I would like to have post-quantum algorithm support in ring. I think KEM is a higher priority than signatures at this point. But, also, I think we need more clarity about which algorithms people need, before we can get started.

[mouse07410]

I would like to have post-quantum algorithm support

Great!

I think KEM is a higher priority than signatures at this point

Absolutely.

I think we need more clarity about which algorithms people need, before we can get started

Obviously, people will need the winner(s). Also, people may like to have finalists available. Luckily, majority of them is Lattice-based, which could make it possible to support more than one algorithm. So, perhaps, it's time to start adding support for Lattice operations...?

Of the finalists, to me Kyber looks like the best choice - let's see whether NIST shares my opinion. ;-)

[saolof]

Yeah, if we're going to speculate about winners in this thread, I'd give an ~80% probability of DiLithium winning on signatures due to being the best default option for most uses. For the KEMs, I would give 45% - 25% - 30% probabilities for on Kyber - Saber - NTRU.

Saber and Kyber are fairly close in terms of technical merit but Kyber is cheaper to evaluate because it was designed for NTT multiplication from the start, while Saber has the advantage of being based on a deterministic problem and of not needing rejection sampling as a result. Both are better than NTRU which has a somewhat weaker safety assumption and runs slower, but due to complicated politics (NIST/CNRS dispute on Kyber and Saber) , NTRU could get the NIST standardization for non-technical reasons.

Classic McEliece and Sphinx+ will probably get some form of standardization as the significantly-less-practical but ultraconservative backups to add as a second layer for applications that need extremely strong security guarentees in the unlikely event that someone finds a quantum attack against structured lattices.

Some KEMs based on other methods may get standardization later (for example based on supersingular isogenies), but those have tradeoffs (SIKE has smaller keys but is two orders of magnitude more compute intensive), but overall the lattice methods and the CRYSTALS suite in particular seems to be the most practical default option in the near term, in combination with classical ECC crypto during the initial phase of adoption, and AWS & Cloudflare already have announced support for it in TLS. But the decision is up to NIST and whatever they choose will have the advantage of becoming the official standard which trumps any minor technical considerations.

[josephlr]

It's worth noting that the Open Quantum Safe (OQS) project has a fork of BoringSSL (https://github.com/open-quantum-safe/boringssl) that implements a ton of various KEM and signature algorithms. Might be useful as ring uses a subset of the BoringSSL code.

However, it seems that fork mostly just forwards stuff to https://github.com/open-quantum-safe/liboqs/ which has the actual implementations. It also has a great docs folder (https://github.com/open-quantum-safe/liboqs/tree/main/docs/algorithms/kem) containing a TON of references to other optimized implementations.

[joshsleeper]

heads up that NIST published their final selections just yesterday~

https://csrc.nist.gov/projects/post-quantum-cryptography/selected-algorithms-2022

[saolof]

Yeah, at this point the crystals suite looks like the best option to implement in order to support a general-purpose post-quantum option. Both KEMs and signatures need efficient ring operations and NTT ops for the ring Z_q[X]/(X^256+1) with q = 3329 = 0xD01 , and then build the algorithms on top of that.

[mouse07410]

@briansmith ping? Considering that the winners have been announced, and the intersection of NIST PQC results with CNSA-2.0 is

• Kyber
• Dilithium

Plus, NIST supports Falcon and SPHINCS++.

Submitters of the algorithms that were chosen already implemented tweaks they announced.

Could you share your plans for adding these algorithms (at the very least, Kyber and Dilithium) to ring? Thanks!

[josephlr]

Note that both CRYSTALS-KYBER (KEM) and CRYSTALS-DILITHIUM (Signature) are not yet standardized by NIST. It seems like Dilithium going to have some changes and Kyber's FO transform might be tweeked before standardization.

Maybe it makes sense to wait until the algorithm is frozen (and test vectors are fixed).

I agree that Kyber and Dilithium seem like the most promising candidates to include given that they won NIST PQC and are part of CNSA-2.0.

[mouse07410]

Note that both CRYSTALS-KYBER (KEM) and CRYSTALS-DILITHIUM (Signature) are not yet standardized by NIST.

Well, we're splitting hairs here. They are standardized, sans the (most likely minor) tweaks and changes, which have already been aired at the PQC-Forum. It's more obvious for Kyber, slightly less so for Dilithium.

Maybe it makes sense to wait until the algorithm is frozen (and test vectors are fixed).

The updates to Kyber are already on the PQ-CRYSTALS web site, and so are the new KAT vectors.

I'd say it makes sense to start putting placeholders in the code, adding implementations of the basic Lattice functions, etc.

I agree that Kyber and Dilithium seem like the most promising candidates to include

:-) You can say that, since NIST Draft Standards are expected to come out in a couple of months.

[briansmith]

I am willing to bring in BoringSSL's Kyber implementation:

• The ring Kyber support must be gated on a new feature named "kyber-c". The "-c" means "this requires a C compiler." This way, if/when Kyber is the last C code left in ring, people who are not using Kyber will be able to build ring without a C compiler. In other words, having a Rust implementation of Kyber won't block most people from using a no-C ring.
• The tests from BoringSSL for Kyber must be ported into ring's build system. This should be easy to do because the BoringSSL tests are already data driven crypto/kyber/kyber_tests.txt. Use ring::testfile::test_file! as other data-driven tests in ring do.
• The parts that use openssl/bytestring (CBB) in BoringSSL need to be rewritten in Rust using untrusted like other Parsers in ring. We most likely will not bring openssl/bytestring.h into ring.

PLMK if/when we want me to bring in the crypto/kyber/* files from BoringSSL.

[mouse07410]

@briansmith that would be great if Kyber can be added to ring. I've one question: why use a C implementation from BoringSSL instead of pure Rust implementation like https://github.com/Argyle-Software/kyber.git ?

[briansmith]

I moved (and slightly expanded) the Kyber proposal above into its own discussion: Issue :#1685. My proposal in #1685 is useful reading for three reasons:

1. It shows the "fast path" framework towards implementing post-quantum algorithms that BoringSSL already implements.
2. It provides a template for proposing adding any particular post-quantum algorithm to ring
3. It allows me to close this issue.

I'm closing this issue because each proposed algorithm should be discussed individually.