2
$\begingroup$

Are the methodologies (hard problems being used to secure the encryption) in post-quantum algorithms inherently slower than what we have right now? If not, why weren't they used initially?

$\endgroup$
1
  • 2
    $\begingroup$ Any good block cipher with 256 bit keys like AES-256 is secure against Quantum computers. NIST PQC doesn't include encryption rather, Key establish, Digital signature, public-key encryption. You might need to change your question. The answer is already yes. $\endgroup$
    – kelalaka
    Apr 9, 2022 at 19:16

2 Answers 2

3
$\begingroup$

Computation wise, there are schemes faster in some functions (e.g. KEM, sign, verify).

Commnication cost wise, generally PQC schemes have larger communication cost than current public key cryptosystems.

For speed comparison, you may checkout https://bench.cr.yp.to/supercop.html

For some real-world application attemps, you may checkout https://blog.cloudflare.com/the-tls-post-quantum-experiment/

Or you can do benchmark on your own: https://openquantumsafe.org/liboqs/

$\endgroup$
2
$\begingroup$

Found the answer:

At equivalent cryptographic strength, NTRU performs costly private key operations much faster than RSA does. The time of performing an RSA private operation increases as the cube of the key size, whereas that of an NTRU operation increases quadratically.

While NTRU is technically faster than RSA in encryption operations per second, it is not overall faster in verification, so which is faster depends on a breakdown of your usecase. (see @Habib's comment)

Sources: https://tbuktu.github.io/ntru/, https://homes.esat.kuleuven.be/~fvercaut/papers/ntru_gpu.pdf

$\endgroup$
3
  • 2
    $\begingroup$ While this is true, it is misleading. Generally, verification time is the most important time between key generation, signature, and verification algorithms. And, I believe there is no digital signature that can beat RSA in that (with 65537 as the exponent.) Also, performance is not only about computational complexity but also signature and public-key size. Lower performance is an important factor against PQC adaptation. However, the main reason is that they hasn't been studied enough. Every now and then, a new attack against PQC algorithms pops up. $\endgroup$
    – Habib
    Apr 9, 2022 at 21:58
  • $\begingroup$ @Habib thanks, I'll edit my answer to address that. Actually, no point in that seeing as your comment is detailed enough $\endgroup$
    – belkarx
    Apr 9, 2022 at 22:07
  • 1
    $\begingroup$ @Habib: "And, I believe there is no digital signature that can beat RSA in that (with 65537 as the exponent.)" - counterexample: Rabin-Williams :-) $\endgroup$
    – poncho
    Apr 10, 2022 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.