# Does asymmetric order-preserving encryption exist?

As I understand from this post, mapping from plaintext space to ciphertext space is the fundamental point of all order-preserving encryption. So the only way that we let someone encrypt an arbitrary plaintext is to give him/her this mapping. But, on the other hand, if we give someone this mapping, the encryption breaks because anyone who has access to it can easily decrypt any ciphertext since this mapping is usually reversible.

I am not sure at all that I have understood this correctly. Hence this post. To sum up, my question is: Is there any order-preserving encryption that gives everyone the possibility to encrypt an arbitrary message?

• You are looking for something asymmetric with public encryption key and private decryption? Do you expect everyone to be able to compare order of ciphertexts? Jul 24, 2021 at 16:03
• Yes. I need it to be asymmetric and the encryption key can be published publicly. Jul 24, 2021 at 16:13
• If the comparison on the ciphertexts is a public operation, you can recover the plaintext using a simple binary search. Jul 24, 2021 at 18:53

Consider any PKE scheme for plaintext space $$\mathbb{Z}_n$$ for which there exists a public operation that given two ciphertexts (and possibly the public key) allows to test the relative order of the corresponding plaintexts.
Given a ciphertext $$c$$, and the public key we can then recover the plaintext using simple binary search over $$\mathbb{Z}_n$$ in $$O(\log n)$$ steps.