(Impossibility of?) Associative Pseudorandom Permutation

Question

I'm not sure whether this had been a long-standing open problem in cryptography.

Definition

An associative pseudorandom permutation $f(k,m)$ is a permutation such that:

• $f(k_1, f(k_2, m)) = f(f(k_1, k_2), m)$
• Given $s = f(k, m)$ and $k$, the only way to find $m$ is brutal-force search.
• The output of $f$ is indistinguashable from random using polynomial-time algorithms.

With such a permutation, constructing key encapsulation and digital signature would be as easy as calculating 1+1. But as of 2017, the best approximation seem to be homomorphic encryption.

Question

If everyone can infer that APP is the ideal solution to PKC, then why isn't there a concrete instance of one? What are the practical difficulties and open problems standing in the way?

Answer 1

As mentioned by Meir Naor in the comments, what you are describing is impossible. The reason is that the associativity gives us leverage to distinguish the function from a random function. To do so an adversary $\mathcal{A}$ with access to an oracle that is either $f(k,\cdot)$ for a random key $k$ or a truly random function $g(\cdot)$ can proceed as follows:

1. Choose random $k'$ and $x$ and compute $y := f(k',x)$.
2. Query $y$ to the oracle and receive back $z$.
3. Query $k'$ to the oracle and receive back $k''$.
4. Compute $z':= f(k'',m)$ and check whether $z'=z$.
5. If it is output $1$, otherwise output $0$.

To see that $\mathcal{A}$ is a successful distinguisher for $f$ we want to analyse $$\left|\Pr[\mathcal{A}^{f(k,\cdot)}(1^n)=1] - \Pr[\mathcal{A}^{g(\cdot)}(1^n)=1]\right|$$ and see that this difference is noticeably greater than $1/2$.

In the first case we have by the associativity of the function $f$ that $z=f(k,f(k',x))=f(f(k,k'),x)$. Further we have that $k'' = f(k,k')$ and thereby $z'=f(k'',x) = f(f(k,k'),x) = z$. Therefore we have $$\Pr[\mathcal{A}^{f(k,\cdot)}(1^n)=1] = 1.$$

In the second case we have that both $z$ and $k''$ are truly random independently sampled values in $\{0,1\}^n$. In particular $z'=f(k'',x)$ is some value that is distributed independently of $z$. Therefore we have that $\Pr[z=z'] = 2^{-n}$ (i.e., the probability that an independently randomly sampled $z$ takes any particular fixed value). This means that $$\Pr[\mathcal{A}^{g(\cdot)}(1^n)=1] = 2^{-n}$$ and we get $$\left|\Pr[\mathcal{A}^{f(k,\cdot)}(1^n)=1] - \Pr[\mathcal{A}^{g(\cdot)}(1^n)=1]\right| = 1-2^{-n}$$ which is noticeably greater than $1/2$. (In fact it's only negligibly smaller than $1$.)

This shows that any fixed associative function is always distinguishable from a random function. Also note that this attack does not go away by just constraining $g$ to be a random associative function. This is because we are not simply checking whether the oracle is associative. We are specifically using the associativity of $f$ to check whether the oracle is $f$. In the case where $g$ is associative, the analysis gets a bit more complicated because $z$ and $z'$ are now no longer completely independent. But the attack still works.

Answer 2

Let's demonstrate the difficulty (I'm not sure if it'd be impossible) from the following aspects:

1. For a permutation to be called pseodorandom, it must be at least a non-linear function of its input, otherwise, linear analasis would be trivial.

2. It's a general truth, that most non-linear operations are also non-associative. One of the most familiar example is quadratic sum: $x^2+y^2$ generally don't equal $(x+y)^2$.

Side Note: Assuming you're looking for a permutation that preserve ciphertext size during evaluation, such permutation would almost certainly require more information during evaluation than the information it produces.

An example can be seen with Rainbow signature, where the public key is the composition $L_1 \circ F \circ L_2$, where $L_1$ and $L_2$ are affine linear maps and $F$ the quadratic function. It is mentioned in "Rainbow, a New Multivariable Polynomial Signature Scheme" that

The public key consists of 27 quadratic polynomials with 33 variables. The total number of coefficients for the public key is 27 × 34 × 35/2 = 16, 065, or about 15 KB of storage.