# (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?

• One of the practical difficulties is that, given so many permutations, the computation of two permutations $f(k_1, k_2)$ might not necessarily be in the set of prepresentable permutations. – DannyNiu Sep 16 '17 at 6:08
• I have edited your title. Please see, "Should questions include “tags” in their titles?", where the consensus is "no, they should not".. Also, you might want to share a link to something that shows how homomorphic encryption is an approximation of an associative psuedorandom permutation, I don't see how that follows. Maybe it's just me, but I have never heard of APP before, so I'm not so sure "everyone knows APP is the ideal solution to PKC" is accurate... (not that I know everything, I don't) – Ella Rose Sep 16 '17 at 19:29
• Obligatory xkcd defining brutal-force search. Leave the typo! – Q-Club Sep 16 '17 at 21:28
• I might be missing something, but how could an APP be used to generate a signature (apart from a hash based signature, obviously)? – poncho Nov 28 '17 at 19:47
• The way you define indistinguishable from random contradicts the associativity requirement. Random functions are very unlikely to be associative so the distinguishing attack is checking for associativity. This is not to say a weaker requirement like no attack on key or plain text better than generic attacks isn't attainable. – Meir Maor Jan 27 '18 at 7:16

## 2 Answers

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.

• Eh... the probability is slightly off because we're talking about permutations not general functions. I'll fix it tomorrow. – Maeher Jan 27 '18 at 10:52

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.