But the claim is that Apple does that "on device". To the best of my understanding, this would mean that both parties in the PSI protocol are "on the same device". Do they probably use some kind of TEE (Trusted Execution Environment) to evaluate the "other side" of the PSI protocol?
Probably using some sort of probabilistic query like a bloom filter.