Design 2 - caveats and benefits - metadata

With regard to: "There is a false-positive rate associated with cuckoo filters. This means that there is a chance (albeit a small one) that a user might get a notification that he is at risk even though he didn't encounter an infectious person." - I'd add that for population sizes (e.g. DE, NL or the US) the number is, in a naive implementation already 'ridiculously' small; i.e. 6 to 10 orders of magnitude smaller than general medical process error rates; while still preserving the < 20% of data volume win. If the health authorities would tune the filter daily (which is realistic; as it is a one-off effort) then you'd be hit around 15% if you assume a country > 10 Million and less 10 Billion inhabitants and COVID infection rates.

Secondly - and also with regard to "Only a single-bit of information can be transferred (whether the ID is reported or not)" -- it is quite common (or if you would want < 5% volume wins) to fetch; on a (potential false) positive - a partial (e.g. 1/1024th part) full fetch; which can include an arbitrary amount of metadata.

In that case; the cost/win relative to PACT and TCN is 100 - 5% + 1/1024th =~ 95% less bandwidth than the TCN case; while revealing around 10 to 30 bits of the full hash in the CF table and (in this example) 10 bits of the 256 bits (so less than the 30-50 in the CF) in the full set.

Or alternatively -if you want to reduce the subsequent fetches and have no issue with false positives; around 20% of the volume (80% saved) and 30-50 bits revealed.