HEGP CHALLENGE

Homomorphic Encryption of Genotypes and Phenotypes (HEGP)
Edit text!

1 HEGP challenge

2020-11-01 The authors announce the HEGP (heegeepee; hiːdʒiːpiː) Challenge, with a $1,000 (one thousand dollar) prize for the individual or group who can crack HEGP encrypted data.

See this page for a general introduction and relevance of HEGP

2 Details

The authors offer a reward of $1000 (one thousand US dollar) for cracking the HEGP homomorphic encryption method for genotypes and phenotypes as described in this open access paper.

The challenge consists of decryption of two genotype data sets.

In both data sets, plain text genotypes are represented numerically as matrices of allele dosages, with rows representing individuals and columns representing SNP sites or genotype markers (see below toy example). Each plain text genotype dosage takes the integer values 0,1,2. After encryption these dosages are transformed into floating point cyphertexts that are approximately normally distributed. The challenge is to recover the unencrypted original values from the cyphertext.

In HEGP, the ciphertext has been generated by matrix multiplication of the plaintext genotype matrix by a random orthogonal matrix (the key generated using Linux /dev/random and rustiefel) which is unknown to you. The task therefore is to find the inverse of this matrix, which because it is orthogonal, will be the transpose of original key.

For the first challenge1 we encrypted a data set consisting of 500 individuals by 12,359 SNP genotypes which exists in the public domain. We consider this data cracked if 50 individuals (10%) are identified correctly. Note that this data might be from human, mouse, rat, nematode or plants. Note also that these genotypes are a subset of a public dataset, and that any missing genotypes in the public data have been imputed before encryption.

The second challenge2 may be harder. We encrypted a mammalian data set that is not in the public domain (yet), consisting of 1,586 individuals and 12,561 SNPs. We consider the code cracked if you can compute the plaintext genotypes of this matrix correctly with mean error of under 10%.

The ciphertext files for challenge1 and challenge2 can be downloaded from http://ipfs.genenetwork.org/ipfs/QmWb3RupNtA9rvjD83jtB75AA3SjT8opx2M7T3CP8x5pqs

The MD5 checksums of the ciphertext files are found in md5sum.txt. The full list, also for the original (secret for now) plaintext and keys is

5605626a9403ebdf96041d2dd766a516  challenge1.ciphertext.RData
148ce09c6dfc878af09874c090a7bd64  challenge1.ciphertext.txt
abbc5ce33025e723805cb14a332f6c9d  challenge1.maf.txt
29f348fd4d9fbd453f658def53dbb87a  challenge1.key.RData
b03e91f69d8124658e30562e1fa3b64c  challenge1.key.txt
dcf724ff4798f4ec6674d029f220385f  challenge1.plaintext.RData
e26367b991dfcedeaee139ffcc9a38a7  challenge1.plaintext.txt
d2db18e96a3a8173b12383aa8d606583  challenge1.sample.ids.txt

6d5d10279424a7c952ed8f9b0b086e84  challenge2.ciphertext.RData
c3706ecf12275859e3a040b23af1c9f9  challenge2.ciphertext.txt
15fa26a4d03e18f05643e917b8480216  challenge2.maf.txt
9615196bf89fb19105686a018e4c40c0  challenge2.key.RData
ecf00d15e233b6dda73e40ebdc3358d2  challenge2.key.txt
a007e8f5f085798a88180386ffbfa58f  challenge2.plaintext.RData
2b1870215dd67cfe1b19c423979ab3c7  challenge2.plaintext.txt

With this challenge we want to address the concern that individuals might be identified based on information in the public domain and/or by finding patterns in the encrypted data.

We will release the plaintext file and the key file when the challenge is cracked or after six months (which is May 1st 2021). In case the prize is unclaimed we'll create a new dataset for a fresh challenge.

The ciphertext Datasets are provided as RData objects which can be manipulated using the hegp R package. Briefly, a dataset D is a list, comprising of minimally a phenotype vector D$y, and a genotype dosage matrix D$geno (rows are individuals, columns are SNPs). There are additional components that are useful for GWAS but not relevant for the decryption challenge. Full details are in the documentation of the R package. The challenge datasets have fake phenotype data that can be ignored.

To unpack the RData original datasets and write the genotypes and allele frequencies to tab-delimited text files from R, convert with

library(readr)
load("challenge2.ciphertext.RData")
write.csv( De$geno, "challenge1.ciphertext.txt", quote=F)

To run a GWA use the mixed-model-gwas and hegp-R packages you can run in R

library(hegp)
load("challenge2.ciphertext.RData")
ge.mm=basic.mm.gwas(De,mc.cores=1)
  Built kinship dim 1586 1586
  estimated heritability 4.355436e-05
ls(ge.mm)
  [1] "bp"   "chr"  "logP"
ge.mm$logP[0:6]
  [1] 0.22838514 0.74881022 0.13431556 0.00929719 1.13027222 0.13211178

and draw a plot with

library(ggplot2)
ggplot(ge.mm) + geom_point(aes(bp, logP), colour="#000099")

To validate we ran the encrypted version (De) and then plaintext version (D) to compare outcomes with

library(hegp)
load("challenge2.ciphertext.RData")
load("challenge2.plaintext.RData")
ls()
  [1] "D"  "De"
ls(D)
  [1] "cov"  "geno" "maf"  "map"  "y"
ls(De)
  [1] "cov"  "geno" "map"  "y"
g=basic.gwas(D)
ge=basic.gwas(De)
mean(abs(g$logP-ge$logP))
  0.02951522
ge.mm=basic.mm.gwas(De,mc.cores=1)
  Built kinship dim 1586 1586
  estimated heritability 4.355436e-05
g.mm=basic.mm.gwas(D,mc.cores=1)
  Built kinship dim 1586 1586
  estimated heritability 4.356434e-05
mean(abs(g.mm$logP-ge.mm$logP))
   [1] 0.02943622

Documentation for the R encryption and GWA functions can be found here.

3 Reference code

The reference code for HEGP is published under GPLv3 licensed R code and Julia code. An example of running a GWA as presented in the paper can be found here. The algorithm with a description of brute force attack is described in the results section.

4 Submissions

Submissions should be posted in a permanent public git account (GitHub, gitlab or similar) and reward will be given in USD. The solution should be reproducible and announced on the website issue tracker. In case you don't want to use the issue tracker it is also possible to E-mail the authors to indicate where the solution is hosted. One such E-mail address is pjotr.public542 at thebird dot nl.

Important note: only real solutions will be considered that can reliably crack the key of any such dataset. If the original key somehow gets ripped from one of our laptops, for example, it does not count. Security stands or falls with how data is handled and how a key is generated. Even so, this challenge is about algorithmically cracking the code for the general case.

5 Feedback

Feedback on the challenge, this website etc., can be posted to the issue tracker.

6 General introduction

The homomorphic encryption method consists of an orthogonal transformation by multiplication by the orthogonal matrix P with a matrix containing the data y and G.

From the original paper: privacy in relation to quantitative genetic analysis. (A) A numeric phenotype vector y (left) and genotype dosage matrix G (right) are represented as colours and shades of gray. Each row of the matrix represents one individual and each column one SNP. Genotypes are encoded as imputed dosages clustered at the values Embedded Image giving the numbers of alternate alleles. (B) The same data after multiplication by an orthogonal matrix P (a rotation represented by the curved orange arrow). The genotype dosages are now represented by a continuum of real numbers. (C) The distribution of dosages for a particular SNP (column of G), clustered around 0,1,2. (D) The distribution of the same dosages after orthogonal transformation by multiplication by the orthogonal matrix P (black histogram) with the normal distribution with same mean and variance superimposed in red. (F) The normal QQ plot for the data in D, showing the transformed dosages are very close to a normal distribution. (E) A cartoon of the HEGP scheme. The top black arrow and equation show the linear mixed model relating the phenotype y to genotype G with regression coefficients β representing the allelic effects. The variance matrix for the residuals is V. After multiplication by orthogonal matrix P, plaintext data y, G and the mixed linear model are transformed as shown in orange. The likelihood and regression estimates β are preserved. HEGP, homomorphic encryption for genotypes and phenotypes; QQ, quantile–quantile.

7 Toy Example

The task is best described with an small example, a SNP dosage matrix G with 10 subjects (rows) and 8 SNPs (columns):

sub1     0    1    2    1    1    1    1    2
sub2     0    1    2    1    2    2    2    2
sub3     1    1    2    1    2    2    2    1
sub4     2    1    2    2    1    2    1    1
sub5     2    2    2    0    1    1    2    1
sub6     2    2    2    1    1    2    2    2
sub7     1    2    1    1    1    1    2    2
sub8     0    1    2    1    2    1    2    2
sub9     1    1    2    2    1    1    1    2
sub10    1    2    2    1    2    2    2    1

The first step standardises each column to have mean 0 and variance 1. This does not encrypt the data but it makes the encryption easier to process. The resulting plaintext dosage matrix H is

sub1  -1.224745e+00 -0.7745967  0.3162278 -0.1761661 -0.7745967 -0.9486833 -1.449138  0.7745967
sub2  -1.224745e+00 -0.7745967  0.3162278 -0.1761661  1.1618950  0.9486833  0.621059  0.7745967
sub3  -5.749536e-10 -0.7745967  0.3162278 -0.1761661  1.1618950  0.9486833  0.621059 -1.1618950
sub4   1.224745e+00 -0.7745967  0.3162278  1.5854946 -0.7745967  0.9486833 -1.449138 -1.1618950
sub5   1.224745e+00  1.1618950  0.3162278 -1.9378267 -0.7745967 -0.9486833  0.621059 -1.1618950
sub6   1.224745e+00  1.1618950  0.3162278 -0.1761661 -0.7745967  0.9486833  0.621059  0.7745967
sub7  -1.761818e-09  1.1618950 -2.8460499 -0.1761661 -0.7745967 -0.9486833  0.621059  0.7745967
sub8  -1.224745e+00 -0.7745967  0.3162278 -0.1761661  1.1618950 -0.9486833  0.621059  0.7745967
sub9   5.584054e-10 -0.7745967  0.3162278  1.5854946 -0.7745967 -0.9486833 -1.449138  0.7745967
sub10 -7.763129e-10  1.1618950  0.3162278 -0.1761661  1.1618950  0.9486833  0.621059 -1.1618950

Next, we sample a random orthogonal 10x10 matrix P (the key)

 [1,] -0.02512827 -0.4797328  0.07364427  0.29302653 -0.52531836 -0.06077012 -0.035656119 -0.21264789 -0.03656364  0.59199429
 [2,]  0.49690414 -0.2130092 -0.18437213 -0.08094409 -0.33989098  0.11458794  0.382316649  0.51918534 -0.29625914 -0.18714471
 [3,]  0.23650365  0.2027581  0.09184543  0.01711933  0.45947279 -0.11898452  0.549979207  0.04901441  0.03087585  0.60259531
 [4,] -0.12668661  0.2640016 -0.24657807 -0.31047136 -0.08100156  0.01898761 -0.009330209 -0.34743514 -0.77909552  0.14950124
 [5,]  0.55558644 -0.1256327 -0.11075554 -0.35350803  0.12981113  0.51028646 -0.332763562 -0.28269321  0.20446208  0.16914618
 [6,] -0.20079972 -0.1310010  0.33769938 -0.45070382  0.09236098 -0.05672098 -0.390626201  0.58184807 -0.14355153  0.31914343
 [7,]  0.30606137  0.1956211  0.67114299 -0.30536330 -0.32325985 -0.31468499  0.106176504 -0.27993855  0.04238805 -0.17152201
 [8,] -0.31057809 -0.5813563  0.28456863 -0.21173902  0.26275032  0.30931163  0.411201611 -0.21696952 -0.12053771 -0.21059453
 [9,]  0.07808339 -0.3843085 -0.42321573 -0.37251969  0.13692025 -0.68291915 -0.007551188 -0.12694060  0.15450958 -0.05619238
[10,] -0.36775701  0.2383173 -0.23348592 -0.45381168 -0.41614295  0.20969099  0.325976664  0.04578156  0.44759290  0.14716487

Then we encrypt the dosages F = PH to make the ciphertext

sub1   0.5198393  0.26551339 -0.01916052  1.4507213  0.2713387  1.18915219 -0.7379842 -1.16229696
sub2  -1.3586430 -0.22207809 -1.14214913 -0.1029684 -0.2902612 -1.24575229 -0.1165288  1.69811232
sub3  -0.1600357  1.24824503 -1.06841109 -1.0985638  0.1892755 -0.50328813  0.7284091 -0.62463676
sub4  -0.1988559  1.28854213 -0.43475181 -1.5181190  0.7876347  1.15643550  1.6061022 -0.19111906
sub5   0.1706426  0.64079385  1.16737846 -0.5553653 -0.9595529 -0.17537980 -0.6155911  0.60202029
sub6  -0.8145915 -0.03660399  1.22187582 -1.2021241  2.1778375  0.07512188  1.6196177 -0.61084795
sub7  -1.4268916 -1.30507703 -0.35896396  0.1191278  0.8610707  0.21228333 -0.1347692  0.19297276
sub8   1.7994281  1.79366813 -1.42174710 -0.9805980 -1.1053001 -0.41331874  1.0923847 -0.53943417
sub9  -0.5944334  0.12376342 -0.50869100 -0.3285796 -0.6138749 -2.04363166 -0.7562708  0.08008153
sub10 -0.7061947  0.56034104 -1.04875037  0.7321312  0.4268941 -0.12102879  0.7390060  1.80792099

This form of encryption is homomorphic with respect to many quantitative genetics analyses, particularly the mixed model GWAS.

To decrypt the ciphertext it is necessary to multiply it by the inverse of the key P, which is equal to the transpose of P because it is orthogonal.

The challenge is, in the absence of knowing either P or H, to find an orthogonal matrix Q such that QF "looks like" a genotype dosage matrix. That is, the distribution of the plaintext for a given SNP will be trimodal (or bimodal is the rarer homozygote genotype is absent from the sample) with expected modes specified by the Hardy-Weinberg equilibrium distribution. We provide the allele frequencies of the plaintext, which will help in defining these expected modes (see the maf.txt files on IPFS). It is reasonable to provide this information even though it might make the encryption less secure because users of the ciphertext would need this information for some genetic analyses.

We provide the toy dataset and its encryption key as R objects in the file "toy.hegp.RData" from Toy-HEGP so that you can reproduce these analyses. E.g.

# Load a table
toy = read.table("toy2.txt",header=F,row.names=1)

library(hegp)
load("toy.hegp.RData") # loads encryption key
plaintext.toy$geno = as.matrix(toy)
c = encrypt.D(plaintext.toy, key.toy)
d = encrypt.D(c, key.toy, invert=TRUE)
mean(abs(c$geno-d$geno))
[1] 2.524352e-09

8 References