ivargr / privvg-challenge Goto Github PK

Conglatulations @ivargr and @knutdrand! You've solved the Human Chromosome 6 Privacy Challenge!

For completeness, here is my answer key:

0 is based on the full data
name=HG01978 i=1
name=HG01891 i=2
name=HG02109 i=3
name=HG02572 i=4
name=HG03540 i=5

You also used your method to detect an error in my script (that resulted in all 6 sequence sets having no samples removed) that I used to post the first versions of these datasets! I've corrected this in the blog post and will cross-reference it in a followup post.

The challenge was designed to be as simple (and possibly solvable) as possible. You're starting from a unique position---you have the full truth set of all genomes out of which the sets are generated. This provides a very broad attack surface. That said, it still should not be possible to reliably solve this challenge if odgi priv is providing the appropriate guarantees.

The goal of this challenge was to engage an independent security review, and you've completed that brilliantly. We can test against your exploit to improve the existing implementation and develop new models. This will be invaluable in driving the development of practical, correct differential privacy models for pangenomes. I'll be in touch about the offered bounty!

notes on the attack and potential resolution

I am hopeful that the security flaw that allowed you to recover the missing individuals is in the implementation, and not the conceptual model driving it. I have a hint as to what it might be. Your analysis suggests that a different parameterization of odgi priv might have generated a set for which your method wasn't 100% reliable, at least for small numbers of variants.

The specific curve of recovery accuracy versus epsilon is unexpected. It decreases as epsilon decreases from 10->0.1. But, as we get below 10^-1, it then begins to increase rapidly. You suggest that this may be due to the higher epsilon sampling more-frequent paths. This is not what should be happening. Instead, the utility should be weighted more heavily at low epsilon, leading to this behavior. Something is definitely not working as expected!

During the development of odgi priv, I caught and fixed an issue related to numerical singularities in the weighting that drives the haplotype sampling. My resolution was probably incomplete, in that it only shifted by a few orders of magnitude the threshold at which the singularities occur. These singularities would break the privacy guarantees. I'm first going to review this possibility.

If I find a potential solution, would you be willing to take another independent look at the results?