Caution
This Kyber implementation is conformant with Kyber specification https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf and I also try to make it timing leakage free, using dudect (see https://github.com/oreparaz/dudect) -based tests, but be informed that this implementation is not yet audited. If you consider using it in production, be careful !
CRYSTALS-Kyber: Post-Quantum Public-key Encryption & Key-establishment Algorithm
Kyber is being standardized by NIST as post-quantum secure key encapsulation mechanism (KEM), which can be used for key establishment.
Kyber offers an IND-CCA2-secure Key Encapsulation Mechanism - its security is based on the hardness of solving the learning-with-errors (LWE) problem in module (i.e. structured) lattices.
Kyber Key Encapsulation Mechanism is built on top of IND-CPA-secure Kyber Public Key Encryption, where two communicating parties, both generating their key pairs, while publishing only their public keys to each other, can encrypt fixed length ( = 32 -bytes ) message using peer's public key. Cipher text can be decrypted by corresponding secret key ( which is private to the keypair owner ) and 32 -bytes message can be recovered back. Then a slightly tweaked Fujisaki–Okamoto (FO) transform is applied on IND-CPA-secure Kyber PKE - giving us the IND-CCA2-secure KEM construction. In KEM scheme, two parties interested in establishing a secure communication channel over public & insecure channel, can generate a shared secret key ( of arbitrary byte length ) from a key derivation function ( i.e. KDF which is SHAKE256 Xof in this context ) which is obtained by both of these parties as result of seeding SHAKE256 Xof with same secret. This secret is 32 -bytes and that's what is communicated by sender to receiver using underlying Kyber PKE scheme.
Algorithm | Input | Output |
---|---|---|
KEM KeyGen | - | Public Key and Secret Key |
Encapsulation | Public Key | Cipher Text and SHAKE256 KDF |
Decapsulation | Secret Key and Cipher Text | SHAKE256 KDF |
Here I'm maintaining kyber
- a header-only and easy-to-use ( see more in usage ) C++ library implementing Kyber KEM, supporting Kyber-{512, 768, 1024} parameter sets, as defined in table 1 of Kyber specification. sha3
, subtle
and dudect
(for timing leakage tests) are dependencies of this library, which are pinned to specific git commits, using git submodule.
Note
Find Kyber specification https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf - this is the document that I followed when implementing Kyber. I suggest you go through the specification to get an in-depth understanding of Kyber PQC suite.
- A C++ compiler with C++20 standard library such as
clang++
/g++
.
$ clang++ --version
Ubuntu clang version 17.0.2 (1~exp1ubuntu2.1)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin
$ g++ --version
g++ (Ubuntu 13.2.0-4ubuntu3) 13.2.0
- Build tools such as
make
,cmake
.
$ make --version
GNU Make 4.3
$ cmake --version
cmake version 3.25.1
- For testing Kyber KEM implementation, you need to globally install
google-test
library and headers. Follow this guide, if you don't have it installed. - For benchmarking Kyber KEM implementation, targeting CPU systems, you'll need to have
google-benchmark
header and library globally installed. I found guide @ https://github.com/google/benchmark#installation helpful.
Note
If you are on a machine running GNU/Linux kernel and you want to obtain CPU cycle count for KEM routines, you should consider building google-benchmark
library with libPFM
support, following https://gist.github.com/itzmeanjan/05dc3e946f635d00c5e0b21aae6203a7, a step-by-step guide. Find more about libPFM @ https://perfmon2.sourceforge.net.
Tip
Git submodule based dependencies will mostly be imported automatically, but in case that doesn't work, you can manually initialize and update them by issuing $ git submodule update --init
from inside the root of this repository.
For testing functional correctness and conformance with Kyber specification, you have to issue
Note
Known Answer Test (KAT) files living in this directory are generated by following (reproducible) steps, described in https://gist.github.com/itzmeanjan/c8f5bc9640d0f0bdd2437dfe364d7710.
make -j # Run tests without any sort of sanitizers
make asan_test -j # Run tests with AddressSanitizer enabled
make ubsan_test -j # Run tests with UndefinedBehaviourSanitizer enabled
[10/10] KyberKEM.ArithmeticOverZq (149 ms)
PASSED TESTS (10/10):
1 ms: build/test.out KyberKEM.NumberTheoreticTransform
1 ms: build/test.out KyberKEM.PolynomialSerialization
1 ms: build/test.out KyberKEM.Kyber768KeygenEncapsDecaps
2 ms: build/test.out KyberKEM.Kyber512KeygenEncapsDecaps
2 ms: build/test.out KyberKEM.Kyber1024KeygenEncapsDecaps
16 ms: build/test.out KyberKEM.Kyber512KnownAnswerTests
21 ms: build/test.out KyberKEM.Kyber1024KnownAnswerTests
22 ms: build/test.out KyberKEM.Kyber768KnownAnswerTests
99 ms: build/test.out KyberKEM.CompressDecompressZq
149 ms: build/test.out KyberKEM.ArithmeticOverZq
In case you're interested in running timing leakage tests using dudect
, execute following
Note
dudect
is integrated into this library implementation of Kyber KEM to find any sort of timing leakages. It checks for constant-timeness of all vital functions including Fujisaki-Okamoto transform, used in decapsulation step. It doesn't check constant-timeness of function which samples public matrix A
, because that fails the check anyway, due to use of uniform rejection sampling. As matrix A
is public, it's not critical that it must be strictly constant-time.
# Can only be built and run x86_64 machine.
make dudect_test_build -j
# Before running the constant-time tests, it's a good idea to put all CPU cores on "performance" mode.
# You may find guide @ https://github.com/google/benchmark/blob/main/docs/reducing_variance.md helpful.
timeout 10m taskset -c 0 ./build/dudect/test_kyber512_kem.out
timeout 10m taskset -c 0 ./build/dudect/test_kyber768_kem.out
timeout 10m taskset -c 0 ./build/dudect/test_kyber1024_kem.out
Tip
dudect
documentation says if t
statistic is < 10, we're probably good, yes probably. You may want to read dudect
documentation @ https://github.com/oreparaz/dudect. Also you might find the original paper @ https://ia.cr/2016/1123 interesting.
...
meas: 58.90 M, max t: +2.61, max tau: 3.40e-04, (5/tau)^2: 2.16e+08. For the moment, maybe constant time.
meas: 58.99 M, max t: +2.65, max tau: 3.45e-04, (5/tau)^2: 2.10e+08. For the moment, maybe constant time.
meas: 59.07 M, max t: +2.65, max tau: 3.44e-04, (5/tau)^2: 2.11e+08. For the moment, maybe constant time.
meas: 59.16 M, max t: +2.63, max tau: 3.42e-04, (5/tau)^2: 2.13e+08. For the moment, maybe constant time.
meas: 59.25 M, max t: +2.68, max tau: 3.49e-04, (5/tau)^2: 2.06e+08. For the moment, maybe constant time.
meas: 59.33 M, max t: +2.65, max tau: 3.44e-04, (5/tau)^2: 2.12e+08. For the moment, maybe constant time.
meas: 59.42 M, max t: +2.75, max tau: 3.57e-04, (5/tau)^2: 1.96e+08. For the moment, maybe constant time.
meas: 59.50 M, max t: +2.72, max tau: 3.53e-04, (5/tau)^2: 2.01e+08. For the moment, maybe constant time.
meas: 59.59 M, max t: +2.68, max tau: 3.47e-04, (5/tau)^2: 2.08e+08. For the moment, maybe constant time.
meas: 59.66 M, max t: +2.70, max tau: 3.50e-04, (5/tau)^2: 2.04e+08. For the moment, maybe constant time.
meas: 59.74 M, max t: +2.70, max tau: 3.50e-04, (5/tau)^2: 2.05e+08. For the moment, maybe constant time.
meas: 59.82 M, max t: +2.72, max tau: 3.51e-04, (5/tau)^2: 2.03e+08. For the moment, maybe constant time.
meas: 59.89 M, max t: +2.72, max tau: 3.51e-04, (5/tau)^2: 2.03e+08. For the moment, maybe constant time.
meas: 59.97 M, max t: +2.64, max tau: 3.41e-04, (5/tau)^2: 2.14e+08. For the moment, maybe constant time.
For benchmarking Kyber KEM routines ( i.e. keygen, encaps and decaps ) for various suggested parameter sets, you have to issue.
make benchmark # If you haven't built google-benchmark library with libPFM support.
make perf # If you have built google-benchmark library with libPFM support.
Note
Benchmarking expects presence of google-benchmark
header and library in global namespace ( so that it can be found by the compiler ).
Caution
When benchmarking, ensure that you've disabled CPU frequency scaling, by following guide @ https://github.com/google/benchmark/blob/main/docs/reducing_variance.md.
Note
make perf
- was issued when collecting following benchmarks. Notice, cycles column, denoting cost of executing Kyber KEM routines in terms of CPU cycles. Follow this for more details.
Compiled with gcc version 13.2.0 (Ubuntu 13.2.0-4ubuntu3).
$ uname -srm
Linux 6.5.0-14-generic x86_64
2024-01-22T19:09:06+04:00
Running ./build/perf.out
Run on (16 X 752.14 MHz CPU s)
CPU Caches:
L1 Data 48 KiB (x8)
L1 Instruction 32 KiB (x8)
L2 Unified 1280 KiB (x8)
L3 Unified 18432 KiB (x1)
Load Average: 1.35, 0.74, 0.64
---------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations CYCLES items_per_second rdtsc
---------------------------------------------------------------------------------------------------------
kyber512/keygen_mean 14.1 us 14.1 us 10 64.8786k 71.1611k/s 35.056k
kyber512/keygen_median 13.9 us 13.9 us 10 64.8328k 71.8418k/s 34.704k
kyber512/keygen_stddev 0.363 us 0.362 us 10 533.391 1.73436k/s 903.837
kyber512/keygen_cv 2.58 % 2.57 % 10 0.82% 2.44% 2.58%
kyber512/keygen_min 13.8 us 13.8 us 10 64.1864k 66.4408k/s 34.367k
kyber512/keygen_max 15.1 us 15.1 us 10 66.2011k 72.5455k/s 37.531k
kyber1024/decap_mean 47.9 us 47.9 us 10 222.332k 20.8836k/s 119.488k
kyber1024/decap_median 47.8 us 47.8 us 10 222.36k 20.909k/s 119.335k
kyber1024/decap_stddev 0.345 us 0.345 us 10 847.653 149.328/s 860.065
kyber1024/decap_cv 0.72 % 0.72 % 10 0.38% 0.72% 0.72%
kyber1024/decap_min 47.4 us 47.4 us 10 220.724k 20.529k/s 118.295k
kyber1024/decap_max 48.7 us 48.7 us 10 223.956k 21.0947k/s 121.542k
kyber768/encap_mean 28.9 us 28.9 us 10 133.838k 34.632k/s 72.0448k
kyber768/encap_median 28.8 us 28.8 us 10 133.943k 34.7766k/s 71.729k
kyber768/encap_stddev 0.389 us 0.389 us 10 424.097 455.864/s 969.721
kyber768/encap_cv 1.35 % 1.35 % 10 0.32% 1.32% 1.35%
kyber768/encap_min 28.5 us 28.5 us 10 133.171k 33.474k/s 71.097k
kyber768/encap_max 29.9 us 29.9 us 10 134.415k 35.0874k/s 74.524k
kyber512/encap_mean 17.5 us 17.5 us 10 81.3077k 56.9959k/s 43.7583k
kyber512/encap_median 17.5 us 17.5 us 10 81.3109k 57.1806k/s 43.614k
kyber512/encap_stddev 0.178 us 0.178 us 10 224.364 572.266/s 443.14
kyber512/encap_cv 1.01 % 1.01 % 10 0.28% 1.00% 1.01%
kyber512/encap_min 17.3 us 17.3 us 10 80.9421k 55.7884k/s 43.182k
kyber512/encap_max 17.9 us 17.9 us 10 81.6759k 57.7496k/s 44.702k
kyber1024/encap_mean 44.1 us 44.1 us 10 204.634k 22.6603k/s 110.119k
kyber1024/encap_median 44.0 us 44.0 us 10 204.79k 22.7169k/s 109.836k
kyber1024/encap_stddev 0.358 us 0.356 us 10 751.071 180.658/s 891.891
kyber1024/encap_cv 0.81 % 0.81 % 10 0.37% 0.80% 0.81%
kyber1024/encap_min 43.7 us 43.7 us 10 202.876k 22.2099k/s 109.114k
kyber1024/encap_max 45.0 us 45.0 us 10 205.644k 22.8667k/s 112.348k
kyber1024/keygen_mean 37.6 us 37.6 us 10 174.399k 26.5696k/s 93.9229k
kyber1024/keygen_median 37.7 us 37.7 us 10 174.662k 26.5444k/s 94.024k
kyber1024/keygen_stddev 0.417 us 0.415 us 10 1.34601k 292.441/s 1.04079k
kyber1024/keygen_cv 1.11 % 1.10 % 10 0.77% 1.10% 1.11%
kyber1024/keygen_min 36.9 us 36.9 us 10 172.239k 26.0098k/s 91.983k
kyber1024/keygen_max 38.5 us 38.4 us 10 176.088k 27.1239k/s 95.953k
kyber768/keygen_mean 23.6 us 23.6 us 10 109.11k 42.3017k/s 58.9747k
kyber768/keygen_median 23.7 us 23.7 us 10 109.577k 42.2725k/s 59.0055k
kyber768/keygen_stddev 0.310 us 0.310 us 10 786.552 554.447/s 772.922
kyber768/keygen_cv 1.31 % 1.31 % 10 0.72% 1.31% 1.31%
kyber768/keygen_min 23.2 us 23.2 us 10 108.011k 41.3191k/s 57.748k
kyber768/keygen_max 24.2 us 24.2 us 10 109.909k 43.1928k/s 60.37k
kyber512/decap_mean 19.7 us 19.7 us 10 91.4808k 50.6517k/s 49.2443k
kyber512/decap_median 19.7 us 19.7 us 10 91.4678k 50.6475k/s 49.2465k
kyber512/decap_stddev 0.186 us 0.186 us 10 554.643 475.223/s 463.271
kyber512/decap_cv 0.94 % 0.94 % 10 0.61% 0.94% 0.94%
kyber512/decap_min 19.5 us 19.5 us 10 90.7913k 49.8154k/s 48.691k
kyber512/decap_max 20.1 us 20.1 us 10 92.7485k 51.2228k/s 50.066k
kyber768/decap_mean 31.8 us 31.8 us 10 147.512k 31.4865k/s 79.2379k
kyber768/decap_median 31.7 us 31.7 us 10 147.59k 31.5118k/s 79.1735k
kyber768/decap_stddev 0.129 us 0.128 us 10 344.756 126.89/s 320.866
kyber768/decap_cv 0.41 % 0.40 % 10 0.23% 0.40% 0.40%
kyber768/decap_min 31.6 us 31.6 us 10 146.652k 31.2195k/s 78.891k
kyber768/decap_max 32.0 us 32.0 us 10 147.851k 31.6233k/s 79.914k
Compiled with gcc version 13.2.0 (Ubuntu 13.2.0-4ubuntu3).
$ uname -srm
Linux 6.5.0-1008-raspi aarch64
2024-01-22T19:22:33+04:00
Running ./build/perf.out
Run on (4 X 1800 MHz CPU s)
CPU Caches:
L1 Data 32 KiB (x4)
L1 Instruction 48 KiB (x4)
L2 Unified 1024 KiB (x1)
Load Average: 2.32, 2.85, 1.46
----------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations CYCLES items_per_second
----------------------------------------------------------------------------------------------
kyber1024/decap_mean 250 us 250 us 10 448.76k 4.00416k/s
kyber1024/decap_median 250 us 250 us 10 448.888k 4.00246k/s
kyber1024/decap_stddev 0.401 us 0.405 us 10 738.224 6.49398/s
kyber1024/decap_cv 0.16 % 0.16 % 10 0.16% 0.16%
kyber1024/decap_min 249 us 249 us 10 447.75k 3.99346k/s
kyber1024/decap_max 251 us 250 us 10 450.06k 4.01306k/s
kyber512/decap_mean 106 us 106 us 10 189.763k 9.469k/s
kyber512/decap_median 106 us 106 us 10 189.753k 9.4696k/s
kyber512/decap_stddev 0.293 us 0.291 us 10 529.974 26.0654/s
kyber512/decap_cv 0.28 % 0.28 % 10 0.28% 0.28%
kyber512/decap_min 105 us 105 us 10 189.096k 9.41547k/s
kyber512/decap_max 106 us 106 us 10 190.852k 9.50263k/s
kyber768/encap_mean 148 us 148 us 10 265.507k 6.76869k/s
kyber768/encap_median 148 us 148 us 10 265.41k 6.77083k/s
kyber768/encap_stddev 0.566 us 0.567 us 10 1.0282k 25.9589/s
kyber768/encap_cv 0.38 % 0.38 % 10 0.39% 0.38%
kyber768/encap_min 147 us 147 us 10 263.583k 6.71972k/s
kyber768/encap_max 149 us 149 us 10 267.479k 6.81811k/s
kyber512/encap_mean 90.0 us 90.0 us 10 161.649k 11.117k/s
kyber512/encap_median 90.0 us 89.9 us 10 161.581k 11.121k/s
kyber512/encap_stddev 0.345 us 0.347 us 10 626.388 42.6811/s
kyber512/encap_cv 0.38 % 0.39 % 10 0.39% 0.38%
kyber512/encap_min 89.6 us 89.6 us 10 160.933k 11.0122k/s
kyber512/encap_max 90.9 us 90.8 us 10 163.199k 11.1667k/s
kyber768/keygen_mean 119 us 119 us 10 213.516k 8.416k/s
kyber768/keygen_median 119 us 119 us 10 213.534k 8.41435k/s
kyber768/keygen_stddev 0.275 us 0.277 us 10 496.099 19.6189/s
kyber768/keygen_cv 0.23 % 0.23 % 10 0.23% 0.23%
kyber768/keygen_min 118 us 118 us 10 212.691k 8.3908k/s
kyber768/keygen_max 119 us 119 us 10 214.168k 8.44783k/s
kyber1024/keygen_mean 188 us 188 us 10 337.777k 5.3203k/s
kyber1024/keygen_median 188 us 188 us 10 337.479k 5.32517k/s
kyber1024/keygen_stddev 0.785 us 0.791 us 10 1.42498k 22.2604/s
kyber1024/keygen_cv 0.42 % 0.42 % 10 0.42% 0.42%
kyber1024/keygen_min 187 us 187 us 10 336.121k 5.26713k/s
kyber1024/keygen_max 190 us 190 us 10 341.212k 5.34588k/s
kyber512/keygen_mean 69.0 us 68.9 us 10 123.818k 14.5129k/s
kyber512/keygen_median 69.0 us 68.9 us 10 123.807k 14.5138k/s
kyber512/keygen_stddev 0.152 us 0.148 us 10 253.268 31.0736/s
kyber512/keygen_cv 0.22 % 0.21 % 10 0.20% 0.21%
kyber512/keygen_min 68.7 us 68.7 us 10 123.395k 14.4549k/s
kyber512/keygen_max 69.2 us 69.2 us 10 124.311k 14.5653k/s
kyber768/decap_mean 170 us 170 us 10 304.634k 5.89868k/s
kyber768/decap_median 170 us 169 us 10 304.463k 5.9015k/s
kyber768/decap_stddev 0.654 us 0.648 us 10 1.15668k 22.5143/s
kyber768/decap_cv 0.39 % 0.38 % 10 0.38% 0.38%
kyber768/decap_min 169 us 169 us 10 303.091k 5.86043k/s
kyber768/decap_max 171 us 171 us 10 306.634k 5.92931k/s
kyber1024/encap_mean 224 us 224 us 10 401.823k 4.47202k/s
kyber1024/encap_median 224 us 223 us 10 401.482k 4.4752k/s
kyber1024/encap_stddev 0.802 us 0.804 us 10 1.47807k 16.038/s
kyber1024/encap_cv 0.36 % 0.36 % 10 0.37% 0.36%
kyber1024/encap_min 223 us 223 us 10 400.254k 4.44088k/s
kyber1024/encap_max 225 us 225 us 10 404.723k 4.48965k/s
Compiled with Apple clang version 15.0.0 (clang-1500.1.0.2.5).
$ uname -srm
Darwin 23.2.0 arm64
2024-01-22T19:33:49+04:00
Running ./build/bench.out
Run on (10 X 24 MHz CPU s)
CPU Caches:
L1 Data 64 KiB
L1 Instruction 128 KiB
L2 Unified 4096 KiB (x10)
Load Average: 2.44, 2.58, 2.80
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations items_per_second
-----------------------------------------------------------------------------------
kyber768/keygen_mean 20.2 us 20.2 us 10 49.5202k/s
kyber768/keygen_median 20.2 us 20.2 us 10 49.5691k/s
kyber768/keygen_stddev 0.078 us 0.075 us 10 182.819/s
kyber768/keygen_cv 0.39 % 0.37 % 10 0.37%
kyber768/keygen_min 20.2 us 20.1 us 10 49.0094k/s
kyber768/keygen_max 20.5 us 20.4 us 10 49.6414k/s
kyber1024/encap_mean 38.4 us 38.3 us 10 26.1344k/s
kyber1024/encap_median 38.3 us 38.2 us 10 26.1544k/s
kyber1024/encap_stddev 0.130 us 0.127 us 10 86.5122/s
kyber1024/encap_cv 0.34 % 0.33 % 10 0.33%
kyber1024/encap_min 38.2 us 38.1 us 10 25.957k/s
kyber1024/encap_max 38.6 us 38.5 us 10 26.2225k/s
kyber512/keygen_mean 12.0 us 11.9 us 10 83.7302k/s
kyber512/keygen_median 12.0 us 11.9 us 10 83.7409k/s
kyber512/keygen_stddev 0.019 us 0.020 us 10 141.747/s
kyber512/keygen_cv 0.16 % 0.17 % 10 0.17%
kyber512/keygen_min 11.9 us 11.9 us 10 83.5254k/s
kyber512/keygen_max 12.0 us 12.0 us 10 83.9197k/s
kyber768/encap_mean 25.0 us 24.9 us 10 40.0959k/s
kyber768/encap_median 25.0 us 24.9 us 10 40.106k/s
kyber768/encap_stddev 0.053 us 0.056 us 10 89.5965/s
kyber768/encap_cv 0.21 % 0.22 % 10 0.22%
kyber768/encap_min 24.9 us 24.8 us 10 39.9002k/s
kyber768/encap_max 25.1 us 25.1 us 10 40.2567k/s
kyber1024/keygen_mean 32.3 us 32.2 us 10 31.0263k/s
kyber1024/keygen_median 32.3 us 32.2 us 10 31.0496k/s
kyber1024/keygen_stddev 0.100 us 0.098 us 10 94.0295/s
kyber1024/keygen_cv 0.31 % 0.31 % 10 0.30%
kyber1024/keygen_min 32.2 us 32.2 us 10 30.7662k/s
kyber1024/keygen_max 32.6 us 32.5 us 10 31.0832k/s
kyber768/decap_mean 26.2 us 26.1 us 10 38.2517k/s
kyber768/decap_median 26.2 us 26.1 us 10 38.2788k/s
kyber768/decap_stddev 0.072 us 0.071 us 10 103.849/s
kyber768/decap_cv 0.27 % 0.27 % 10 0.27%
kyber768/decap_min 26.1 us 26.1 us 10 37.9778k/s
kyber768/decap_max 26.4 us 26.3 us 10 38.3546k/s
kyber512/encap_mean 15.2 us 15.1 us 10 66.0548k/s
kyber512/encap_median 15.2 us 15.1 us 10 66.0441k/s
kyber512/encap_stddev 0.019 us 0.018 us 10 76.3748/s
kyber512/encap_cv 0.13 % 0.12 % 10 0.12%
kyber512/encap_min 15.1 us 15.1 us 10 65.9247k/s
kyber512/encap_max 15.2 us 15.2 us 10 66.1939k/s
kyber1024/decap_mean 39.7 us 39.6 us 10 25.2636k/s
kyber1024/decap_median 39.7 us 39.6 us 10 25.2559k/s
kyber1024/decap_stddev 0.052 us 0.047 us 10 30.0564/s
kyber1024/decap_cv 0.13 % 0.12 % 10 0.12%
kyber1024/decap_min 39.6 us 39.5 us 10 25.2259k/s
kyber1024/decap_max 39.8 us 39.6 us 10 25.3094k/s
kyber512/decap_mean 16.1 us 16.1 us 10 62.1168k/s
kyber512/decap_median 16.1 us 16.1 us 10 62.1323k/s
kyber512/decap_stddev 0.023 us 0.024 us 10 93.9076/s
kyber512/decap_cv 0.14 % 0.15 % 10 0.15%
kyber512/decap_min 16.1 us 16.1 us 10 61.9199k/s
kyber512/decap_max 16.2 us 16.1 us 10 62.2184k/s
kyber
is written as a header-only C++ library, majorly targeting 64 -bit platforms and it's pretty easy to get started with. All you need to do is following.
- Clone
kyber
repository.
cd
# Multi-step cloning and importing of submodules
git clone https://github.com/itzmeanjan/kyber.git && pushd kyber && git submodule update --init && popd
# Or do single step cloning and importing of submodules
git clone https://github.com/itzmeanjan/kyber.git --recurse-submodules
- Write your program while including proper header files ( based on which variant of Kyber KEM you want to use, see include directory ), which includes declarations ( and definitions ) of all required KEM routines and constants ( such as byte length of public/ private keys and cipher text ).
// main.cpp
#include "kyber512_kem.hpp"
#include <algorithm>
#include <array>
#include <cassert>
int
main()
{
std::array<uint8_t, 32> d{}; // seed
std::array<uint8_t, 32> z{}; // seed
std::array<uint8_t, kyber512_kem::PKEY_LEN> pkey{};
std::array<uint8_t, kyber512_kem::SKEY_LEN> skey{};
std::array<uint8_t, 32> m{}; // seed
std::array<uint8_t, kyber512_kem::CIPHER_LEN> cipher{};
// Be careful !
//
// Read API documentation in include/prng.hpp
prng::prng_t prng;
prng.read(d);
prng.read(z);
prng.read(m);
kyber512_kem::keygen(d, z, pkey, skey);
auto skdf = kyber512_kem::encapsulate(m, pkey, cipher);
auto rkdf = kyber512_kem::decapsulate(skey, cipher);
std::array<uint8_t, 32> sender_key{};
skdf.squeeze(sender_key);
std::array<uint8_t, 32> receiver_key{};
rkdf.squeeze(receiver_key);
assert(std::ranges::equal(sender_key, receiver_key));
return 0;
}
- When compiling your program, let your compiler know where it can find
kyber
,sha3
andsubtle
headers, which includes their definitions ( kyber being a header-only library ) too.
# Assuming `kyber` was cloned just under $HOME
KYBER_HEADERS=~/kyber/include
SHA3_HEADERS=~/kyber/sha3/include
SUBTLE_HEADERS=~/kyber/subtle/include
g++ -std=c++20 -Wall -O3 -march=native -I $KYBER_HEADERS -I $SHA3_HEADERS -I $SUBTLE_HEADERS main.cpp
Kyber KEM Variant | Namespace | Header |
---|---|---|
Kyber512 KEM Routines | kyber512_kem:: |
include/kyber512_kem.hpp |
Kyber768 KEM Routines | kyber768_kem:: |
include/kyber768_kem.hpp |
Kyber1024 KEM Routines | kyber1024_kem:: |
include/kyber1024_kem.hpp |
Note
Kyber parameter sets are selected from table 1 of Kyber specification https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf.
See example program, where I show how to use Kyber512 KEM API. You can almost similarly use Kyber768 or Kyber1024 KEM API, by just importing correct header file and using KEM functions/ constants from respective namespace.
g++ -std=c++20 -Wall -Wextra -pedantic -O3 -march=native -I ./include -I ./sha3/include -I ./subtle/include/ examples/kyber512_kem.cpp && ./a.out
Kyber512 KEM
pubkey : 175782d35b2666833aee098617626d88dbcc47091a011882d52105acc218c9287a95276a3259a6a94aa386d8148886abdcc1841f39260ce4754ebacc1fd36102905d4c623d0b27930b4c249ee7380758c0ac5982b0e932eda95184a40f55c451d835861ca2b314dbce97829f1b92752dda592d8960b2540f464988ea1c974c63467c439b1de540490b0af0491a6507951ebc971887bd2b4a11327381d99586f10668c83abe92fb649b113da7ec666729bc1cc38a1de137dd3cc4e3a6abb9881a2ee63e7df3ad6cb680664ba1559ca17448c968b7c867ac5f324911ffd43993b8a7b8f57094c786877c1208fa7f53e51d6f1a46ae71bc81f78ebe5808d48200b7e1bc81ec3d31070a6993aa5db237eb3a4c592aa559a73bd769583a0ad095ec1669b952be4a71fe8603f5d597f007a048cc9d7fea6735383b6b8bbf896b74dc48a21840a92c497a9bc7434b0241a9e42e6428515d477c4e0b3678fab1d619b794f01b828648e7577bb2e5297915b9fdf33cb291a37de51b51c7aca6f07994193bd981134da2340c23a93cda8b68e429ac801d3748b8d112b57e388511e3305e50a51184b623607447468be94351cd0b9111a119b4b3c6f270c1cfea749a2ac89455590280c369163946481dbaeb4693dbb376202db2d8464c61aea6411cd887080f5c59e1587da01510cd1b0e8b030a5c200639ba26376134e88279891b90373cc92e7a76c0aaa33d084ab3f61e175010996652e441300ad5aefda9cc88f17fef2102b643179e0a49a60c47ce06c5b1a0b150b09ca4593e5dd48a9b1979d103ba862c43ed354d2ec99575b70e741808288aa0e1cb792c0a458d4584ddfa1870d7b797e2aac7d4cc08916015401338d8841d226d9656661cda93f53343e0f906b82bce8f25428b02a639a47f7dda5b946a3785656fb6d083df5a5ec7493cc017a2469b1f43c96f2e3bbc9d6cb07bec82d721a4cfba6ca2c59b0e01bda98585692b9da753923f830b52c843b6d963f959ad60189f42d61df7808f4d131c4d233e246c4735193e516452061701e6114cf1587a54c79105f48fdce9c2134bb60550b242945ea011ec54c570054b93d96f072426b7c9b524db8d2f136b7db2d1f38897
seckey : a598a250c2008688af8f71a285abae5b528a19479acf915cd2f92a7365bc757c670accc4b2190aa77b7d0c76355962a0ea9b6a1f4400be77797a6851776815032307913aa475b733a1ba698b2134ea25a57bd9b979e2bcb7d99f24f06ee760227486ae1cdaba79065bc3180d79a0906c514e5b973435c00f34b87e882643ef6b42bcbca4a3b65207abb5dca76e49a9be7a6013d256bc09b1211b70bb28e2151200c6c1e00082e88634600a29e3cf5ff541051c703ac373a91228a6d30491221df6749e22b21429612ed4ba07a7d7789717809e498f2e3a1b8a6a40afe0a7d2460350074a2a5127cc20c0b03446977a612a096324337cd5bc455f77cdbe4600e147b02fe58bc9c383b1e84ea3bc5755d3a87ce515b07c96741a72d9eb702d445acc3374531c70ef221216db2c9198110d83084f7b508da18fd34b8ee9f45d1204a627609d09a89c73e8bfc1f987c6bc906fac0d01720b169061b3d8015a5121a0d3beab454a03cc24a9bc5725e6c4aaf44d8f8b7242443f289c0751226448ec794a02a1ba411caeabb99f7a90510b8812a91a0ad69f1476408940381724a1dbfb7f69642788267b068c585bf41bf3f857fd14bcd9506b95b6a257d7481a07628004944e136a4c97842c13451e960cf4e08a8b6666e17a6aac016d701c1a00c82072939a092397c7104d7fd6332b860034f2ace5191e2792cf10e21f5166304bf329696128d63640b7882809b750f1f89e5d513fa08a8439e1ad5fe0affd887b0f06ab91798c35d48f39261af3dab7ddbc899be21d1f751b8d317b8e280f400b637ac6a471b4065973a6253235c94117e22083562b715ce680fafb78da9113f0f52692c52625ea8e1c24a1d8837beb963a5ab078455c8a43cbab68dc4eaa4c7646c9bb45803442250e935738944c7228aa3f7137567eb1231c63bff7552a7858525b92bdca832a41cb20fb24647a62af1da27e50c41f3cd070ed8c1d1213c22b1540a5c1412d67ab4ff334c2e5217c06a5f8a93c0637bd0fb4736c19591f67c378aa80f7c9587b346bbfe81eff8574c7e0acc3164c3df048019639a80377b97457175782d35b2666833aee098617626d88dbcc47091a011882d52105acc218c9287a95276a3259a6a94aa386d8148886abdcc1841f39260ce4754ebacc1fd36102905d4c623d0b27930b4c249ee7380758c0ac5982b0e932eda95184a40f55c451d835861ca2b314dbce97829f1b92752dda592d8960b2540f464988ea1c974c63467c439b1de540490b0af0491a6507951ebc971887bd2b4a11327381d99586f10668c83abe92fb649b113da7ec666729bc1cc38a1de137dd3cc4e3a6abb9881a2ee63e7df3ad6cb680664ba1559ca17448c968b7c867ac5f324911ffd43993b8a7b8f57094c786877c1208fa7f53e51d6f1a46ae71bc81f78ebe5808d48200b7e1bc81ec3d31070a6993aa5db237eb3a4c592aa559a73bd769583a0ad095ec1669b952be4a71fe8603f5d597f007a048cc9d7fea6735383b6b8bbf896b74dc48a21840a92c497a9bc7434b0241a9e42e6428515d477c4e0b3678fab1d619b794f01b828648e7577bb2e5297915b9fdf33cb291a37de51b51c7aca6f07994193bd981134da2340c23a93cda8b68e429ac801d3748b8d112b57e388511e3305e50a51184b623607447468be94351cd0b9111a119b4b3c6f270c1cfea749a2ac89455590280c369163946481dbaeb4693dbb376202db2d8464c61aea6411cd887080f5c59e1587da01510cd1b0e8b030a5c200639ba26376134e88279891b90373cc92e7a76c0aaa33d084ab3f61e175010996652e441300ad5aefda9cc88f17fef2102b643179e0a49a60c47ce06c5b1a0b150b09ca4593e5dd48a9b1979d103ba862c43ed354d2ec99575b70e741808288aa0e1cb792c0a458d4584ddfa1870d7b797e2aac7d4cc08916015401338d8841d226d9656661cda93f53343e0f906b82bce8f25428b02a639a47f7dda5b946a3785656fb6d083df5a5ec7493cc017a2469b1f43c96f2e3bbc9d6cb07bec82d721a4cfba6ca2c59b0e01bda98585692b9da753923f830b52c843b6d963f959ad60189f42d61df7808f4d131c4d233e246c4735193e516452061701e6114cf1587a54c79105f48fdce9c2134bb60550b242945ea011ec54c570054b93d96f072426b7c9b524db8d2f136b7db2d1f3889778f791d583227a702cdfa4a9f95014df019495f14e02318b3704dc3794af523705be75f29753f47b2888ceef235d82caca9f983b40bf10b29672da272113a973
cipher : bcee459c896ea378dcc458a532c35c029eff6b8cf8adc83f484fb6f9bfe32612f7c936cbf4dbd7c5262288dc3966a0d769f94a0bd57913a60a71efae09321c22c53839d836cef5fb8bf5c630bd3b3d657492eabfc7e67a42a631c95391656f0fce607a181e418144dff3d97f1192a2825a94da5113bcffc2e5f3e043f7583e6159902ddd009f8bcb18046a05695917bdef48accc2e3708f8536aabb420a7fd7989c60bca6c1941af45eac2f03cf71c8506721f8cd69bd3c573f036e3e8ae72b85632d06e0cab6fa1fea078d84aa1a116ac58ee632a0542b2d0e6a7026ae814ceeb46478d1cefd082c9b19efa7bb6ddd7abda8e43eab7b5a5204449273ea056b36d3797371f855d0c7ff0436279b21b831ad0970c26cc39f8627deb932689b8df48e73b1b5893987fa4dbc65571a78287f1573beeb85db52a3edbad6f50725bcbfa40423e3ce1ab00c16ea3922bc42e6782ce224ccfb3c978d8704584b9768a8edb6a950c0208b1c1c9a6a4e0d6300a9cfe788389697460efc41308448e9752d2022dfdecd118440346e2fabb07559b76301943f3b186adaaba09828efb28db1cd4a5e82e01f360451cb3c487f371af05725ea0e7d61932a8dc38108e99182e9b50d2aa828a773a2e18f5271ac75e5a5c50b9221f893e5f7076732beb0ffb9e4b82e1c0648192c9547870372b78c6a3e3a1b00d904a4a1492d5944e0510acee62e40c78cecef97922b04807cdd47d4d403a7bb16316598e6eee760b257382d9648c9920c3395717d8ac829bd37465c0f3e7f0c7e6fc351aac802edb722200776906eb36f622c0b8702958e44317961f583265a83b8cfcd9eed80f15b9ef848ebb7355df9718a60c532e20074854797685b3e4a25f929fce9ad02a5af114f92210abd3b73fddf28f116c2d4c27ceda6428a3892eb0c18fc12b07596e4153f2a3df9aa440957704bc56bbbee06cd99def3218c046344b4c5a811840a088bcbbad76fca4a20b9bf608873b2830afd6097b05022e8b1d42af3e5e4f00303adc9f130a84cdde3fef9335ccd1120b3f2050f17ef0c10fd226268965cbfc13738ada0632
shared secret : 508ac79bf97e90d75267159ba5189b73c48ab41a91aec0f32edd6cd1e66465b5
Caution
Before you consider using Psuedo Random Number Generator which comes with this library implementation, I strongly advice you to go through include/prng.hpp.
Note
Looking at API documentation, in header files, can give you good idea of how to use Kyber KEM API. Note, this library doesn't expose any raw pointer based interface, rather everything is wrapped under statically defined std::span
- which one can easily create from std::{array, vector}
. I opt for using statically defined std::span
based function interfaces because we always know, at compile-time, how many bytes the seeds/ keys/ cipher-texts/ shared-secrets are, for various different Kyber KEM parameters. This gives much better type safety and compile-time error reporting.