Secure computation of shared data intersections

A method for providing an extended private set intersection nested cuckoo hashing scheme for secure computation of private set intersections, the method comprising:

• exchanging, between a server and a client, a set of outer hash functions and a set of inner hash functions,
• wherein the set of outer hash functions maps a set of client items to a set of client outer indices, and the set of outer hash functions maps a set of client items and a set of server items to a set of client outer indices and server outer indices, respectively, and wherein the set of inner hash functions maps a set of client items and a set of server items to a set of client inner indices and server inner indices, respectively;
• creating a server outer hash table using an outer hash function in the set of outer hash functions and the set of server items to create a set of server bins;
• and
• for each server bin in the server outer hash table, iteratively placing server items to be inserted into a server inner cuckoo hash table using a plurality of inner hash functions corresponding to each server bin, based on determining that a first corresponding hash table position is free.

A system for providing an extended private set intersection nested cuckoo hashing scheme for secure computation of private set intersections, the system comprising:

• at least one processor;
• and at least one non-transitory memory storing computer executable instructions that when executed by the at least one processor cause the system to carry out actions comprising:
• exchanging, between a server and a client, a set of outer hash functions and a set of inner hash functions,
• wherein the set of outer hash functions maps a set of client items to a set of client outer indices, and the set of outer hash functions maps a set of client items and a set of server items to a set of client outer indices and server outer indices, respectively, and wherein the set of inner hash functions maps a set of client items and a set of server items to a set of client inner indices and server inner indices, respectively;
• creating a server outer hash table using an outer hash function in the set of outer hash functions and the set of server items to create a set of server bins;
• and
• for each server bin in the server outer hash table, iteratively placing server items to be inserted into a server inner cuckoo hash table using a plurality of inner hash functions corresponding to each server bin, based on determining that a first corresponding hash table position is free.