(Impossibility of?) Associative Pseudorandom Permutation 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?
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:


Choose random $k'$ and $x$ and compute $y := f(k',x)$.
Query $y$ to the oracle and receive back $z$.
Query $k'$ to the oracle and receive back $k''$.
Compute $z':= f(k'',m)$ and check whether $z'=z$. 
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.