Jerome Marot
Well-known member
Apple and google are jointly developing a contact tracing app that would tell people if they were near a infected people in the past 2 weeks. The underlying mathematics are interesting.
How do the apps work?
A naive approach would be to store the position of the whole population all the time and compute the distances. But that would be prohibitively expensive in terms of computing power and a privacy nightmare, so we don’t do that. Instead the phone uses close radio communication (bluetooth) and pings regularly to find other phones in close distance.
There are various problems with that approach. Bluetooth security model was not designed for that kind of use and is not very good anyway, so that is another security risk for your phone. There is also the problem that radio waves do not travel like viruses and ping behind walls, so if you jog in a city you may have pings with all the people living along the way while they were at home and you simply jogging along and you never actually met.
But let's assume that Bluetooth doesn't work well through walls and my phone has data on what devices have been within a 2m radius in the last two weeks. How do we do that?
We could use a fix device ID, and each phone would have pairs of IDs each linked to a given person. That would be a major privacy issue, as the list would be a wonderful way to track everyone.
So, for privacy reasons we don't store the real ID of the device, but your phone generates a new “random” token regularly. The token would be such that your device can recognise it, but nobody else can assign it to your device. If you now find out that you have caught Covid-19, you go to a server with the list of tokens from the last two weeks and upload them there.
This is another major privacy issue. The server sees your IP and that you're infected. That's not good. But let's say we could somehow, maybe through Tor, make it anonymous. How does the server tell the people you went close to them and they have a problem? It's not like you can just link people to the tokens. The token were designed to avoid that.
So you'd have to make all the devices periodically check the server for a list of tokens, and then see if they have a contact to one of the affected token. That would mean very fast and very large downloads. So you'd rather make a system where the tokens are not directly assignable, but where you upload a value when you query it, which the server can use to identify the tokens that affect me. This value could be set daily or hourly on the phone, for example, to make the assignment more difficult. But if we do that, the server can see who is infected.
A crypto solution has been considered. You do this by generating the tokens with a pseudo-random number generator. They work by feeding the generator a random value and the rest of the spit out values look random and are practically unpredictable unless you know the initial value. You could take advantage of this by publishing the seed in case of infection, and the tokens will stay on the end devices. Then my phone could fetch the list of seeds from the server and see if it can generate any of the stored tokens. Disadvantage: This would be a very battery unfriendly operation for your phone. And since the amount of data is is so high (every device in the country once a day) this is still a lot of traffic.
As you see, the design of such an app is not easy, as we have large amounts of data and limited bandwidth and processing power. The point of this post was to give you a sense of what some of the dimensions of the problem are.
These are the official documents from Apple and Google:
How do the apps work?
A naive approach would be to store the position of the whole population all the time and compute the distances. But that would be prohibitively expensive in terms of computing power and a privacy nightmare, so we don’t do that. Instead the phone uses close radio communication (bluetooth) and pings regularly to find other phones in close distance.
There are various problems with that approach. Bluetooth security model was not designed for that kind of use and is not very good anyway, so that is another security risk for your phone. There is also the problem that radio waves do not travel like viruses and ping behind walls, so if you jog in a city you may have pings with all the people living along the way while they were at home and you simply jogging along and you never actually met.
But let's assume that Bluetooth doesn't work well through walls and my phone has data on what devices have been within a 2m radius in the last two weeks. How do we do that?
We could use a fix device ID, and each phone would have pairs of IDs each linked to a given person. That would be a major privacy issue, as the list would be a wonderful way to track everyone.
So, for privacy reasons we don't store the real ID of the device, but your phone generates a new “random” token regularly. The token would be such that your device can recognise it, but nobody else can assign it to your device. If you now find out that you have caught Covid-19, you go to a server with the list of tokens from the last two weeks and upload them there.
This is another major privacy issue. The server sees your IP and that you're infected. That's not good. But let's say we could somehow, maybe through Tor, make it anonymous. How does the server tell the people you went close to them and they have a problem? It's not like you can just link people to the tokens. The token were designed to avoid that.
So you'd have to make all the devices periodically check the server for a list of tokens, and then see if they have a contact to one of the affected token. That would mean very fast and very large downloads. So you'd rather make a system where the tokens are not directly assignable, but where you upload a value when you query it, which the server can use to identify the tokens that affect me. This value could be set daily or hourly on the phone, for example, to make the assignment more difficult. But if we do that, the server can see who is infected.
A crypto solution has been considered. You do this by generating the tokens with a pseudo-random number generator. They work by feeding the generator a random value and the rest of the spit out values look random and are practically unpredictable unless you know the initial value. You could take advantage of this by publishing the seed in case of infection, and the tokens will stay on the end devices. Then my phone could fetch the list of seeds from the server and see if it can generate any of the stored tokens. Disadvantage: This would be a very battery unfriendly operation for your phone. And since the amount of data is is so high (every device in the country once a day) this is still a lot of traffic.
As you see, the design of such an app is not easy, as we have large amounts of data and limited bandwidth and processing power. The point of this post was to give you a sense of what some of the dimensions of the problem are.
These are the official documents from Apple and Google:
