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.

  • $\begingroup$ Are you using the full symmetric group $S_n$ or a subset? Since $14! < 2^{37}$ that seems like a small key space. $\endgroup$ – user47922 Jun 6 '17 at 2:09
  • $\begingroup$ 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. $\endgroup$ – Rebecca J. Stones Jun 6 '17 at 2:10
  • 1
    $\begingroup$ 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). $\endgroup$ – user47922 Jun 6 '17 at 3:13
  • $\begingroup$ 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. $\endgroup$ – Hilder Vitor Lima Pereira Jun 6 '17 at 7:35
  • $\begingroup$ I doubt it; the symmetric group is non-abelian. $\endgroup$ – Rebecca J. Stones Jun 6 '17 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.