12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Apr 5 '18 at 17:40
  • $\begingroup$ 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. $\endgroup$ – irakliy Apr 5 '18 at 18:43
  • $\begingroup$ Why do you have such a requirement? Do you need the combination ab to be commutative? ab=ba? $\endgroup$ – Meir Maor Apr 6 '18 at 5:03
  • $\begingroup$ This is for zero-knowledge info sharing system I'm designing. The combination doesn't really need to be commutative, though Pohlig-Hellman is. $\endgroup$ – irakliy Apr 6 '18 at 5:12
  • 1
    $\begingroup$ 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). $\endgroup$ – Mark Apr 20 at 16:18
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – fgrieu Oct 22 '18 at 6:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.