Security defined with space complexity

Question

My question is about security defined through space complexity. Suppose I have an encryption function $C=E(K,P)$ for which it can be proved (algebraically) that given $P,C,$ the possible keys which match the equation belongs to a set $S(P,C)$ of exponential size but $$|S(P,C)|\ll O(2^{\ell(K)})$$ where $\ell$ is the key length.

Then the key can be verified in parallel in polynomial time breaking the scheme in polynomial time by parallel computation but far better than brute force search. If no other estimate of $S(P,C)$ of smaller size is known, can this be considered a secure scheme? In such a case can the security be be considered weak if $|S(P,C)|$ can be shown to be bounded by sub exponential size?

Answer 1

Firstly, I assume you use the $\ll$ not as in number theory where $f(\ell)\ll g(\ell)$ means $f(\ell)=O(g(\ell))$ but as much less than, which usually means $$f(\ell)\leq \frac{g(\ell)}{h(\ell)}$$ where $h(n)$ is some increasing function of $\ell.$ The crucial question is how fast is $h(\ell)$ growing?

To break the cryptosystem in parallel polynomial time, you need an exponential number of processors, unless $h(\ell)$ is itself growing very fast in $\ell.$ In fact this argument could apply to any cryptosystem which is considered secure, such as AES, for example. And this is NOT far better than brute force, it is just parallel brute force in the presence of the obvious embarrassing parallelism in the key space, since you need to deploy an exponential number of processors, as in the EFF key search attacks on DES.

What I am trying to say, not very well, is that any secure cryptosystem is insecure under parallel computation to some extent. So I'd say in answer to your first question, this is not a real weakness.

As to your second question, yes, if $S(P,K)$ is subexponential in size, this is a real weakness.

And finally, since you are talking algebraic attacks, presumably you have an algebraic specification of what $S(P,K)$ looks like, which you can use in your attacks.