Join Log in
Score:0
Mahsa Bastankhah avatar Crypto

Comparing two private values and extracting the ciphertext corresponding to the minimum value

de flag
Mahsa Bastankhah

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.

  • Consider a node "B" with private value "BPrivateValue = b"
  • B's ancestor is called "A" and A's private value is "APrivateValue = a".
  • B's descendant is called "C" and C's private value is "CPrivateValue = c".

I want every node in this graph to be able to do the following(here we just consider node B for simplicity):

  1. B does some interaction with A and finds out if APrivateValue > BPrivateValue or APrivateValue < BPrivateValue. But nothing more than this comparison leaks to A and B about the private value of the other party.
  2. if APrivateValue < BPrivateValue B changes his private value to "a" i.e. BPrivateValue = a (Note that actually, B doesn't know the value of a, he has a commitment or encryption of "a" but he knows that he should change his private value)
  3. Now C does the same thing with B and this protocol goes on until the last node in this path in the graph. At the end, a commitment or encryption of the minimum private value in this path is the output.

Now, what scheme or tool do you think can help me to implement this functionality. First of all, I thought about asymmetric privacy-preserving encryption. All the node encrypt their private value and send the encryption to the next node. The next node does the comparison and sends the encrypted value of the minimum private value to the next node. But then I realized that asymmetric privacy-preserving encryption isn't secure at all and anyone can calculate the plaintext corresponding to a ciphertext with a simple binary search. So what do you suggest?

51
0 + 4
Reppiz avatar
gb flag
Reppiz
Are there any further restrictions? For example at the end, does it matter which of the node's actually encrypted the value which is the output of the last node? Is there some limit of what the nodes can store by themselves? And can the protocol for communication be designed "freely"?
1
Reply
SEJPM avatar
us flag
SEJPM
I'm not sure if there's any solution to this problem as stated that does not leak as much as using straight order revealing encryption. The best solution outside of that would probably be a full-on Multi-Party Computation with all involved parties supplying their private value as input and the designated receiver learning the minimum of the inputs and which node held that input. The tricky part would then become to ensure that malicious nodes do in fact not lie about their private value which is probably doable using an appropriate Zero-Knowledge proof with the found min holder.
1
Reply
Mahsa Bastankhah avatar
de flag
Mahsa Bastankhah
Isn't order revealing encryption symmetric? here we can't use symmetric encryption because we want everyone to be able to encrypt an arbitrary message.
0
Reply
Mahsa Bastankhah avatar
de flag
Mahsa Bastankhah
MPC doesn't work here because all of these nodes don't know each other and they just know their own ancestor and descendants. and here we don't worry about it that some adversary may lie about their private value. we want a scheme that if everyone is semi-honest we can always find the minimum and the least possible information about private values leak.
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.