I always tend to think of information as follows: If we have an information set $I$, and it is possible to derive from $I$ another information set $X$, then $I$ really contained $X$ all along, and we haven't actually discovered "new information". We've merely found out something new about the information we already had.

But sometimes, deriving $X$ from $I$ is computationally very complex, so that it may take 1000 years to do it. In this case, any reasonable person in every day life, would say that we don't have the information $X$, even though we have $I$ and $X$ can theoretically be computed from $I$.

My question is, is there a concept that captures this notion of not having a piece of information merely because it is hard to compute? i.e. it could be something like: $I_{405}^*$ is the information set containing all information that can be generated by at most 405 computational steps from $I$. This is a somewhat vague definition, but I'm wondering if there is something more formal

  • $\begingroup$ Unless you can be very precise about what "information" is, there's no hope. And if you do that, it may turn out that the definitions are not at all interesting. $\endgroup$ – Raphael Dec 8 '17 at 9:12
  • $\begingroup$ @Raphael, yes, maybe. I'm thinking it could be that someone already came up with a precise definition of information in this sense already. Alternatively, it could be that someone captured this idea without employing the concept of information. $\endgroup$ – user56834 Dec 8 '17 at 9:31
  • $\begingroup$ Perhaps if you tell us what you want to do with this concept or how you want to apply it, we might be able to suggest a useful definition. You could look at the notion of a simulator in the definition of a zero-knowledge proof to see how that captures "computational information" in some sense, as well as the notion of a simulator in Goldwasser-Micali-'s original definition of semantic security. $\endgroup$ – D.W. Dec 9 '17 at 6:12
  • $\begingroup$ @D.W., thank you. I am thinking about this because I'm thinking of how to derive a probability distribution over an event, where I'm only allowed to take into account information that is computationally achievable given my knowledge $I$, rather than information that is logically implied by $I$. $\endgroup$ – user56834 Dec 9 '17 at 6:39
  • $\begingroup$ What do you mean by "derive a distribution"? If it's a distribution over an exponentially large space (e.g., $\{0,1\}^n$), usually you can't write down the distribution explicitly: that would require writing down $2^n$ numbers, which you can't do in a computationally feasible way. So I encourage you to think through what you're trying to achieve and see if you can define a task or goal. If you had a way to derive the distribution, what would you want to be able to do with it? What computation would you want to be able to do on the distribution? $\endgroup$ – D.W. Dec 9 '17 at 6:49

The distinction between information theoretic and computational knowledge is an issue which is fairly common in cryptography.

Consider for example the one-time-pad encryption, that given a message $m\in\{0,1\}^l$, encrypts it using a secret key $k$ (chosen uniformly at random) by $m\oplus k$. Clearly, one learns no information from seeing the encryption of one message (it is a uniformly distributed string), so you could say that you have information theoretic security, which should make you very happy. However, if you insist on such a strict notion of security, it turns out you cant encrypt messages who are longer than the key, and if you want to do that, you should settle for a weaker notion, which is security against bounded resources adversaries (see semantic security).

One example which seems to fit your question well is one way permutations. A function $f:\{0,1\}^*\rightarrow \{0,1\}^*$ is called a one-way permutation if for every $n\in\mathbb{N}$, $f|_{\{0,1\}^n}$ is a permutation of $\{0,1\}^n$, and for some bounded resources adversaries, almost no knowledge of $x$ is exposed from $f(x)$. Since $f$ is a permutation, $f(x)$ completely determines $x$, but it is extremely hard to recover.

That said, I will strengthen Raphel's comment and say that there isn't a general definition for information (or what you call computational information), this is an issue which strongly depends on the context.

  • $\begingroup$ Thank you. This is definitely the direction I was thinking in. Perhaps I'll have to drop the idea of a unifying concept indeed. But do you know of an introductory text that deals conceptually with this topic? If possible, specifically I'm interested in the idea that some statements might be easily computed from $f(x)$, but not everything. e.g. maybe we cannot at all derive what the exact value of $x$ is, but we might be able to derive the length of $x$, or the amount of $0$'s and $1$'s. I'm not sure if that's true for this example, but I'm interested in these general issues. $\endgroup$ – user56834 Dec 8 '17 at 10:22
  • $\begingroup$ Note that if $f$ is a permutation, $f(x)$ does reveal the length of $x$. One way functions can reveal the number of zeros. You could look at any book which talks about these cryptographic primitives, e.g. foundations of cryptography by Goldreich, or Introduction to modern cryptography by Katz & Lindell. $\endgroup$ – Ariel Dec 8 '17 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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