I'm relatively new to this topic, and I have a question that might seem basic. I appreciate your patience. In most PSI schemes(2 party or multi party),the intersection result is always output by only one of the parties.If this party modify the final result,the scheme is obviously unsafe.I guess there is some assumption or something i did not notice.So,i wonder if this problem is discussed before and what is the solution?
2 Answers
$\begingroup$
$\endgroup$
In actively secure 2PC/MPC, the adversary cannot
- learn more about honest parties' inputs than in the ideal world, nor
- influence honest parties' outputs more than in the ideal world.
The security definition doesn't care about what the adversary itself reports as output (to the environment). Of course a corrupt party can say that the output was anything.
Let's take a simple 2-party example. Alice & Bob do PSI, and Alice learns the output.
If Bob is corrupt, then the protocol should ensure that honest Alice computes a "correct" output (one that is consistent with the ideal world). Active security guarantees this.
If Alice is corrupt, then honest Bob should compute the "correct" output, which is the empty output in this case. This is very easy since the protocol always instructs Bob to give empty output.
Perhaps you are imagining the following protocol:
- Alice & Bob run 2-party PSI, with Alice learning the output.
- Alice sends the PSI output to Bob.
- Both parties output this PSI output.
This is an attempt to transform the one-sided-output protocol into a 2-sided-output protocol. But, as you point out, it is not secure against active adversaries. The "PSI output" message from Alice to Bob is part of the protocol, and Bob just accepts whatever Alice says, so Alice can easily lie.
None of this is specific to PSI; it's true about any 2PC.
If you are wondering about actively secure 2-party PSI with 2-sided output, then yes this is non-trivial. It is a difficult problem, and there are not many good options available. In most/all one-sided PSI protocols it is easy for Alice to to prove to Bob that some item was in the intersection, but it is hard for her to prove that she hasn't excluded any items from the intersection.
$\begingroup$
$\endgroup$
In the dishonest-majority setting, even identifying which parties engage in dishonest behavior becomes costly. Therefore, in the general case of MPC allowing malicious adversaries, established constructions rely on generic zero-knowledge proofs, secure oblivious transfer (OT), or homomorphic primitives.
