0
$\begingroup$

I see the claim (which I'm not doubting) that encrypting data using asymmetric algorithms is slower than symmetric algorithms.

But I never see citation on these claims, not here, on wikipedia or even in papers.

It seems in academic papers RSA and the like are for signatures and are never considered when comparing encryption algorithms.

Is there a more comprehensive review I'm missing?

$\endgroup$
  • $\begingroup$ Of course I find one immediately after asking, but surely there are more. $\endgroup$ – Minix Jan 19 at 18:24
  • 2
    $\begingroup$ The link posted is to a paper from 2012 without any content, "testing" algorithms at least 15 years old. It's full of spelling mistakes and the "professors" of this Indian university have problems spelling words such as "Feistel" in an accepted paper in one of those journals that have over 3000 pages and exist just to accept these kind of papers. $\endgroup$ – Maarten Bodewes Jan 19 at 19:01
  • $\begingroup$ There is not necessarily much of a performance difference between asymmetric and symmetric encryption. RSA encryption with $e=3$ can be quite fast. Problem is, we know no asymmetric encryption scheme which decryption is fast. $\endgroup$ – fgrieu Jan 19 at 20:56
1
$\begingroup$

There are three different possible things you are asking for:

  • Concrete stats and numbers from a benchmark
  • Analysis of the algorithms in terms of bit operations required
  • Proof that asymmetric encryption must be more expensive than symmetric encryption

Benchmarks

If you're just looking for actual stats and numbers, there are the SUPERCOP/eBATS benchmarks.

You can also investigate the command openssl speed.

Bit operations

If you're looking for a theoretical analysis of the number bit operations used by asymmetric encryption compared to the number of bit operations used by symmetric encryption, that may be harder to come by in the form of a single paper. You'd need to do an analysis of the number of bit operations of all the relevant $\operatorname{encrypt}$ function (which may be different than the $\operatorname{decrypt}$ function).

For symmetric algorithms, the introductory paper(s) will typically provide a measure in cycles per byte. But cycles per byte are a feature of architecture and implementation, not intrinsic to the abstract algorithm, and so are not useful here.

You would need to know which algorithm is being used to implement the required function. For example, with modular exponentiation the naive algorithms of multiplying $g$ times itself $x$ times will have a drastically different number of bit operations compared to using the square and multiply algorithm.

And on that note, you would also need to know the most optimal algorithm for implementing each functionality to conclusively say that algorithm $A$ requires more bit operations than algorithm $B$. That could prove to be a challenge at the very least, and maybe even prohibitive in the worst case.

Proof it must be this way

If you're looking for a proof that says asymmetric encryption must be slower than symmetric encryption, then I doubt such a result exists.

There is a paper that shows that (secure) key exchange in the random oracle model is impossible.

One supporting argument might Diffie-Hellman and the discrete logarithm problem. There are generic attacks against the discrete logarithm problem which place a minimum on the size of the used group, which consequently raise the cost of using the algorithm.

However, DH is not public-key encryption, it is key agreement, and it is only a single algorithm, so it certainly does not qualify as proof that all asymmetric encryption must be slower than symmetric encryption.

On a related note, in general, asymmetric algorithms (discounting hash-based signatures) have structure, whereas symmetric algorithms (typically) do not. This structure appears to contribute to an increase in the amount of space required to use such algorithms, which again contributes to an increase in the amount of time required to use such algorithms. However, this is again not proof that it must be this way.

$\endgroup$
  • $\begingroup$ I'm most interested in the benchmark, but I can't find a direct comparison. All I can find are these kinds of graphs no actual data. $\endgroup$ – Minix Jan 19 at 20:08
  • $\begingroup$ @Minix I'm quite sure that SUPERCOP/eBats is your best bet. They absolutely do have data and not just graphs that I can admit are difficult to read. $\endgroup$ – Ella Rose Jan 19 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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