2PC Private Set Intersection Optimized for asymmetrically sized sets
It is easy to observe that any secure protocol must touch every bit of both parties' inputs -- otherwise it's not secure.

However recent work has shown that you can amortize the protocol complexity over several runs, with state stored between the runs, so that not every execution will touch every bit.   See here for the paper.  It doesn't address set intersection directly, but since it covers a generic function it applies to your case.