# Question about the definition of Associative Pseudorandom Permutation [closed]

In question about associative pseudo-random permutation the definition uses:

$$f(k_1, f(k_2, m)) = f(f(k_1, k_2), m)$$

What is defined by that? No luck with google so far.
As far as I know a permutation is defined by item number at a certain index. If $$f$$ is a table the item number count would be higher than the number of columns/rows which would result in invalid indices. Or is it a permutation in each row and column? Number of rows and columns need to be equal then. Would be some kind of Latin-square matrix. If that's the case the definition would result in a symmetric matrix which would be the same permutation in each direction.

• Look up the definition of a pseudorandom permutation, for starters. – fkraiem Sep 25 '19 at 14:22
• There had never been such thing, otherwise such silverbullet to PKC would have already been discovered! And the title of the linked question is clear enough: The "Impossibility" of ... – DannyNiu Sep 26 '19 at 1:50
• @DannyNiu The question is about what the definition means, not about whether such objects exist. – fkraiem Sep 26 '19 at 7:23
• @DannyNiu you write '(I'm not sure if it'd be impossible)' in this thread. Can you please define what $f$ and $k1$,$k2$,$m$ stand for. I'm fine with just two words like table,function, permutation, index, variable... – J. Doe Sep 26 '19 at 15:10

$$f(k_1, f(k_2, m)) = f(f(k_1, k_2), m)$$

What is defined by that?

$$f$$ is just a binary operator written in the notation of a function.

Suppose $$f: P \times P \rightarrow P$$ is a binary operator taking 2 permutations encoded as bitstrings as operands and produce another permutation (also encoded as bitstring) as result, the associativity can be illustrated by replacing $$f(a,b)$$ as $$a+b$$, and the original equation will be:

$$k_1 + (k_2 + m) = (k_1 + k_2) + m$$

Here, suppose we're in a digital signature scheme, the $$k_1$$ and $$(k_1+k_2)$$ will be the public key, $$k_2$$ will be the private key, and $$m$$ is the (digest of) message being signed.

And that, is just my wishful thinking that public-key cryptography can be as simple as a one-year-old's mind.