0

Assume there are 2 people in a conversation. Each one may support a given stance on an issue (the support is binary, either agreement=1, or disagreement=0). Both want to find more like-minded individuals, without revealing their (potentially incriminating) stance to someone who does not support it. We can assume that neither one of them wants to be misrepresenting themselves, so they will not lie about their stance, but otherwise if possible, both will attempt to find out the stance of their counterparty without giving out their own.

In technical terms: 2 parties (called A, B), each knowing 1 boolean value (v_A, v_B), want to compute a shared value v_A AND v_B, without revealing the underlying values to each other. By the properties of AND, it is unavoidable that if v_A is true, A is able to deduce v_B from the result, but in the opposite case (v_A is false), this isn't possible (as requested).

In a centralized scenario, this could be easily solved by both parties providing the values to a trusted third party, which computes the result and sends it back to both parties, but TTP might not always be available.

Is it possible to construct a protocol that achieves this goal without a third party, under the constraints mentioned at the end of first paragraph?

I know undergraduate math reasonably well, with some basics in homomorphic encryption, signature algorithms, and a few articles about zero knowledge proofs. Feel free to leave pointers to more literature, I'm be happy to learn what's necessary on my own.

P.S.: I'm aware that the practical cryptographic use of such a protocol is very limited, as neither of the parties can be forced to provide correct value (and always providing 1 leads to discovery of the other value), and trying to incriminate them by publishing it, even if undeniable, would reveal your own support.

Your Answer

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

Browse other questions tagged or ask your own question.