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.


closed as unclear what you're asking by Squeamish Ossifrage, kelalaka, AleksanderRas, puzzlepalace, e-sushi Sep 29 at 10:33

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Look up the definition of a pseudorandom permutation, for starters. $\endgroup$ – fkraiem Sep 25 at 14:22
  • $\begingroup$ 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 ... $\endgroup$ – DannyNiu Sep 26 at 1:50
  • $\begingroup$ @DannyNiu The question is about what the definition means, not about whether such objects exist. $\endgroup$ – fkraiem Sep 26 at 7:23
  • $\begingroup$ @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... $\endgroup$ – J. Doe Sep 26 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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.