Score:2

Crypto

Are PKI PQC algorithms slower than their nonPQ counterparts? (e.g. NTRU vs RSA)

belkarx

8/9/23, 7:10 PM

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?

146

0 + 0

encryption

post-quantum-cryptography

pki

kelalaka

8/9/23, 7:16 PM

Any good block cipher with 256 bit keys like AES-256 is secure against Quantum computers. [NIST PQC](https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions) doesn't include encryption rather, Key establish, Digital signature, public-key encryption. You might need to change your question. The answer is already yes.

Score:3

Crypto

9f241e21

8/10/23, 2:40 AM

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/

0 + 0

Score:2

Crypto

belkarx

8/9/23, 7:57 PM

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

0 + 0

Habib

8/9/23, 9:58 PM

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.

belkarx

8/9/23, 10:07 PM

@Habib thanks, I'll edit my answer to address that. Actually, no point in that seeing as your comment is detailed enough

poncho

8/10/23, 2:43 AM

@Habib: "And, I believe there is no digital signature that can beat RSA in that (with 65537 as the exponent.)" - counterexample: Rabin-Williams :-)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Are PKI PQC algorithms slower than their nonPQ counterparts? (e.g. NTRU vs RSA)

TH: อัลกอริทึม PKI PQC ช้ากว่าคู่ที่ไม่ใช่ PQ หรือไม่ (เช่น NTRU กับ RSA)

RO: Sunt algoritmii PKI PQC mai lenți decât omologii lor nonPQ? (de exemplu, NTRU vs RSA)

RU: Являются ли PKI-алгоритмы PQC медленнее, чем их аналоги без PQ? (например, NTRU против RSA)

VI: Các thuật toán PKI PQC có chậm hơn so với các thuật toán không phải PQ của chúng không? (ví dụ: NTRU so với RSA)

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.