# 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.

1. Can a new $$\pi$$ or set of $$\pi$$s be constructed to arrive at an identical output for all messages with $$ 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| > 1$$?
2. Considering the trivial case mentioned above, is there some relationship between $$N$$ and $$|m|$$ that determines the answer?
3. If a reduced set of new $$\pi$$s might theoretically exist, how might it found in practice?

Notes:

1. Some of this question is clearly on topic here, but not sure about it's entirely.
2. I see small parallels with permutations and non linearity, construction of S boxes, and their combinations.

3. 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.

4. 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} & m_{2} & m_{3} & m_{4} \\ a & b & c & d \end{bmatrix}$$ $$\phi_2= \begin{bmatrix} m_{1\phi_1} & m_{2\phi_1} & m_{3\phi_1} & m_{4\phi_1} \\ e & f & g & 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 & 5 & 1 & 2 \\ 4 & 2 & 3 & 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} & m_{2} & m_{3} & m_{4} \\ 3 & 2 & 4 & 1 \end{bmatrix} \rightarrow m_{\phi_1}=m_3m_2m_4m_1$$

$$\rightarrow\phi_2= \begin{bmatrix} m_{3} & m_{2} & m_{4} & m_{1} \\ 4 & 2 & 3 & 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} & m_{2} & m_{3} & m_{4} \\ 1 & 2 & 4 & 3 \end{bmatrix} \rightarrow \pi(m)=m_1m_2m_4m_3$$

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

• Hi. Re. "Claim:" I'm having difficulty in matching this to my question. I appreciate the reduction of simple multiple permutations. But these are part of a hash. So in your example, $m=3512$, and therefore as an example $H_4(m) = 110$ for a hash with 4 permutation tables. In the linked question we used 2 tables. – Paul Uszak Mar 27 at 10:46
• I'm trying to find out whether such a composition of permutation tables can be reduced to fewer tables, and thus less memory to store all of them. It's a functional composition reduction thingie job, but I'm not really sure what to call it... – Paul Uszak Mar 27 at 10:47