# Is Pohlig-Hellman Cipher the only option?

I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a and b.

So far, the only cipher I could find that would work like this is Pohlig-Hellman Exponentiation Cipher. But as I understand, it has the following drawbacks:

1. It is slow - though, this is not really a concern for me
2. I can't find any actual implementations of the cipher. It shouldn't be too difficult to implement from scratch, but still...

Is there another cipher that can accomplish the same thing?

• Hi Irakliy and welcome. Could you extract that last part of your question about the sizes and create a different question for it? It seems rather distinct from the main question. Apr 5, 2018 at 17:40
• Thanks! Sure thing - I just removed the last part of the question. I'll create a separate question later if Pohling-Hellman is indeed the only thing I can use. Apr 5, 2018 at 18:43
• Why do you have such a requirement? Do you need the combination ab to be commutative? ab=ba? Apr 6, 2018 at 5:03
• This is for zero-knowledge info sharing system I'm designing. The combination doesn't really need to be commutative, though Pohlig-Hellman is. Apr 6, 2018 at 5:12
• Key-homomorphic encryption allows you to compute $\mathsf{Enc}_k(m)\stackrel{f}{\mapsto} \mathsf{Enc}_{f(k)}(m)$ for any arbitrary computable $f$. This is close to what you want, but I'd imagine it has similar issues as Pohlig-Hellman (although I haven't checked).
– Mark
Apr 20, 2019 at 16:18

If you define $E_a(M) = M \oplus a$ then the key $ab$ can also be defined as $a \oplus b$ as follows:

$E_b(E_a(M)) = (M \oplus a) \oplus b$

$E_{ab}(M) = M \oplus (a \oplus b)$

However using the same key and/or message more than once in XOR will leak the other one. So I think it's potentially not what you're looking for.

As far as I know, SRA is also a variant, where you get regular RSA where both parties use the same modulus (and prime numbers) and create their own encryption, decryption exponents; and keep it secret. This way you achieve the same commutativity as in PH.

• $E(M,k) = M \oplus k$ uses the same math as the One Time Pad. Problem is (as noted in the answer) that when considered a cipher, $E$ is insecure under even Known Plaintext attack. The OTP is not a cipher, or is insecure; that's depending on if "One Time" is applied, or not.
– fgrieu
Oct 22, 2018 at 6:47