Score:3

Does asymmetric order-preserving encryption exist?

de flag

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?

Meir Maor avatar
in flag
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?
Mahsa Bastankhah avatar
de flag
Yes. I need it to be asymmetric and the encryption key can be published publicly.
cn flag
If the comparison on the ciphertexts is a public operation, you can recover the plaintext using a simple binary search.
Score:6
cn flag

No, an order preserving public key encryption scheme cannot be secure.

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.

Mahsa Bastankhah avatar
de flag
you are right. So how can I solve this problem: I have a directed graph of nodes that can be malicious and all of them have a private value. I want every node in this graph to be able to compare his private value with the private value of his ancestor and send the minimum of these two values to his descendants. But notice that these values are private i.e. I want this comparison between private value can happen with the least leakage of information that is fundamentally possible.
cn flag
Is interaction allowed between nodes? Non-interactively you can probably do it using FHE. Otherwise some kind of 2PC protocol should work. This sounds a lot like Yao's Millionaires' problem.

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.