Alice has a set $S_A$ with a low cardinality (say ~30k). Bob on the other hand has a set $S_B$ with a much higher cardinality than of Alice's (say ~100M).

We're trying to create a reduced cardinality set ${S_B}'$ which satisfies the following:

$(S_A \cap S_B) \subset {S_B}' \subset S_B $

Is there a way for Bob to sample $S_B$ (with some privacy preserving input from Alice) in such a way that the cardinality of ${S_B}'$ (say ~1M) is significantly smaller than the cardinality of $S_B$?

Note: As the title of the question suggests, the purpose of the ${S_B}'$ is to implement a (lighter) Private Set Intersection (with associated data). Assume we can already do a PSE between $S_A$ and $S_B$; however due to the size of $S_B$ it's not feasible.

Due to the nature of the sets, both $S_A$ and $S_B$ can grow or shrink over time (but not dramatically); and we need to ensure forward-privacy (is this a term?), and assume this sampling and subsequent PSI will be applied periodically. Subsequent executions of this protocol should not undermine the privacy of $(S_A \cap S_B)$ or $S_A$ altogether.

One possible attack I can already see is: For every execution of this protocol, if the elements in ${S_B}'$ would be selected randomly; intersection of different instances of ${S_B}'$ would converge to $(S_A \cap S_B)$. So the entropy(?) of ${S_B}'$ should be maintained consistently.

A good example dataset having this behaviour would be user ids being active on different systems over days/months.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.