Optery also has a Help Desk article on this catch-22 where in order to opt out of data broker sites, you must first tell them who you are, otherwise, how else would they know who to opt out: https://help.optery.com/en/article/what-information-does-opt...
They could use a bloom filter with some sort of a cryptographic hash. On a hit, the data broker could challenge them to compute a salted hash of the "matched" data. If the salted hash matched, the data broker would remove the data.
I think the same algorithms that are used for password storage would work for this without modification (except the data broker would pick different salts during each session, and you'd send the hash over the network).
No company wants to implement this. I've been involved in efforts to use this approach with hospitals -- a perfect PII-preserving situation -- that went nowhere. We got it working with a startup once where we published the bloom filter to reduce the traffic load for the counterparty. Do you know what they did? They reverse engineered the filter by blasting it with every key and cached the result.
I think the same algorithms that are used for password storage would work for this without modification (except the data broker would pick different salts during each session, and you'd send the hash over the network).