-1
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

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