ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo
E?cient(Secure(Outsourcing(of(
Genome3wide(Associa8on(Studies
1"Dept."of"Computer"Science,"Univ."of"Tsukuba"
"
2"Life"Science"Research"Center,"Mie"Univ.""
"
3"JST"CREST
Wenjie"Lu1,""Yoshiji"Yamada2,""Jun"Sakuma1,3"
MoFvaFons
?? GWAS"
To"?nd"geneFc"variaFons"associated"with"a"
parFcular"disease."
?? Outsourcing"
To"use"the"cloud"resources"to"conduct"largeNscale"
GWAS"computaFons.""
?? Personal"privacy"
""""GeneFc/clinical"data"is"very"sensiFve."
Outsourcing"GWAS
Limited(
Resource(
Unlimited(
Resource(
x
f(x)
The"evils"in"the"detail"
Limited(
Resource(
Unlimited(
Resource(
x
f(x)
x
f(x)
ProtecFon"from"Cryptosysmtem"
Limited(
Resource(
Unlimited(
Resource(
???
x
f(x)
ProtecFon"from"Cryptosysmtem"
Limited(
Resource(
Unlimited(
Resource(
???
Can(the(cloud(
s8ll(compute(
these(for(us?
Fully"Homomorphic"EncrypFon(FHE)
?? MathemaFc"operaFons"can"be"carried"out"on"
encrypted"values"without'disclosing"these"values
a b a+b
a "b? axb
Gentry"Craig,"¡°A"fully"homomorphic"encrypFon"scheme¡±,"""
Doctoral"dissertaFon,"Stanford"University,"2009
Ring"Learning"With"Error(RLWE)
?? Fully"homomorphic"encrypFon"
?? A'plaintext'is'a'polynomial'
P.S.:"An"integer"in""""""can"be"seen"as"a"degreeN0"
polynomial
Brakerski"Zvika"et"al.,"¡°Leveled"fully"homomorphic"encrypFon"without"
bootstrapping¡±,"Proceedings"of"the"3rd"InnovaFons"in"TheoreFcal"Computer"
Science"Conference,"ACM,"2012."
Outsourcing"StaFsFcal"Test
For"a"single'nucleo5de'polymorphisms(SNP)"and"
a"disease,"e.g."diabetes."
?? Genotype:""""[AA,""""aa,""""""""""Aa,""""AA,"""¡­¡­]"
?? Phenotype:""[case,"control,"case,"case,"¡­¡­]
N(people
"""""Case:"with"diabetes"
Control:"without"diabetes
Outsourcing"StaFsFcal"Test
Genotype A a Count
Case
Control
Count
Observa8on
A a
Expecta8on
?? Genotype:""""[AA,""""aa,""""""""""Aa,""""AA,"""¡­¡­]"
?? Phenotype:""[case,"control,"case,"case,"¡­¡­]
N(people
Outsourcing"StaFsFcal"Test
Genotype A a Count
Case
Control
Count
Observa8on
A a
Expecta8on
?? Genotype:""""[AA,""""aa,""""""""""Aa,""""AA,"""¡­¡­]"
?? Phenotype:""[case,"control,"case,"case,"¡­¡­]
N(people
Our"Encoding"for"SNP"data
?? Genotype:""""[AA,""""aa,""""""""""Aa,""""AA,"""¡­¡­]"
?? Phenotype:""[case,"control,"case,"case,"¡­..]
[2,(0,(1,(2,(¡­]
[1,(0,(1,(1,(¡­]
Compute"the"conFngency"table
Genotype A a Count
Case
Control
Count
Compute"the"conFngency"table
Genotype A a Count
Case
Control
Count
Compute"the"conFngency"table
Genotype A a Count
Case
Control
Count
	
How(to(e?ciently(
compute(the(
scalar(product(on(
encrypted(data(??(
Scalar"product:"A"na?ve"way
	
1 4?
2 5?
3 6?
Scalar"product:"more"e?cient"way
Yasuda"Masaya,"et"al.""Secure"paeern"matching"using"somewhat"homomorphic"encrypFon.""
Proceedings"of"the"2013"ACM"workshop"on"Cloud"compuFng"security"workshop."ACM,"2013. 	
?
Only"need"ONE"mulFplicaFon"!"
Scalability
?? Plaintext"space:"
?? """""""">="N"?"To"parFFon"into"smaller"parts
	
For"example:"N"="8192,""to"conduct""""""""""""="10000;"
k"="2
The"whole"image
???
AA
case
control
Aa
	
x y
Comparison"Method
?? Genotype:""""[AA,""""aa,""""Aa,""""AA,"""¡­¡­"]"
?? Phenotype:""[case,"control,"case,"case,"¡­..]
AA"!"[1],"[0],"[0]"
Aa"!"[0],"[1],"[0]"
aa"!"[0],"[0],"[1]"
case"!"[1],"[0]"
control"!"[0],"[1]"
Genotype"
Encoding
Phenotype"
Encoding
KrisFn"Lauter"and"Adriana"LopezNAlt"and"Michael"Naehrig""¡°Private"computaFon"on"
encrypted"genomic"data¡±"14th"Privacy"Enhancing"Technologies"Symposium,"Workshop"
on"Genome"Privacy."2014
Experiment"Sepngs
?? EncrypFon"ImplementaFon:"HElib"
?? The"maximum"degree"of"the"polynomial:"N"="8192"
?? Security"parameter:">"80bits"
?? CPU"2.3GHz;"RAM"16G""
[heps://github.com/shaih/Helib]
Experimental"Result:"CommunicaFon"Size
Comparison(Encoding:(
5000(Records(=>(25000(ciphers(
Proposal(Encoding:(
5000(Records(=>(only(2(ciphers279
2792
13960
5.6 5.6 5.6
11.2
100
10000
100 1000 10000
SampleSize
CommunicationSize(MB)
Method
Lauter+
Prop.
5000
Number(of(Records
"
"
"
"
"
"
"
"
Commu.(
Size((MB)
Par88on(into(k(=(2(
Experimental"Result:"ComputaFon"Time
15
148
774
0.61 0.65 0.68
1.14
10
1000
100 1000 10000
SampleSize
ComputationTime(s)
Method
Lauter+
Prop.
5000
Number(of(Records
"
"
"
"
"
"
"
"
Comp.(
Time((s)
Was"25"+"3"minutes""
+"0.34s"in"Magma"
"[LAN14]
Par88on(into(k(=(2(
Conclusion
1.? With"suitable"data"arrangement,"
e?cient"computaFon"is"achievable."
2.? Our"method"helps"space/Fme"
complexity.
Thank"you!

More Related Content

Genopri2015