Semi-honest 2PC ⇒ PSI

Fully-black-box reduction · standard model · folklore · security loss: none

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