# Private Set Intersection using a subset of the larger set

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.