7
$\begingroup$

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?

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Jul 2, 2018 at 21:20

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

To complement poncho's answer: from a theoretical point of view, as poncho pointed out if it can be broken in polynomial time, then this requires only polynomial space, hence considering only time in security analysis makes perfect sense if one only cares about asymptotic security ('polynomial' versus 'superpolynomial'). However, your question becomes particularly interesting when one consider the concrete security of a cryptographic primitive.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.