These applications can easily handle an 80 sec delay. It's also likely that queries scale well by batching into larger combined queries (since you need to involve every row already anyway).
1. Alice provides Bob with her public and evaluation keys.
2. Bob encrypts each row of the blacklist with her public key.
3. Alice encrypts her query (e.g. for "Eve") and sends to Bob.
4. Bob evaluates some circuit on Alice's query and Bob's rows, and sends her one (encrypted) result per row
5. Alice decrypts the rows and sees if any are ones.
Ways this can be made more efficient:
* Outputs from each row's evaluation can chain into the next evaluation, so Bob only need return O(1) data.
* Bloom filters could cut down on average-case performance, but that would make Alice leak information (whether she follows up her FHE bloom filter query with a more precise query.)