3
$\begingroup$

In the book written by Ivan Damagard titled "Secure Multiparty Computation and Secret Sharing", at the end of the third chapter he provides a proof for why it is impossible to securely compute 2 party AND function under perfect and passive security with one corrupt party.

Can someone help me provide an intuitive explanation for why the above is true. I was unable to grasp the solution provided by Damagard. I could not find any other resource regarding the same either.

$\endgroup$
8
$\begingroup$

The intuition behind the proof is as follows. Since the output of AND equals 0 when party P2 has input 0, then the transcript is distributed identically when P1 has input 0 and when P2 has input 1. Likewise, in the opposite direction. Thus, the set of possible transcripts when P1 has 1 and P2 has 0 equals the set of possible transcripts when both have 0, and the set of possible transcripts when P1 has 0 and P2 has 1 equals the set of possible transcripts when both have 0.

In the proof, they further show that the intersection of the set of transcripts as above is a subset of the set of transcripts when both parties have 1 (just by the definition of how the transcripts are defined).

As a result, the set of transcripts when both parties have 0 is a subset of the set of transcripts when both parties have 1.

The proof proceeds by arguing that the intersection between these sets of transcript actually has to be empty (since you can't output both 0 and 1). However, I actually think that the proof is already complete when they show that $T(1,0) \cap T(0,1) \subset T(1,1)$. In order to see this, let $t\in T(1,0)$; by what we have stated now it also follows that $t\in T(1,1)$. Since P1's output is determined by its input and transcript, it follows that it outputs the same bit in both cases. This contradicts correctness.

(I emailed with both Ivan Damgård and Jesper Nielsen on this; so thanks to them for them help.)

$\endgroup$
  • $\begingroup$ Thank you professor for your reply. The intuition you provided helped me go through the proof in the book and I clearly understand it now. $\endgroup$ – Itachi Mar 29 '16 at 15:06
  • $\begingroup$ Glad to be of help. $\endgroup$ – Yehuda Lindell Mar 29 '16 at 18:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.