This package is an "Additional Optimized" implementation of the Key Encapsulation Mechanism (KEM) BIKE.
It is developed and maintained solely by the DGK team that consists of Nir Drucker, Shay Gueron, and Dusan Kostic.
BIKE is a KEM submission to the Post-Quantum Cryptography Standardization project. At this point in time, NIST is considering BIKE as a fourth round candidate in the PQC Standardization process (link).
The official BIKE website is: https://bikesuite.org. This package corresponds to the Round 4 specification document "BIKE_Spec_2022.10.10.1.pdf" (Spec v.5.1), but also includes other options that the DGK team deems as useful (via compilation flags).
The package includes implementations for several CPU architectures. In particular, it can be compiled for a 64-bit ARM and for x86 processors. ARM architectures are supported by a fully portable implementation written in C. When the code is compiled for x86 processors, the resulting binary contains the following implementations:
When the package is used on an x86 CPU, it automatically (in runtime) detects the CPU capabilities and runs the fastest available code path, based on the detected capabilities. The fully portable version, which is built by default, requires OpenSSL. The library can also be compiled in a "stand-alone" mode, without OpenSSL, but only for a processor that supports AES-NI and AVX instructions. This mode can be enabled by a compilation flag described below.
The package includes testing and it uses the KAT generation utilities provided by NIST.
All the functionalities in the package are implemented in constant-time, which means that:
The optimizations in this package use, among other techniques, algorithms presented in the following papers:
Nir Drucker, Shay Gueron, "A Toolbox for Software Optimization of QC-MDPC Code-Based Cryptosystems." Journal of Cryptographic Engineering, January 2019, 1–17 https://doi.org/10.1007/s13389-018-00200-4.
Chou, T.: QcBits: Constant-Time Small-Key Code-Based Cryptography. In: Gier-lichs, B., Poschmann, A.Y. (eds.) Cryptographic Hardware and Embedded Systems– CHES 2016. pp. 280–300. Springer Berlin Heidelberg, Berlin, Heidelberg (2016)
Guimarães, Antonio, Diego F Aranha, and Edson Borin. 2019. “Optimized Implementation of QC-MDPC Code-Based Cryptography.” Concurrency and Computation: Practice and Experience 31 (18): e5089. https://doi.org/10.1002/cpe.5089.
The GF2X inversion in this package is based on:
The definition and the analysis of the constant-time BGF decoder used in this package is given in:
The code contains additional versions that can be enabled by the following flags: BIND_PK_AND_M and USE_SHA3_AND_SHAKE. The flags can be turned on individually or both at the same time.
Flag BIND_PK_AND_M enables binding of the public key and the message when generating the ciphertext in encapsulation. This security measure was proposed in:
Flag USE_SHA3_AND_SHAKE turns on the version of BIKE which uses SHA3 algorithm as a hash function (wherever a hash function is needed) and SHAKE based PRF. This modification was proposed by the BIKE team in https://bikesuite.org/files/v4.2/BIKE_Spec.2021.07.26.1.pdf.
This project is licensed under the Apache-2.0 License.
This package requires
To build the directory first create a working directory
mkdir build
cd build
Then, run CMake and compile
cmake -DCMAKE_BUILD_TYPE=Release ..
make
By default the package is compiled with parameters defined for NIST security Level-1 (64-bit quantum security). The default compilation options require OpenSSL to be available on the system. The "stand-alone" compilation, which can be enabled by a flag, assumes that AES_NI and POPCNT instructions are available.
Additional compilation flags:
To clean - remove the build
directory. Note that a "clean" is required prior
to compilation with modified flags.
To format (clang-format-9
or above is required):
make format
To use clang-tidy (clang-tidy-9
is required):
CC=clang-9 cmake -DCMAKE_C_CLANG_TIDY="clang-tidy-9;--fix-errors;--format-style=file" ..
make
Before committing code, please test it using
tests/run_tests.sh 0
This will run all the sanitizers.
The package was compiled and tested with clang (version 10.0.0) in 64-bit mode,
on a Linux (Ubuntu 20.04) on Intel Xeon (x86) and Graviton 2 (ARM) processors.
The x86 tests are done with Intel SDE which can emulate any Intel CPU.
Compilation on other platforms may require some adjustments.
The KATs are located in the tests/kats/
directory.
The performance of different versions of BIKE measured on two CPUs, one with vector-PCLMUL support and the other one without. The numbers represent average number of processor cycles required to complete each operation.
Measurements on Intel(R) Xeon(R) Platinum 8175M CPU @ 2.50GHz (doesn't support vector-PCLMUL):
L1 | a | b | c | d | e |
------------------------------------------------------------------------------|
keygen | 602,189 | 589,401 | 595,447 | 603,593 | 604,667 |
encaps | 129,970 | 97,967 | 114,787 | 133,078 | 158,862 |
decaps | 1,184,546 | 1,135,597 | 1,157,761 | 1,190,043 | 1,214,234 |
L3 | a | b | c | d | e |
------------------------------------------------------------------------------|
keygen | 1,824,934 | 1,823,910 | 1,824,686 | 1,828,516 | 1,833,566 |
encaps | 286,974 | 223,367 | 254,540 | 285,981 | 339,143 |
decaps | 3,956,456 | 3,887,439 | 3,939,558 | 3,963,570 | 3,977,745 |
L5 | a | b | c | d | e |
------------------------------------------------------------------------------|
keygen | 4,559,483 | 4,555,773 | 4,566,744 | 4,603,036 | 4,583,101 |
encaps | 564,340 | 459,785 | 510,131 | 548,016 | 623,044 |
decaps | 9,779,774 | 9,738,607 | 9,650,434 | 9,770,514 | 9,836,698 |
Measurements on Intel(R) Xeon(R) Platinum 8375C CPU @ 2.90GHz (supports vector-PCLMUL):
L1 | a | b | c | d | e |
----------------------------------------------------------------|--------------
keygen | 370,689 | 366,456 | 365,549 | 370,630 | 369,250 |
encaps | 95,512 | 74,838 | 87,397 | 99,579 | 119,274 |
decaps | 1,194,070 | 1,177,511 | 1,190,863 | 1,201,765 | 1,222,844 |
L3 | a | b | c | d | e |
------------------------------------------------------------------------------|
keygen | 1,064,040 | 1,049,339 | 1,058,253 | 1,063,406 | 1,053,004 |
encaps | 204,959 | 164,422 | 185,810 | 209,930 | 243,466 |
decaps | 3,531,790 | 3,512,350 | 3,491,114 | 3,544,996 | 3,571,774 |
L5 | a | b | c | d | e |
------------------------------------------------------------------------------|
keygen | 2,629,963 | 2,643,342 | 2,653,044 | 2,614,496 | 2,625,225 |
encaps | 399,718 | 325,787 | 363,979 | 397,391 | 463,783 |
decaps | 9,187,778 | 9,106,695 | 9,150,513 | 9,181,999 | 9,304,213 |
where:
The rejection sampling design and implementation that was used (until Spec v4.2) is described in the document entitled "Isochronous implementation of the errors-vector generation of BIKE". That document explains our response to the paper Don't reject this: Key-recovery timing attacks due to rejection-sampling in HQC and BIKE by Qian Guo et al, which is implemented here (since June 2022).