4
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ As far one big and recent and practical example that illustrate the RAM phenomena considered in the previous posts, you can read the literature about the cryptanalysis of SVP, where the authors use very complex algorithm to obtain the best Space-time compromise : link.springer.com/chapter/10.1007/978-3-319-76578-5_14 $\endgroup$ – Ievgeni Jul 22 '19 at 16:50
4
$\begingroup$

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 tasks/techniques/concepts/results/articles about time-complexity than space-complexity. Overwhelmingly, programming contests are about time-complexity.
  • Space/memory can be reused easily. Available space can be expanded easily. On the other hand, time needed for computing cannot be shorten that easily. Parallelization helps, but it cannot speed up the serial part of the program. Practically and relatively speaking, we are enjoying the cheap memory 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 have $O(1)$ space time-complexity. Although space might be critical such as in embedded devices, there is not much value of space-complexity in general.
  • On the other hand, the time-complexity is the critical factor of a cryptographic algorithm, especially in encryption/decryption. It should produce data fast enough. Authorized users should be able to retrieve the plaintext fast enough while adversaries do not have fast algorithms to decrypt the ciphertext.
| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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(\sqrt{n})$ time and space complexity in crypto)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This isn't true for offline algorithms. One easy way to quickly solve questions is to build a lookup table of all questions and their answers; this allows you to answer any (decidable) problem in time $O(n)$ and space $O(2^n)$. Of course there is at least $O(2^n)$ time (and possibly a lot more) spent building the lookup table, but in offline algorithms that isn't counted as a resource. $\endgroup$ – Mario Carneiro Jun 12 '19 at 1:27
  • $\begingroup$ @MarioCarneiro Your use of the term "offline algorithm" seems non-standard. Is this really a model of computation that people study? $\endgroup$ – Tom van der Zanden Jul 22 '19 at 17:03
  • 1
    $\begingroup$ @Tom It is. It's actually quite practical in certain circumstances, and lookup tables often form the base case of some advanced algorithms. For example, if you have a sorting algorithm then you might stop at n = 20 and brute force an optimal sorting network below that. The cost is entirely up front and you get an efficient algorithm at the end. There are lots of areas where time is much more valuable than space, for example a server that needs to respond to requests with low latency but can waste as much memory as it likes to do so. $\endgroup$ – Mario Carneiro Jul 23 '19 at 8:48
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.