Join Log in
Score:3
Mahsa Bastankhah avatar Crypto

Does asymmetric order-preserving encryption exist?

de flag
Mahsa Bastankhah

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?

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

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.

0 + 2
Mahsa Bastankhah avatar
de flag
Mahsa Bastankhah
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.
0
Reply
cn flag
Maeher
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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.