# 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?

This is about the Theory of Computability not the Theory of Complexity.

The halting problem is a decision problem in CS. From Wikipedia's introduction;

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program's execution; it can take arbitrarily long and use an arbitrary amount of storage space before halting. The question is simply whether the given program will ever halt on a particular input.

This doesn't mean that all instances of the problem are not decidable[*]. Just that there is no general algorithm that works for all possible algorithms and all possible inputs to the algorithms.

In Information-theoretic security, SSS or OTP is computable but there isn't a well-defined correct answer. Yes, an unlimited power ( or given enough time to a Universal Turing Machine) can compute all possible solutions to SSS or OTP but cannot literally decide the solution without extra information. So; no information no solution.

There is an important distinction, some of the instances of the Halting can be decidable[*] but no instance of SSS or OTP can have well-defined answer ( assuming that the setup is correct!).

[*]The halting problem is theoretically decidable for linear bounded automata (LBAs) or deterministic machines with finite memory.

• Shoot me if I've written wrongly! – kelalaka Feb 7 at 19:54
• You've written very well. This is a great answer. – forest Feb 7 at 22:22
• Terminology quibble: "Decidable"/"undecidable" refers to yes/no problems (essentially, boolean functions). "Computable"/"uncomputable" refers to general (usually non-boolean) functions. But inferring the secret without enough shares isn't either of those, because it isn't even a well-defined function. All answers are possible, so there isn't a well-defined correct answer. – Gordon Davisson Feb 8 at 8:56
• @GordonDavisson thanks for the shoot. I did not use the undecidable in the sense of CS term, however, that creates the conflict. I've borrowed your last sentence to explain that in parenthesis. – kelalaka Feb 8 at 13:17
• @kelalaka: Re: "the OP wanted the comparison": Oops, you're right, I somehow missed that sentence in the question! OK, yes, I'm good with this answer now. :-) – ruakh Feb 8 at 23:30

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 $$>5$$)

• The is one nitpick in this example: In cryptography, we use mostly discrete math, SSS uses finite field arithmetic and cannot achieve Information-theoretic security with integer arithmetic. In your case, it is impossible to even list all solutions. If you use a mod, we can simply say, a UTM can work on them on a finite step but there is no information to provide the solution. – kelalaka Feb 10 at 8:59
• @kelalaka I agree (that's why I added the parenthetical caveat). I was trying to distill out the core issue to as simple and intuitive form as possible, and that meant removing (/ignoring) as many of the technical complications as possible, – Gordon Davisson Feb 10 at 22:49

As others have noted, information-theoretic security really has no connection to computational complexity. Yes, with sufficient computing power, you could enumerate all the solutions (including the right one). But without enough information (e.g. the key in OTP, or enough shares in SSS) you would still have no way of telling which of the solutions is the correct one.

Let me illustrate this with a simple example. Let's say we're doing 2-out-of-2 Shamir's Secret Sharing in GF(3). That is, we have a secret $$s \in \{0,1,2\}$$ and two shares $$a_1, a_2 \in \{0,1,2\}$$ chosen at random from among the solutions to the modular congruence: $$a_1 - s \equiv a_2 - a_1 \pmod 3.$$ (Given $$s$$, we can generate such a random solution e.g. by choosing $$a_1$$ uniformly at random and then solving the congruence for $$a_2$$, or vice versa.)

Now, if we know both $$a_1$$ and $$a_2$$, we can easily solve the congruence above for $$s$$. In fact, since the number of possible values is so small, we can just list all the possible combinations in a table: $$\begin{array}{cc} & \quad\quad \color{red}{a_2} \\ \lower{0.7em}\color{green}{a_1} & \begin{array}{r|ccc|} & \color{red}0 & \color{red}1 & \color{red}2 \\ \hline \color{green}0 & 0 & 2 & 1 \\ \color{green}1 & 2 & 1 & 0 \\ \color{green}2 & 1 & 0 & 2\\ \hline \end{array} \end{array}$$

If you examine this table, you'll notice something interesting: every value of $$s$$ occurs exactly once on each row, and exactly once on each column. And knowing only $$a_1$$ only tells us which row the correct solution lies in, while knowing only $$a_2$$ tells us only which column the solution lies in.

So what about, say, an attacker who only knows one of the shares? Well, with enough computing power (which in this case is very little) they can also iterate by brute force over all possible values of the shares, generating a table like the one above, look up the row or column corresponding to the share they know, and find out that… the secret is either $$0$$, $$1$$ or $$2$$.

In fact, this is a general property (in fact, the fundamental property) of Shamir's Secret Sharing that holds regardless of how many shares there are and which finite field is used: given any $$m$$ shares, where $$m$$ is less than the reconstruction threshold, each possible value of the secret appears in exactly the same number of possible solutions. Which means that just knowing that one of those solutions must be the correct one doesn't give the attacker any information about the secret that they did not already possess.

And it doesn't matter how much computing power they spend examining this fact, because the additional information just isn't there to be found.

To me the key mental image with information theoretic security is that given a ciphertext ($$c$$), for any possible plaintext ($$p$$) there will be a key ($$k$$) to decrypt the ciphertext to it.

So given a $$c$$ we have $$\forall p: \exists k: Dec_k(c) = p$$

Which means that even if you brute-force try all the keys, you can get any output you might want and you will not know what the output for the correct key would have been.

As a simple example, if you know the ciphertext is the answer to the question if some nukes should be launched, than there exist keys which will decrypt to "yes" and keys which will decrypt to "no". So even after trying all the keys you will still not know what the intended answer was.

And because by definition any output is possible and as likely as any other, you will not only find "yes" and "no" answers, you will also find "Let's be nice and send them pancakes instead" as possible decryption output.

• But this is not strong enough to give perfect secrecy, since not only must there be a valid key, all possible keys must be equally likely, given the ciphertext. Some authors allow that observing the ciphertext still gives the same key distribution as the unconditional distribution – kodlu Feb 9 at 21:32

Information-theoretic security means that knowing the ciphertext doesn't help you find the plaintext. Knowing all $$b$$ bits of a single Shamir share tells you as much about the secret as knowing $$0$$ of the bits. You can still try to find the secret, and you could even succeed, but whatever you did would have worked just as well without the Shamir share.

As such, I don't think it makes sense to talk about the complexity of "breaking information theoretic security", because you didn't do that in any sense deserving of the name, even if you found the secret.