Can multiple Pearson permutation tables be reduced or merged? There was a recent question answered where the accepted solution was a double Pearson hash. It consisted of the following pseudo code:- h = T1[h ^ x[i]] followed immediately by h = T2[h ^ x[i]] so effectively you run one lookup table into the other. Tables T1 and T2 are unique random 8 bit permutations. Output collisions can   occur at the classic $ 1 \over e $ rate given the presence of the 2nd table, with the hash behaving as a pseudo random function.

Developing this construction further, assume that the permutation tables are $ \pi $, giving a more general form for hashing a message $m$ with multiple consecutive but unique permutations:-

$$   h_{i} =  \pi_j [h_{i-1} \oplus m[i]]; recursive   $$ 

creating a functional composite as in:-

$$      h = \pi_3[(\pi_2[(\pi_1 [h \oplus m[i]]) \oplus m[i])]) \oplus m[i]]     $$ 

if $j=3$ . And let's call each calculation of $h$ for any given $\pi$ a 'step'.  Overall, we get $ output = H_N(m) $ for this cool/weird hash consisting of $N$ tables/steps. As an example, it might be that $ H_3(3512)=110 $  for a hash with 3 permutation tables. In the linked question we used 2 tables.


Can a new $\pi$ or set of $\pi$s be constructed to arrive at an identical output for all messages with $&lt;N$ steps? In other words can multiple $\pi$ permutations be reduced or merged somehow into new ones, even theoretically?  Clearly they can in the special and trivial case of $|m| = 1$. What about generally for $|m| &gt; 1$?
Considering the trivial case mentioned above, is there some relationship between $N$ and $|m|$ that determines the answer?
If  a reduced set of new $\pi$s might theoretically exist, how might   it found in practice?




Notes:


Some of this question is clearly on topic here, but not sure about it's entirely.
I see small parallels with permutations and non linearity, construction of S boxes, and their combinations.
Whilst hallucinating one might assume values of $\pi_j$  be likened to multiple keys $k_j$, so the answer to Security of a block cipher if double encryption $E_{K_2} \circ E_{K_1}$ is always single encryption $E_{f(K_1,K_2)}$ comes to mind as there is an attempt at a similar(?) reduction.
I'm happy to be migrated outa here.
Claim: A $\pi$ permutation table can be found such that applying it to a message $m$ will yield the same output as applying multiple, different permutations to that message $m$.

i.e. For any number of permutation steps $\phi_n$, $m_{initial}\rightarrow\phi_1\rightarrow\phi_2\rightarrow...\rightarrow\phi_n\rightarrow m_{permuted}$

$\exists$ a single permutation $\pi$ such that: $m_{initial}\rightarrow\pi\rightarrow m_{permuted}$ 

Where both $m_{permuted}$'s are identical.

Proof:

Assume we have two permutation tables, $\phi_1$ and $\phi_2$ s.t. 

$\phi_1=
\begin{bmatrix}
    m_{1} &amp; m_{2} &amp; m_{3} &amp; m_{4} \\
    a &amp; b &amp; c &amp; d
\end{bmatrix} $
$\phi_2=
\begin{bmatrix}
    m_{1\phi_1} &amp; m_{2\phi_1} &amp; m_{3\phi_1} &amp; m_{4\phi_1} \\
    e &amp; f &amp; g &amp; h 
\end{bmatrix} $

Where the first row contains the input broken into bits and the second row contains the positions that each bit will be mapped to. (For $\phi_2$ notice that each bit of $m$ is now $m_{0\phi_1}$, indicating that it is the first bit of the message after being permuted by $\phi_1$). For example:

$
m=3512
$

\begin{bmatrix}
    3 &amp; 5 &amp; 1 &amp; 2 \\
    4 &amp; 2 &amp; 3 &amp; 1 
\end{bmatrix}

yields a $m_{permuted}=2513$, and then this new permuted message can be permuted again (as many times as desired).

Right, so back to our earlier example using $m$, $\phi$, and $a,b,c,...$.

Going through the first permutation, we will have the message $m_{\phi_1}=m_{a}m_{b}m_{c}m_{d}$

Going through the second permutation, we will have the message 
$m_{\phi_2}=m_em_fm_gm_h$

So, it is sufficient to find a permutation matrix that directly maps $m_1,m_2$ etc. to the locations that $m_1,m_2,...$ end up in the final permutation matrix. Finding such a permutation matrix is quite simple, as you can pass a message $m$ through the multiple permutations $\phi_n$, observe where they end up, and create the mapping based on that. This is best illustrated by and example, but proof by example is not acceptable, so I added the other info in before this. Also note that this works for any size of $m$ assuming the permutation has mappings that include all bits in $m$ (So each bit gets assigned a new place). 

Example: 

$m=m_1m_2m_3m_4$

$\rightarrow$$\phi_1=
\begin{bmatrix}
    m_{1} &amp; m_{2} &amp; m_{3} &amp; m_{4} \\
    3 &amp; 2 &amp; 4 &amp; 1
\end{bmatrix} $$\rightarrow m_{\phi_1}=m_3m_2m_4m_1$

$\rightarrow$$\phi_2=
\begin{bmatrix}
    m_{3} &amp; m_{2} &amp; m_{4} &amp; m_{1} \\
    4 &amp; 2 &amp; 3 &amp; 1 
\end{bmatrix} $$\rightarrow m_{\phi_2}=m_1m_2m_4m_3$

$\therefore$ It is sufficient to have a permutation table to complete the mapping $m_1m_2m_3m_4 \rightarrow m_1m_2m_4m_3$

This matrix is
$\pi=
\begin{bmatrix}
    m_{1} &amp; m_{2} &amp; m_{3} &amp; m_{4} \\
    1 &amp; 2 &amp; 4 &amp; 3 
\end{bmatrix} $$\rightarrow \pi(m)=m_1m_2m_4m_3$

And $\phi_2(\phi_1(m))=\pi(m)$