# Expected entropy in $P(x)\oplus x$ for random $x$, where $P$ is a random permutation

Let $P$ be a random permutation of $n>1$ bits. Let $F$ be the function on the same domain $\{0,1\}^n$, defined by $F(x)=P(x)\oplus x$. When $P$ is a block cipher with key a message block, that's the Davies-Meyer construction of a one-way compression function, a variant of which being used in MD5, SHA-1, and SHA-2.

Let $H_F$ be the entropy (in bits) of the source $F(x)$ where $x$ is a vector of $n$ random unbiased independent bits. That is \begin{align*} H_F&=\sum_{y\in F(\{0,1\}^n)}-\Pr(F(x)=y)\cdot\log_2\big(\Pr(F(x)=y)\big)\\ \\ & = n-{1\over2^n}\cdot\sum_{y\in F(\{0,1\}^n)}\big(\#{\{x, F(x)=y)\}}\big)\cdot\log_2\big(\#{\{x, F(x)=y)\}}\big) \\ & = n-{1\over2^n}\cdot\sum_{2\le\,j\,\le2^n}\big(\#{\{y,(\#\{x:F(x)=y\})=j\}}\big)\cdot j\cdot\log_2(j) \end{align*} Note: $\#{\{x, F(x)=y)\}}$ of the 2nd equation is the number of preimages of vector $y$; and $\#{\{y,(\#\{x:F(x)=y\})=j\}}$ of the 3rd is the number of vectors with exactly $j$ preimages.

$H_F$ can be from $0$ (when $P$ happens to be XOR with some constant) to $n$ bits (when $F$ happens to be a permutation, e.g. for $P:$ $00\to00$, $01\to10$, $10\to11$, $11\to01$ ).

Let $H(n)$ be the expected value of $H_F$; that is, the average of $H_F$ over all $(2^n)!$ permutations $P$. A plausible conjecture is that $$\lim_{n\to\infty}{H(n)\over n}=1$$ How to prove this, and what's a first order approximation of $n-H(n)$ for large $n$?

If $F$ was a random function, we'd have $n-H(n)\approx0.8272\dots$ starting with moderate $n$ according to my analysis there. But I fail to rigorously derive that for the much narrower class of $F$ in the question.

• Trying to understand your formulation. Is your definition of entropy related to the image size of the map $P(x)+x$? So entropy of the "source" $F(x)$ is the entropy of the output of $F$ with input $x$ uniform. – kodlu Jan 31 '17 at 23:00
• In case the term is useful: A permutation P such that P(x) ^ x also defines a permutation is called an orthomorphism. – bmm6o Feb 1 '17 at 17:14
• Do you have any numerical results for $n - H(n)$ for large $n$? I'd like to be able to check my theoretical result before posting it as an answer. – Aleph Feb 3 '17 at 18:14
• @Aleph: No. But I'd be mildly surprised if the limit was not the same as for a random function, 0.827245389153.. – fgrieu Feb 3 '17 at 18:18
• @fgrieu Ok, then I'll post the answer showing that it is the same. Although I think you've actually shown it yourself. – Aleph Feb 3 '17 at 18:20

As far as I understand it, your question boils down to: "What is the probability distribution of the number of fixed points of a random permutation?"

As you note in the question,

$$H_F = n-{1\over2^n}\cdot\sum_{2\le\,j\,\le2^n}\big(\#{\{y,(\#\{x:F(x)=y\})=j\}}\big)\cdot j\cdot\log_2(j).$$

I'll rewrite this using probabilities for brevity:

$$n - H_F = \sum_{2\le\,j\,\le2^n}\Pr\big(|F^{-1}(y)|=j\big)\cdot j\cdot\log_2(j).$$

where $|F^{-1}(y)|$ is the size of the preimage of $y$. Importantly, this entire sum is a random variable and below we take the expectation over the random function $F$.

Taking expectations, we get

$$\mathbf{E}\left[n - H_F\right] = \sum_{2\le\,j\,\le2^n}\mathbf E\left[\Pr\big(|F^{-1}(y)|=j]\big)\right]\cdot j\cdot\log_2(j).$$

Note that $\mathbf{E}\left[\Pr\left(|F^{-1}(y)| = j\right)\right]$ is independent of $y$, so we might as well compute $\mathbf{E}\left[\Pr\left(|F^{-1}(0)| = j\right)\right]$. Since $F(x) = P(x) \oplus x = 0$ iff $P(x) = x$, we are really looking for the probability distribution of the number of fixed points of a random permutation.

It is well known that as $n \to \infty$, this distribution is Poisson with expectation 1, that is:

$$\mathbf{E}\left[\Pr\left(|F^{-1}(0)| = j\right)\right] \approx \frac{1}{ej!}.$$

An exact value (for finite $n$) could be obtained in terms of the Rencontres numbers.

Hence,

$$\lim_{n \to \infty} \mathbf{E}\left[n - H_F\right] = \sum_{j = 2}^{\infty} \frac{j\log_2(j)}{ej!}.$$

Note that I've implicitly made use of the bounded convergence theorem, that is, since $\Pr\left(|F^{-1}(y)| = j\right)$ is bounded above for every $n$, and since

$$\lim_{n \to \infty} \Pr\left(|F^{-1}(0)| = j\right) = \frac{1}{ej!},$$

we also have

$$\lim_{n \to \infty} \mathbf{E}\left[\Pr\left(|F^{-1}(y)| = j\right)\right] = \mathbf{E}\left[\lim_{n \to \infty} \Pr\left(|F^{-1}(y)| = j\right)\right].$$

• I hope I didn't miss anything. To me it seems like you actually did most of the work. – Aleph Feb 3 '17 at 19:11
• The step "Taking expectations.." initially made me uncomfortable since the $\Pr\big(|F^{-1}(y)|=j\big)$ are dependent; but that is definitely OK. I like how you get rid of $y$ and get to the probability distribution of the number of fixed points of a random permutation. And I'm happy to know the precise theorem used when getting to the limit. Yes I had some intuition of the formula, but you proved it. Also, with the Rencontre numbers, you give a way to compute things for small $n$. – fgrieu Feb 3 '17 at 23:42

All functions (including permutations) mapping a finite field $\mathbb{F}_q$ to itself can be uniquely represented by polynomials (via Lagrange Interpolation, possibly followed by reduction modulo $x^{q}-x.$ When $q=2^n,$ the linear permutations $F(x)=x+a,$ for $a\neq 0,$are exactly the type of polynomial that give zero entropy in your formulation since $F(x)+x=a$ a constant.

Focusing only on $q=2^n$ due to crypto applications, we don't know explicit representation of many other permutations but some include certain monomials $F(x)=x^{e}$ with special conditions on exponent $e,$ as well as families such as Dickson's polynomials, which don't have an $x$ term in their polynomial and won't suffer the weakness of zero entropy for $F(x)+x$. As for computing what fraction of overall permutation polynomials have an $x$ in their polynomial expression, it's likely to be a difficult problem.

Edit: The below is redundant, due to your comment, the above is still relevant but I can take it to a comment if requested, it's a bit long.

If we model the map $F(x)=P(x)+x$ by a random mapping instead of a random permutation from $A=\{0,1\}^n$ to itself, then the number of points $y$ in $A$ that have no preimages, i.e., there is no $x\in A$ with $f(x)=y,$ is on average equal to $e^{-1}\#A=\frac{2^n}{e}.$

This would mean that the expected size of the range of $F$ is $$\mathbb{E}[F(A)]=(1-e^{-1}) 2^n\approx 0.6321 \cdot 2^n$$ yielding $$H(n)\approx n+\log_2(0.6321)= n-0.66172,$$ so as you predicted the $\lim_{n\rightarrow \infty}H(n)/n=1.$

References for this type of argument include Sedgewick and Flajolet's book An Introduction to the Analysis of Algorithms, and the paper "Random Mapping Statistics" by Flajolet and Odlyzko in Eurocrypt'89, but a very readable account is in Chapter 5 of Riordan's classic book An Introduction to Combinatorial Analysis, from 1958.

• There is a gap at the line reading "yielding": the entropy $E_F$ does not only depend on the number $m$ of points in $\{0,1\}^n$ that have no preimage by $F$ (at least, for an arbitrary function $F$); for a given $m$, the entropy will be higher if the other $2^n-m$ points have $\lfloor{2^n\over 2^n-m}\rfloor$ or $\lceil{2^n\over 2^n-m}\rceil$ preimages, than if $2^n-m-1$ points have a single preimage and a single other point has $m+1$ preimages. I believe that makes the $0.66172$ significantly off. – fgrieu Feb 1 '17 at 10:38
• I see, so you actually want the expected entropy of $2^{-n}(N_0,\ldots,N_{2^n-1})$ where $N_y=\#\{x:F(x)=y\}$ using integer notation for $y$ for simplicity. – kodlu Feb 1 '17 at 10:47
• I think that the second formula for $H_F$ in the question as now modified matches what you mean in the above comment. – fgrieu Feb 1 '17 at 12:13
• In the first paragraph, $a = 0$ also does give one of the 0-entropy results ($x + 0 + x = 0$ in a field with characteristic 2). In general, from the number of elements which are not in the image of $F$, you can not calculate the entropy of the image of $F$: The actual distribution of the elements in the image matter just as much as those which are not in the image. – tylo Feb 1 '17 at 12:15
• @fgrieu thanks, very useful. I'll modify my answer when I get some time soon – kodlu Feb 2 '17 at 0:01

The probability for $0$ not being in the image of $x\mapsto P(x)\oplus x$ is for big $n$ about $\frac{1}{e}$, as it is equivalent to $P$ being fixed-point-free.

By symmetry (replace $P$ by $P_k(x) := P(x)\oplus k$ for fixed $k$) the probability of any value $k$ to be not in the image of $P$ for big $n$ is hence also about $\frac{1}{e}$.

Phrased differently, the random variable $X_k$ defined as $X_k=1$ if $k$ is in the image of $x\mapsto P(x)\oplus x$ and $X_k=0$ otherwise has expectation about $1-\frac{1}{e}$.

Summing over the $X_k$ for all $k$ one gets that the expected size of the image is about $\frac{e-1}{e}\cdot 2^n$.

For a given size $s = \sum X_k$ of the image, the entropy is maximal if every value in the image is equally likely, and then the entropy $H_{\rm max} = \log_2 s$. Hence by Jensen's Inequality $$\mathbb{E}(H_{\rm max}) = \mathbb{E}(\log_2(s)) \le \log_2(\mathbb{E}(s)) \approx \log_2(\frac{e-1}{e}\cdot 2^n) = n-\log_2(\frac{e}{e-1})$$ giving an upper bound for the entropy.

[The entropy is minimal for given $s$, if all but one of the images has a unique preimage and all other values are mapped to the one. It is not difficult to derive the formula for $H_{\rm min}$, but as the second derivative of $H_{\rm min}$ is negative, applying Jensen's inequality doesn't yield anything useful. Anyway, I would expect the true entropy be closer to $H_{\rm max}$ than $H_{\rm min}$.]

Remark: I'd expect that for permutations the entropy is lower than for general functions, because of the following heuristics: If one restricts oneself to (the relatively tiny subset of) all linear functions rsp. bijections, then $x\mapsto P(x)\oplus x$ is bijective if and only if the linear map $P$ does not have the eigenvalue $1$. The restriction to permutations forbids the eigenvalue $0$, which increases the chance of having $1$ as eigenvalue.

Towards a lower bound of $\frac{n+1}{2}$ for the average entropy: If the image has size $s$ the entropy is minimal in the case described above in the brackets, where one finds $$H_\min(s) = \frac{(s-1)\cdot n}{2^n} - (1-\frac{s-1}{2^n})\cdot\log_2(1-\frac{s-1}{2^n}).$$ As $H_\min$ increases with $s$ one gets the lower bound $$\mathbb{E}(H) \ge \mathbb{E}(H_\min) \ge \mathrm{Prob}(s>2^{n-1})\cdot H_\min(2^{n-1}+1) = \mathrm{Prob}(s>2^{n-1})\cdot\frac{n+1}{2}.$$

Proving $\mathrm{Prob}(s>2^{n-1})\to 1$ for $n\to\infty$ I leave to you, as this idea is anyway based on your comment.

• If the size of the image is $s\approx{e-1\over e}\cdot 2^n$, and (maximizing the entropy) every value in the image is as about equally likely as possible given that $s$ , then $2s-2^n$ values have exactly 1 preimage, and $2^n-s$ values have exactly 2 preimages. That yields (by the third equality in the question) $H_F=n-{1\over2^n}\cdot(2^n-s)\cdot2$. Thus $H_F\le n-0.736$ for large $n$ and a restriction to those $F$ with (close to) the expected size of the image. However I fail to see how we move from there to the full class of $F$ in the question, and/or to average entropy. – fgrieu Feb 3 '17 at 13:01
• Your sharper estimate with $0.736$ works only for sizes $s>2^{n-1}$. Taking $\log_2$ gives always an upper bound for the entropy given the image size $s$. Now apply Jensen's inequality. – NoPermanentCookiesHere Feb 3 '17 at 13:09
• I think Jensen tells us the opposite: the average entropy is lower than the entropy in the average case, so the latter gives only an upper bound, not the desired lower bound. – NoPermanentCookiesHere Feb 3 '17 at 13:40
• Per your suggestion, I have written a reformulated question at cross-validated; I had some precious few good experiences there. – fgrieu Feb 3 '17 at 16:24