0
$\begingroup$

I was wondering about what is permutation entropy(PE). Then, I came to know this paper which describes PE. Now, let's assume that we have a pseudorandom permutation that is generated using an entropy source and we used a uniform shuffle algorithm(like Fisher-Yates shuffling algorithm). Also, assume that we use a 256-bit entropy to shuffle $\{0,1\}^8\rightarrow\{0,1\}^8$. Then is the fact true that the output permutation can have at max 256-bits of entropy? For every value of entropy, we shall get a unique corresponding permutation.

$\endgroup$
2
$\begingroup$

Assume that we use a 256-bit entropy to shuffle $\{0,1\}^8\rightarrow\{0,1\}^8$. Then is the fact true that the permutation can have at max 256-bits of entropy?

There's a semantic problem: in cryptography, unless otherwise stated, we consider Shannon entropy, and that's defined for a symbol-generating process, not for a symbol. A permutation can be a symbol, not a process. Hence "permutation … have … bits of entropy" is not something defined. That's true including if we consider Permutation Entropy (a different breed of entropy, discussed in the second section of the present answer).

What we can define is the entropy at the output of a deterministic process/algorithm generating permutations. And then yes, if there is 256-bit entropy (per symbol) at the input of this process (for example, if the input consists of 256-bit bitstrings chosen uniformly at random, uniquely defining one output permutation in a deterministic manner), then there can be at most 256 bits of entropy (per symbol produced, that is permutation) at the output. Argument: applying any deterministic function $f$ to a source of symbols $s$ can not increase it's Shannon entropy, defined as $$\sum_{s\text{ with }\Pr[s]>0}\Pr[s]\,\log_2\left(\frac1{\Pr[s]}\right)$$ because $f$ can only change that sum when $f(s)=f(s')$ with $s\ne s'$, $\Pr[s]>0$ and $\Pr[s']>0$, and then that change is the negative $$\Pr[s]\,\log_2\left(\frac{\Pr[s]}{\Pr[s]+\Pr[s']}\right)\,+\,\Pr[s']\,\log_2\left(\frac{\Pr[s']}{\Pr[s]+\Pr[s']}\right)$$

What's more, that threshold of 256-bit output entropy is exactly achievable: there are $(2^8)!=2^{1683.996\ldots}$ shuffles of $\{0,1\}^8$, and that's (way) more than $2^{256}$. Depending on how we use Fisher-Yates shuffling and the form of the entropy at the input, that threshold will be reached, or not.

One way to reach this 256-bit output entropy threshold, if the 256-bit input entropy is in the form of a 256-bit uniformly random bitstring, goes: the first 64 times the Fisher-Yates algorithm requires a random integer $j$ in range $[0,i]$ with $i\ge15$, we pick an integer $j$ in $[0,15]$ based on 4 bits of the input (that we assemble into an integer per big-endian convention, then discard). And any other time the algorithm requires a random integer, we pick the integer $j=0$. That method will generate one of $2^{256}$ distinct permutations with probability $2^{-256}$ for each, and probability $0$ for the $(2^8)!-2^{256}$ other possible permutations. That's exactly 256-bit Shannon entropy per permutation output by this process.

As noted by Maeher, the above must not be used to generate a pseudo-random permutation from a 256-bit uniformly random bitstring in a cryptographic context! If that's needed, one option is to seed a Cryptographically Secure Pseudo Random Number Generator (CSPRNG) and use it to generate the $j$ in $[0,i]$ during Fisher-Yates. The output entropy will still be near 256-bit per permutation, but it will be computationally impossible to distinguish the output permutations from permutations generated at random (that is, with $1683.996\ldots$ bits of entropy per permutation).


Answering the title of the question

What Permutation Entropy really is?

Permutation Entropy, and the "paper" linked in the question (which I won't discuss or seriously consider), have no relation with the entropy of a permutation generator. Permutation Entropy is an alternate entropy defined by Christoph Band and Bernd Pompe's Permutation entropy: a natural complexity measure for time series in Physical Review Letters, 2002 (paywalled).

Given a source of values, it's Permutation Entropy of order $2$ is the Shannon entropy of a modification of the source, where we replace a symbol by $0$ if it's lower than the next, by $1$ otherwise.

This generalizes to Permutation Entropy of order $n>2$: we replace each symbol by an integer $k$ in $[0,n!)$ characteristic of the order of $n$ symbols starting from there.

A property of Permutation Entropy is that it's invariant when the source goes thru any strictly monotonous transformation. Perhaps that's interesting in physics, but I do not see that this property, or Permutation Entropy in general, is much useful in cryptography.

$\endgroup$
  • 1
    $\begingroup$ It may be noteworthy that, while your suggestion for preserving the entropy through FY works as far as I can see (it generates distinct permutations for each possible input value) it would be a terrible way of shuffling, that's trivially distinguishable from a random permutation. (It's also not really FY, or it's modern equivalent, anymore, since that mandates uniformly choosing the indices.) $\endgroup$ – Maeher Nov 10 '20 at 11:45
  • $\begingroup$ Can you elaborate on why FY can be a terrible idea to shuffle? $\endgroup$ – Radium Nov 10 '20 at 15:25
  • $\begingroup$ FY is fine if you use uniform randomness or a pseudorandom generator. However a PRG would not guarantee preservation of entropy, so @fgrieu defined a way of mapping 256bits to the randomness required by FY in a way that does preserve entropy but results in garbage shuffling. (Basically everything beyond the first 64 entries will simply be shifted by one position.) $\endgroup$ – Maeher Nov 10 '20 at 15:44
  • $\begingroup$ If a PRG obeys it's definition then it shall produce a bit string which should be indistinguishable from a random bit string stream(|Y|>256bit). A 256bit seed(X, uniformly random) should be enough for present standards. Though a PRG will always leave some $\delta$ advantage to the attacker. Is it the case that if someone use the said PRG in FY then the advantage to the attacker is more than $\delta$? $\endgroup$ – Radium Nov 10 '20 at 16:26
  • 1
    $\begingroup$ @Radium: I have added a way to generate a permutation from a random 256-bit bitstring that is computationally indistinguishable from having maximal entropy (1683.996… bit per permutation). I think it is important to not confuse Permutation Entropy (a variant of entropy), entropy of a permutation (undefined), entropy of a permutation-generating process as in the question (256-bit or less, including with a CSPRNG+FY), entropy of a true-random permutation-generating process (near 1684 bit) that's indistinguishable from CSPRNG+FY. $\endgroup$ – fgrieu Nov 10 '20 at 16:43

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.