Set Intersection with asymmetric set sizes I'm looking for an algorithm to perform set intersection where set $N_1$ is very small and set $N_2$ is very large.  

Due to the constraints of the problem I am solving, I cannot rely on an algorithm which sorts or depends on sorted elements.  Further, the simple method of performing $N_1$ hash look ups in a hash table of size at least $N_2$ will also not work.

Are there any non-naive approaches to this problem that I am missing?
They do not have to be as efficient as either approach, but obviously the more performant the better.

Edit:  Since my constraints were a bit vague, I'll go ahead and spell them out.

The application I have in mind is one type of MPC. Here, I would like to perform a set intersection while neither party reveals anything about the elements that are not in the intersection. One party will be performing the comparisons, and the other party will be transmitting the elements of their set in an encrypted format.

Sorting is out because an encrypted value cannot be evaluated for anything besides equality. Doing so would either reveal more about the elements in the set or would come with significant computational overhead.

Hash table look ups have great promise, but all approaches involving them require that both parties pretend they have a set size of $max(N_1, N_2)$. The most effective way to optimize the communication between the parties is hash tables, but privacy requires inserting enough false elements so that each bin of the hash table has the same number of items.

Bloom filters also suffer from similar problems as hash tables.  To be correct and secure, the size of the smaller bloom filter must be large enough to fit the larger set.

I'm really just looking for a fundamentally different algorithm that I can use to design a different approach to the problem. I would like for the communication and computation to be dominated by the size of the smaller set. I recognize that this is a research problem that no one will have a perfect solution to. Instead, I am trying to find different types of structure that can be used to improve on the naive approach.
If you have exactly one intersection to compute, building a hash table from $N_1$ and doing $N_2$ lookups goes through the same number of hash operations as building one from $N_2$ and doing $N_1$ lookups.