[femto113]

Bloom filters could work that direction as well: phone produces a filter of observed keys and uploads it to the service, service checks all positive keys to see if they're in the filter. I think the main point of doing the checking on the phone is that way you're the only one who knows if you've been exposed.