ntrust-native

A safe pure-rust implementation of the NTRU post-quantum scheme.

• NTRU is a lattice-based key encapsulation mechanism (KEM)
• The implementation is based on the NTRU reference implementation of NIST round 3
• The implementation does not utilize any concurrency techniques (SIMD/threading/…, except maybe auto-vectorization on your CPU)
• It depends on tiny-keccak as SHA-3 implementation and aes as AES block cipher (used as RNG) implementation
• It passes the 100 testcases of the C reference implementation
• It implements the NTRU-HPS (Hoffstein-Pipher-Silverman) scheme in three variants
• It implements the NTRU-HRSS (Hülsing-Rijneveld-Schanck-Schwabe) scheme in one variant
• The implementation takes between 20 milliseconds (ntruhps2048509) and 45 milliseconds (ntruhps4096821) to run on a modern computer
• The implementation is constant-time on software instruction level
• The random number generator is based on AES256 in counter mode
• NTRUst is the name of a WebAssembly implementation. Thus, this implementation is called ntrust-native.

Who should use it?

Anyone, how wants to use the NTRU scheme to negotiate a key between two parties.

How does one use it?

Add this to your Cargo.toml:

[dependencies]
ntrust-native = "1.0"

To use a specific NTRU variant, you need to import it with the corresponding feature flag:

[dependencies]
ntrust-native = { version = "1.0", features = ["ntruhrss701"] }

The simple example illustrates the API:

use ntrust_native::AesState;
use ntrust_native::{crypto_kem_dec, crypto_kem_enc, crypto_kem_keypair};
use ntrust_native::{CRYPTO_BYTES, CRYPTO_CIPHERTEXTBYTES, CRYPTO_PUBLICKEYBYTES, CRYPTO_SECRETKEYBYTES};

use std::error;

fn main() -> Result<(), Box<dyn error::Error>> {
  let mut rng = AesState::new();
  let mut pk = [0u8; CRYPTO_PUBLICKEYBYTES];
  let mut sk = [0u8; CRYPTO_SECRETKEYBYTES];
  let mut ct = [0u8; CRYPTO_CIPHERTEXTBYTES];
  let mut ss_alice = [0u8; CRYPTO_BYTES];
  let mut ss_bob = [0u8; CRYPTO_BYTES];

  crypto_kem_keypair(&mut pk, &mut sk, &mut rng)?;
  crypto_kem_enc(&mut ct, &mut ss_bob, &pk, &mut rng)?;
  crypto_kem_dec(&mut ss_alice, &ct, &sk)?;

  assert_eq!(ss_bob, ss_alice);

  Ok(())
}

How does one run it?

This library comes with two examples:

$ cargo run --example simple

The output annotates messages with Alice/Bob to illustrate which data is processed by which party. The katkem example implements the classic request/response file structure which is part of the NIST PQC framework.

$ cargo run --example katkem PQCkemKAT_935.req PQCkemKAT_935.rsp
$ cargo run --example katkem PQCkemKAT_935.rsp

The different variants (ntruhps2048509, ntruhps2048677, ntruhps4096821, ntruhrss701) can be enabled through feature flags:

$ cargo run --example katkem --features ntruhrss701 -- PQCkemKAT_1450.req PQCkemKAT_1450.rsp

ntruhps2048509 is the default variant. You cannot enable two variants simultaneously.

How fast is it?

All data uses clock cycles as unit. The rust implementation has the following clock-cycle count characteristics (the smaller the better):

	complete KEM	keypair	enc	dec
ntruhps2048509	19,980,855	14,105,680	472,909	1,122,414
ntruhps2048677	27,478,939	24,077,519	895,930	2,333,079
ntruhps4096821	42,083,125	36,882,783	1,487,401	3,367,818
ntruhrss701	32,433,993	28,506,984	828,162	2,919,074

The C reference implementation has the following clock-cycle count characteristics (the smaller the better):

	complete KEM	keypair	enc	dec
ntruhps2048509	15,912,900	12,139,200	811,651	1,812,650
ntruhps2048677	28,911,500	22,233,600	1,520,640	3,668,860
ntruhps4096821	41,914,800	32,138,300	2,089,350	5,908,570
ntruhrss701	28,966,600	23,134,700	1,368,270	3,462,640

The tests were done on a Lenovo Thinkpad x260 (Intel Core i5-6200U CPU @ 2.30GHz). In the case of rust, criterion 0.3.5 has been used as given in benches/ and in case of C, Google's benchmark with PFM support and disabled CPU frequency scaling. Our summary is that both implementations have comparable runtime. rust is a little bit slower (but uses many copy operations for type safety you could replace with unsafe {} code). You can run the benchmark suite yourself with the bench subcommand and optionally some variant feature flag:

$ cargo bench --features ntruhrss701

Where is the source code?

On github.

What is the content's license?

MIT License

Changelog

• 2022-05-04 version 1.0.1: documentation fix
• 2022-05-03 version 1.0.0: public release

Where can I ask you to fix a bug?

On github.