# Is there a public key encryption for permutations which is homomorphic under permutation composition?

I'm brainstorming an idea for extending our Latin square autotopism secret sharing scheme (proposed here [open access]) to a repairable scheme. I seek a cryptographic method, which may or may not exist.

• We are encrypting permutations. (For the application I have in mind, restricting to permutations of $\{1,2,\ldots,14\}$ would be fine.)

• It's a public key encryption method. So I generate a public key $k$ and private key $p$, and I can distribute $k$ for others to encrypt with, but I decrypt with the private key $p$.

So any permutation $\alpha$ is encrypted to $E_k(\alpha)$, say.

• It's homomorphic on permutation composition. I.e., if $\alpha$ and $\beta$ are any two permutations, then $E_k(\alpha \beta)=E_k(\alpha) E_k(\beta)$.

Does such an $E$ exist?

For the application I have in mind, it doesn't need to be efficient computationally.

• Are you using the full symmetric group $S_n$ or a subset? Since $14! < 2^{37}$ that seems like a small key space. – user47922 Jun 6 '17 at 2:09
• The full symmetric group. At the moment, I'm at the "proof of concept" stage (brainstorming). I don't know if it will be helpful in the end. – Rebecca J. Stones Jun 6 '17 at 2:10
• If you're wondering just about existence, check out homomorphic shuffles, particularly Section 2.2. It's not exactly your problem though (they are interested in proving correctness of shuffles). – user47922 Jun 6 '17 at 3:13
• Rebecca, is it not possible to find an isomorphism between the symmetric group you want to use and some group $(\mathbb{Z}_m, +)$? (Maybe by some theorem like the Cayley's one?). Because if it is possible, than you can just use "classic" homomorphic schemes like Paillier. – Hilder Vítor Lima Pereira Jun 6 '17 at 7:35
• I doubt it; the symmetric group is non-abelian. – Rebecca J. Stones Jun 6 '17 at 7:38