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.

But what about space complexity?


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'?
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...
Maybe there is an encryption scheme out there that can be 'broken' in polynomial time, but only with super-polynomial space.


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.