2
$\begingroup$

Assume we have a set of random bit strings: $S=\{s_1,...,s_n\}$, where each of them is of length $\lambda$ ($s_i\leftarrow\{0,1\}^{\lambda}$).

We give the set $S$ to an adversary who picks one of the set elements at will and outputs it. Let's $s'\in S$ be the adversary's choice.

Question: What is the entropy of $s'$?

|improve this question
$\endgroup$
  • $\begingroup$ What values can a string contain? Only alphabetical letters or also numbers (alphanumerical) or even more? $\endgroup$ – AleksanderRas Feb 11 at 12:53
  • $\begingroup$ @AleksanderRas It can be bitstring of length $\lambda$. I've also slightly modified the question. $\endgroup$ – Ay. Feb 11 at 12:57
  • $\begingroup$ I think the entropy of a bit string of length $\lambda$ is $log_2(2^\lambda) = \lambda$. Now you need to figure out how the amount of possible $s'$ ($s_n$) has a further impact... $\endgroup$ – AleksanderRas Feb 11 at 13:31
  • 1
    $\begingroup$ If the adversary knows which one he picked, the entropy (that is, the measure of uncertainty that the adversary has) is 0 $\endgroup$ – poncho Feb 11 at 14:56
4
$\begingroup$

You did not define what the probability that $s_i = s^\prime$ for each $i$. Therefore entropy is undefined.

The definition of (Shannon) entropy is:

$$H = - \sum_{i} p_i \log_2 p_i$$

When you determine every non-zero probability $p_i$ then come back and enter those numbers into the formula.

Knowledge of $|S|$, the elements of $S$, or $\lambda$ is insufficient for calculation purposes. In different contexts (even if $S$ and $\lambda$ are the same), the probability of each message can follow a different distribution. The entropy depends only on what that distribution is. Therefore, the entropy of $s^\prime$ can be different depending on context.

Examples of the different contexts:

  • We care about the adversary's ability to guess $s^\prime$. This is trivial. The adversary picked the number. The adversary is certain what that number is. Certainty means one outcome has a probability of exactly one. The only non-zero $p$ is one. Entropy is zero because the log of one is zero.
  • A first party ("us") sends the set $S$ to a second party. The second party picks an element of that set. The first party wants to guess it before the adversary reveals it. The entropy can be at least zero bits and at most $\log_2 {|S|}$ bits. Exactly what value that entropy is depends on what the probability distribution is that describes which element the adversary picks.
  • The above scenario, except the first party tries to guess the number after the the second party reveals it to them. The entropy is zero. The first party is certain what that value is. $p = 1$
  • The first party chooses a set. A second party chooses an element of that set. A third party is supposed to guess what element was chosen with no knowledge of what choices the first or second party made. The entropy, $H$ satisfies, $0 \leq H \leq \log_2{|S|} \leq \log_2 (2^\lambda)$ The exact value depends both on the distribution of possible $S$ values the first party may choose and the distribution describing which element the second party may choose from any given set. See "joint entropy".
|improve this answer
$\endgroup$
  • 2
    $\begingroup$ I think you may be misunderstanding the question. I think the point is that the $s_i$ are sampled uniformly, and then an arbitrarily malicious algorithm $A$ can choose one of those. The question is then whether there is a lower bound on the entropy of this partially malicious sampling process, quantified over all $A$. I.e., that the $p_i$ are underspecified is very much by design. (I'm not sure how such a lower bound could be derived at the moment, but it's an interesting and non-trivial question about sampling under malicious conditions.) $\endgroup$ – Maeher Feb 12 at 18:09
  • $\begingroup$ @Maeher Yes it's not the best of questions, but surely if any form of choice is made, entropy must be generated? And given that a choice is simply made, how can it be so adversarial to have zero entropy? The die analogy stands; what would be adversarial die tossing? Surely H cannot be 0 unless no choice is made and one string repeated ad infinitum. $\endgroup$ – Paul Uszak Feb 12 at 23:33
  • $\begingroup$ Even if this was the right end of the stick, the problem with the Shannon formula in a general complex case is that you cannot easily determine every non-zero probability $p_i$ and sum them. It doesn't work anything at all like that. $\endgroup$ – Paul Uszak Feb 12 at 23:39
  • 2
    $\begingroup$ Determining a probability mass function is not an optional step. (It almost goes without saying that there is an exception for Hartley entropy, but Hartley entropy isn't useful precisely because it ignores probability.) As of the time I'm writing this the question text doesn't go into the necessary specifics. This is the only appropriate answer at this time. I'm not going to attempt mind-reading to answer a question the OP might have meant to ask. Besides, it's a universal answer to any "What is the entropy of" question. Entropy is well defined, not fuzzy. Just like mean, median, variance, etc $\endgroup$ – Future Security Feb 13 at 4:25
  • 2
    $\begingroup$ I ought to clarify things in my answer. (I hope to do so later.) s' in the context of my answer is a random variable, not a plain old variable representing the value of a sample. Strings, numbers, bits, passwords do not have entropy. (As in entropy is not the property of a value. That means something different than saying it has zero bits entropy.) If you want to know how much entropy a process has, then you model the collection of possible outcomes as a random variable. Entropy, once you pick which kind you're referring and what PMF to use to describe the variable, is unambiguous. $\endgroup$ – Future Security Feb 13 at 4:46
-3
$\begingroup$

I suggest that it's unknown entropy is simply $ log_2 (|S|) $. All of the strings are known, and thus the content of the set is known. The only decision made and reflected back to the original owners of $S$ is which string is chosen. And that's a direct function of the domain size.

This seems analogous to handing your mate a die and asking him to toss it for you.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ While the question is lacking in detail, what is probably meant is the entropy of the sampling process that is defined as uniformly choosing $n$ bitstrings of length $\lambda$ and then having a possibly malicious party choose one of them. $\endgroup$ – Maeher Feb 11 at 21:57
  • $\begingroup$ @Maeher Err, sorry I can't quite see what you're getting at. Did I not describe the entropy of the sampling process? $\endgroup$ – Paul Uszak Feb 11 at 22:08
  • 2
    $\begingroup$ no, you considered the entropy of A sampling s' from a fixed set S. But for any fixed S the only lower bound on the entropy of the sampling of s' is 0. This is because A is malicious and can act deterministically. $\endgroup$ – Maeher Feb 11 at 22:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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