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

Question

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 2^nd equation is the number of preimages of vector $y$; and $\#{\{y,(\#\{x:F(x)=y\})=j\}}$ of the 3^rd 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.

Answer 1

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].$$

Answer 2

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.

Answer 3

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.