Semi-honest 2PC ⇒ PSI
Statement
A protocol that securely computes against semi-honest adversaries, with each set encoded as a string of a fixed length, which exists when semi-honest 2PC is achieved, is a semi-honest secure PSI protocol for every universe and size bounds and , where , and are polynomials in — folklore.
Sketch
is computed in time polynomial in , and , so the general protocol applies to it, and for each corrupted party the PSI semi-honest game is the semi-honest 2PC game for — standard.
Notes
- Run on a protocol secure with abort against a malicious adversary corrupting one party (2PC), and with an input that encodes no admissible set replaced by , the same construction gives PSI with malicious security (2PC ⇒ malicious PSI) — folklore.
- Semi-honest OT gives semi-honest secure computation of every functionality (semi-honest OT ⇒ semi-honest MPC) — GMW87, Gol04 — and conversely non-degenerate PSI gives semi-honest OT (PSI ⇒ OT) — folklore.