0
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Any non-naive approach is going to exploit some structural aspect of the data. So what exactly is this set data that resists both sorting and hashing? $\endgroup$
    – Kyle Jones
    Commented Feb 26, 2015 at 3:30
  • $\begingroup$ If you have the leeway (and willingness) to pick particular data structures, Realz Slaw's answer to this question could be useful. $\endgroup$
    – Luke Mathieson
    Commented Feb 26, 2015 at 3:43
  • 1
    $\begingroup$ I agree; we need to know a) which set representation(s) you (can) use, and b) whatever you know about the data. $\endgroup$
    – Raphael
    Commented Feb 26, 2015 at 7:10
  • $\begingroup$ @Raphael I spelled out my constraints quite a bit more. The elements in the set can be translated into any arbitrary structure, but the security constraints require that the structure not reveal the value of the elements. If you want more background on the problem, see this recent paper. $\endgroup$
    – Guest
    Commented Feb 27, 2015 at 4:44
  • $\begingroup$ I still find this confusing. I know about MPC, but I don't understand why hash tables require both parties pretend they have a set size of $\max(N_1,N_2)$. Can you elaborate? And can you elaborate on what precisely is your model? Are you looking for a circuit? What are the inputs to the circuit? What is your measure of the complexity of the circuit? Right now the question is not very specific. $\endgroup$
    – D.W. ♦
    Commented Feb 27, 2015 at 6:23

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Now that I've spelled out my constraints, I think it's clear this solution doesn't contribute a lot. Thanks for the thought. $\endgroup$
    – Guest
    Commented Feb 27, 2015 at 4:40
  • $\begingroup$ @Guest, alas, it's not clear to me yet. Thanks for editing the question, as it helped partially, but I think I need more explanation to understand. $\endgroup$
    – D.W. ♦
    Commented Feb 27, 2015 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.