2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Florian May 29 at 19:41

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.