When is a cryptosystem (like RSA) or its algorithm for keygeneration, encryption and decryption of messages considered efficient? Is there some bound in complexity which splits both efficient and not efficient cryptosystems or algorithms of cryptosystems?

  • 4
    $\begingroup$ I’m voting to close this question because this is about computational algorithms in general, and not specific to cryptography. You can try searching on ComputerScience.SE first to see if this had a relevant answer already. $\endgroup$
    – DannyNiu
    Jun 3 '20 at 8:32
  • $\begingroup$ In my PC OpenSSL have 1.5GB/s encryption on AES-NI. 16522 2048 bits private RSA's in 10.00s. Now compare! $\endgroup$
    – kelalaka
    Jun 3 '20 at 8:34
  • 2
    $\begingroup$ @DannyNiu I disagree. Different domains of computer science have different notions of efficiency. Even within cryptography, there should be a discussion, at least, of asymptotic bounds and practical calculation times. $\endgroup$ Jun 3 '20 at 8:58
  • $\begingroup$ @Gilles'SO-stopbeingevil' Thank you, that's why I asked this here. Efficiency is a very objective topic and I think that efficiency does mean something else in terms of Cryptography. In Computer-Science one could say that polynomial time captures the intuitive notion of efficiency, and exponential time captures the intuitive notion of inefficiency. However, there are steps in the basic RSA-Cryptosystem which aren't efficient in terms of Computer-Science, for example the exponentiation while encrypting or decrypting messages. $\endgroup$
    – Doesbaddel
    Jun 3 '20 at 10:35
  • 1
    $\begingroup$ @DannyNiu: I do not see how a question asking (in addition to other related things) what an efficient cryptosystem is could be entirely off-topic on crypto.SE. Invoke that it is not worded correctly, does not show enough work, anything else, and I'm more ready to follow that. $\endgroup$
    – fgrieu
    Jun 3 '20 at 12:44

I'll be retracting my close vote, and submit my reasoning of cryptogrphic algorithms' efficiency.

To answer the question:

Is there some bound in complexity which splits both efficient and not efficient cryptosystems or algorithms of cryptosystems?

there isn't a clear separation between efficient and inefficient algorithms and cryptosystems, but often, they can be compared on the following 3 aspects of cryptographic efficiency.

1. Algorithm execution complexity

The most direct efficiency we think of is the time complexity of algorithms; for most of the time, we consider an algorithm efficient, when it takes polynomial time to complete.

But time isn't the only factor in considering the efficiency of an algorithm - space complexity is one of the other metrics we consider.

Also, for adversaries, we consider query complexity (sometimes called sample or data in the literature, but I'm not very sure. Feel free to correct me).

So there are 3 dimensions to the efficiency of algorithms: Time-Space-Query, and these combined is the actual complexity that should be considered. As an example, the best attack (excluding related-key) on the AES block cipher (biquelic attack) takes exponential space complexity to reduce the time complexity of attacking AES by only a factor of ~4.

2. Algorithm security-wise efficiency.

For cryptography, the rate at which increasing the cost of the algorithm instance increases the cost of adversary must be considered. We informally call this adversary defence efficiency for now.

For symmetric cryptography, this is mostly about deterring non-generic attacks such as differential analysis, linearization.

For public-key cryptography, this is more interesting.

Let's go back in history.

In "Secrecy, Authentication, and Public Key Systems", author Ralph Merkle proposed what can be considered earliest public-key encryption and digital signature schemes.

The PKE is a puzzle of symmetric-key cipher that provides only quadratic security against adversaries, and the signature scheme is very primitive and is based on hash functions.

The RSA and Diffie-Hellman cryptosystems are the next step in improving adversary defence efficiency to super-polynomial level. The hard problems on which these cryptosystems are based has non-generic attack - Generic Number Field Sieving (GNFS) which prevents them from achieving exponential adversary defence efficiency.

Then, elliptic curve cryptography eliminates the non-generic attack present in integer number field, leaving only Pollard-rho algorithm for discrete logarithm for generic attack. This gives elliptic curve cryptography security similar to that of collision-resistant hash functions.

3. Algorithm implementation optimization

The last type of efficiency is the capability of implementations of algorithms to maximize the utility of host of execution, may it be a computer CPU or a HSM (hardware security module).

This is an active area of research.

For symmetric-key cryptography, the NIST Lightweight Cryptography project is interesting to follow.

For public-key cryptogarphy, I find this proposition from the presentation on Crystals-Kyber KEM/PKE algorithm made by Peter Schwabe at the Second PQC Standardization Conference in 2019 interesting. On page 7, it says among others:

Benchmarks of lattice-based KEMs are really benchmarks of symmetric crypto

This was said in the presentation to highlight the fact that lattice-based KEMs/PKEs are based on super-efficient mathematical objects, yet the bottleneck of their efficiency lies in the symmetric cryptographic algorithms they internally employ.

  • $\begingroup$ Thank you for changing your mind and providing a detailed answer! $\endgroup$
    – Doesbaddel
    Jun 6 '20 at 9:05

From a theoretical perspective in cryptography, a cryptosystem is efficient when the execution time of the algorithm run by the legitimate user grows as a polynomial of a security parameter $k$, while the execution time for the best algorithm an adversary can run to break the system grows faster than any polynomial of $k$ (some change that to: exponentially with $k$, thus giving a different, less common definition).

This definition does not require to specify what $k$ is, and it's readily proven that changing $k$ to a polynomial in $k$ does not change the outcome of the above test. But often, $k$ is the size of something in bit, like the key, or the signature. In symmetric crypto, it is typically the size of the secret key.

From a practical perspective, the line is not clear. Make it: whatever is acceptable in the context.

  • 2
    $\begingroup$ From a practical perspective, it also shifts over time. The theoretical definition doesn't change. $\endgroup$
    – Maeher
    Jun 3 '20 at 18:14
  • 1
    $\begingroup$ Note that "grows faster than any polynomial" $\neq$ "grows exponentially", the gap has runtimes like $L_p[1/2,4]$ or algorithms like the quadratic sieve or the GNFS. $\endgroup$
    – SEJPM
    Jun 5 '20 at 7:43

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.