Privacy Preserving Contact Tracer

[david415]

this paper describes a cryptographic protocol designed to be used with a mixnet such that it allows the spread of infection to be traced in a privacy preserving manner:

https://github.com/JonathanLogan/covidtracer/blob/master/pp-contact-tracer.pdf

[willscott]

this hasn't gone through peer review, which the bibliography generally tries to wait for

[david415]

ok

[burdges]

Any thoughts on mixnet vs PIR for this application? I suppose mixnets might give cheaper mailbox queries?

Could your mobile device just hand out SURBs using mixnode keys that lives for at least two weeks?

[burdges]

I described a mixnet solution with a 32 byte SURB at TracingWithPrivacy/paper#10 but it leaks infected users activities, like all current "privacy preserving" designs.

You could fix the SURB scheme with some narrow mailbox server design, while you can only fix the non-mixnet schemes like DP-3T, etc. with TEEs, but iOS lacks any TEE. It resembles some voting mixnet more than Sphinx though: no MACs, no block ciphers, only stream ciphers or ElGamal. It might employ either universal reencryption or a server side TEE to protect infected user's privacy, but uninfected users privacy depends only upon the mixnet.

I think PIR could protect infected user's privacy, but IT-PIR leaks all users' activities against powerful enough adversaries, well like the mixnet. It's possible relatively inexpensive variants for C-PIR might exist based on homomorphic hashing with lattices, not sure. Any thoughts @willscott ?

[david415]

@burgdes I can give you @willscott contact information if you need to discuss something with him as he doesn't seem to be responding to your comments here. also this particular issue tracker is supposed to be for the mix bibliography and not for design discussions.

[willscott]

It seems that what you really want is a zero-knowledge rendezvous system of some sort.

Re: C-PIR vs IT-PIR balance - I continue to suspect that it is more difficult for an adversary to subvert multiple disjoint entities who have set up an IT-PIR system / mixnet, than to gain sufficient computational advantage to subvert a C-PIR scheme.

[burdges]

Oh wow? I wouldn't have suspected that, unless you mean C-PIR remains outright intractable for acceptable security parameters. I noticed a flurry of C-PIR papers, but did not read them.