Plans to implement post-quantum cryptography?

[jon-chuang]

Although standardisation is still several years away, I wonder if it might be interesting to implement some of the major variants of post-quantum crypto so people could play around with them and have a feel for how they might fit into future crypto.

Most implementations are now in C, so it could be interesting to port them to pure Rust.

This could be an experimental feature that could be built upon in the future as things get more serious.

[tarcieri]

We don't have any plans for this right now, or aside from the signatures repo a place to put them (e.g. KEMs).

If someone is strongly interested in working on post-quantum KEMs, I can make a KEMs repo.

[jon-chuang]

Hi Tony,

I would be interested in working on post-quantum (hybrid) KEMs. In particular, I would like to start with implementing BIKE.

From there, perhaps one of the LWE-based schemes (NTRU/NTRU Prime, NewHope, Kyber), or Rank-based (Rollo) and from there SIKE. At some point I might also venture into the Dilithium signature scheme and forgo its KEM cousin, Kyber. My priority for now is BIKE and an LWE scheme.

I would probably extract some of the common arithmetic into a separate module, which may become useful in the future since most proposed schemes share some underlying algebra.

By the way, are there any good examples of how I should call into the SIMD instructions in the SIMD repo? Although, this is something I will work on much later, perhaps.

[tarcieri]

I would be interested in working on post-quantum (hybrid) KEMs. In particular, I would like to start with implementing BIKE.

Great! I think it'd also be good to consider working on a trait for expressing KEMs. Pretty much every other type of cryptographic algorithm in this project has such a trait:

https://github.com/rustcrypto/traits

By the way, are there any good examples of how I should call into the SIMD instructions in the SIMD repo? Although, this is something I will work on much later, perhaps.

That repo is pretty much defunct. For modern SIMD implementations I'd suggest using core::arch directly to access the relevant architecture-specific intrinsics, and if you want some ready-made portable SIMD types, using the packed_simd crate, which implements the proposed std::simd API

[burdges]

These post-quantum KEMs require a considerably more flexible trait than many classical KEMs, although maybe the differences recede once you consider PAKEs, etc.

[tarcieri]

Fancier algorithms can still expose all of their functionality through methods on the struct while providing the "least common denominator" API via the trait.

[burdges]

I think CSIDH is only post-quantum key exchange in which both sides propose identical keys. We've no shortage of classical algorithms require identical keys from both sides, or other properties. Yes, once you say KEM then you've adopted non-identical keys, so what I'm saying is: algebra tends to wreck trait/typeclass/etc hierarchies.

[tarcieri]

I'm not sure what you're getting at @burdges. A unified KEM interface is definitely possible. As an example of one, check out libpqcrypto:

https://libpqcrypto.org/

[mberry]

If someone is strongly interested in working on post-quantum KEMs, I can make a KEMs repo.

I have one of the first round NTRUPrime algos written in pure rust with wasm bindings but it has changed somewhat for the second round, this may again change by final submission and regardless could end up shunned by the community, although openssh is using it experimentally.

Waiting for the NIST PQC standardisation project to finish up seems like a good idea for anyone wanting post-quantum KEMs and signatures. There was a lot of entrants into the project, this has now been pruned down to 28 for the second round, which is still a lot.

https://csrc.nist.gov/News/2019/pqc-standardization-process-2nd-round-candidates

https://github.com/MitchellBerry/Streamlined-NTRU-Prime

[tarcieri]

I noticed this issue was filed against the hashes repo... it should probably be filed under https://github.com/rustcrypto/traits instead?

Notably quantum attacks do not impact hash functions in a particularly severe way. I am only aware of two attacks that impact them: Grover and claw-finding attacks.

Grover theoretically reduces the preimage resistance by a factor of 2, meaning any digest with at least a 256-bit output should be PQ secure (at a 128-bit level).

Quantum computers have not been particularly helpful in finding collisions in hash functions either.

While I think PQ crypto is a great issue to discuss, IMO it doesn't impact this repo in particular, so I'm going to close this and suggest reopening it against the RustCrypto/traits repo.