I would like to compare ciphertext based on the order assumed on the message space.

So, do you know if there exists some encryption scheme with the follow property:

Let $c_0 = E(m_0)$ and $c_1 = E(m_1)$ for all $m_0$ and $m_1$ in the message space. So,

$$c_0 \leq_C c_1 \Leftrightarrow m_0 \leq m_1$$

Note that I used $\leq_C$ instead of $\leq$, because the partial order relation on the ciphertext space may be different from the partial order of the message space.

For example, if I have $c_0$ and $c_1$ such that $c_0 = E(-3)$ and $c_1 = E(103)$, I would like to know that $c_0 \leq_C c_1$ without knowing the clear texts $-3$ and $103$.

If something is unclear, just let me know.

Thank you.

  • 1
    $\begingroup$ I re-tagged that question as about order-preserving encryption. This answer might help. $\endgroup$ – fgrieu Mar 10 '15 at 17:32
  • $\begingroup$ I've voted to close this as a duplicate (since the literal answer to your question is basically "this is called order-preserving encryption"), but +1 for a well-asked question. $\endgroup$ – Ilmari Karonen Mar 10 '15 at 20:13
  • $\begingroup$ Ok, I think it's better close this question too. I just asked it because I didn't know the term "order preserving encryption", so, when I searched here, I found nothing (I searched "comparision ciphertext", but it returned me comparisions among schemes, I searched for "partial order", but it returned me nothing, and so on...) $\endgroup$ – Hilder Vitor Lima Pereira Mar 10 '15 at 20:42