pq-crystals / kyber

Kyber

This repository contains the official reference implementation of the Kyber key encapsulation mechanism, and an optimized implementation for x86 CPUs supporting the AVX2 instruction set. Kyber has been selected for standardization in round 3 of the NIST PQC standardization project.

Build instructions

The implementations contain several test and benchmarking programs and a Makefile to facilitate compilation.

Prerequisites

Some of the test programs require OpenSSL. If the OpenSSL header files and/or shared libraries do not lie in one of the standard locations on your system, it is necessary to specify their location via compiler and linker flags in the environment variables CFLAGS, NISTFLAGS, and LDFLAGS.

For example, on macOS you can install OpenSSL via Homebrew by running

brew install openssl

Then, run

export CFLAGS="-I/usr/local/opt/[email protected]/include"
export NISTFLAGS="-I/usr/local/opt/[email protected]/include"
export LDFLAGS="-L/usr/local/opt/[email protected]/lib"

before compilation to add the OpenSSL header and library locations to the respective search paths.

Test programs

To compile the test programs on Linux or macOS, go to the ref/ or avx2/ directory and run

make

This produces the executables

test/test_kyber$ALG
test/test_kex$ALG
test/test_vectors$ALG

where $ALG ranges over the parameter sets 512, 768, 1024, 512-90s, 768-90s, 1024-90s.

• test_kyber$ALG tests 1000 times to generate keys, encapsulate a random key and correctly decapsulate it again. Also, the program tests that the keys cannot correctly be decapsulated using a random secret key or a ciphertext where a single random byte was randomly distorted in order to test for trivial failures of the CCA security. The program will abort with an error message and return 1 if there was an error. Otherwise it will output the key and ciphertext sizes and return 0.
• test_kex$ALG tests the authenticated key exchange schemes derived from the Kyber KEM
• test_vectors$ALG generates 10000 sets of test vectors containing keys, ciphertexts and shared secrets whose byte-strings are output in hexadecimal. The required random bytes come from a simple deterministic expansion of a fixed seed defined in test_vectors.c.

Benchmarking programs

For benchmarking the implementations, we provide speed test programs for x86 CPUs that use the Time Step Counter (TSC) or the actual cycle counter provided by the Performance Measurement Counters (PMC) to measure performance. To compile the programs run

make speed

This produces the executables

test/test_speed$ALG

for all parameter sets $ALG as above. The programs report the median and average cycle counts of 1000 executions of various internal functions and the API functions for key generation, encapsulation and decapsulation. By default the Time Step Counter is used. If instead you want to obtain the actual cycle counts from the Performance Measurement Counters, export CFLAGS="-DUSE_RDPMC" before compilation.

Please note that the reference implementation in ref/ is not optimized for any platform, and, since it prioritises clean code, is significantly slower than a trivially optimized but still platform-independent implementation. Hence benchmarking the reference code does not provide meaningful results.

Our Kyber implementations are contained in the SUPERCOP benchmarking framework. See here for cycle counts on an Intel KabyLake CPU.

Shared libraries

All implementations can be compiled into shared libraries by running

make shared

For example in the directory ref/ of the reference implementation, this produces the libraries

libpqcrystals_kyber$ALG_ref.so

for all parameter sets $ALG, and the required symmetric crypto libraries

libpqcrystals_aes256ctr_ref.so
libpqcrystals_fips202_ref.so

All global symbols in the libraries lie in the namespaces pqcrystals_kyber$ALG_ref, libpqcrystals_aes256ctr_ref and libpqcrystals_fips202_ref. Hence it is possible to link a program against all libraries simultaneously and obtain access to all implementations for all parameter sets. The corresponding API header file is ref/api.h, which contains prototypes for all API functions and preprocessor defines for the key and signature lengths.

CMake

Also available is a portable cmake based build system that permits building the reference implementation.

By calling

mkdir build && cd build && cmake .. && cmake --build . && ctest

the Kyber reference implementation gets built and tested.

kyber's Issues

about the correctness of the sk parameter in KAT

I downloaded the KAT of NIST-PQ-Submission Kyber-2021001 from nist website https://pq-crystals.org/kyber/resources.shtml. However, in some cases, sk seems to be incorrect and the verification failed. For example, in the case of Kyber768, when count=33, 77 and 88, some bytes of sk are incorrect, while all other cases and parameters are correct. In the case of Kyber512 and Kyber1024, there may also be similar issues.
For example, in the KAT, Kyber768, count=33,
sk = 8B78635AC351C94BB6B1D2B861E4914DCBA415F66CCC465B370578E136330A2C5CB0CA2857E1CB733A75E5CC4FCDF7A12580017F1C0FF484401CB23318A98000637B3D065608678103940D8BA75CCBE58206C130ED62BBC0132317B6556A9C2AE8F71A43712002D795CA52007782652D291DFE535F75034B0D624277527A6EF623168AACFBF721A9E8753195B82EB9855467322AAB0AB1701546C470AD139944B6736E1C97C9768370846B45693AAED9C80A7B53B863830DF61FE9600AD5717BFA2C8E59E30C8A20179B27B59341C855677880330AFD1A227B6C6313E17C46E87D109A4AEC4C1795908DB6046598483159907A667378F80BCB84472D5A748043B1BAC10BA5BCF61B07A2B13B12C347F3253E26C25EF0AF6A003A67B0BEE98A7C5A489C9EC9AC1F042C6F2BC7585CB01BB4B55496A93DE903EC974398E277CA7CC25E3265A879420EA0BD8451716AC21F1BB806C12B3488D408EBF18B89B79B1F8C09EACA235F1C165F9504FF987139590F9977513EE037249B4E25E51A296526BA76CD3295895A571CAC279BC65642CBA501C8F131EB52B5C7CB73B17757440B1EE4E9295D404177E542BD744AA587738BFAC0EF3C1FA0F19B0A5C5E28B53C2340C7FA061AD354C85AD26993087B61AC2002795D5ADA7A3E6747AB8110367C824988CA705B818D7A921DBA33371405AD235B18E463A8AC88180C88F071579FA5AB6D904A2F53B03F7C7EC39C473632369F984F8CC66DBD1924206A6376706CA36601BE7B16EDD17E93CB9A0437B3615374329B0712794F5058790D88182BE4863293133A83AA00E07C8E79C6F12C33FA9437ED984A1392903DA89BD43184DB6C8DACE3789AF5CBBA092010B889CA98AF99E5B0B3D4399BF61266E833A55A85E11784708B98EFAB223A27AEA1A16E76A73C2027759FD97A7DB870F9FC79AFC89435D092DB556E0A738C133B259F86C98D78A43A49744F306DA8CC6C9098A5A9CB091C9BAD94970F03B543D669A9AA4944E0C08DDFCC1D7D485FA414B0765A88F175AB6C94B12A2177DCD4998E6AA263EC3FD5BAA2466CA04568869466887F7BCF636C7A1F084277532841F51C3EDC5C1873BCE0F07A8871740C4AA82BB5AB164916082B795EB0660BE32DA9972840C927B7BB4061343D56757258BA4C91624F21DA11CB265B00B9AAFBB1665679C86EABBDA12B74F1C5917101D0EA2BB293C71AD5B556369378A8D5B7297C9731705DD4493DBB173AD01458686A93287B6DA0A6923B913989B69612A915A03A0962379BBC466A03F5517AAA0C0B030C6CA420636B2EE8821916E9C7F2BA228BB2AEABBC292F6C07AD85C6F43CA90D42629759536046394936C3AC5AB979D5CEC1A1CC19B5C17EDB47B0F47F34D616027B29A12725BF14B62FBAC4F2CC6EECE89CA0467D4868C11C17299373687B657D132C55785080F5B87F0E3C1504673825B98E8A0AA35F2C8D84F41B060AB43A930E7BE1C9D04746169BB4AB403ED8C74AACB868B4A93F1DC55144738E2736749AC64170CA7D0F0348A9550EE494466A49617B541068F2C57AD4108AB813DB58526C7647D55C1CB657CCD1143343AAA8421C23BD0C822F763B6A82B7D0041648A143BCC43163992E0D6A8F811B3F0D30807456C84C8BBB008D3B126A31424954CBC6CDBCE91E25B19928F4A41B1371447BA3D173915580BBD7899E9ADCA37B4B5A21E715101717710BC7EEC56EC2E58002127D1898BC55F8A3BE385D607B3BA6561991AC6F0913617303830DA25F0CF0AC14E67ABB8097D17B0AD1EA8C6C267ADF51A15A9A363D7AA5C8EA535A89115C984AC5D6BFA922C6FC44A3B35CB667F939FA6B2676BA212C17BCD25C82E8172F6A7506E8B77D82CB21D7066DA93A7EB3CAB8E881A24C7592BC6B656E459AF33A06FC2846D71221F1DA641004B68BD65DC28A59036CA678508614B15A93E74F89B8AF58200D50E718DAB1C41C4556CD47B43F14092CA47397243983406E12E423233C90CFEB661A32CE65AB464DB58C922BB693F56553961868B064E17A11162A7F0E3AB0B0AA76B8494BA394C902C598C23721DC16C51D46B8258C635763776B922FCAC747985B94C006696F18BA49D0C5EB0525CAD1349745691320969B6BCFF69C30851B41E66AAC3353C6894AB0097B4EC49783CFE4960D61A6F94B317D488D2D04A8B42C7FB7D89D52D89B2DE30336333C50895348870BBC311611F27845C7775128A9CC831966FCCC06292D86B582A18C6AB2FB3CCE03701BA91047227A9FCBC6F16130710756C5DC288BA92402B5B7DC90C39193737C206F3F8230261852F1694258D47C469C7452156E70634384825BC52B03E90720066B609A4102862433E2621987E23AF51121BED807810501200B776F847FF615C0F594420DC29CA6573276559C1C84B0723569DC2A76728909D9D1279A8C240A3979B0B44003687A412389581B8EBF0CCB06C797F7F5815CCBB434132ED5F1340E2C669430B13A709F7D1612AF876454F06CCB7841F84C60F3806D5E423CB34B23BBA90AB630403A46783329707388A1F4232785D4723C993CC62284D0E35242E52CFD6981268B86F598B11472900F83333C48627D402ABBA59C6740B4A40ABC3200B5D9E13010FB4DD6BB503548C777256E0729905A89BB386459E0B885B6E3017C94BA93C7518F017695F5BF5B99214C8555BDA863FDD11D40053C0D652696286D2BA14D569915E4532132527CE1B88122640AD668A20964476DB20AFCA5CA663C6C17156AB3CC8E4B723B3A5209D2D10767DA52B2443764F91A7F3AABB35137EE18A1F744562E22385716892CA77D518C4BEC578E0F1145B3241C1831BF782C760F9081A1191812790531648954163B10E6A1F02B2B9E17CDD439C6707AAB0DF09236BA33D9B271196A398FF0B2C9521E57B6C8833489C5328F4866C14D2CC1CE037400DC610B28CD99150404A175662102F9617205C1CBC24B5716C7B9B0E8635BF960BE5B632A976156C64078CBB23EB86B7BE9A2D3E12F5B56406CC51796C66A6E871DEB601CC767C0B8E45744346DE60BB160808210506C5779BC275940E000314F30555677689F23009A583CD6F9779C83530E5B2A5A0A771BF1376F0091C627AFECAC104FB2BA251C074E359E5FC44DEC244CCB78423532A7EB27C8313A341DC1431035162838835C85C677A420B67C847DC6605821587C8064E0BC2F4FE6A6B22113E73519125B92B3A66F15564666023EA99273D0D5657CFE1B1B3BBF85039A8189076A3752784E23D8A802023FD0743EB03D989A6968672E53B28D579974D268132187E7BD72238639C6F2CA154D50D98C74096EC33075D12195EC32A8686D0600E45D4A7F54219B0D7A3826D193A51B9156ECF2EDD6

I regenerated the. rsp files with PQCgenKAT. kem. c and found that, in Kyber768, when count=33,
sk = 8B78635AC351C94BB6B1D2B861E4914DCBA415F66CCC465B370578E136330A2C5CB0CA2857E1CB733A75E5CC4FCDF7A12580017F1C0FF484401CB23318A98000637B3D065608678103940D8BA75CCBE58206C130ED62BBC0132317B6556A9C2AE8F71A43712002D795CA52007782652D291DFE535F75034B0D624277527A6EF623168AACFBF721A9E8753195B82EB9855467322AAB0AB1701546C470AD139944B6736E1C97C9768370846B45693AAED9C80A7B53B863830DF61FE9600AD5717BFA2C8E59E30C8A20179B27B59341C855677880330AFD1A227B6C6313E17C46E87D109A4AEC4C1795908DB6046598483159907A667378F80BCB84472D5A748043B1BAC10BA5BCF61B07A2B13B12C347F3253E26C25EF0AF6A003A67B0BEE98A7C5A489C9EC9AC1F042C6F2BC7585CB01BB4B55496A93DE903EC974398E277CA7CC25E3265A879420EA0BD8451716AC21F1BB806C12B3488D408EBF18B89B79B1F8C09EACA235F1C165F9504FF987139590F9977513EE037249B4E25E51A296526BA76CD3295895A571CAC279BC65642CBA501C8F131EB52B5C7CB73B17757440B1EE4E9295D404177E542BD744AA587738BFAC0EF3C1FA0F19B0A5C5E28B53C2340C7FA061AD354C85AD26993087B61AC2002795D5ADA7A3E6747AB8110367C824988CA705B818D7A921DBA33371405AD235B18E463A8AC88180C88F071579FA5AB6D904A2F53B03F7C7EC39C473632369F984F8CC66DBD1924206A6376706CA36601BE7B16EDD17E93CB9A0437B3615374329B0712794F5058790D88182BE4863293133A83AA01ED7C8E79C6F12C33FA9437ED984A1392903DA89BD43184DB6C8DACE3789AF5CBBA092010B889CA98AF99E5B0B3D4399BF61266E833A55A85E11784708B98EFAB223A27AEA1A16E76A73C2027759FD97A7DB870F9FC79AFC89435D092DB556E0A738C133B259F86C98D78A43A49744F306DA8CC6C9098A5A9CB091C9BAD94970F03B543D669A9AA4944E0C08DDFCC1D7D485FA414B0765A88F175AB6C94B12A2177DCD4998E6AA263EC3FD5BAA2466CA04568869466887F7BCF636C7A1F084277532841F51C3EDC5C1873BCE0F07A8871740C4AA82BB5AB164916082B795EB0660BE32DA9972840C927B7BB4061343D56757258BA4C91624F21DA11CB265B00B9AAFBB1665679C86EABBDA12B74F1C5917101D0EA2BB293C71AD5B556369378A8D5B7297C9731705DD4493DBB173AD01458686A93287B6DA0A6923B913989B69612A915A03A0962379BBC466A03F5517AAA0C0B030C6CA420636B2EE8821916E9C7F2BA228BB2AEABBC292F6C07AD85C6F43CA90D42629759536046394936C3AC5AB979D5CEC1A1CC19B5C17EDB47B0F47F34D616027B29A12725BF14B62FBAC4F2CC6EECE89CA0467D4868C11C17299373687B657D132C55785080F5B87F0E3C1504673825B98E8A0AA35F2C8D84F41B060AB43A930E7BE1C9D04746169BB4AB403ED8C74AACB868B4A93F1DC55144738E2736749AC64170CA7D0F0348A9550EE494466A49617B541068F2C57AD4108AB813DB58526C7647D55C1CB657CCD1143343AAA8421C23BD0C822F763B6A82B7D0041648A143BCC43163992E0D6A8F811B3F0D30807456C84C8BBB008D3B126A31424954CBC6CDBCE91E25B19928F4A41B1371447BA3D173915580BBD7899E9ADCA37B4B5A21E715101717710BC7EEC56EC2E58002127D1898BC55F8A3BE385D607B3BA6561991AC6F0913617303830DA25F0CF0AC14E67ABB8097D17B0AD1EA8C6C267ADF51A15A9A363D7AA5C8EA535A89115C984AC5D6BFA922C6FC44A3B35CB667F939FA6B2676BA212C17BCD25C82E8172F6A7506E8B77D82CB21D7066DA93A7EB3CAB8E881A24C7592BC6B656E459AF33A06FC2846D71221F1DA641004B68BD65DC28A59036CA678508614B15A93E74F89B8AF58200D50E718DAB1C41C4556CD47B43F14092CA47397243983406E12E423233C90CFEB661A32CE65AB464DB58C922BB693F56553961868B064E17A11162A7F0E3AB0B0AA76B8494BA394C902C598C23721DC16C51D46B8258C635763776B922FCAC747985B94C006696F18BA49D0C5EB0525CAD1349745691320969B6BCFF69C30851B41E66AAC3353C6894AB0097B4EC49783CFE4960D61A6F94B317D488D2D04A8B42C7FB7D89D52D89B2DE30336333C50895348870BBC311611F27845C7775128A9CC831966FCCC06292D86B582A18C6AB2FB3CCE03701BA91047227A9FCBC6F16130710756C5DC288BA92402B5B7DC90C39193737C206F3F8230261852F1694258D47C469C7452156E70634384825BC52B03E90720066B609A4102862433E2621987E23AF51121BED807810501200B776F847FF615C0F594420DC29CA6573276559C1C84B0723569DC2A76728909D9D1279A8C240A3979B0B44003687A412389581B8EBF0CCB06C797F7F5815CCBB434132ED5F1340E2C669430B13A709F7D1612AF876454F06CCB7841F84C60F3806D5E423CB34B23BBA90AB630403A46783329707388A1F4232785D4723C993CC62284D0E35242E52CFD6981268B86F598B11472900F83333C48627D402ABBA59C6740B4A40ABC3200B5D9E13010FB4DD6BB503548C777256E0729905A89BB386459E0B885B6E3017C94BA93C7518F017695F5BF5B99214C8555BDA863FDD11D40053C0D652696286D2BA14D569915E4532132527CE1B88122640AD668A20964476DB20AFCA5CA663C6C17156AB3CC8E4B723B3A5209D2D10767DA52B2443764F91A7F3AABB35137EE18A1F744562E22385716892CA77D518C4BEC578E0F1145B3241C1831BF782C760F9081A1191812790531648954163B10E6A1F02B2B9E17CDD439C6707AAB0DF09236BA33D9B271196A398FF0B2C9521E57B6C8833489C5328F4866C14D2CC1CE037400DC610B28CD99150404A175662102F9617205C1CBC24B5716C7B9B0E8635BF960BE5B632A976156C64078CBB23EB86B7BE9A2D3E12F5B56406CC51796C66A6E871DEB601CC767C0B8E45744346DE60BB160808210506C5779BC275940E000314F30555677689F23009A583CD6F9779C83530E5B2A5A0A771BF1376F0091C627AFECAC104FB2BA251C074E359E5FC44DEC244CCB78423532A7EB27C8313A341DC1431035162838835C85C677A420B67C847DC6605821587C8064E0BC2F4FE6A6B22113E73519125B92B3A66F15564666023EA99273D0D5657CFE1B1B3BBF85039A8189076A3752784E23D8A802023FD0743EB03D989A6968672E53B28D579974D268132187E7BD72238639C6F2CA154D50D98C74096EC33075D12195EC32A8686D0600E45D4A7F54219B0D7A3826D193A51B9156ECF2EDD6

---

Possibly oversized cmp buffer in crypto_kem_dec standard branch

the size of the cmp buffer at:

kyber/ref/kem.c

Line 148 in 4ecce06

uint8_t cmp[KYBER_CIPHERTEXTBYTES+KYBER_SYMBYTES];

seems to no longer need the extra KYBER_SYMBYTES

Many compiler warnings with GCC 11 / -Wall

Compiling with GCC 11 leads to many compiler warnings like:

aes256ctr.c:420:19: warning: array subscript 117 is outside array bounds of ‘uint64_t[64]’ {aka ‘long unsigned int[64]’} [-Warray-bounds]
  420 |         q[5] ^= sk[5];
      |                   ^

aes256ctr.c:557:64: warning: argument 3 of type ‘const uint8_t *’ {aka ‘const unsigned char *’} declared as a pointer [-Warray-parameter=]
  557 | void aes256ctr_prf(uint8_t *out, size_t outlen, const uint8_t *key, const uint8_t *nonce)
      |                                                 ~~~~~~~~~~~~~~~^~~
In file included from aes256ctr.c:27:
aes256ctr.h:19:34: note: previously declared as an array ‘const uint8_t[32]’ {aka ‘const unsigned char[32]’}
   19 |                    const uint8_t key[32],
      |                    ~~~~~~~~~~~~~~^~~~~~~

Hit error when running `make` under `avx2` (related to issue #14)

I guess this issue is related to my previous question---issue #14 (which has been solved), I hit the error when running make under the folder of avx2:

In file included from kem.c:6:
./symmetric.h:10:10: fatal error: 'openssl/sha.h' file not found
#include <openssl/sha.h>
         ^~~~~~~~~~~~~~~
1 error generated.
In file included from indcpa.c:9:
./symmetric.h:10:10: fatal error: 'openssl/sha.h' file not found
#include <openssl/sha.h>
         ^~~~~~~~~~~~~~~
1 error generated.
In file included from poly.c:9:
./symmetric.h:10:10: fatal error: 'openssl/sha.h' file not found
#include <openssl/sha.h>
         ^~~~~~~~~~~~~~~
1 error generated.
make: *** [test_kyber512-90s] Error 1

Many thanks.

What are the requirements for the random number generator?

With little cryptographic background I was wondering if there are special requirements for the random generator used in randombytes.c?

Does a pseudorandom number impair the algorithm's ability to be quantum secure?
The question came up because I recently ported this repo for the avr-32 microcontroller architecture where a pseudorandom number generator is used.

The rand() function computes a sequence of pseudo-random integers in the range of 0 to RAND_MAX (as defined by the header file <stdlib.h>).

main fails to compile

MacOS Sonoma 14.1.2, Xcode-15.1

[ 25%] Building C object ref/CMakeFiles/test_kyber512_ref.dir/test_kyber.c.o
/Users/ur20980/src/kyber/ref/test_kyber.c:9:21: error: a function declaration without a prototype is deprecated in all versions of C [-Werror,-Wstrict-prototypes]
static int test_keys()
                    ^
                     void
/Users/ur20980/src/kyber/ref/test_kyber.c:34:29: error: a function declaration without a prototype is deprecated in all versions of C [-Werror,-Wstrict-prototypes]
static int test_invalid_sk_a()
                            ^
                             void
/Users/ur20980/src/kyber/ref/test_kyber.c:62:35: error: a function declaration without a prototype is deprecated in all versions of C [-Werror,-Wstrict-prototypes]
static int test_invalid_ciphertext()
                                  ^
                                   void
3 errors generated.

Proposed fix is obvious (it also addresses the fact that MacOS has shasum, but not sha256sum):

index 313ab24..6bc127d 100644
--- a/ref/CMakeLists.txt
+++ b/ref/CMakeLists.txt
@@ -114,4 +114,8 @@ else()
   add_test(NAME vectors1024-90s_ref COMMAND sh -c "\"$<TARGET_FILE:test_vectors1024-90s_ref>\" > tvecs1024-90s")
 endif()
 
-add_test(NAME hashes COMMAND sha256sum -c ../../SHA256SUMS)
+if (DARWIN)
+  add_test(NAME hashes COMMAND shasum -a 256 -c ../../SHA256SUMS)
+else()
+  add_test(NAME hashes COMMAND sha256sum -c ../../SHA256SUMS)
+endif(DARWIN)
diff --git a/ref/test_kyber.c b/ref/test_kyber.c
index 0f28af5..cac6b41 100644
--- a/ref/test_kyber.c
+++ b/ref/test_kyber.c
@@ -6,7 +6,7 @@
 
 #define NTESTS 1000
 
-static int test_keys()
+static int test_keys(void)
 {
   uint8_t pk[CRYPTO_PUBLICKEYBYTES];
   uint8_t sk[CRYPTO_SECRETKEYBYTES];
@@ -31,7 +31,7 @@ static int test_keys()
   return 0;
 }
 
-static int test_invalid_sk_a()
+static int test_invalid_sk_a(void)
 {
   uint8_t pk[CRYPTO_PUBLICKEYBYTES];
   uint8_t sk[CRYPTO_SECRETKEYBYTES];
@@ -59,7 +59,7 @@ static int test_invalid_sk_a()
   return 0;
 }
 
-static int test_invalid_ciphertext()
+static int test_invalid_ciphertext(void)
 {
   uint8_t pk[CRYPTO_PUBLICKEYBYTES];
   uint8_t sk[CRYPTO_SECRETKEYBYTES];

Ask for the link of the security estimation of kyber

Hello, developers of kyber,
I am an phd candidate work on security estimate, and want to refer to your source code about security estimate of core-SVP at the website: https://github.com/pq-crystals/kyber/ tree/master/scripts/. , but found out that the link is deactivated. And wonder ask whether there's any other link about the security estimate of Kyber plz.
Thanks for reading my request! Best wishes for you!

Wenwen,

2022.1.6

how to know the decryption is not the real message

Hi, I'm studing PQC schem : Light Kyber (Baby Kyber).
When I am trying to do some examples of KeyGen(), Enc(), and Dec(), sometimes the decryption gives me the same message I sent but sometimes it doesn't.

As an example my message is m=5 but after decryption it's m'=8, so if I'm just a receiver how to know that "8" is not the correct message, or if I'm the sender how to know that it would give an error so I will change "r" or "e1", ...

I know the failure depends on matrixes s, e, e1, e2, r, but I don't know how to detect the error before sending the message.
Thank you

Add Dockerfile

Mac users may prefer to use docker, this works for me:

# Pull base image.
FROM ubuntu:latest

# Install.
RUN \
    sed -i 's/# \(.*multiverse$\)/\1/g' /etc/apt/sources.list && \
    apt-get update && \
    apt-get -y upgrade && \
    apt-get install -y build-essential && \
    apt-get install -y software-properties-common && \
    apt-get install -y byobu curl git htop man unzip vim wget && \
    apt-get install libssl-dev && \
    rm -rf /var/lib/apt/lists/*

# Set environment variables.
ENV HOME /root

# Define working directory.
WORKDIR /root

RUN git clone https://github.com/pq-crystals/kyber.git && \
    cd kyber/ref && make &&\
    cd ../avx2 && make

# Define default command.
CMD ["bash"]

I hearby grant permission to the maintainers of this repo to add this code or any modification of it without attribution.

.gitignore symbolic link

After cloning this repo, when running a git status command, a warning message pops up that states "unable to access avx2/.gitignore: too many levels of symbolic links" (using git v2.39.3).
As stated here: https://git-scm.com/docs/gitignore/2.32.0#:~:text=Git%20does%20not%20follow%20symbolic,tree%20versus%20from%20the%20filesystem.
gitignore files must not be symbolic links.

Configuring error during "hashes"

I am using MacBook Air M2. Below error is occurred.

18 out of 19 test are successfully completed. 95% tests passed, 1 tests failed out of 19.

Why do you mean by line 117 in CMakeList.txt
add_test(NAME hashes COMMAND sha256sum -c ../../SHA256SUMS)

Error logs attached below:

LastTests.log:
19:hashes

LastTestsFailed.log:

Start testing: Jun 19 22:24 +03
----------------------------------------------------------
1/19 Testing: kyber512_ref
1/19 Test: kyber512_ref
Command: "/Users/macospc/kyber/build/ref/test_kyber512_ref"
Directory: /Users/macospc/kyber/build/ref
"kyber512_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
CRYPTO_SECRETKEYBYTES:  1632
CRYPTO_PUBLICKEYBYTES:  800
CRYPTO_CIPHERTEXTBYTES: 768
<end of output>
Test time =   0.83 sec
----------------------------------------------------------
Test Passed.
"kyber512_ref" end time: Jun 19 22:24 +03
"kyber512_ref" time elapsed: 00:00:00
----------------------------------------------------------

2/19 Testing: kex512_ref
2/19 Test: kex512_ref
Command: "/Users/macospc/kyber/build/ref/test_kex512_ref"
Directory: /Users/macospc/kyber/build/ref
"kex512_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
KEX_UAKE_SENDABYTES: 1568
KEX_UAKE_SENDBBYTES: 768
KEX_AKE_SENDABYTES: 1568
KEX_AKE_SENDBBYTES: 1536
<end of output>
Test time =   0.25 sec
----------------------------------------------------------
Test Passed.
"kex512_ref" end time: Jun 19 22:24 +03
"kex512_ref" time elapsed: 00:00:00
----------------------------------------------------------

3/19 Testing: kyber512-90s_ref
3/19 Test: kyber512-90s_ref
Command: "/Users/macospc/kyber/build/ref/test_kyber512-90s_ref"
Directory: /Users/macospc/kyber/build/ref
"kyber512-90s_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
CRYPTO_SECRETKEYBYTES:  1632
CRYPTO_PUBLICKEYBYTES:  800
CRYPTO_CIPHERTEXTBYTES: 768
<end of output>
Test time =   0.92 sec
----------------------------------------------------------
Test Passed.
"kyber512-90s_ref" end time: Jun 19 22:24 +03
"kyber512-90s_ref" time elapsed: 00:00:00
----------------------------------------------------------

4/19 Testing: kex512-90_ref
4/19 Test: kex512-90_ref
Command: "/Users/macospc/kyber/build/ref/test_kex512-90s_ref"
Directory: /Users/macospc/kyber/build/ref
"kex512-90_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
KEX_UAKE_SENDABYTES: 1568
KEX_UAKE_SENDBBYTES: 768
KEX_AKE_SENDABYTES: 1568
KEX_AKE_SENDBBYTES: 1536
<end of output>
Test time =   0.25 sec
----------------------------------------------------------
Test Passed.
"kex512-90_ref" end time: Jun 19 22:24 +03
"kex512-90_ref" time elapsed: 00:00:00
----------------------------------------------------------

5/19 Testing: kyber768_ref
5/19 Test: kyber768_ref
Command: "/Users/macospc/kyber/build/ref/test_kyber768_ref"
Directory: /Users/macospc/kyber/build/ref
"kyber768_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
CRYPTO_SECRETKEYBYTES:  2400
CRYPTO_PUBLICKEYBYTES:  1184
CRYPTO_CIPHERTEXTBYTES: 1088
<end of output>
Test time =   0.81 sec
----------------------------------------------------------
Test Passed.
"kyber768_ref" end time: Jun 19 22:24 +03
"kyber768_ref" time elapsed: 00:00:00
----------------------------------------------------------

6/19 Testing: kex768_ref
6/19 Test: kex768_ref
Command: "/Users/macospc/kyber/build/ref/test_kex768_ref"
Directory: /Users/macospc/kyber/build/ref
"kex768_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
KEX_UAKE_SENDABYTES: 2272
KEX_UAKE_SENDBBYTES: 1088
KEX_AKE_SENDABYTES: 2272
KEX_AKE_SENDBBYTES: 2176
<end of output>
Test time =   0.24 sec
----------------------------------------------------------
Test Passed.
"kex768_ref" end time: Jun 19 22:24 +03
"kex768_ref" time elapsed: 00:00:00
----------------------------------------------------------

7/19 Testing: kyber768-90s_ref
7/19 Test: kyber768-90s_ref
Command: "/Users/macospc/kyber/build/ref/test_kyber768-90s_ref"
Directory: /Users/macospc/kyber/build/ref
"kyber768-90s_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
CRYPTO_SECRETKEYBYTES:  2400
CRYPTO_PUBLICKEYBYTES:  1184
CRYPTO_CIPHERTEXTBYTES: 1088
<end of output>
Test time =   1.38 sec
----------------------------------------------------------
Test Passed.
"kyber768-90s_ref" end time: Jun 19 22:24 +03
"kyber768-90s_ref" time elapsed: 00:00:01
----------------------------------------------------------

8/19 Testing: kex768-90_ref
8/19 Test: kex768-90_ref
Command: "/Users/macospc/kyber/build/ref/test_kex768-90s_ref"
Directory: /Users/macospc/kyber/build/ref
"kex768-90_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
KEX_UAKE_SENDABYTES: 2272
KEX_UAKE_SENDBBYTES: 1088
KEX_AKE_SENDABYTES: 2272
KEX_AKE_SENDBBYTES: 2176
<end of output>
Test time =   0.24 sec
----------------------------------------------------------
Test Passed.
"kex768-90_ref" end time: Jun 19 22:24 +03
"kex768-90_ref" time elapsed: 00:00:00
----------------------------------------------------------

9/19 Testing: kyber1024_ref
9/19 Test: kyber1024_ref
Command: "/Users/macospc/kyber/build/ref/test_kyber1024_ref"
Directory: /Users/macospc/kyber/build/ref
"kyber1024_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
CRYPTO_SECRETKEYBYTES:  3168
CRYPTO_PUBLICKEYBYTES:  1568
CRYPTO_CIPHERTEXTBYTES: 1568
<end of output>
Test time =   1.13 sec
----------------------------------------------------------
Test Passed.
"kyber1024_ref" end time: Jun 19 22:24 +03
"kyber1024_ref" time elapsed: 00:00:01
----------------------------------------------------------

10/19 Testing: kex1024_ref
10/19 Test: kex1024_ref
Command: "/Users/macospc/kyber/build/ref/test_kex1024_ref"
Directory: /Users/macospc/kyber/build/ref
"kex1024_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
KEX_UAKE_SENDABYTES: 3136
KEX_UAKE_SENDBBYTES: 1568
KEX_AKE_SENDABYTES: 3136
KEX_AKE_SENDBBYTES: 3136
<end of output>
Test time =   0.24 sec
----------------------------------------------------------
Test Passed.
"kex1024_ref" end time: Jun 19 22:24 +03
"kex1024_ref" time elapsed: 00:00:00
----------------------------------------------------------

11/19 Testing: kyber1024-90s_ref
11/19 Test: kyber1024-90s_ref
Command: "/Users/macospc/kyber/build/ref/test_kyber1024-90s_ref"
Directory: /Users/macospc/kyber/build/ref
"kyber1024-90s_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
CRYPTO_SECRETKEYBYTES:  3168
CRYPTO_PUBLICKEYBYTES:  1568
CRYPTO_CIPHERTEXTBYTES: 1568
<end of output>
Test time =   2.05 sec
----------------------------------------------------------
Test Passed.
"kyber1024-90s_ref" end time: Jun 19 22:24 +03
"kyber1024-90s_ref" time elapsed: 00:00:02
----------------------------------------------------------

12/19 Testing: kex1024-90_ref
12/19 Test: kex1024-90_ref
Command: "/Users/macospc/kyber/build/ref/test_kex1024-90s_ref"
Directory: /Users/macospc/kyber/build/ref
"kex1024-90_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
KEX_UAKE_SENDABYTES: 3136
KEX_UAKE_SENDBBYTES: 1568
KEX_AKE_SENDABYTES: 3136
KEX_AKE_SENDBBYTES: 3136
<end of output>
Test time =   0.25 sec
----------------------------------------------------------
Test Passed.
"kex1024-90_ref" end time: Jun 19 22:24 +03
"kex1024-90_ref" time elapsed: 00:00:00
----------------------------------------------------------

13/19 Testing: vectors512_ref
13/19 Test: vectors512_ref
Command: "/bin/sh" "-c" ""/Users/macospc/kyber/build/ref/test_vectors512_ref" > tvecs512"
Directory: /Users/macospc/kyber/build/ref
"vectors512_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
<end of output>
Test time =   4.75 sec
----------------------------------------------------------
Test Passed.
"vectors512_ref" end time: Jun 19 22:24 +03
"vectors512_ref" time elapsed: 00:00:04
----------------------------------------------------------

14/19 Testing: vectors512-90s_ref
14/19 Test: vectors512-90s_ref
Command: "/bin/sh" "-c" ""/Users/macospc/kyber/build/ref/test_vectors512-90s_ref" > tvecs512-90s"
Directory: /Users/macospc/kyber/build/ref
"vectors512-90s_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
<end of output>
Test time =   5.25 sec
----------------------------------------------------------
Test Passed.
"vectors512-90s_ref" end time: Jun 19 22:24 +03
"vectors512-90s_ref" time elapsed: 00:00:05
----------------------------------------------------------

15/19 Testing: vectors768_ref
15/19 Test: vectors768_ref
Command: "/bin/sh" "-c" ""/Users/macospc/kyber/build/ref/test_vectors768_ref" > tvecs768"
Directory: /Users/macospc/kyber/build/ref
"vectors768_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
<end of output>
Test time =   6.03 sec
----------------------------------------------------------
Test Passed.
"vectors768_ref" end time: Jun 19 22:24 +03
"vectors768_ref" time elapsed: 00:00:06
----------------------------------------------------------

16/19 Testing: vectors768-90s_ref
16/19 Test: vectors768-90s_ref
Command: "/bin/sh" "-c" ""/Users/macospc/kyber/build/ref/test_vectors768-90s_ref" > tvecs768-90s"
Directory: /Users/macospc/kyber/build/ref
"vectors768-90s_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
<end of output>
Test time =   8.23 sec
----------------------------------------------------------
Test Passed.
"vectors768-90s_ref" end time: Jun 19 22:24 +03
"vectors768-90s_ref" time elapsed: 00:00:08
----------------------------------------------------------

17/19 Testing: vectors1024_ref
17/19 Test: vectors1024_ref
Command: "/bin/sh" "-c" ""/Users/macospc/kyber/build/ref/test_vectors1024_ref" > tvecs1024"
Directory: /Users/macospc/kyber/build/ref
"vectors1024_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
<end of output>
Test time =   8.36 sec
----------------------------------------------------------
Test Passed.
"vectors1024_ref" end time: Jun 19 22:24 +03
"vectors1024_ref" time elapsed: 00:00:08
----------------------------------------------------------

18/19 Testing: vectors1024-90s_ref
18/19 Test: vectors1024-90s_ref
Command: "/bin/sh" "-c" ""/Users/macospc/kyber/build/ref/test_vectors1024-90s_ref" > tvecs1024-90s"
Directory: /Users/macospc/kyber/build/ref
"vectors1024-90s_ref" start time: Jun 19 22:24 +03
Output:
----------------------------------------------------------
<end of output>
Test time =  11.49 sec
----------------------------------------------------------
Test Passed.
"vectors1024-90s_ref" end time: Jun 19 22:24 +03
"vectors1024-90s_ref" time elapsed: 00:00:11
----------------------------------------------------------

Unable to find executable: sha256sum
19/19 Testing: hashes
19/19 Test: hashes
Command: "" "-c" "../../SHA256SUMS"
Directory: /Users/macospc/kyber/build/ref
"hashes" start time: 
Output:
----------------------------------------------------------
<end of output>
Test time =   0.00 sec
----------------------------------------------------------
Test Passed.
"hashes" end time: Jun 19 22:24 +03
"hashes" time elapsed: 00:00:00
----------------------------------------------------------

End testing: Jun 19 22:24 +03

NTT ideas

I recently wrote some NTT code for my Leopard project and found a 50% speed boost using decimation-in-time version, where I take groups of 4 positions and operate on them (rather than 2 at a time). This allows us to effectively run two layers of the NTT/FFT/AFFT/etc in registers at a time rather than laborously writing them out and reading them back in again. It was hard to follow your AVX2 qhasm code but I think it doesn't do that so maybe a good win there?

e.g. https://github.com/catid/leopard/blob/master/LeopardFF16.cpp#L616

Another suggestion is to use ISPC instead of qhasm since it appears to support ARM NEON also, but I don't have any personal experience (yet) to back up that suggestion..

Why NTT and INTT use the same zeta array only with different order? and Why signed number is used not unsigned number?

I notice that NTT and INTT use the same(not different) zeta array(ref/ntt.c) since commit.

Why is it effective?

And, in Dilithium implementation, intt also uses the same zeta array with ntt except zeta = -zetas[k--] not zeta = zetas[k--], that's why?

In Kyber and Dilithium implementation, why signed number is used not unsigned number?

Why are you using GAS?

Congrats on making it to round 3!

Many modern compilers no longer support this old AT&T style dialect, but all the major compilers including GCC and Clang, support the more modern Intel syntax used in MASM. Windows servers are a huge piece of the market, and the go-to tool for Windows programming is Visual Studio, which does not support this older syntax. As a result, a number of downstream prototyping libraries, including my own, have not implemented the AVX versions of these codes. Please consider changing the ASM to the Intel syntax in Dilithium and Kyber, it would save a lot of people a lot of work.

Cheers,
John

Valgrind gives tons of errors

I'm running Valgrind on the latest version of the codebase (AVX2 version), and getting tons of errors like the following:

==22435== Conditional jump or move depends on uninitialised value(s)
==22435==    at 0x109BA0: pqcrystals_kyber512_avx2_gen_matrix (indcpa.c:253)
==22435==    by 0x109EC3: pqcrystals_kyber512_avx2_indcpa_enc (indcpa.c:581)
==22435==    by 0x10930E: pqcrystals_kyber512_avx2_enc (kem.c:69)
==22435==    by 0x1D9602: test_keys (test_kyber.c:23)
==22435==    by 0x1D98A1: main (test_kyber.c:98)
==22435==  Uninitialised value was created by a stack allocation
==22435==    at 0x10976C: pqcrystals_kyber512_avx2_gen_matrix (indcpa.c:210)
...
==23591== Use of uninitialised value of size 8
==23591==    at 0x110093: _mm_storeu_si128 (emmintrin.h:727)
==23591==    by 0x110093: pqcrystals_kyber512_avx2_rej_uniform_avx (rejsample.c:351)
==23591==    by 0x109A3A: pqcrystals_kyber512_avx2_gen_matrix (indcpa.c:251)
==23591==    by 0x109CC0: pqcrystals_kyber512_avx2_indcpa_keypair (indcpa.c:497)
==23591==    by 0x1091D9: pqcrystals_kyber512_avx2_keypair (kem.c:26)
==23591==    by 0x1D95E5: test_keys (test_kyber.c:20)
==23591==    by 0x1D98A1: main (test_kyber.c:98)
==23591== 

Debugging error PQCgenKAT_kem.c

How do you debug your code PQCgenKAT_kem.c I am getting below error.

cc -o PQCgenKAT_kem -g2 /Users/kursatc/kyber/ref/PQCgenKAT_kem.c
Undefined symbols for architecture arm64:
"_pqcrystals_kyber768_ref_dec", referenced from:
_main in PQCgenKAT_kem-4da757.o
"_pqcrystals_kyber768_ref_enc", referenced from:
_main in PQCgenKAT_kem-4da757.o
"_pqcrystals_kyber768_ref_keypair", referenced from:
_main in PQCgenKAT_kem-4da757.o
"_randombytes", referenced from:
_main in PQCgenKAT_kem-4da757.o
"_randombytes_init", referenced from:
_main in PQCgenKAT_kem-4da757.o
ld: symbol(s) not found for architecture arm64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

How are the pre-computed zetas in the AVX2 implementation calculated?

Could you explain how _ZETAS_EXP and _ZETAS_INV_EXP are calculated in const.c?

Load shared library by using module ctypes of python

I build shared library by using command cd ref && make shared.
The outputs file is

ref/libpqcrystals_aes256ctr_ref.so
ref/libpqcrystals_fips202_ref.so
ref/libpqcrystals_sha2_ref.so
ref/libpqcrystals_kyber512-90s_ref.so
ref/libpqcrystals_kyber512_ref.so
ref/libpqcrystals_kyber768-90s_ref.so
ref/libpqcrystals_kyber768_ref.so
ref/libpqcrystals_kyber1024-90s_ref.so
ref/libpqcrystals_kyber1024_ref.so

After that, I using python try to open these .so file

import os
from ctypes import cdll

shared_lib    = os.path.abspath(os.path.join(__file__, '..', 'ref'))
aes256ctr     = cdll.LoadLibrary(os.path.join(shared_lib, 'libpqcrystals_aes256ctr_ref.so'    ))
fips202       = cdll.LoadLibrary(os.path.join(shared_lib, 'libpqcrystals_fips202_ref.so'      ))
sha2          = cdll.LoadLibrary(os.path.join(shared_lib, 'libpqcrystals_sha2_ref.so'         ))


try: kyber512 = cdll.LoadLibrary(os.path.join(shared_lib, 'libpqcrystals_kyber512_ref.so'))
except Exception as ex: print(ex)


try: kyber512_90s = cdll.LoadLibrary(os.path.join(shared_lib, 'libpqcrystals_kyber512-90s_ref.so'))
except Exception as ex: print(ex)


try: kyber768 = cdll.LoadLibrary(os.path.join(shared_lib, 'libpqcrystals_kyber768_ref.so'))
except Exception as ex: print(ex)


try: kyber768_90s = cdll.LoadLibrary(os.path.join(shared_lib, 'libpqcrystals_kyber768-90s_ref.so'))
except Exception as ex: print(ex)


try: kyber1024 = cdll.LoadLibrary(os.path.join(shared_lib, 'libpqcrystals_kyber1024_ref.so'))
except Exception as ex: print(ex)


try: kyber1024_90s = cdll.LoadLibrary(os.path.join(shared_lib, 'libpqcrystals_kyber1024-90s_ref.so'))
except Exception as ex: print(ex)

And i have a problem

Traceback (most recent call last):
/home/tz/Documents/KYBER/kyber_python/ref/libpqcrystals_kyber512_ref.so: undefined symbol: pqcrystals_kyber_fips202_ref_shake256
/home/tz/Documents/KYBER/kyber_python/ref/libpqcrystals_kyber512-90s_ref.so: undefined symbol: pqcrystals_kyber_aes256ctr_ref_init
/home/tz/Documents/KYBER/kyber_python/ref/libpqcrystals_kyber768_ref.so: undefined symbol: pqcrystals_kyber_fips202_ref_shake256
/home/tz/Documents/KYBER/kyber_python/ref/libpqcrystals_kyber768-90s_ref.so: undefined symbol: pqcrystals_kyber_aes256ctr_ref_init
/home/tz/Documents/KYBER/kyber_python/ref/libpqcrystals_kyber1024_ref.so: undefined symbol: pqcrystals_kyber_fips202_ref_shake256
/home/tz/Documents/KYBER/kyber_python/ref/libpqcrystals_kyber1024-90s_ref.so: undefined symbol: pqcrystals_kyber_aes256ctr_ref_init

I am new in C/C++. Please help me fix these thing.

Where is the python script that compute the failure probability of Kyber?

Hi, I am reading the paper "CRYSTALS – Kyber: a CCA-secure module-lattice-based KEM" (https://eprint.iacr.org/2017/634.pdf).

In Remark 1, it mentions that "1. We provide with our software a Python script that allows to compute a tight upper bound \delta".

I want to figure out how the failure probability is computed. But there is no python file in this repository. Is it moved somewhere else?

By the way, can we only compute the failure probability by computer programs? Is it a theoretic way to do this?

Thanks!

Incremental Keccak API

When building a library containing both dilithium and kyber, the symbols in the namespace pqcrystals_fips202_ref are the same and thus, permit linking. However, it seems the functionalities in some functions (e.g., keccak_absorb) seem to be different (incremental vs. always-zeroing). (Accordingly?) arbitrary crashes occur in the "mixed library".

If you agree that libraries containing both kyber and dilithium --possibly sharing as much code as possible (see Dilithium issue #21 )-- are sensible, I see two alternatives immediately:

• separate out the incremental API with explicit naming of the functions (and add some testing to ensure the 'common' code in kyber and dilithium is "common" indeed, so others building on this don't fall in the same "trap").
• separate the name spacing of pqcrystals_fips202_ref into a kyber and a dilithium version (causing some code bloat, though).

Further alternatives would be welcome. For the time being/as a workaround, I apply sed to separate the namespaces to allow kyber and dilithium to co-exist in a direct import to liboqs. I'd be glad to see a better approach (again, ideally minimising the code footprint, i.e., maximising the amount of shared/common code).

Round 3 Kyber1024 AVX2 implementation of poly_decompress reads out of bounds

The _mm_loadu_si128 at line 204 of poly.c

kyber/avx2/poly.c

Lines 203 to 204 in b5857a3

	for(i=0;i<KYBER_N/16;i++) {
	f = _mm256_broadcastsi128_si256(_mm_loadu_si128((__m128i *)&a[10*i]));

reads 16 bytes from a[150]. This will include 6 out-of-bounds bytes when unpack_ciphertext is called here in indcpa_dec

kyber/avx2/indcpa.c

Lines 681 to 688 in b5857a3

	void indcpa_dec(uint8_t m[KYBER_INDCPA_MSGBYTES],
	const uint8_t c[KYBER_INDCPA_BYTES],
	const uint8_t sk[KYBER_INDCPA_SECRETKEYBYTES])
	{
	polyvec bp, skpv;
	poly v, mp;
	unpack_ciphertext(&bp, &v, c);

Quick and dirty fix here: https://github.com/jschanck/package-pqclean/blob/88ee652a0dcc7c23da4f65b477905a193fc30e7a/kyber/patches/avx2_indcpa.c#L12-L25

avx2 build question

Hi,
Does the avx2 version test the running processor for the existence of each specific instruction? I ask because the risk of an 'invalid instruction' can be difficult to test for and is fatal, and I don't necessarily run on the machine I build.

Also, in randombytes.c:62, shouldn't the open() have a corresponding close() somewhere?

randombytes_custom_algorithm supporrt

do we have a similar API like liboqs https://github.com/open-quantum-safe/liboqs/blob/bdce95401037aef04fd78f7674aef76bdb435ff2/src/common/rand/rand.h#L46

Are there any plans to support this feature?

keccak4x/AVX2 update

OQS fixed an undefined behavior/memory alignment issue in the keccak4x code: open-quantum-safe/liboqs#919

The same update should be considered here.

trailing whitespaces?

Hi, I just wanted to report that there are around 2KB of trailing whitespaces, which are superfluous and could be confusing for patches.

$ du --bytes --exclude .git
104146	./ref
60495	./avx2/keccak4x
243768	./avx2
20410	./scripts
374081	.
$ find . -type f -not -path './.git/*' -exec sed -i -e's/[[:space:]]*$//' {} +
$ du --bytes --exclude .git
103351	./ref
60495	./avx2/keccak4x
243270	./avx2
20209	./scripts
372585	.

This is a list of affected files:

$ git status
On branch master
Your branch is up to date with 'origin/master'.

Changes not staged for commit:
  (use "git add <file>..." to update what will be committed)
  (use "git checkout -- <file>..." to discard changes in working directory)

	modified:   AUTHORS
	modified:   README.md
	modified:   avx2/PQCgenKAT_kem.c
	modified:   avx2/cbd.h
	modified:   avx2/fips202.c
	modified:   avx2/fips202x4.c
	modified:   avx2/fips202x4.h
	modified:   avx2/genmatrix.c
	modified:   avx2/indcpa.c
	modified:   avx2/indcpa.h
	modified:   avx2/kem.c
	modified:   avx2/kex.c
	modified:   avx2/ntt.h
	modified:   avx2/params.h
	modified:   avx2/poly.c
	modified:   avx2/poly.h
	modified:   avx2/polyvec.c
	modified:   avx2/randombytes.c
	modified:   avx2/randombytes.h
	modified:   avx2/reduce.c
	modified:   avx2/rng.c
	modified:   avx2/speed.c
	modified:   avx2/test_kex.c
	modified:   avx2/test_kyber.c
	modified:   avx2/testvectors.c
	modified:   avx2/verify.c
	modified:   ref/PQCgenKAT_kem.c
	modified:   ref/cbd.c
	modified:   ref/fips202.c
	modified:   ref/indcpa.c
	modified:   ref/indcpa.h
	modified:   ref/kem.c
	modified:   ref/kex.c
	modified:   ref/ntt.c
	modified:   ref/ntt.h
	modified:   ref/params.h
	modified:   ref/poly.c
	modified:   ref/poly.h
	modified:   ref/polyvec.c
	modified:   ref/polyvec.h
	modified:   ref/precomp.c
	modified:   ref/randombytes.c
	modified:   ref/randombytes.h
	modified:   ref/reduce.c
	modified:   ref/rng.c
	modified:   ref/speed.c
	modified:   ref/test_kex.c
	modified:   ref/test_kyber.c
	modified:   ref/testvectors.c
	modified:   ref/verify.c
	modified:   scripts/Kyber.py
	modified:   scripts/Kyber_failure.py
	modified:   scripts/MLWE_security.py
	modified:   scripts/model_BKZ.py
	modified:   scripts/proba_util.py

no changes added to commit (use "git add" and/or "git commit -a")

Perhaps you want to configure your editor to strip them automatically?
Good luck !

macOS - issue for implementation - "This header is only meant to be used on x86 and x64 architecture"

Hi,

Did you test the repo in a Mac? Are you sure working fine?

I am getting below error. I think issue is an architecture related paradigm. I want to know if you have successfully compiled repo in your Mac PCs. If not, I will change my platform to linux.

I think the error is related with below issue. Could you please validate me ?

ISSUE 👍🏻

The error message indicates that the code you're trying to compile includes the smmintrin.h header, which is only meant to be used on x86 and x64 architectures. This error suggests that the code you're trying to compile may not be compatible with the architecture of your current system.

The code you mentioned earlier (keccak4x/KeccakP-1600-times4-SIMD256.c) seems to contain SIMD (Single Instruction, Multiple Data) instructions specific to x86/x64 architectures. These instructions may not be supported on other architectures, such as ARM.

To resolve this issue, you have a few options:

Make sure you are compiling the code on an x86/x64 architecture machine. If you're currently using a different architecture (e.g., ARM), try compiling the code on an x86/x64 machine.

Check if there are any alternative implementations or versions of the code that are compatible with your current architecture. Look for any architecture-specific files or instructions and see if there are alternatives available.

Modify the code to remove or replace the architecture-specific instructions. This might involve rewriting certain parts of the code or finding alternative algorithms or libraries that are compatible with your architecture.

It's important to note that modifying or rewriting the code may require a deep understanding of the algorithm and the specific instructions used. If you're not familiar with low-level programming or the algorithm in question, it may be best to consult with the original code authors or seek assistance from an expert in the field.

ERROR MESSAGE 👍🏻

pcs@pcs-MacBook-Air avx2 % make
cc -I/opt/homebrew/opt/[email protected]/include -Wall -Wextra -Wpedantic -Wmissing-prototypes -Wredundant-decls -Wshadow -Wpointer-arith -mavx2 -mbmi2 -mpopcnt -maes -march=native -mtune=native -O3 -fomit-frame-pointer -c keccak4x/KeccakP-1600-times4-SIMD256.c -o keccak4x/KeccakP-1600-times4-SIMD256.o
clang: warning: argument unused during compilation: '-mavx2' [-Wunused-command-line-argument]
clang: warning: argument unused during compilation: '-mbmi2' [-Wunused-command-line-argument]
clang: warning: argument unused during compilation: '-mpopcnt' [-Wunused-command-line-argument]
clang: warning: argument unused during compilation: '-maes' [-Wunused-command-line-argument]
In file included from keccak4x/KeccakP-1600-times4-SIMD256.c:19:
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/smmintrin.h:14:2: error: "This header is only meant to be used on x86 and x64 architecture"
#error "This header is only meant to be used on x86 and x64 architecture"
^
In file included from keccak4x/KeccakP-1600-times4-SIMD256.c:19:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/smmintrin.h:17:
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/tmmintrin.h:14:2: error: "This header is only meant to be used on x86 and x64 architecture"
#error "This header is only meant to be used on x86 and x64 architecture"
^
In file included from keccak4x/KeccakP-1600-times4-SIMD256.c:19:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/smmintrin.h:17:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/tmmintrin.h:17:
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/pmmintrin.h:14:2: error: "This header is only meant to be used on x86 and x64 architecture"
#error "This header is only meant to be used on x86 and x64 architecture"
^
In file included from keccak4x/KeccakP-1600-times4-SIMD256.c:19:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/smmintrin.h:17:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/tmmintrin.h:17:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/pmmintrin.h:17:
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/emmintrin.h:14:2: error: "This header is only meant to be used on x86 and x64 architecture"
#error "This header is only meant to be used on x86 and x64 architecture"
^
In file included from keccak4x/KeccakP-1600-times4-SIMD256.c:19:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/smmintrin.h:17:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/tmmintrin.h:17:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/pmmintrin.h:17:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/emmintrin.h:17:
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/xmmintrin.h:14:2: error: "This header is only meant to be used on x86 and x64 architecture"
#error "This header is only meant to be used on x86 and x64 architecture"
^
In file included from keccak4x/KeccakP-1600-times4-SIMD256.c:19:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/smmintrin.h:17:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/tmmintrin.h:17:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/pmmintrin.h:17:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/emmintrin.h:17:
In file included from /Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/xmmintrin.h:17:
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:14:2: error: "This header is only meant to be used on x86 and x64 architecture"
#error "This header is only meant to be used on x86 and x64 architecture"
^
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:54:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_vec_init_v2si(__i, 0);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:133:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_packsswb((__v4hi)__m1, (__v4hi)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:163:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_packssdw((__v2si)__m1, (__v2si)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:193:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_packuswb((__v4hi)__m1, (__v4hi)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:220:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_punpckhbw((__v8qi)__m1, (__v8qi)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:243:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_punpckhwd((__v4hi)__m1, (__v4hi)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:264:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_punpckhdq((__v2si)__m1, (__v2si)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:291:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_punpcklbw((__v8qi)__m1, (__v8qi)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:314:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_punpcklwd((__v4hi)__m1, (__v4hi)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:335:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_punpckldq((__v2si)__m1, (__v2si)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:356:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_paddb((__v8qi)__m1, (__v8qi)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:377:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_paddw((__v4hi)__m1, (__v4hi)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/lib/clang/14.0.3/include/mmintrin.h:398:12: error: invalid conversion between vector type '__m64' (vector of 1 'long long' value) and integer type 'int' of different size
return (__m64)__builtin_ia32_paddd((__v2si)__m1, (__v2si)__m2);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fatal error: too many errors emitted, stopping now [-ferror-limit=]
20 errors generated.

Constant time fix

In commit 9b8d306 you've basically split the code into 2 files, preventing the compiler from seeing both pieces of code and optimizing it. Have you tried putting them in the same file, or tried with LTO?

Looking at the code, I suspect the compiler is either still converting it, or will in the future. OpenSSL and BoringSSL have a value barrier function to prevent the compiler from doing optimizations based on the value.

the result of test_speed seems like some problem

I run "make speed" and run "test_speed512" ang got following result:

I noticed that the median of gen_a is 61888cycles/ticks and indcpa_keypair is 88894cycles/ticks.

Does this mean gen_a cost 69.6% time of indcpa_keypair?

But according other data, for example, NTT is 6832 cycles/ticks, and 4-time NTTs are necessary for indcpa_keypair, which is 30.7% time of indcpa_keypair.

So, 69.6%+30.7%=100.3%？And other steps also should cost some time, such as basemul/keccak and so on.

Maybe the measured time cost by gen_a is wrong?

gen_a:
median: 61888 cycles/ticks
average: 55950 cycles/ticks

poly_getnoise_eta1:
median: 5672 cycles/ticks
average: 5309 cycles/ticks

poly_getnoise_eta2:
median: 2358 cycles/ticks
average: 2357 cycles/ticks

NTT:
median: 6832 cycles/ticks
average: 6841 cycles/ticks

INVNTT:
median: 10282 cycles/ticks
average: 10290 cycles/ticks

polyvec_basemul_acc_montgomery:
median: 7538 cycles/ticks
average: 7827 cycles/ticks

poly_tomsg:
median: 862 cycles/ticks
average: 942 cycles/ticks

poly_frommsg:
median: 110 cycles/ticks
average: 152 cycles/ticks

poly_compress:
median: 632 cycles/ticks
average: 631 cycles/ticks

poly_decompress:
median: 60 cycles/ticks
average: 60 cycles/ticks

polyvec_compress:
median: 2364 cycles/ticks
average: 2364 cycles/ticks

polyvec_decompress:
median: 1086 cycles/ticks
average: 1087 cycles/ticks

indcpa_keypair:
median: 88894 cycles/ticks
average: 92470 cycles/ticks

indcpa_enc:
median: 102660 cycles/ticks
average: 106733 cycles/ticks

indcpa_dec:
median: 31482 cycles/ticks
average: 33258 cycles/ticks

kyber_keypair:
median: 98828 cycles/ticks
average: 102650 cycles/ticks

kyber_encaps:
median: 124006 cycles/ticks
average: 127835 cycles/ticks

kyber_decaps:
median: 144542 cycles/ticks
average: 149224 cycles/ticks

kex_uake_initA:
median: 222886 cycles/ticks
average: 229872 cycles/ticks

kex_uake_sharedB:
median: 270726 cycles/ticks
average: 280474 cycles/ticks

kex_uake_sharedA:
median: 146330 cycles/ticks
average: 152676 cycles/ticks

kex_ake_initA:
median: 222870 cycles/ticks
average: 230413 cycles/ticks

kex_ake_sharedB:
median: 394732 cycles/ticks
average: 406949 cycles/ticks

kex_ake_sharedA:
median: 290918 cycles/ticks
average: 300254 cycles/ticks

License clarification

Kindly confirm which one among the below two licenses are applicable.

Public Domain (License text - Public domain code is not subject to any license. )
Creative Commons Zero v1.0 Universal (https://creativecommons.org/publicdomain/zero/1.0/)

Stack overflow in AVX2 code

Compiling test_kyber512 with -fsanitize=address,undefined on gcc 10.1.0 leads to the following:

=================================================================
==288165==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55b880d170b8 at pc 0x55b880c9b0fc bp 0x7fff1a3c8950 sp 0x7fff1a3c8940
READ of size 16 at 0x55b880d170b8 thread T0
    #0 0x55b880c9b0fb in pqcrystals_kyber512_avx2_rej_uniform_avx (/home/thom/git/phd/kyber/avx2/test_kyber512+0x710fb)
    #1 0x55b880c897c6 in pqcrystals_kyber512_avx2_gen_matrix (/home/thom/git/phd/kyber/avx2/test_kyber512+0x5f7c6)
    #2 0x55b880c8b5e0 in pqcrystals_kyber512_avx2_indcpa_keypair (/home/thom/git/phd/kyber/avx2/test_kyber512+0x615e0)
    #3 0x55b880c88a61 in pqcrystals_kyber512_avx2_keypair (/home/thom/git/phd/kyber/avx2/test_kyber512+0x5ea61)
    #4 0x55b880d13b9a in test_keys.isra.0 (/home/thom/git/phd/kyber/avx2/test_kyber512+0xe9b9a)
    #5 0x55b880c888ba in main (/home/thom/git/phd/kyber/avx2/test_kyber512+0x5e8ba)
    #6 0x7f366960a001 in __libc_start_main (/usr/lib/libc.so.6+0x27001)
    #7 0x55b880c8896d in _start (/home/thom/git/phd/kyber/avx2/test_kyber512+0x5e96d)

0x55b880d170c0 is located 0 bytes to the right of global variable 'idx' defined in 'rejsample.c:8:22' (0x55b880d168c0) of size 2048
SUMMARY: AddressSanitizer: global-buffer-overflow (/home/thom/git/phd/kyber/avx2/test_kyber512+0x710fb) in pqcrystals_kyber512_avx2_rej_uniform_avx
Shadow bytes around the buggy address:
  0x0ab79019adc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab79019add0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab79019ade0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab79019adf0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab79019ae00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0ab79019ae10: 00 00 00 00 00 00 00[00]f9 f9 f9 f9 00 00 00 00
  0x0ab79019ae20: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab79019ae30: 00 00 00 04 f9 f9 f9 f9 06 f9 f9 f9 f9 f9 f9 f9
  0x0ab79019ae40: 00 00 00 00 00 00 00 00 00 00 00 00 00 01 f9 f9
  0x0ab79019ae50: f9 f9 f9 f9 00 00 00 00 00 00 00 04 f9 f9 f9 f9
  0x0ab79019ae60: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==288165==ABORTING

ARM assembly support?

I'm attempting to work on a PoC using mobile devices, wondering if anyone has attempted to translate the AVX2 code over to something that is compatible with ARM64 CPUs?

INVNTT of NTT produces not the same results.

Hello all, I have a question regarding the NTT part of the Kyber implementation. When reading about NTT it is often mentioned, that the result of INVNTT(NTT(data)) should be the same as data in the beginning.

I tried to test this property with the rudimental testing code below using the ntt_avx implementation on the master branch.

#include "consts.h"
#include "ntt.h"
#include <stdio.h>

#define NTESTS 1

int main() {
    unsigned int i;
    int16_t data[256] = {0};
    for (int h = 0; h < 256; h++) {
        data[h] = h + 1;
    }

    printf("Input data:\n");
    for (int h = 0; h < 256; h++) {
        printf("%i ", data[h]);
    }
    printf("\n\n");

    for (i = 0; i < NTESTS; i++) {
        ntt_avx(data, qdata);
    }

    printf("NTT:\n");
    for (int h = 0; h < 256; h++) {
        printf("%i ", data[h]);
    }
    printf("\n\n");

    for (i = 0; i < NTESTS; i++) {
        invntt_avx(data, qdata);
    }

    printf("INVNTT:\n");
    for (int h = 0; h < 256; h++) {
        printf("%i ", data[h]);
    }
    printf("\n");

    return 0;
}

Unfortunately, this produces different results. Could you maybe give me some pointers on what I am missing here? Or is this implementation specialized for the use case and does not fulfil the previously mentioned property?

Thanks!

Is montgomery calculation is necessary?

There is much montgomery field calculation in latest version reference code(master and round 3 branch, ref/ directory).

And, key generated is seems in montgomery field too.

But specification documents(version 3.0, October 1, 2020 and 3.01/3.02 version)(in NIST submission package for round3(zip), Supporting_Documentation/kyber.pdf) don't show anything about montgomery(I mean algorithm specification except security problem), for example, "KYBER.CPAPKE.KeyGen(): key generation".

So, is montgomery calculation is necessary? If I do hardware implmentation, must I implement montgomery to keep key generated and ciphertext is compatible to software reference implementation?

Why the result of barrett_reduce is in {-(q-1)/2,...,(q-1)/2} congruent to a modulo q?

In the history implementation of barrett_reduce function, the output is in {0,...,q} congruent to a modulo q.
But in Commits on Nov 20, 2020, the output of barrett_reduce is in {-(q-1)/2,...,(q-1)/2} congruent to a modulo q.
Why is it modified like this？

Out of bound check in NTT/INTT

Dear gregorseiler,

In ntt.c source code, there is out-of-boundary check inside ntt and intt functions. For example, in ntt function in line #68 integer j used in the for loop is defined but not initialized:

for(start = 0; start < 256; start = j + len)

As a result, this causes r[j + len] to go out-of-boundary somehow. Could you please comment on this?

Thanks,
Sherif

Question about polynomial compression

The code in polyvec.c KYBER_POLYVECCOMPRESSEDBYTES choses different compression formats based on the value of KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * N) for N in {256,288,320,352}. However the Kyber paper only seems to describe case 352 (which is what is set by default in params.h). If I try other values for KYBER_POLYVECCOMPRESSEDBYTES everything seems to work (in that test_kyber does not complain, obviously I understand that these variants are not compatible with the NIST submission).

My questions is, are these variants described anywhere? It seems useful to have smaller public keys and ciphertexts so I am curious why you chose the 352 byte encoding. Perhaps this adversely affects the error rate to the point the smaller keys are not worthwhile?

Another comment, for N=256 actually the tests all failed for me, so there may be some problem in the code for that case.

Kyber Ref dead code ?

Hello all,

I was analyzing Kyber768 ref code and found a possible deadcode.

Can this line be reached : https://github.com/pq-crystals/kyber/blob/main/ref/indcpa.c#L185 ?

GEN_MATRIX_NBLOCKS is 3 & XOF_BLOCKBYTES is168 (also multiple of 3) that makes off ( @ https://github.com/pq-crystals/kyber/blob/main/ref/indcpa.c#L183) always 0.

---EDIT---
The same is applicable for Dilithium as well : https://github.com/pq-crystals/dilithium/blob/master/ref/poly.c#L360

Thanks.

Error when running `cd kyber/ref && make shared`

When I am running the follow command: cd kyber/ref && make shared, I got this message:

cc -shared -fPIC -I/usr/local/opt/[email protected]/include -Wall -Wextra -Wpedantic -Wmissing-prototypes -Wredundant-decls -Wshadow -Wpointer-arith -O3 -fomit-frame-pointer -DKYBER_K=2 kex.c kem.c indcpa.c polyvec.c poly.c ntt.c cbd.c reduce.c verify.c symmetric-shake.c -o libpqcrystals_kyber512_ref.so
Undefined symbols for architecture x86_64:
  "_pqcrystals_kyber_fips202_ref_sha3_256", referenced from:
      _pqcrystals_kyber512_ref_keypair in kem-9bb932.o
      _pqcrystals_kyber512_ref_enc in kem-9bb932.o
      _pqcrystals_kyber512_ref_dec in kem-9bb932.o
  "_pqcrystals_kyber_fips202_ref_sha3_512", referenced from:
      _pqcrystals_kyber512_ref_enc in kem-9bb932.o
      _pqcrystals_kyber512_ref_dec in kem-9bb932.o
      _pqcrystals_kyber512_ref_indcpa_keypair in indcpa-c434fa.o
  "_pqcrystals_kyber_fips202_ref_shake128_absorb_once", referenced from:
      _pqcrystals_kyber512_ref_kyber_shake128_absorb in symmetric-shake-9d277b.o
  "_pqcrystals_kyber_fips202_ref_shake128_squeezeblocks", referenced from:
      _pqcrystals_kyber512_ref_gen_matrix in indcpa-c434fa.o
  "_pqcrystals_kyber_fips202_ref_shake256", referenced from:
      _kex_uake_sharedB in kex-3b6c2e.o
      _kex_uake_sharedA in kex-3b6c2e.o
      _kex_ake_sharedB in kex-3b6c2e.o
      _kex_ake_sharedA in kex-3b6c2e.o
      _pqcrystals_kyber512_ref_enc in kem-9bb932.o
      _pqcrystals_kyber512_ref_dec in kem-9bb932.o
      _pqcrystals_kyber512_ref_kyber_shake256_prf in symmetric-shake-9d277b.o
      ...
  "_randombytes", referenced from:
      _pqcrystals_kyber512_ref_keypair in kem-9bb932.o
      _pqcrystals_kyber512_ref_enc in kem-9bb932.o
      _pqcrystals_kyber512_ref_indcpa_keypair in indcpa-c434fa.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)
make: *** [libpqcrystals_kyber512_ref.so] Error 1

I installed openSSL (I am on MacOS) and exported this flags:

export CFLAGS="-I/usr/local/opt/[email protected]/include"
export NISTFLAGS="-I/usr/local/opt/[email protected]/include"
export LDFLAGS="-L/usr/local/opt/[email protected]/lib"

What's the issue?

Thanks

randombytes.c dependency on shared libraries

Hello
When compiling Kyber as shared libraries, I believe that you are missing the randombytes.c file in the Makefile. I tried using the shared library in a Python script and it states "OS Error: randombytes symbol not found". I fixed it, by adding said file to the compilation command and now it works perfectly.

Environment:
Ubuntu 20.04
GCC 9.3.0
Python 3.8

Reproductible action:
Compiling shared libraries with "make shared" and then calling the libraries from Python

Expected result:
Libraries loaded and functions working

Actual result:
Library not loaded and error message "OS Error: randombytes symbol not found"

Cheers !

Improving code comments: Document length of buffer arguments

It would be very helpful to document which constants describe the lengths of the input/output buffers.

As an example here's the code comment for the function indcpa_enc:

/*************************************************
* Name:        indcpa_enc
* 
* Description: Encryption function of the CPA-secure 
*              public-key encryption scheme underlying Kyber.
*
* Arguments:   - unsigned char *c:          pointer to output ciphertext
*              - const unsigned char *m:    pointer to input message (of length KYBER_SYMBYTES bytes)
*              - const unsigned char *pk:   pointer to input public key
*              - const unsigned char *coin: pointer to input random coins used as seed
*                                           to deterministically generate all randomness
**************************************************/

All 4 parameters have a fixed size, however only for m it's documented. Without being familiar with the internals of kyber it's hard to figure out what size c, pk and coin should have. I'd therefore recommend to document in all cases of input buffers which constant from params.h describes their length.

Error when running `cd kyber/ref && make`

Error message:

rng.c:10:10: fatal error: 'openssl/conf.h' file not found
#include <openssl/conf.h>
         ^~~~~~~~~~~~~~~~
1 error generated.
make: *** [PQCgenKAT_kem] Error 1

Thanks.

About the plaintext length of CPAPKE

May I ask why CPAPKE can only encrypt data with a fixed length of 32 bytes? I don't seem to have found any explanation about this in the document. Does this mean that I cannot consider CPAPKE as a public key encryption scheme that can replace RSA?