A new private-set intersection paper, claiming to scale orders of magnitude better than predecessors, has just been released [1]. I don't know whether it solves your problem, as I haven't read anything beyond the abstract, but you might want to check it out anyway.

[1] https://research.microsoft.com/en-us/um/people/senyk/pubs/sa...