-1
$\begingroup$

Entropy defined in cipher system as a measure of information or uncertainty. Is it possible to be zero or infinite? What would it mean based on Entropy formula: $$H(X)=-\sum_{x \in X} P(x) \log_2{P(x)}$$

I think 0 would be the absolute certainty like a coin with both side heads but I cant "understand it mathematically". For infinite I have no clue

UPDATE I found this on infinite entropy and yes it is possile but still I cannot explain it so good:

Infinite Shannon entropy

Even if a probability distribution is properly normalizable, its associated Shannon (or von Neumann) entropy can easily be infinite. ---more here: source : https://arxiv.org/abs/1212.5630

$\endgroup$
  • $\begingroup$ This could be relevant with infinite entropy arxiv.org/abs/1212.5630 $\endgroup$ – partizanos Oct 9 '17 at 23:48
  • 1
    $\begingroup$ Infinite is an imaginary number, and symbolizes a really large number we can't compute. So, yes in theory there can be an infinite amount of entropy. The log of infinity is also infinity. $\endgroup$ – ATLUS Oct 9 '17 at 23:53
  • $\begingroup$ can you give me an example of such a system $\endgroup$ – partizanos Oct 9 '17 at 23:56
  • 2
    $\begingroup$ This makes no sense. $\endgroup$ – fkraiem Oct 10 '17 at 0:47
  • 2
    $\begingroup$ Please define "Entropy of a cipher system". It is so much easier to discuss about the possible values of a quantity when it has a definition! $\endgroup$ – fgrieu Oct 10 '17 at 7:52
3
$\begingroup$

A cryptosystem has a few requirements:

  • It is defined with a messagespace and a ciphertext space. Both of them are usually some finite algebraic structure. Also, the key is chosen from some algebraic structure, and for symmetric ciphers that's usually finite. For asymmetric ciphers, usually a certain length (e.g. for RSA) is set, which also restricts the possible keyspace.
  • Encryption (and decryption) is a bijective function, because otherwise it's impossible to have a unique decryption. The only exception I know is the Rabin cryptosystem, which leaves figuring out the correct message to the user.

    Entropy defined in cipher system as a measure of information or uncertainty. Is it possible to be zero or infinite? What would it mean based on Entropy formula: $$H(X)=-\sum_{x \in X} P(x) \log_2{P(x)}$$

In the definition of entropy, you can see the set $X$ and a probability distribution $P(X)$. It does not make any sense to talk about entropy when they are not properly defined.

With respect to a cryptosystem, we could measure or define entropy over the message space, with some set of messages and a distribution. And since encryption is bijective, the entropy of the ciphertext space would be equal.

Achieving entropy $0$ for the message space and ciphetext space is simple: There is just one message, and it has probability $1$. It doesn't actually matter how many bits are used to represent this message.

Infinite entropy does not exist in a system with a finite number of elements. It doesn't really make any sense - unless you are also willing to deal with infinite length keys. As a general rule: The length of the text is not kept confidential, and the adversary gets this information. With that, even arbitrary length strings can't have infinite entropy - assuming the adversary actually gets any information.

$\endgroup$
  • $\begingroup$ All good stuff, but have you actually read the paper? It's about quantum mechanics and therefore, yes, a finite number of elements can have an infinite number of states -> infinite entropy. You've grossly simplified the paper's topic to a cat in a box which was a deliberately illustrative simplification in the first place so that children could understand it. $\endgroup$ – Paul Uszak Oct 10 '17 at 13:16
  • $\begingroup$ Did you have an opportunity to read my initial comment before it was mysteriously disappeared? It explained the problem you're having. $\endgroup$ – Paul Uszak Oct 10 '17 at 13:17
  • $\begingroup$ @PaulUszak I don't think I read your comment. Regarding the paper and infinite entropy: The paper has no ties to cryptography at all. Even in the context of quantum cryptography I can't see any practical application. We don't have any hardness assumptions for continuous spaces and typical assumptions like DLOG, facotring, NP problems, codes with errors, etc. are all based on discrete structures and usually are finite. And so far I have not seen any proper cryptosystem on infinite discrete structures where you wouldn't also have to consider infinite length keys, e.g. all integers without bound $\endgroup$ – tylo Oct 10 '17 at 14:38
  • $\begingroup$ Yes it's only loosely related to cryptography via the entropy concept. That's why you should refer to my comment above... $\endgroup$ – Paul Uszak Oct 10 '17 at 20:41
1
$\begingroup$

I think that this sentence in the introduction sums it up (get it?):-

These simple observations demonstrate that to obtain infinite Shannon entropy, an infinite number of states must have non-zero probability

The infinite number of states comes from the super position principle whereby a quantum particle can simultaneously be in many and all possible states. So in Shannon's equation, there is an infinite number of x's, each of a very small but not zero probability. Hence the summation of an infinite number of small values should tend towards infinity as they suggest. I can kinda see that up to this statement, but fall flat on my face later in their paper...


Actually this is not a zillion miles away from a question I posed everywhere regarding the entropy of a continuous distribution wrt the sampling resolution. Clearly as the sampling depth increases, entropy increases (to infinity?). The resolution of the samples is analogous to the number of possible quantum states I guess. It's not been answered for 18 months.

$\endgroup$

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.