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):
- 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.
- 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)
- 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?