Mfcttrf

I've noticed quite a few cryptographic algorithms speak mainly of the time complexity of an algorithm. For example, with a hashing function h, find x given y = h(x). We normally speak on how long it will take. Or the time to find the discrete log for a public key.

Edit:

While writing this question, I pondered that maybe because for most algorithms in cryptography (that I have seen) , have O(1) space time complexity. i.e. If the solution does not work, we throw it away and encrypt.

Clarification on this will be really helpful.

In fact, when we are talking about algorithms in general, time-complexity is discussed much more frequently than space-complexity. Let me provide a few ideas to support that more general phenomenon which applies to the cryptography as well.

• There are much more about time-complexity to talk about in computer science and software industry while space-complexity is more restricted to hardware. It occurs to me that there are over 10 times more techniques/concepts/tasks/papers about time-complexity than space-complexity. Overwhelmingly, programming contests are about time-complexity.


• Unlike time, space/memory can be reused. Practically speaking, we see that memory is cheap now while we are still hungry for computing speed.

Now come to the cryptography side of the question.

• As you have observed, most algorithms in cryptography (that I have seen), have $O(1)$ space time-complexity. So there is not much value of space-complexity.


• On the other hand, the time-complexity is the critical factor of a cryptographic algorithm. It should produce data fast enough. It should produce data secure enough, meaning the time-complexity of all decrypting algorithms should be very slow.

To add to what Apass.Jack said, in most computational models (e.g. Turing Machines, maybe RAM as well, I don't know), space used is bounded by time : you need to do at least one operation per unit of memory to "use" it.

For example you won't find algorithms with $O(n^2)$ time complexity and $O(2^n)$ space complexity.

Space complexity is usually studied/mentioned when it is critical, for example when it is as big as the time complexity (e.g. Shank's algorithm with $O(sqrtn)$ time and space complexity in crypto)

If you are looking at theoretical results, they are theoretical.

If you are looking at practical results, the one that is more important is the one that keeps you from getting results. For the price of a small new car, I can buy a computer with $2 cdot 10^12$ bits of RAM, which can perform about $5 cdot 10^15$ operations per day. With that computer, the space needed MUST be below $2 cdot 10^12$ bits, or I cannot solve that problem. The number of operations SHOULD be below $5 cdot 10^15$, or I will have to wait quite a while for results - but for say $10^17$ operations I still have the choice between being patient or investing the time into improving the algorithm or the implementation.