[byteshift]

My understanding is that this is even feasible without location information if you use an approximate filter (e.g., a Cuckoo Filter [1]), which they propose in DP-3T (II).

With 20 bits/key such filters yield a false positive rate (FPR) of 0.001%. Meaning for 100,000 new cases per day worldwide, you would only need to download 0.24 MiB.

Note that the FPR applies to each lookup. That is, if you have collected say 100 tokens on a given day, the overall probability of a false positive will be 0.01% (assuming independence). With each extra bit per key you can roughly halve that probability. So in practice size won't be an issue.

[1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf