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?
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.
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.