Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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.)
