# Space complexity and cryptography

It appears that in cryptography a lot of definitions are based on the time complexity of various algorithms. For example, a "good" encryption scheme should be resilient against a polynomial adversary. Or, inverting the image of a one-way function should take more than polynomial time.

1. Why is there hardly any discussion (at least in introductory textbooks) of space complexity? Maybe there is an encryption scheme out there that can be 'broken' in polynomial time, but only with super-polynomial space. Should that scheme also be considered 'safe'?

2. Are there any known non-trivial results about the space complexity of some cryptographic primitive? By non-trivial I mean something that isn't an immediate result of $\mathrm{NP}\subseteq \mathrm{PSPACE}$ or something similar...

• In my experience papers that describe attacks with explicit time complexity estimates usually explicitly include the space complexity. If it's omitted it might be because: It needs O(1) space and it's fairly obvious. Or it's fairly clear it needs space proportional to the number of function evaluations (which is proportional time). Or there is a time space trade off. Or it's a bad paper. – Future Security Jul 2 '18 at 21:20

That possibility can be excluded; if an algorithm uses $F(x)$ time (for any $F$), then that algorithm can be implemented using $O(F(x))$ space. The reason is fairly obvious; in $F(x)$ steps, the algorithm can access at most $\ell F(x)$ memory locations (assuming a 'step' accesses at most $\ell$ memory locations, where $\ell$ is some constant). So, by tracking which memory locations the algorithm actually touches, and just tracking those (which another constant multiplier in terms of overhead), and so this modified algorithm uses (at most) a constant factor more memory than the total number of steps.
To give a simple example, suppose that you have an encryption for which a known attack recovers the key in time $$2^{64}$$. Should you use this encryption scheme? The standard answer would be essentially no: $$2^{64}$$ is not out of reach for today's computational power. But looking more closely, considerations about space do in fact matter a lot here: if the best key-recovery attack requires time $$2^{64}$$ and space (say) $$2^{10}$$, it's obviously insecure. But it might be that the best known attack requires both time and space $$2^{64}$$. This is important: space is way more costly than time in practice. Doing $$2^{64}$$ operations can be envisioned; storing $$2^{64}$$ bits of data is considerably more involved (I won't make precise guesses about how feasible it could be nowadays - but you get the point).
In fact, until quite recently, the importance of taking memory cost into account when estimating security was somewhat overlook in the cryptographic community. This was recently addressed in a very cool paper. They make the following observation: often, to argue that a primitive A is as secure as a primitive B, one uses a cryptographic reduction, showing that an algorithm breaking A in time $$t$$ can be converted into an algorithm breaking B in time $$t'$$, where $$t'$$ is "not so much larger" than $$t$$. But if the reduction is memory-loose, it might be that the algorithm breaking A in time $$t$$ with memory $$m$$ leads to an algorithm breaking B in time $$t'$$ using a memory $$m'$$ much larger than $$m$$. Now, if $$m'$$ is too large, then your reduction might not in fact give you any good security guarantee for A: it might be infeasible to concretely break B using this algorithm if $$m'$$ is huge, even though it could be feasible to concretely break A with memory $$m$$, hence one cannot say that "if it's infeasible to break B, then it's infeasible to break A", while this was the all point of the reduction. The paper goes on with defining memory-tight reduction, which preserve as much as possible the memory cost of the algorithm in the reduction, and initiate a systematic study of which reductions in cryptography are memory-tight.