Computational Complexity Of Breaking Information Theoretic Security Wikipedia mentions that Shamir's secret sharing(SSS) for example, has information theoretic security. While I understand the concept that the adversary would just not have enough information to break the security, it must also correspond to some computatioal complexity class, shouldn't it? Let's say I'm an adversary and am presented with an instance of SSS. I have unlimited computational powers. Would I find it at least as hard as the Halting problem? Is it easier than that? Which class can be assigned to breaking such information theoretically secure protocols?
Here's an simpler but analogous problem that may illustrate what's going on:

Given that $X=Y+Z$ and $Y=5$, compute $X$.

The problem isn't that the answer is difficult to compute, the problem is that there isn't enough information there to give you any idea (any information about) what the answer is. That's what's meant by information-theoretic security.
(Note: what I've given above isn't actually an example of SSS, and if you actually try to apply statistical information theory to it, you'll run into trouble because the integers are infinite. If you're really worried about the latter issue, assume we're doing arithmetic modulo some integer $&gt;5$)