My understanding is that, simply put, a stream cipher is just a CSPRNG such that $R(i,k)$ will produce a deterministic but statistically random sequence, where $i$ is an IV, and $k$ is the session key. The resultant key-stream $K$ is then combined with plaintext (i.e. $C = K \oplus M$).

Now, if we take two messages $m_1$ and $m_2$, and assume $\mathcal{E}(x)$ and $\mathcal{D}(x)$ are functions that encrypt and decrypt a message as described above, surely the following is a partially homomorphic cryptosystem?

$$\mathcal{D}(\mathcal{E}(m_1) \oplus m_2) = m_1 \oplus m_2$$

This seems a really simple and fundamental way to perform unauthenticated homomorphic cryptography, yet the Wikipedia article doesn't mention it at all.

Am I incorrect in saying that this process demonstrates homomorphism?


To answer your question: no this is not homomorphic encryption because one of the plaintexts is used unencrypted. There may be times when it is a useful property, but the only uses I know of it are to demonstrate the malleability of xor ciphers.

To be a homomorphic encryption function, it should be possible to calculate the encryption of some function of the plaintexts from their respective ciphertexts without using the key. That is, given $c_1=e_k(m_1)$, $c_2=e_k(m_2)$ one should be able to calculate $c_3=e_k(f(m_1,m_2))$ by evaluating some $g(c_1,c_2)$.

More generally, a homomorphism is a mathematical function that preserves some operation. For example, if an encryption scheme $e$ would be xor-homomorphic if $$ e(m_1)\oplus e(m_2) = e(m_1\oplus m_2) $$

More complex schemes might commute with other operations. For example the Pallier scheme uses the fact that $$ a^x \cdot a^y = a^{x+y} $$

To construct a scheme that uses multiplication of ciphertexts to calculate the sum of plaintexts.

  • $\begingroup$ This makes sense. I think malleable was the term I was originally trying to think of to describe this property. $\endgroup$ – Polynomial Dec 4 '13 at 14:52
  • $\begingroup$ was going to edit this in, but since its more a side-point: An efficient Fully Homomorphic Encryption scheme (FHE) is in many ways the holy grail of cryptography, since it would allow encrypted evaluation of any circuit - which basically means you can secretly evaluate any function. $\endgroup$ – figlesquidge Dec 4 '13 at 17:40

We typically refer to a homomorphic cipher if we can take two ciphertexts and combine them in a way that has a predictible result on the plaintexts. In your example you have taken one ciphertext and one plaintext.

Using a stream cipher correctly you should never have 2 ciphertexts encrypted with the same portion of a keystream. So, combining two ciphertexts you would have the xor of the two messages encrypted with the xor of the two keys. That is not typically what we think of when we think of homomorphic ciphers.

  • $\begingroup$ Well, with a stream cipher, we can take three ciphertexts, and combine them with predictable results. Does that count :-? $\endgroup$ – poncho Dec 4 '13 at 14:36
  • $\begingroup$ Does that requirement imply that there are no truly homomorphic symmetric ciphers, since generating the second ciphertext would require knowledge of the key? $\endgroup$ – Polynomial Dec 4 '13 at 14:38
  • $\begingroup$ @poncho, not sure, but I sure don't want to use software that spits out multiple ciphertexts encrypted with the same keystream (whether it spits out 2 or 3 or more). $\endgroup$ – mikeazo Dec 4 '13 at 14:38
  • $\begingroup$ @Polynomial Most homomorphic ciphers allow you to add and/or multiply in plaintext values (in addition to ciphertext values). I just believe that to be called a homomorphic cipher it should securely be able to combine ciphertexts. $\endgroup$ – mikeazo Dec 4 '13 at 14:43

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.