Make a conceptual map of the Cambrian Explosion of contact tracing systems.

[hdevalence]

Now that there's a semi-stable 0.4 protocol for apps to use while they iterate, I think it's worth trying to focus on what an 0.5 protocol would look like (#56), and I think a good first step to doing that would be doing a survey of the Cambrian explosion of contact tracing protocols and trying to map out the high-level building blocks of each proposal. Having mapped out all of the building blocks, we could try to understand each proposal as combining those building blocks in different ways, and try to synthesize a protocol that combines the best ideas from all of the existing protocols.

For instance, one basic building block could be broadcasting pseudorandom identifiers. Another could be the idea of deriving multiple pseudorandom identifiers from some secret, as is done in TCN 0.4 and the AG protocol. These use different mechanisms, but they have the same goal. Can we write this goal explicitly, and compare the mechanisms for each part? What are the benefits and costs? Another idea is the way that TCN has clients prove in zero knowledge that they generated the identifiers they report. Can we express this goal independently of the mechanism and describe its benefits to compare against its costs? Or, the latest DP3T proposal uses Bloom filters, and there are other ideas in the PACT-E and PACT-W proposals, etc.

After having mapped out these conceptual building blocks independently of the specific mechanisms, we can then express each proposal in terms of composition of a common set of blocks (though the mechanism for each of these blocks may be different for each proposal). And we can then try to create a hybrid of the proposals, first selecting one or more combinations of blocks, and then selecting the best mechanism for each one.

[hdevalence]

The first step to doing this would be to create a building_blocks.md with rough notes towards this goal. We can refine the notes later.

[degregat]

#70 has a rought first draft

[Vanuan]

I'd structure it this way:

• BLE protocol (Service UUID, Characteristic UUID, key format)
• Backend API (OpenAPI specification)
• Cryptography (key derivation / contact tracing algorithms)
• Android/iOS API (encapsulates contacts database)

But to effectively compare them, we need a common glossary. At least a correspondence table between different terminologies.

After that, there is additional differentiation:

• risk factor algorithms
• authentication of infected status
• interoperability (server-to-server, app-to-app, app-to-server, server-to-app)

[degregat]

@Vanuan good idea! I started a glossary in #74

[Vanuan]

I've created a similar issue in DP3T: DP-3T/documents#227

[dirkx]

I am trying to compare the designs on where they are different (skipping over the similarities).

Some first thoughts here - before I summarize and add to that ticket #61

Stuffing/Smearing

• DP3T Design 1 & 2
  -- Seed is the 'proof'; after disclosure it therefore needs to be re-created.
• TCN
  -- A specific verification key is available. ratchet prevents.
• PACT
  -- it is the plain hash - so nothing here really. you have to trust the operational setting.
• CAGT
  -- relies on API on the mobile - so on trust in the mobile phone OS security and operational/deployment settings apple/google. Which are arguably axiomatically trusted anyway.

Collusion prevention (Higher N / day cycle - e.g to 60-15 mins range)

• TCN, DP3T design 1
  -- no real impact - though with TCN the cost at the client increases a lot more for a high N.
• DP3T Design 2
  --increases size of CF filter* (but as in normal use - we are at 10-20% of design 1 and < 5% for TCN we have room!). Only options that has protection on the back (assuming no metadata)
• PACT
  -- it is the plain hash - so nothing here really. you have to trust the operational setting. Sizes goes up linearly
• GACT
  -- as above. Size goes up linearly too. Unless the API starts to expose the seed.

Additional (match/clinical) metadata (skipping over de-anonymisation risks)

• TCN
  -- inherent in the protocol
• DP3T - Design 1
  -- can be added to the protocol with same cost/technique as TCN; same for 'sig'. Or it could be a 2-step process (see **) if you are wedded to the much lower bandwidth
• DP3T - Design 2
  -- in worst case*, if added, kills efficiency and cloaking/PSI-like effect and makes it Design 1. At app still-useful infection rates - still a win.
• PACT
  -- very easy - and up to *** N times as costly as for TCN/DP3T as all keys need to be shared.
  -GACT
  -- very easy - and up to *** N times as costly as for TCN as all keys need to be shared.

Notes:
*: complexity here/what helps is that the viability of the app assumes a relatively small number of infected 'hits' per `mobile'. Because once infected a person is 'out of the pool that needs to be told they are infected for M days'. So it is fair to assume (fractions of %) of the population are told each day that they are infected.
**: Given *, it is fair, say for the metadata to do a CF check (or a design 1 check) and, for the 1% of the phones it matches, fetch the 'extra info' file for that hit - or, to make cross correlation harder, fetch all extra-metadata that have the same first 8 bits of a hash of the match. (edited)
***: depending if one is willing to reveal if N keys are all correlated to the same person (completely reveal or hash level reveal some 10+ bits of that).

API - can we make an API (for app developers and mock) that lets people implement clients/mobile apps while not having to pick a protocol yet.

Issues 1) metadata, 2) geo-region extra data.

[Vanuan]

Collusion

or collision?

[Vanuan]

-- Seed is the 'proof'; after disclosure it therefore needs to be re-created.

Maybe clients should ignore any ephemeral ids encountered after a secret key was published? Since anybody can fake them after disclosure.

[dirkx]

Yes. very good point. That is not explicitly in any of the papers. it should be. as it is easy to miss. Raised DP-3T/documents#228.

[dirkx]

yes - it works both ways. the client should recycle - and clients should ignore during hte 14 days that they may learn of that seed post infection moment.

[degregat]

Additional discussion about a glossary in #74