0

Apologies if this is not the best place to post this, but there are permutations and reductions involved and it's not the programming that I'm interested in. If not I'd be happy for this question to be transferred somewhere else more appropriate. I don't really know how to phrase this other than by pseudo computer code.

Let's consider the Pearson hash function, which I describe in pseudo code:-

algorithm pearson hashing is
    h := 0

for each c in C loop
    h := T[ h xor c ]
end loop

return h

where T is a permutation such as:-

    T = [1, 87, 49, 12, 176, 178, 102, 166, 121, 193, 6, 84, 249, 230, 44, 163,
         14, 197, 213, 181, 161, 85, 218, 80, 64, 239, 24, 226, 236, 142, 38, 200,
         110, 177, 104, 103, 141, 253, 255, 50, 77, 101, 81, 18, 45, 96, 31, 222,
         25, 107, 190, 70, 86, 237, 240, 34, 72, 242, 20, 214, 244, 227, 149, 235,
         97, 234, 57, 22, 60, 250, 82, 175, 208, 5, 127, 199, 111, 62, 135, 248,
         174, 169, 211, 58, 66, 154, 106, 195, 245, 171, 17, 187, 182, 179, 0, 243,
         132, 56, 148, 75, 128, 133, 158, 100, 130, 126, 91, 13, 153, 246, 216, 219,
         119, 68, 223, 78, 83, 88, 201, 99, 122, 11, 92, 32, 136, 114, 52, 10,
         138, 30, 48, 183, 156, 35, 61, 26, 143, 74, 251, 94, 129, 162, 63, 152,
         170, 7, 115, 167, 241, 206, 3, 150, 55, 59, 151, 220, 90, 53, 23, 131,
         125, 173, 15, 238, 79, 95, 89, 16, 105, 137, 225, 224, 217, 160, 37, 123,
         118, 73, 2, 157, 46, 116, 9, 145, 134, 228, 207, 212, 202, 215, 69, 229,
         27, 188, 67, 124, 168, 252, 42, 4, 29, 108, 21, 247, 19, 205, 39, 203,
         233, 40, 186, 147, 198, 192, 155, 33, 164, 191, 98, 204, 165, 180, 117, 76,
         140, 36, 210, 172, 41, 54, 159, 8, 185, 232, 113, 196, 231, 47, 146, 120,
         51, 65, 28, 144, 254, 221, 93, 189, 194, 139, 112, 43, 71, 109, 184, 209]

and xor is the Exclusive OR function. So for example a Pearson hash of "Hello" might return 42. What I want to focus on is table T, which is a random permutation on the range (0, 255). Let me now add more independent permutations (T2, T3 and T4) into the loop:-

for each c in C loop
    h := T1[ h xor c ]
    h := T2[ h xor c ]
    h := T3[ h xor c ]
    h := T4[ h xor c ]
end loop

So we have four different permutation tables, T1, T2, T3 and T4 and the value h passes through all four sequentially.

Q. Is it possible to reduce all four tables to one single new one (Tnew) that produces the same output, as:-

for each c in C loop
    h := Tnew[ h xor c ]
end loop

?

Paul Uszak
  • 499
  • Are you asking how to compute the product of permutations? https://math.stackexchange.com/questions/500198/product-of-permutations – JBL Oct 16 '22 at 17:56
  • @JBL Oh gosh, no. It's probably necessary to read Pearson's paper (linked). The function creates a singular hash value for input messages of varying length. So for example f("Hello") = 42. I'm wondering if when multiple permutation tables are used, can they be replaced with a single new one that mimics the others' outputs. I'm sorry, but I can't describe this problem in any other way... – Paul Uszak Oct 16 '22 at 20:34

1 Answers1

0

There will be no such table in general.

A simple counterexample is when you have two tables, T1 and T2, and T1 is the identity. Then c cancels out in the two XORs, so the combined effect is simply h -> T2[h], independent of c. To mimic this for zero inputs, Tnew would have to be T2. But then it’s a permutation, and thus its output isn’t independent of c.

joriki
  • 238,052
  • Thanks joriki. Just to clarify, are you saying that in general, obtaining Tnew is just difficult or mathematically impossible? – Paul Uszak Mar 19 '23 at 13:42
  • @PaulUszak: Impossible. I provided a proof that it's impossible in a very simple case. My impression is that it would be impossible in most cases, though of course you can always construct cases where it's possible. – joriki Mar 19 '23 at 13:53