# Symmetric property of DDT of inverse function

Given a bijective function $$F: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$$.

The entry of the Difference Distribution Table (DDT) at row $$\alpha$$ and column $$\beta$$ is defined as

$$DDT_{F}(\alpha,\beta) = \delta_F(\alpha, \beta) = |\{ x \in \mathbb{F}_2^n | F(x) + F(x+\alpha) = \beta \}|$$

I need to show that

$$DDT_{F}(\alpha,\beta) = DDT_{F^{-1}}(\beta, \alpha)$$

with

$$DDT_{F^{-1}}(\beta, \alpha) = \delta_{F^{-1}}(\beta, \alpha) = |\{ x \in \mathbb{F}_2^n | F^{-1}(x) + F^{-1}(x+\beta) = \alpha \}|$$

Unfortunately, I do not know how to start to show the equality, but I assume substitution is the way to go. Can you please give me a hint?

I tried the same approach I used to show that this symmetric property does also hold for the Linear Approximation Table (LAT), i.e.

$$LAT_{F}(\alpha,\beta) = LAT_{F^{-1}}(\beta, \alpha)$$

with

$$LAT_F(\alpha,\beta) = \widehat{F}(\alpha,\beta) = \sum_{x \in \mathbb{F}_2^n} (-1)^{<\alpha,x> + <\beta,F(x)>}$$

$$LAT_{F^{-1}}(\beta,\alpha) = \widehat{F^{-1}}(\beta,\alpha) = \sum_{x \in \mathbb{F}_2^n} (-1)^{<\beta,x> + <\alpha,F^{-1}(x)>}$$

For the LAT, the trick was to substitute. Since $$F$$ is a permutation and the sum goes over all elements in $$\mathbb{F}_2^n$$, substitution only changes the order in which the elements in $$\mathbb{F}_2^n$$ are processed.

$$x = F(y)$$

This leads to:

$$\widehat{F^{-1}}(\beta,\alpha) = \sum_{x \in \mathbb{F}_2^n} (-1)^{<\beta,x> + <\alpha,F^{-1}(x)>} = \sum_{y \in \mathbb{F}_2^n} (-1)^{<\beta,F(y)> + <\alpha,y>} = \widehat{F}(\alpha,\beta)$$

Unfortunately, substituting $$x = F(y)$$ did not solve my issue with the DDT.

## 1 Answer

The proof for DDT is shown as following:

given: $$y=F(x) ;\\ x=F^{-1}(y) \> \> (1)$$ The forward DDT is $$F(x) + F(x+\alpha) = \beta \>\> (2)$$ substituting (1) into (2) $$F(x) + F(F^{-1}(y)+\alpha) = \beta$$

$$y+ \beta +F(F^{-1}(y)+\alpha) =0$$

re-arranging and applying inverse function $$F^{-1}(y+ \beta) +F^{-1}((F(F^{-1}(y)+\alpha))=0$$

$$F^{-1}(y+ \beta) +F^{-1}(y) = \alpha$$

Therefore ,

$$DDT_{F^{-1}}(\beta, \alpha) = \delta_{F^{-1}}(\beta, \alpha) = |\{ x \in \mathbb{F}_2^n | F^{-1}(x) + F^{-1}(x+\beta) = \alpha \}|$$

The same concept applied to LAT proof.

• Applying $F^{-1}()$ after the substitution was the part I didn't get. Now the solution seems to be pretty obvious. Thank you for helping me out. – Florian May 29 '19 at 19:41