[dboreham]

The "side effect free number crunching" in this case is: is <encrypted_phone_number> in <set_of_encrypted_bad_numbers>

You're on the right track with the idea of hashing -- I find it helpful to explain any fancy encryption scheme beginning with "if it were just hashing", then extend to "well this is a very fancy kind of hash", and <poof> now I kind of understand what's going on. Or at least it's no longer magic.

[saagarjha]

I don't think the set of bad numbers needs to be encrypted.

[vlovich123]

It does - otherwise you would know which numbers are queried to process the query, letting you narrow things down (ie huge side channel and thus not HE anymore).

[saagarjha]

How so? You can just query all the numbers and discard results you don't want.

[vlovich123]

Sure, you can query the database all you want. The important property is that the server cannot observe the client querying the database - processing a query occurs in an encrypted space that it does not have the keys to. Similarly, one would expect that each query, even if it's for the same phone number, would be observed to be reading randomly from the database each time.