Subject: Re: [pqc-forum] A question on the keypair generation of Classic McEliece From: Tung Chou Date: Mon, 3 Aug 2020 17:46:20 +0800 To: Joo Yeon Cho , pqc-forum@list.nist.gov Message-ID: Hi Joo, First of all, it is not clear to us what you meant by the "H matrix". If you meant the matrix \hat{H} in our specification, then using it as the public key will lead to an insecure cryptosystem. If you actually meant S\hat{H} where S is a random invertible matrix, this is not necessarily faster as there is still the cost of finding an invertible S which has the same 0.29 success probability. We'd be happy to help solve the performance problem you are facing. Can you please tell us which protocol you are using, which implementation you are using, and which platform you are working on? Which protocol you are using determines how frequently you have to perform key generation. For example, if you use ephemeral keys, then for each connection you will need to pay for the cost of key generation. Note that Classic McEliece is designed to be CCA2-secure, so reusing a key is safe and does not lose any security. We have highly-optimized bitsliced implementations sse and avx for platforms with corresponding x86-64 extensions. We also have a portable bitsliced implementation vec, which has been included in the latest versions of SUPERCOP. The ref implementation is also portable, but it is much slower than vec. As far as we know, your experiments were carried out on a 32-bit platform, so the best choice at this moment is to use the vec implementation. Please note that as the vec implementation works on 64-bit words, the compiler might not be able to compile it into efficient 32-bit binaries, not to mention that vec does not use any platform-specific optimizations. Please let us know if you run into problems compiling this version. Although this has not been announced before, Ming-Shing Chen and I have been working on implementing Classic McEliece on Cortex-M4 (specifically, the board is stm32f4-Discovery). This is a 32-bit architecture without much RAM. Our implementation was adapted from the vec implementation. We suggest that you can specify your platform and show us your latest experimental results, so that we can figure out how to modify our M4 implementation to fit your platform. Best regards, Tung Chou (on behalf of the Classic McEliece team)