Bursting The Myth on Post Quantum Cryptography (PQC) Being Slow
Bursting The Myth on Post Quantum Cryptography (PQC) Being Slow
I posted an article on LinkedIn on PQC, and managed to get a comment of:
And, which I think is completely wrong, and I believe PQC methods are on a-par with elliptic curve methods, and much faster than RSA. So let me show you:
For this, I ran tests on all of the finalists for the key exchange methods [here]. For Kyber512 we get:
Configuration info
==================
Target platform: x86_64-Linux-5.4.0-94-generic
Compiler: gcc (9.3.0)
Compile options: [-march=native;-Werror;-Wall;-Wextra;-Wpedantic;-Wstrict-prototypes;-Wshadow;-Wformat=2;-Wfloat-equal;-Wwrite-strings;-O3;-fomit-frame-pointer;-fdata-sections;-ffunction-sections;-Wl,--gc-sections;-Wbad-function-cast]
OQS version: 0.7.2-dev
Git commit: fb8f0ffa18dacfcb47b0cd987c0eb3807d5bd6d2
OpenSSL enabled: Yes (OpenSSL 1.1.1f 31 Mar 2020)
AES: OpenSSL
SHA-2: OpenSSL
SHA-3: C
OQS build flags: OQS_OPT_TARGET=auto CMAKE_BUILD_TYPE=Release
CPU exts compile-time: AES AVX AVX2 BMI1 BMI2 PCLMULQDQ POPCNT SSE SSE2 SSE3
Speed test
==========
Started at 2022-01-31 19:10:01
Operation | Iterations | Total time (s) | Time (us): mean | pop. stdev | CPU cycles: mean | pop. stdev
------------------------------ | ----------:| --------------:| ---------------:| ----------:| -------------------------:| ----------:
Kyber512 | | | | | |
keygen | 151224 | 3.000 | 19.838 | 3.479 | 39455 | 6765
encaps | 133941 | 3.000 | 22.398 | 5.971 | 44574 | 11844
decaps | 202623 | 3.000 | 14.806 | 4.076 | 29462 | 8053This means that key generation is 19.8 microseconds for key generation, 22.4 microseconds for key encapsulation, 14.8 microseconds for key decapsulation. Thus we can perform over 50,000 key generations per second.
For Dilithium (with digital signatures) [here], we have the following:
Configuration info
==================
Target platform: x86_64-Linux-5.4.0-94-generic
Compiler: gcc (9.3.0)
Compile options: [-march=native;-Werror;-Wall;-Wextra;-Wpedantic;-Wstrict-prototypes;-Wshadow;-Wformat=2;-Wfloat-equal;-Wwrite-strings;-O3;-fomit-frame-pointer;-fdata-sections;-ffunction-sections;-Wl,--gc-sections;-Wbad-function-cast]
OQS version: 0.7.2-dev
Git commit: fb8f0ffa18dacfcb47b0cd987c0eb3807d5bd6d2
OpenSSL enabled: Yes (OpenSSL 1.1.1f 31 Mar 2020)
AES: OpenSSL
SHA-2: OpenSSL
SHA-3: C
OQS build flags: OQS_OPT_TARGET=auto CMAKE_BUILD_TYPE=Release
CPU exts compile-time: AES AVX AVX2 BMI1 BMI2 PCLMULQDQ POPCNT SSE SSE2 SSE3
Speed test
==========
Started at 2022-01-31 21:22:58
Operation | Iterations | Total time (s) | Time (us): mean | pop. stdev | CPU cycles: mean | pop. stdev
------------------------------ | ----------:| --------------:| ---------------:| ----------:| -------------------------:| ----------:
Dilithium2 | | | | | |
keypair | 51315 | 3.000 | 58.463 | 175.138 | 116511 | 349422
sign | 17473 | 3.003 | 171.848 | 1143.485 | 342726 | 2281463
verify | 53125 | 3.001 | 56.486 | 176.715 | 112506 | 351939In this case, the key pair generation is 58 microseconds, the signing at 171 microseconds and 56.5 microsecond to verify. This is much faster than RSA. We can see that rather than it being slot-crypt, Kyber and Dilithium peform well.
Performance of PQC
Every single tick of the clock on a computer system costs a little bit of energy, and where a processor running at 100% consumes much more energy than it idling. Along, with challenges in the amount of energy that our digital systems consume, we have the threat of quantum computers on our existing public key systems. For this, we now see the rise of PQC methods, such as using lattice techniques. But, what is the energy footprint of these PQC methods, and how does it compare with RSA and ECC for our TLS connections?
Well, the energy footprint of PQC with TLS has now been assessed with this new paper:
Figure 2: [1]
The usage of TLS 1.3 matches well with a real-life situation. With PQC, we do not have the concept of the Diffie-Hellman key exchange method, and now replace it with an encapsulation of the key within an encrypted transmission (Figure 3) — KEM (Key Encapsulation Method).
An important part of the process is the signing of the key exchange, and which protects against an Eve-in-the-middle attack. We thus need a digital signature method, alongside our KEM. For PQC KEMs, we have Kyber, Bike, HQC and FrodoKEM, and for digital signatures, we have Dilithium, Sphincs+, and Falcon. Normally, in our TLS 1.3 handshakes, we only use elliptic curve methods, so ECDHE is the standard handshaking technique, and then we can choose RSA or ECDSA for the digital signature.
In the experiment, a PicoScope is used to measure the energy consumption of each method (Figure 4):
Figure 4: Experimental setup [1]
The experiment involves a breakdown of the handshake, and for key generation, encryption (signing) and decryption (verifying). It can be seen from Table 1, that RSA is costly for key generation.
For KEM, we see that Kyber512 compares well with ECDHE, and that the performance is similar in most areas, along with having a similar energy footprint. In fact, Kyber512 improves on ECDHE for energy consumption in the handshake of the key. Bike and FrodoKEM do less well, and are considerably slower the Kyber512 and ECDHE, and also consume much more energy. In the case of FrodoKEM, the energy consumption is more than 25 times greater than Kyber512 and ECDHE. HQC performs better than Bike and FrodoKEM, but still consumes more energy than Kyber512 and ECDHE.
For signatures, we can see why NIST selected Dilithium as a standard, as it has a similar performance to ECDSA. The other PQCs struggle with performance and are even slower than RSA signatures. Sphincs+ is especially hungry for energy and has a poor performance level. Surprisingly Falcon did not do well in this test — even though it is a lattice method (and thus similar to Dilithium).
Table 2 outlines the methods when they are paired. The benchmark for current handshakes is ECDHE with either an RSA or ECDSA signature. Overall, ECDSA+ECDHE has a much lower energy footprint than RSA+ECDHE (due to the costly RSA signature part). For the PQC methods, we see that Dilithium and Kyber provide improved energy consumption to ECDSA+ECDHE, but much better than RSA+ECDHE. Unfortunately, Sphincs+Kyber is extremely costly in both performance and energy consumption. This is due to its large digital signature, and which must be carried in many TLS packets.
When we benchmark energy consumption against RSA+ECDHE and ECDSA+ECDHE (Table 3), we see that Dilithium+Kyber are Falcon+Kyber generally much more efficient compared with RSA+ECDHE, but only Dilithium and Kyber beats ECDSA+ECHDE. The performance of all the PQC methods, apart from Sphincs+ and Kyber, do pretty well compared with our existing key exchange methods.
Conclusions
Don’t believe the hype … the new standards for PQC perform just as good in many cases than our existing public key methods.