Suppose we have an $n$ bit block cipher $E$ with a key $k$ that has the following property $$E(k; m_1⊕m_2) = E(k;m_1) ⊕E(k; m_2).$$ How many minimum number of chosen plaintexts are required to decipher (with probability 1) a given ciphertext (not from the list of ciphetexts corresponding to the chosen plaintexts) without knowing $k$ and what would be those plaintexts be.

I figured replacing $m_2$ with a n-bit string of all 1's can give us $$E(m')=E(m)'$$ where $m'$ is one's complement of the bit string.

I cannot think of anything further than this. Not knowing the encryption algorithm seems to be a hurdle, although my teacher said it should not be.

  • $\begingroup$ And, is this homework? We call this homomorphic encryption. An example is Golderwasser-Micali $\endgroup$ – kelalaka Sep 15 at 18:43
  • $\begingroup$ @kelalaka: "although my teacher said it should not be" - I assume that it is either homework or a classroom exercise... $\endgroup$ – poncho Sep 15 at 18:44
  • 2
    $\begingroup$ Hint: Find two messages that their encryptions' x-or is the target ciphertext! $\endgroup$ – kelalaka Sep 15 at 18:49

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.