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?

  • 1
    $\begingroup$ 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"? $\endgroup$
    – Reppiz
    Jul 26, 2021 at 12:22
  • 1
    $\begingroup$ 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. $\endgroup$
    – SEJPM
    Jul 26, 2021 at 14:09
  • $\begingroup$ 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. $\endgroup$ Jul 26, 2021 at 15:18
  • $\begingroup$ 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. $\endgroup$ Jul 26, 2021 at 15:20


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy