DEIM Forum 2013 P2-5σʔλΞ΢τιʔγϯάʹ͓͚ΔϓϥΠόγʔอ‫ ޢ‬SNP ‫ࡧݕ‬γεςϜͷ࣮૷ྮ‫؛‬࿨৓†ਗ਼ਫሡ‫††ޗ‬ᒟᇞେ†††ඌ࡚‫ܟ‬ೋ†† ࠃࡍ‫ج‬ಜ‫ڭ‬େֶ‫ڭ‬ཆֶ෦ ˟ 181–8585 ౦‫ࡾ౎ژ‬ୋࢢେ୔ 3–10–2†† ֶशӃঁࢠେֶࠃࡍจԽަྲֶྀ෦ ˟ 162–8650 ౦‫ ࢁށ۠॓৽౎ژ‬3–20–1††† ౦‫ژ‬ཧՊେֶༀֶ෦ ˟ 278–8510 ઍ༿‫ݝ‬໺ాࢢࢁ࡚ 2641
E-mail: †c131257e@yamata.icu.ac.jp, ††shogo.shimizu@gakushuin.ac.jp, †††yekwon@rs.noda.tus.ac.jp,††††keiji@icu.ac.jp͋Β·͠ҰԘ‫ج‬ଟ‫ܕ‬ʢSNPʣͱ͸ɼඪ४తͳԘ‫ج‬഑ྻͱҰԘ‫͕ج‬ҟͳΔ͜ͱͰ͋Γɼ֤‫ݸ‬ਓࠩͷ‫ݪ‬Ҽͱ΋‫ݴ‬ΘΕ͍ͯΔ͜ͱ͔Β‫ݸ‬ਓ޲͚ҩྍ΁ͷԠ༻͕‫ظ‬଴͞Ε͍ͯΔɽҰํɼίετ࡟‫ݮ‬ͷͨΊɼσʔλϕʔεͷӡ༻؅ཧΛΞ΢τιʔε͢Δ͜ͱ͕͋Δɽ͜ͷΑ͏ͳαʔϏεΛར༻ͯ͠ SNP ‫ࡧݕ‬γεςϜΛ࣮‫͢ݱ‬Δ৔߹ɼҕୗઌͷ؅ཧऀ͔Β΋ར༻ऀͷ SNP ৘ใΛൿಗԽͰ͖Δ͜ͱ͕๬·͍͠ɽ߈ܸऀ͕എ‫ܠ‬஌ࣝΛ࣋ͭ৔߹ɼ҉߸Խ͞Εͨσʔλ΍໰߹ͤͷස౓Λ༻͍ͨ߈ܸʹର͢Δ଱ੑΛ࣋ͭඞཁ͕͋ΔɽຊߘͰ͸ɼϋογϡʹ‫ࡧͮ͘ج‬Ҿߏ଄ͱൿಗ‫ࡧݕ‬ϓϩτίϧΛ༻͍ͯɼϓϥΠόγʔอ‫ ޢ‬SNP ‫ࡧݕ‬γεςϜΛ࣮૷͠ɼͦͷޮ཰ੑʹ͍ͭͯධՁ͢ΔɽΩʔϫʔυσʔλΞ΢τιʔγϯάɼϓϥΠόγʔอ‫ޢ‬ɼSNP ‫ࡧݕ‬

Implementation of a Privacy-Preserving SNP Search Systemin Data Outsourcing
Kazushiro MINEGISHI† , Shogo SHIMIZU†† , Yeondae KWON††† , and Keiji OSAKI†† College of Liberal Arts, International Christian University, 3–10–2 Osawa, Mitaka, Tokyo 181–8585, Japan†† Faculty of Intercultural Studies, Gakushuin Women’s College
3–20–1 Toyama, Shinjuku, Tokyo 162–8650, Japan††† Faculty of Pharmaceutical Sciences, Tokyo University of Science
2641 Yamazaki, Noda, Chiba 278–8510, Japan
E-mail: †c131257e@yamata.icu.ac.jp, ††shogo.shimizu@gakushuin.ac.jp, †††yekwon@rs.noda.tus.ac.jp,††††keiji@icu.ac.jp
Abstract A single nucleotide polymorphism (SNP) is a DNA sequence variation occurring when a single nucleotide in the genome differs from many other DNA sequences. SNPs are considered to be the cause of personal
differences and expected to be applied to personalized medicine. On the other hand, to reduce the cost of managing
databases, database administration tasks are often outsourced. In outsourced environments, it is desirable that SNP
contents are technically protected against database administrators. When attackers have domain knowledge about
databases, protection methods should be secure from attacks using the frequency of encrypted data and queries.
In this paper, we implement a privacy-preserving SNP search system using hash-based index structures and secure
search protocols and evaluate its efficiency.
Key words data outsourcing, privacy protection, SNP search

1. ͸ ͡ Ί ʹ

1% Ҏ্Λ઎ΊΔλΠϓͷ͜ͱΛ‫͏ݴ‬ɽSNP ͸ DNA ্ͷ༷ʑͳྖҬͰൃ‫͞ݟ‬ΕΔ͕ɼߏ଄Ҩ఻ࢠ΍ௐ੔Ҩ఻ࢠͳͲॏཁͳ෦

Single Nucleotide PolymorphismʢSNPʣͱ͸ɼ఺ಥવมҟ෼ͷ্Ͱ‫͍͖ͯى‬Δ΋ͷ͸ਖ਼ৗͳൃ‫ࢧʹݱ‬োΛ͖ͨ͠ɼ‫ݸ‬ମʹΑͬͯ‫͜ى‬Δ‫ॴہ‬తͳ DNA ͷόϦΤʔγϣϯ͕ूஂ಺Ͱͷ࣬ප΍਎ମͷද‫Ͳͳܕݱ‬ͷಛ௃ͱͯ͠‫ݱ‬ΕΔɽ͜ͷ͏ͪɼ‫ݸ‬

SNP ਍அͰ͸ɼਤ 1 ͷΑ͏ʹɼর߹ର৅ͱͳΔ SNP ηοτ͕ଟ͍৔߹σʔλϕʔεʹอ؅͠ɼর߹ͷࡍʹ໰߹ͤΛߦ͏ɽߋʹɼσʔλϕʔεͷӡ༻؅ཧίετ࡟‫ݮ‬ͷͨΊɼDaaS
ʢDatabase-as-a-Serviceʣͷར༻ɼͭ·ΓσʔλΛੜ੒͢Δ૊৫͕σʔλϕʔε؅ཧ‫ۀ‬຿Λઐ໳ͷ‫֎ʹऀۀ‬෦ҕୗ͢Δ͜ͱ΋࣮ࡍͷ‫ۀ‬຿Ϟσϧͱͯ͠ߟ͑ΒΕΔ [4]ɽ͜ͷΑ͏ͳσʔλΞ΢τιʔγϯά‫ ܕ‬SNP ਍அͰ͸ɼ֎෦ʹ‫ݸ‬ਓ DNA ৘ใͷྲྀग़Λ๷͙ͨΊͷ޻෉͕ඞཁͱͳΔɽਤ1SNP ਍அͷུ֓·ͣɼσʔλͷ֨ೲ΍௨৴ʹ͓͍ͯɼ‫ݸ‬ਓͷ SNP ʹؔ͢Δ৘ใ͸͢΂ͯ҉߸ԽΛࢪ͢ඞཁ͕͋Δɽྫ͑͹ɼ͔ࣖ͋ͷମͷಛ௃ͱͦͷ‫ݪ‬Ҽ SNP ͕΄΅‫׬‬શʹղ໌͞Ε͍ͯΔ΋ͷ΋͋Δ͕ɼ୯Ұ͍҃͸ෳ਺ͷ SNP ͕‫ݸ‬ମͷಛ௃ͱؔ࿈͕͋Δ͜ͱ͕෼͔͍ͬͯΔ΋ͷ΋͋Δɽ͜ΕΒͷൃ‫ݟ‬͸ Genome Wide

Association StudyʢGWASʣͱ‫ݺ‬͹ΕΔήϊϜͷ౷‫ֶܭ‬తͳ

dry/wet Λ਍அ͢Δ SNP Ͱ͋Δ rs17822931 ͸͜Εࣗମ͸ಛʹॏཁͳ‫ݸ‬ਓ৘ใΛ࣋ͭ DNA ͱ͸‫͕͍ͳ͑ݴ‬ɼಉ͡ SNP ͕೔ຊਓঁੑͷೕ͕Μͱؔ࿈͕͋Δ͜ͱ͕஌ΒΕ͍ͯΔɽ͜ͷΑ͏ʹɼҰͭͷ SNP ͕ෳ਺ͷ ਍அ༻ SNP ηοτʹ‫·ؚ‬ΕΔՄղੳʹΑͬͯߦΘΕɼۙ೥ඇৗʹ‫ڀݚͳൃ׆‬෼໺ʹ੒௕ͯ͠ೳੑΛߟ͑Δͱɼ͢΂ͯͷ SNP ৘ใ͸ॏཁͳ৘ใͱଊ͑ͯൿ͍Δɽ

ಗ͢Δ͜ͱ͕๬·͍͠ɽ23andMe ͷΑ͏ͳαʔϏεʹ͓͍ͯ

GWAS ͕஫໨͞Ε͍ͯΔཧ༝ͱͯ͠ɼ‫؞‬΍ΞϧπϋΠϚʔͷ৽ͨͳ਍அํ๏ͱ͢ΔྟচԠ༻΍ DNA ؑఆɼઌ૆ղੳͳͲ঎‫ۀ‬తՁ஋ͷߴ͕͞‫͛ڍ‬ΒΕΔɽถࠃ National Center for Biotech-nology InformationʢNCBIʣ͸ SNP ͷ৘ใΛ‫ڞ‬༗͢ΔͨΊͷσʔλϕʔε dbSNP Λެ։͍ͯ͠ΔɽOnline Mendelian

Inheritance in ManʢOMIMʣσʔλϕʔεͰ͸࣬පؔ࿈ SNPͷ৘ใ͕஝ੵ͞Ε͍ͯΔɽߋʹɼSNPedia ͱ͍͏ wiki Λ༻͍ͨ࣬පؔ࿈ SNP ͷσʔλϕʔε΋ଘࡏ͢ΔɽGWAS ͷ঎‫ۀ‬తར༻Ͱ͸ 23AndMeʢhttp://www.23andme.com/ʣ͕ଣӷ͔Β‫ݸ‬ਓͷ SNP Λղੳ͠ɼՈ‫ܥ‬෼ੳ΍࣬පͷ܏޲ͳͲͷ৘ใΛఏ‫͢ڙ‬ΔαʔϏεΛఏ‫͍ͯ͠ڙ‬Δɽ͜ͷΑ͏ͳ‫ݸ‬ਓ DNA ͷղੳ͕੝ΜʹͳΓͭͭ͋ΔதͰɼϓϥΠόγʔͷ‫͔఺؍‬Β DNA ৘ใ͸ಛʹ৻ॏͳѻ͍͕‫ٻ‬ΊΒΕ
ΔɽຊߘͰ͸ɼ‫ݸ‬ਓ DNA ͷϓϥΠόγʔอ‫ޢ‬΍‫্ྔࢉܭ‬ͷ໰୊Λ౿·্͑ͨͰɼࠓ೔ͷ GWAS ΍ DNA র߹ͷ‫ۀ‬຿ϞσϧΛ૝ఆͨ͠ SNP র߹ख๏ΛఏҊ͢ΔɽҎԼʹຊߘͷߏ੒Λࣔ
͢ɽ2 ষͰ͸ɼ໰୊ઃఆʹ͍ͭͯઆ໌͢Δɽ3 ষͰ͸ɼ2 ষͰड़΂ͨঢ়‫گ‬Λ૝ఆ͠ɼϓϥΠόγʔอ‫ޢ‬Λ࣮‫͢ݱ‬ΔͨΊͷཁૉٕज़Λ঺հ͢Δɽ4 ষͰ͸ɼSNP ਍அखॱʹ͍ͭͯड़΂Δɽ5ষͰ͸ɼ4 ষͷखॱΛ࣮૷͠ɼ֤छͷύϥϝʔλΛม͑ͳ͕Β࣮ߦ࣌ؒͷมԽΛௐ΂ɼޮ཰Խͷख๏΋औΓೖΕͯൺֱ͢Δɽ࠷‫ʹޙ‬ɼ6 ষͰ·ͱΊͱࠓ‫ޙ‬ͷ՝୊ʹ͍ͭͯड़΂Δɽ

2. ໰ ୊ ઃ ఆ
GWAS Ͱ͸ɼྫ͑͹͕Μ‫ऀױ‬ͷάϧʔϓͰ SNP Λ໢ཏతʹௐ΂ͯɼඇ͕Μൃ঱ऀͷάϧʔϓͱൺֱ͠ɼ͕Μ‫ऀױ‬άϧʔϓͷΈʹ‫ڞ‬௨͢Δ SNP Λચ͍ग़͢ͱ͍ͬͨղੳΛߦ͏ɽ͜ͷΑ͏ʹͯ͠ಘΒΕͨ SNP ͸࣬පؔ࿈ SNP ͱ‫ݺ‬͹Εɼಛఆͷ࣬පͱ‫͍ؔڧ‬࿈ੑ͕͋Δͱߟ͑ΒΕ͍ͯΔɽ͜ͷΑ͏ͳ࣬පؔ
࿈ SNP ΍ੜମతಛ௃ؔ࿈ SNP Λ༻͍ͨ਍அ͸ɼඃ਍அऀ͔
Βநग़ͨ͠໢ཏత SNP ͔Βಛఆͷ਍அΛߦ͏ͨΊʹબ͹Εͨಛఆͷ SNP ηοτͱཅੑͷ SNP ηοτͱͷর߹ʹΑͬͯߦΘΕΔɽ΋ɼ΋͠‫ݸ‬ਓͷ݁Ռ͕ެʹͳΔͱ֤߲໨ͷ਍அ݁Ռ͔Β࢖༻ͨ͠ SNP ਍அηοτͱ‫ܕ‬Λ༧૝͠ɼͦΕΒͷཁૉΛ૊Έ߹ΘͤΔ͜ͱͰɼ͕Μ਍அ΍Ξϧίʔϧґଘ਍அͳͲҙਤ͠ͳ͍݁Ռ͕๫࿐͞ΕΔՄೳੑ͕͋Δɽߋʹɼ҉߸Խ͞Εͨσʔλͷग़‫ݱ‬ճ਺ͷ౷‫ܭ‬తස౓͔Βɼ‫ݩ‬σʔλͷ෼෍ʹؔ͢Δഎ‫ܠ‬஌ࣝΛར༻ͯ͠҉߸จͱฏจͷରԠؔ܎Λਪଌ͢Δස౓߈ܸʹ͍ͭͯରࡦ͢Δඞཁ͕͋Δɽฏจ͕‫ݻ‬ఆతͰ͋ͬͨΓ͍҃͸֬ఆత҉߸Ͱ͋Ε͹ස౓෼ੳ͕ՄೳʹͳΔɽຊ‫ۀ‬຿ϞσϧͰ͸ɼ߈ܸऀͱͳΓಘΔαʔό؅ཧऀ͕҉߸จΛ͢΂ͯऩूՄೳͰ͋ΔͨΊɼσʔλϕʔεͷϨίʔυ‫ٴ‬ͼͦΕΒ΁ͷΞΫηε৘ใ΋ස౓෼ੳͷ৘ใͱͳΔɽҎ্ͷϓϥΠόγʔอ‫ޢ‬ͷཁ݅ʹՃ͑ɼর߹࣌ͷޮ཰ੑ΋ॏཁͰ͋Δɽຊ‫Ͱڀݚ‬͸ɼσʔλ͕҉߸Խ͞Εͨ··ͰɼΫϥΠΞϯτͱαʔό͕র߹Ͱ͖Δൿಗ‫ڞ‬௨ू߹‫ࢉܭ‬ϓϩτίϧ [3]Λ༻͍ͯޮ཰ԽΛਤͬͨɽຊϓϩτίϧΛར༻ͨؔ͠࿈‫ͱڀݚ‬ͯ͠ɼσʔλϕʔε΍‫ࡧݕ‬৚݅ͷ৘ใΛ҉߸Խͨ͠··ྨࣅԽ߹෺Λ‫͖Ͱࡧݕ‬Δํ๏͕ఏҊ͞Ε͍ͯΔ [6]ɽ͜ͷख๏͸ɼԽ߹෺ͷ৘ใΛϑΟϯΨʔϓϦϯτͱ‫ݺ‬͹ΕΔ‫ݻ‬ఆ௕ͷϏοτྻͱͯ͠ද‫͠ݱ‬ɼԽ߹෺ͷྨࣅੑΛ͜ΕΒϑΟϯΨʔϓϦϯτಉ࢜ͷൺֱʹΑΓධՁ͠ɼ஋͕Ұக͢ΔϏοτͷՕॴ͕ଟ͚Ε͹ྨࣅ౓͕ߴ͍ͱ͍ͯ͠Δɽ͜ͷϑΟϯΨʔϓϦϯτͷ৘ใΛ४ಉ‫߸҉Ͱ߸҉ܕ‬Խ͓͖ͯ͠ɼσʔλϕʔεʹอ؅͠র߹͢Δɽ·ͨɼαʔόଆ͕ϑΟϯΨʔϓϦϯτͷྨࣅ౓Λ൑ఆ͢Δ‫ࢉܭ‬Λ҉߸จͷ··ߦ͏ͷͰɼΫϥΠΞϯτͱαʔόͰͷॲཧ͕෼ࢄ͞Εͯޮ཰తͱ‫͑ݴ‬Δɽ͜ͷԽ߹෺σʔλϕʔεͷൿಗ‫ࡧݕ‬͸ɼຊߘͱಉ༷σʔλϕʔεͷར༻΍؅ཧαʔό΁ͷ৘ใͷൿಗԽΛ໨తͱ͍ͯ͠ΔɽҰํͰɼԽ߹෺ͱҟͳΓ SNP ͸ߏ଄ࣜͳͲͷಛ௃Ͱද‫͖ͣͰݱ‬ɼ·ͨߴ଎Ͱর߹‫͕ࢉܭ‬Մೳͳσʔλʹม‫͢׵‬Δඞཁ͕͋ΔͳͲͷҧ͍͕͋ΔɽDNA ഑ྻͷྨࣅੑղੳͰ͸ɼೋͭͷ DNA ഑ྻͷর߹Ͱ͸จࣈྻͱͯ͠ฤू‫཭ڑ‬Λ‫͢ࢉܭ‬Δํ๏͕ҰൠతͰ͋Δ͕ɼ͜ͷࡍ‫͕͍ޓ‬อ࣋͢Δ DNA Λ։ࣔͤͣʹฤू‫ࢉܭ཭ڑ‬Λߦ͏র߹ख๏͕͍͔ͭ͘ఏҊ͞Ε͍ͯΔ [1], [2], [5]ɽ͔͜͠͠ΕΒ͸ΦʔτϚτϯΛ༻͍ͨ‫ࢉܭ‬Λ‫͓ͯ͠ʹج‬Γɼฤू‫཭ڑ‬ͷఆٛ O(n2 )ͱ͍͏‫ྔࢉܭ‬ͷ‫͔఺؍‬ΒσʔλϕʔεΛ༻͍ͨর߹ͷద༻͕ࠔ
೉Ͱ͋Δɽ·ͨɼσʔλϕʔεʹ͓͍ͯ໰୊ͱͳΔස౓෼ੳ͕ߟྀ͞Ε͍ͯͳ͍ɽ

3. ཁ ૉ ٕ ज़
3. 1 Bloom ϑΟϧλBloom ϑΟϧλ͸഑ྻͱϋογϡؔ਺Λ༻͍Δۭؒޮ཰ʹ༏Εͨσʔλߏ଄Ͱ͋Δɽओʹɼಛఆͷཁૉ͕ू߹ʹ‫·ؚ‬ΕΔ͔Ͳ͏͔Λ؆қతʹௐ΂Δ໨తͰར༻͞ΕΔɽҎԼʹɼҰൠతͳ Bloom ϑΟϧλͷߏஙํ๏ͱͦͷੑ࣭ʹ͍ͭͯड़΂Δɽ஋ͷ֨ೲͱ‫ʹࡧݕ‬͸ m Ϗοτͷ࿦ཧ‫ܕ‬഑ྻͱk ‫ݸ‬ͷҟͳΔϋογϡؔ਺Λ࢖༻͢ΔɽϑΟϧλʹཁૉΛ௥Ճ͢Δࡍ͸ɼ௥Ճ͢Δཁૉʹର͠ k ‫ݸ‬ͷϋογϡؔ਺Λద༻͠ɼਤ2഑ྻͷରԠ͢Δ֤ఴࣈͷ஋Λਅʹ͢ΔɽϑΟϧλϦϯάɼͭ·SNP ਍அखॱͷ֓ཁΓ໰߹ͤͷࡍ͸ɼௐ΂Δ஋ʹର͠ k ‫ݸ‬ͷϋογϡΛద༻͠ɼಘΒΕͨ k ‫ݸ‬ͷఴࣈͷཁૉ͕͢΂ͯਅͰ͋Δ͔Ͳ͏͔Λௐ΂ΔɽϧλΛੜ੒͢Δɽ͜ͷͱ͖ɼෳ਺ͷϋογϡؔ਺΍ಛఆͷ֬཰ୠ͠ɼ࣮ࡍʹ͸ҟͳΔཁૉͰ͋ͬͯ΋ϋογϡ஋ͷিಥ͕‫͜ى‬Ͱൃੜ͢ΔিಥʹΑ֤ͬͯ SNP ͷස౓ͷภΓ͕֧ཚ͞ΕΔɽ

ΔՄೳੑ͕͋ΔͨΊɼِཅੑ͕ൃੜ͢Δɽn Λ഑ྻʹ௥Ճ͞Εྫ͑͹ɼ૯ SNP ਺Λ 1,000 ͱ͠ɼϋογϡؔ਺Λ 5 ‫ܾͱݸ‬

͍ͯΔཁૉ਺ͱͨ͠ͱ͖ɼٖཅੑͷ֬཰͸࣍ࣜͰ‫ٻ‬ΊΒΕΔɽΊΔɽBloom ϑΟϧλʹରԠ෇͚ΒΕΔ SNP ͷσʔλ͸ҰͭP r = (1 − (1 − 1/m)kn )k ≈ (1 − e−kn/m )kʹ͖ͭ 5 ‫ݸ‬ͷϋογϡؔ਺͕ద༻͞Εɼ5 ‫ݸ‬ͷ഑ྻఴࣈ͕ੜ੒(1)͞ΕΔɽͭ·ΓɼBloom ϑΟϧλʹରԠ෇͚ΒΕΔཁૉ਺ n্͕ࣜࣔ͢Α͏ʹɼ഑ྻͷϏοτ਺ m ͕େ͖͍΄Ͳিಥͷ֬͸߹‫ Ͱܭ‬5,000 ͱͳΔɽ࣍ʹɼ‫ر‬๬ͷِཅੑ཰ΛܾΊΔ͕ɼྫ཰͕খ͘͞ͳΔɽͦͷҰํͰ k ͷେ͖͞ʹ͸࠷దͳ΋ͷɼͭ·͑͹ 1 ˋ ҎԼʹ͚ͨ͠Ε͹ɼࣜ (1) ΑΓ Bloom ϑΟϧλͷΓِཅੑ཰Λ࠷΋খ͘͢͞Δ஋͕ଘࡏ͢Δɽ͜ͷ࠷ద஋Λ KϏοτ਺Λ 10 ഒɼͭ·Γ 50,000 ‫ݸ‬ͷ഑ྻʹ͢Ε͹ِཅੑ཰

ͱ͢ΔͱɼK ͸࣍ࣜͰද͞ΕΔɽ

͸ 0.94 ˋ ఔ౓ʹऩ·Δɽ·ͨࣜ (2) ΑΓɼ࠷దͳϋογϡؔ਺ͷ਺ k ͸ 7 ͱͳΔɽߋʹɼElGamal ҉߸ͷ࣋ͭ४ಉ‫ܕ‬ੑΛ

K = m/n ln 2(2)Bloom ϑΟϧλΛ୯ʹϑΟϧλͱͯ͠࢖༻͢Δ৔߹͸࠷దԽ͞༻͍ͯൿಗ‫ڞ‬௨ू߹‫ʹࢉܭ‬ΑΔর߹Λߦ͏͜ͱͰɼ໰߹ͤΛอ‫͢ޢ‬ΔɽΕͨ k Λ༻͍Δͷ͕޷·͍͕͠ɼ‫ޙ‬ड़͢ΔΑ͏ʹɼຊߘͰఏҊਤ 2 ʹ SNP ਍அखॱͷ֓ཁΛࣔ͢ɽҎԼͰఏҊํࣜΛɼ·͢Δख๏Ͱ͸ِཅੑ͕ൺֱతߴͯ͘΋র߹݁ՌʹӨ‫͍ͳ͕ڹ‬ɽͣσʔλϕʔεߏஙɼ࣍ʹর߹࣌ͷखॱʹ͍ͭͯΫϥΠΞϯτ

3. 2 ४ಉ‫߸҉ܕ‬४ಉ‫ͱ߸҉ܕ‬͸ೋͭͷ҉߸จΛ༻͍ͨ‫߸҉͍͠৽͕ࢉܭ‬จʹଆͱαʔόଆͷॲཧʹ෼͚ͯड़΂Δɽ

4. 1 ֨ ೲ ࣌ͳΓɼͦΕΛ෮߸͢ΔͱରԠ͢Δฏจͷ‫ࢉܭ‬Λͨ͠΋ͷͱಉ͡σʔλϕʔεͷදʹর߹ର৅ͱͳΔ࣬‫ݻױ‬༗ͷ SNP ηοτʹͳΔΑ͏ͳੑ࣭Λ༗͢Δ҉߸Ͱ͋ΓɼEnc Λ҉߸ΞϧΰϦζ

ͷσʔλΛ֨ೲ͢Δɽ͜ͷσʔλ͸ SNP ηοτ͔Β BloomϜɼ⊗ Λԋࢉͱͨ͠ͱ͖ɼ࣍ࣜΛຬͨ͢ɽϑΟϧλΛੜ੒͢ΔࡍʹಘΒΕͨ഑ྻఴࣈΛ ElGamal ҉߸Ͱ

Enc(A) ⊗ Enc(B) = Enc(A ⊗ B)҉߸Խͨ͠΋ͷͰ͋Δɽσʔλϕʔεߏங࣌ʹ࢖༻ͨ͠ BloomϑΟϧλͷ഑ྻ௕ m ͱϋογϡؔ਺͸র߹ͷࡍͰ΋࢖༻͢ΔɽRSA ҉߸΍ ElGamal ҉߸͸ੵʹؔ͢Δಉ‫ܕ‬ੑΛ༗͠ɼPaillier·ͨɼElGamal ҉߸ͷ҉߸ԽͰ࢖༻ͨ͠ཚ਺͸ɼ‫ʹޙ‬ΫϥΠ҉߸͸࿨ʹؔ͢Δಉ‫ܕ‬ੑΛ༗͢ɽΞϯτଆͰ෮߸Λߦ͏ࡍʹ΋࢖༻͢Δɽ

3. 3 ൿಗ‫ڞ‬௨ू߹ϓϩτίϧ

4. 2 ໰ ߹ ͤ ࣌ൿಗ‫ڞ‬௨ू߹ϓϩτίϧ͸ɼೋऀؒͰ֤ʑ͕࣋ͭू߹ཁૉʹ·ͣɼΫϥΠΞϯτͰҎԼͷΑ͏ʹ໰߹ͤΛੜ੒͢Δɽຊর͍ͭ͘ͷ‫ڞ‬௨ཁૉ͕ଘࡏ͢Δ͔Λɼ‫͍ޓ‬ͷཁૉΛൿಗͨ͠··߹ํ๏ͷલஈ֊ͱͯ͠ɼ਍அ͢Δ‫ݸ‬ମͷ DNA ͔Β਍அʹ༻͍‫͢ࢉܭ‬Δख๏Ͱ͋Δ [3]ɽఏҊํࣜͰ͸ɼElGamal ҉߸Λ༻͍Δ͢΂ͯͷ SNP Λநग़ͨ͠‫ޙ‬ɼͦΕΒ͕ԿΒ͔ͷํ๏Ͱූ߸ͯੵʹؔ͢Δಉ‫ܕ‬ੑΛར༻ͨ͠ൿಗ‫ڞ‬௨ू߹‫ࢉܭ‬Λߦ͏ɽԽ͞Ε͍ͯΔͱ͢Δɽྫ͑͹ɼNCBI ͷ dbSNP ͷࣝผ൪߸Λ4. σʔλΞ΢τιʔγϯάʹ͓͚Δ SNP ਍அ༻͍ͯ {rs2980300 T, rs11260554 G,. . .} ͷΑ͏ͳจࣈྻʹม‫͞׵‬Ε͍ͯΔ΋ͷͱ͢Δɽຊߘ͸ɼSNP ਍அͱ͍͏ൺֱతগ਺ͷ SNP Λ༻͍ͯ‫ݸ‬ମͷ(1) σʔλ֨ೲ࣌ͱಉ༷ͷํ๏Ͱɼর߹‫ͳͱݩ‬Δ‫ݸ‬ਓ SNPੜཧతಛ௃͓Αͼ֎తಛ௃ͳͲΛ਍அ͢Δ෼໺΁ͷԠ༻Ͱ͋Δɽ͔Β਍அͷͨΊͷಛఆͷ SNP ηοτΛநग़ͯ͠ Bloom ϑΟDNA ͷม‫͋Ͱܗ‬Δ SNP ͸ͦͷ΋ͷͷස౓ʹภΓ͕͋Δɽ͜ͷϧλΛੜ੒͠ɼରԠ෇͚ΒΕͨ഑ྻఴࣈΛநग़͢ΔɽภΓΛղফ͢ΔͨΊʹจࣈྻͰ͋Δ SNP ৘ใ͔Β Bloom ϑΟ(2) ഑ྻ൪߸Λղͱ͢Δଟ߲ࣜΛੜ੒͠ɼ֤࣍਺ͷ܎਺Λநग़͢Δɽ܎਺Λ ElGamal ҉߸Ͱ҉߸Խ͠ɼαʔόʹૹ৴͢Δɽ͜ͷͱ͖ɼ҉߸Խ͞Εͨ܎਺Λ࣍਺ॱʹ഑ྻʹೖΕΔͳͲ֤ͯ͠܎਺ͷ࣍਺৘ใ΋ૹ৴͢Δɽ۩ମతʹ͸ɼSNP ηοτͷཁૉ N ‫ݸ‬Λղͱ͢Δ N ࣍ͷଟ߲ࣜΛੜ੒͢ΔɽN
N −iΠN)i=1 (x − ci ) = Σi=0 (di x͜ͷଟ߲ࣜల։ͨ͠܎਺ d1 , . . . , dN Λ҉߸Խ͠ɼ܎਺ͷ࣍਺ͷ৘ใͱͱ΋ʹαʔόʹૹ৴͢ΔɽੳΛࠔ೉ʹ͢Δɽ

5. ࣮‫ݧ‬ຊ࣮‫ݧ‬ͷओͳ໨తͷҰͭ͸ఏҊ͢ΔϓϩτίϧΛ࣮૷͠ɼσʔλϕʔεͷσʔλྔͱর߹‫ݩ‬ͷ SNP ηοτ਺Λม࣮͑ͯߦ࣌ؒΛ‫ܭ‬ଌ͢Δ͜ͱͰ͋Δɽ·ͨɼ͜ΕΛ‫ͯ͠ʹج‬ɼස౓෼ੳ଱ੑΛอ࣋ͨ͠ޮ཰Խͷํ๏ʹ͍ͭͯ΋࣮‫͢ݧ‬Δɽຊདྷͷর߹ํ๏ʹ͸ΫϥΠΞϯτɾαʔόϞσϧΛ૝ఆͯ͜͜͠Ͱɼ਍அ༻ SNP Λબ୒͢ΔϓϩηεΛল͖ɼ‫ݸ‬ਓ͔Β͍Δ͕ɼຊ࣮‫Ͱݧ‬͸௨৴‫ڥ؀‬ͷӨ‫ڹ‬Λආ͚ΔͨΊɼҰͭͷ Javaநग़ͨ͠શ SNP Ͱ Bloom ϑΟϧλΛੜ੒͢Δ͜ͱ΋ߟ͑ΒΞϓϦέʔγϣϯͱ࣮ͯ͠૷͢Δɽσʔλϕʔε͸ MySQLΕΔɽ͜ͷࡍɼσʔλϕʔεͷ SNP σʔλͰੜ੒͢Δ BloomΛ࢖༻͠ɼ౷߹‫ڥ؀‬։ൃιϑτͷ eclipse ͷϓϥάΠϯͰ͋Δ

ϑΟϧλ΋શ SNP ༻ͷ Bloom ϑΟϧλͰఆٛͨ͠΋ͷΛ࢖

DBViewer ʹΑΓσʔλϕʔεʹΞΫηε͢Δɽ

༻͢Δɽྫ͑͹ɼSNP ਍அʹ༻͍ΔͨΊɼ‫ݸ‬ਓ͔Βநग़͢Δ

ຊ SNP ਍அͰ͸ҎԼͷύϥϝʔλ͕ଘࡏ͢Δɽ

SNP ͕ 100 ສ‫͋Ͱݸ‬Δͱ͢Δͱɼཁૉ਺ n ͕ 100 ສͱͳΔɽ•aɿ֤਍அͰ࢖༻͢Δ SNP ͷ਺•cɿর߹ର৅ͷςʔϒϧ਺•eɿϋογϡؔ਺ͷ਺͜ͷํ๏͕ΑΓޮ཰తͱߟ͑ΒΕΔཧ༝͸ɼσʔλϕʔεͷશςʔϒϧʹର͠Ұճর߹͢Δͱɼ͢΂ͯͷ਍அΛಉ࣌ʹߦͬͨ͜ͱʹͳΔ͔ΒͰ͋Δɽ͜ͷํ๏ʹରͯ͠ɼநग़ͨ͠ SNP͔Β਍அ͢ΔηοτΛબͿํ๏Ͱ͸ɼηοτͷબ୒ຖʹσʔλϕʔεશମͱর߹͢Δඞཁ͕͋ΓɼແବͳॲཧΛ‫ؚ‬Ή͜ͱʹͳ•bɿ਍அ಺༰ͷ਺•dɿBloom ϑΟϧλͷϏοτ਺•f ɿBloom ϑΟϧλͷཁૉ਺Δɽղܾࡦͱ֤ͯ͠બ୒ SNP ηοτຖʹಛఆͷςʔϒϧͷΈ࣍ʹɼ࣮‫ݧ‬ର৅Ͱ͋Δর߹࣌ؒʹ֤ؔͯ͠ύϥϝʔλͷӨ‫ڹ‬ΛΛબͿͱͯ͠΋ɼσʔλϕʔε؅ཧऀ͕σʔλϕʔεͷΞΫηߟ͑Δɽ͜ͷͨΊɼর߹ॲཧΛଟ߲ࣜల։ɼ୅ೖ‫ࢉܭ‬ɼ෮߸ॲεΛ‫͍ͯ͠ࢹ؂‬ΔͷͰ֧ཚॲཧ͕ඞཁͰ͋Δɽཧͷ 3 ͭʹ෼͚ɼӨ‫ڹ‬ൣғΛ࣍ͷΑ͏ʹ·ͱΊΔɽαʔόଆͰ͸ɼ·ͣɼσʔλϕʔε͔Βর߹ର৅ͱͳΔ SNPηοτͷσʔλ͕֨ೲ͞Ε͍ͯΔ֤දͷσʔλɼͭ·Γ҉߸Խ͞Εͨఴࣈ൪߸ΛऔΓग़͠ɼΫϥΠΞϯτ͔ΒૹΒΕ͖֤ͯͨ•ଟ߲ࣜల։ʢΫϥΠΞϯτଆʣɿa × e, b•෮߸ॲཧʢΫϥΠΞϯτଆʣɿb × c, f (a, e)•୅ೖ‫ࢉܭ‬ʢαʔόଆʣɿb × c, f (a, e)܎਺ʹରԠ͢Δ࣍਺Λ৐ͨ͡ఴࣈ൪߸Λֻ͚Δɽ͜ͷॲཧ͸ଟύϥϝʔλͷӨ‫઀͕ؒڹ‬తͰ͋ͬͨΓɼͦͷӨ‫໌͕ڹ‬Β͔ʹখ߲ࣜͷ֤߲Λಠཱͤͨ͞··୅ೖ͢Δ͜ͱʹ૬౰͢Δɽ͜ͷ͍݁͞৔߹͸আ֎͍ͯ͠Δɽଟ߲ࣜ‫Ͱࢉܭ‬͸ a × e ͕Ө‫͢ڹ‬Δ͕ɼՌಘΒΕͨੵͷ஋ΛΫϥΠΞϯτʹฦ͢ɽྫ͑͹਍அͰ࢖༻͢Δ SNP ͕ rs1 ͱ rs2 ͷೋͭͰ͋Ε͹ɼ͜ΫϥΠΞϯτଆ͸αʔό͔Βฦ͞Ε͖֤ͯͨ࣍਺ͷੵͷ஋ΛΕΒΛҰͭͷϋογϡؔ਺Ͱ഑ྻʹϚοϐϯά͢Δͱɼিಥ͕෮߸͠ɼ଍͠߹ΘͤΔɽElGamal ҉߸͸ੵʹؔ͢Δಉ‫ܕ‬ੑΛ༗ͳ͚Ε͹࠷ऴతʹ͸ 2 ࣍ͷଟ߲ࣜʹͳΔͨΊͰ͋Δɽͭ·Γଟ͢ͷͰɼσʔλϕʔεͷর߹‫ ݩ‬SNP ηοτͷ Bloom ϑΟϧ߲ࣜల։ͷ‫ؒ࣌ࢉܭ‬͸ a × e ͳͷͰͲͪΒ͔ҰํͷΈΛมԽ͞λʹর߹‫ ݩ‬SNP ηοτͷ Bloom ϑΟϧλͱಉ͡ఴࣈ൪߸͕‫·ؚ‬Ε͍ͯΔ͔ɼ·ͨ͸ِཅੑͰ͋Ε͹݁Ռ͸ 0ʢElGamal ҉ͤΕ͹ධՁՄೳͰ͋Δɽ୅ೖ‫ͱࢉܭ‬෮߸‫Ͱࢉܭ‬͸ b × c ͷύϥϝʔλ͕ͲͪΒ΋Ө‫͍ͯ͠ڹ‬Δɽ͜Ε͸ɼҰͭͷ਍அ಺༰ʹର߸Ͱ࢖༻ͨ͠ૉ਺ p Λ๏ͱͯ͠ 0 ͱ߹ಉʣ ͱͳΔɽैͬͯɼরͯ͠ςʔϒϧ͢΂ͯͱর߹͢Δͱ͖ʹ୅ೖ‫͓ࢉܭ‬Αͼ෮߸ॲཧ߹‫ ݩ‬SNP ηοτ͕র߹ର৅ SNP ηοτͱ౳͍͠৔߹͸ɼද͕ߦΘΕΔͨΊͰ͋Δɽ͜Εʹର͠ଟ߲ࣜల։͸ɼ਍அ಺༰Ұͷཁૉ͢΂ͯͷ୅ೖ‫ Ͱࢉܭ‬0 ͱͳΔɽͭʹର͠ΫϥΠΞϯτͰ࠷ॳʹҰճߦΘΕΔͷΈͰ͋ΔͨΊɼ͜͜Ͱɼর߹‫ʹݩ‬ຊདྷରԠ͍ͯ͠Δর߹ର৅͸σʔλϕʔεb ͷΈ͕Ө‫͢ڹ‬Δɽ·ͨɼf (a, e) ͸֤ςʔϒϧ಺Ͱ୅ೖ͢Δཁͷද‫܈‬ͷҰ෦Ͱ͋ΔͨΊɼ͜ͷ‫ࢉܭ‬Λ͢΂ͯͷදʹରͯ͠ߦ͏ૉ਺ʹରԠ͍ͯ͠ΔͷͰɼ୅ೖճ਺ͱͦͷ݁ՌΛ෮߸͢Δճ਺͜ͱ͸ඇޮ཰తͰ͋Δɽྫ͑͹ɼর߹‫͔͕͋ࣖݩ‬ͷ‫ܕ‬Λ਍அ͢ʹӨ‫͢ڹ‬ΔɽҎ্ʹΑΓɼর߹࣌ؒΛ‫ܭ‬ଌ͢ΔͨΊͷύϥϝʔΔͨΊͷ SNP ηοτΛબΜͰ͍Δͷʹɼর߹ର৅͕͔ࣖ͋ͷλ͸ɼଟ߲ࣜల։ʹؔͯ͠͸ a × e ͱ b ΛมԽͤ͞Ε͹Α͘ɼSNP ηοτ͚ͩͰͳ͘৺ଁප΍ 2 ‫ܕ‬౶೘පͳͲຊདྷؔ܎ͳ͍
SNP ηοτͱ΋র߹ΛࢼΈ͍ͯΔ͜ͱʹͳΔɽ͔͠͠ɼ୯७ͳ୅ೖ‫ͱࢉܭ‬෮߸ॲཧʹؔͯ͠͸ b × c ͱ f ͰΑ͍ɽ

5. 1 র߹࣌ؒͷ࣮‫͢༻࢖Ͱݧ‬Δύϥϝʔλͷ஋ͱࠜ‫ڌ‬ํ๏ͰಛఆͷදͷΈΛબ୒͠র߹͢Δ͜ͱ͸σʔλϕʔε؅ཧর߹࣌ؒͷධՁʹ͍ͭͯ͸֤਍அͰ࢖༻͢Δ SNP ͷ਺ aɼ

ऀ͕σʔλϕʔεͷΞΫηε΍σʔλετϦʔϜΛ‫͢ࢹ؂‬Δ͜਍அ಺༰ͷ਺ bɼর߹ର৅ͷςʔϒϧ਺ c ͷ֤ύϥϝʔλΛมͱͰස౓෼ੳՄೳʹͳΔͷͰ๬·͘͠ͳ͍ɽͦ͜ͰɼຊߘͰ͸ɼԽͤ͞Δɽύϥϝʔλͷ஋ʹ͍ͭͯ͸ a ʹؔͯ͠͸ [5,15, 20]ɼແବͳදʹର͢Δ෮߸ΛߦΘͳ͍͜ͱʹΑͬͯޮ཰ԽΛਤΔɽb ʹؔͯ͠͸ [100,200,300,400,500,1000] ͱ͢Δ͕ɼ͜ͷύϥর߹ʹ༻͍ΔཁૉΛ֬཰తσʔλߏ଄ʹอ؅͢ΔͨΊɼ্‫ه‬ϝʔλͷ஋Λ࢖༻͢Δࠜ‫ڌ‬ΛҎԼͰड़΂ΔɽͷΑ͏ͳ‫ڞ‬௨ू߹Λ༻͍ͨ SNP র߹͸୯ͳΔ҉߸ʹΑΔর߹·ͣɼর߹࣌ؒͷධՁ͸Ͱ͖Δ‫ݶ‬Γ࣮ࡍͷ SNP ਍அͰߦΘΕʹൺ΂‫͍ڧ‬ස౓଱ੑΛ࣋ͨͤΔ͜ͱ͕ՄೳͰ͋Δɽ͜ΕʹΑΓΔॲཧʹ͍ۙ‫͋Ͱ͖΂͏ߦͰܗ‬Δͱߟ͑ͨɽͦ͜Ͱ 1 ষͰ঺հSNP ͕࣋ͭ‫ݻ‬༗ͷස౓ΛϥϯμϜԽͰ͖ɼ݁Ռͱͯ͠ස౓෼

ͨ͠ 23andMe ͷ঎‫ۀ‬త SNP ਍அΛϞσϧʹͨ͠ɽ23andMeͰ͸͓Αͦ 100 ສ‫ݸ‬ͷ SNP ͕਍அʹ༻͍ΒΕ͍ͯΔͱ‫͞ه‬Ε͍ͯΔɽ͜ͷ͏ͪɼಛఆͷ SNP ͷ૊߹͕ͤಛఆͷ࣬ප܏޲΍૆ઌͳͲΛ਍அ͢Δηοτͱͯ͠ར༻͞Ε͍ͯΔɽ਍அʹ༻
͍Δ SNP ηοτͷ۩ମతͳ಺༰͸͢΂ͯ͸ެද͞Ε͍ͯͳ͍
͕ɼSNPedia ΍࣬පؔ࿈ SNP ͷจ‫Ͳͳݙ‬Λ‫ݟ‬Δͱɼηοτʹ‫·ؚ‬ΕΔ SNP ͷ਺͸ܾͯ͠ଟ͘ͳ͍ͱ‫͑ݴ‬Δɽྫ͑͹গͳ͍΋ͷͰ 1 ‫ݸ‬ͷ SNP Ͱ਍அͰ͖Δ wet/dry ͷ͔ࣖ͋λΠϓ͕

ද 1 ‫ج‬ຊతͳύϥϝʔλͷมԽͱর߹࣌ؒ
ςʔϒϧ਺ \ SNP ηοτ

5

1020
15. 8

100

1.0

3.3

200

3.5

12.0

53.9

300

7.6

26.3

116.2

400

13.2

46.4

202.6

500

20.3

72.2

313.51,00079.3 288.2 1212.8͋Γɼଟ͍΋ͷͰ΋਺े‫͕ݸ‬ຆͲͰ͋ΔɽҎ্ͷཧ༝͔Β਍அ
ͷ SNP ηοτ͸ൺֱతখ͍͞਺Ͱ্‫ݶ‬Λ 20 ʹ͓͑͞ɼ਍அͷόϦΤʔγϣϯʹԠͯ͡૿Ճ͢Δর߹ճ਺Λ‫ܭ‬ଌՄೳͳൣғ·Ͱେ͖࣮ͨ͘͠‫ݧ‬Λߦ͏ํ͕ΑΓ‫࣮ݱ‬తͰ͋Δͱߟ͑ͨɽͦ͜Ͱ਍அ਺ɼ͓Αͼςʔϒϧ਺͸ɼ[100,200,300,400,500,1000]ͱࡉ͔͘औΔ͜ͱʹ͢Δɽ਍அ਺ͱςʔϒϧ਺ͷύϥϝʔλ͸ͦΕͧΕಠཱʹมԽ͢ΔͷͰͳ͘ɼҰͭͷ਍அʹຊདྷରԠͯ͠
͍Δςʔϒϧ͸ͨͩҰͭͱԾఆͯ͠Ұகͤ͞Δ͜ͱʹ͢Δɽ

SNP σʔλͷ࡞੒ํ๏͸ҎԼͷ௨ΓͰ͋Δɽσʔλϕʔε࡞੒࣌ɼςʔϒϧͷর߹ର৅ͱͳΔ SNP ηοτͷจࣈྻ৘ใΛ 0,1,2,· · · ͷΑ͏ͳ਺ࣈʹ͢Δɽ਍அʹ࢖͏ SNP ηοτ͕ 5 ͭͳΒ͹ɼ1 ൪໨ͷςʔϒϧʹ͸ {0,1,2,3,4}ɼ2 ൪໨ͷςʔϒϧʹ͸ {5,6,7,8,9} ͷΑ͏ͳ਺ࣈΛຊདྷͷ SNP ৘ใͰ

͋Δ rs100212 A ͳͲͷ୅ΘΓʹೖΕ͓ͯ͘ɽর߹࣌ɼΫϥΠΞϯτ͕‫ݸ‬ਓ SNP ͔Βநग़͢Δ਍அ༻ SNP ηοτ͸ɼॱʹ{0,1,2,3,4},{5,6,7,8,9},{10,11,12,13,14} ͷΑ͏ʹ࡞Γ BloomϑΟϧλΛੜ੒͢Δɽ͜ΕʹΑΓɼ֤਍அ SNP ηοτ͸σʔλϕʔεͷςʔϒϧதͰඞͣҰ͚ͭͩ‫׬‬શʹҰக͢Δ΋ͷ͕͋Γɼͦͷଞͷςʔϒϧ಺ͷσʔλͱҰͭͰ΋Ұக͢Ε͹ͦΕِ͕ཅੑͰ͋Δͱ൑ผͰ͖Δɽ࣍ʹ਍அʹ༻͍Δ SNP ͷ਺ 5,10,20 ͕͢΂ͯͷ਍அ಺༰ͰҰఆʹ͢Δཧ༝ʹ͍ͭͯड़΂Δɽ֤਍அͰ࢖༻͢Δ SNP ͷ਺͸ຊདྷ਍அʹΑͬͯมΘΔ͸ͣͰ͋Δɽྫ͑͹ɼ͔ࣖ͋ͳΒ 1‫Ͱݸ‬৺ଁපͳΒ 15 ‫͋ͰͲͳݸ‬Δɽຊ࣮‫Ͱݧ‬͸ɼ਍அͰ༻͍ΔSNP ਺Λ֤ʑͰ‫ݻ‬༗ͳ΋ͷʹ͢Δͱස౓෼ੳʹͭͳ͕ΔͨΊɼμϛʔͱͳΔ SNP ΛύσΟϯά͢Δ͜ͱΛ૝ఆͨ͠ɽ

5. 2 ‫ج‬ຊతͳύϥϝʔλΛมԽ࣮ͤͨ͞‫ݧ‬֤਍அͰ࢖༻͢Δ SNP ਺ a ͕ [5,10,20] ͷ 3 ௨Γɼ਍அ಺༰ͷ਺ b ͱর߹ର৅ͷςʔϒϧ਺ c ͕ [100,200,300,400,500,1000]ͷ 6 ௨ΓͰ͋ΔɽBloom ϑΟϧλͰ࢖༻͢Δ഑ྻͷϏοτ਺͸ཁૉ਺ͷ 10 ഒɼϋογϡؔ਺ͷ਺͸ 1 ͱͨ͠ɽ֤࣮‫Ͱݧ‬ϓϩάϥϜͷ։͔࢝Βऴྃ·Ͱͷ‫ܦ‬ա࣌ؒΛ༗ޮ਺ࣈҰܻͷϛϦඵ୯ҐͰ 3 ճͣͭଌఆ͠ɼฏ‫ۉ‬஋Λࢉग़ͨ͠ɽ࣮‫ݧ‬ͷ݁ՌΛද 1 ʹࣔ͢ɽর߹࣌ؒ͸ςʔϒϧ਺͕ 100ɼ

SNP ηοτ਺͕ 5 ͷ৔߹Λ 1 ͱͯ͠ɼ૬ର஋ʹม‫͍ͯ͠׵‬ΔɽύϥϝʔλͷมԽͱॲཧ࣌ؒͷؔ܎Λௐ΂Δʹ͋ͨΓɼ·ͣςʔϒϧ਺͓Αͼ਍அ਺ͷมԽʹண໨͢Δɽςʔϒϧ਺ͷมԽͱॲཧ࣌ؒ͸ n2 ΑΓ΍΍গͳ͍ΦʔμͰ‫͞ࢉܭ‬Ε͍ͯΔɽҰํɼSNP ਺ͷมԽʹண໨͢Δͱɼಉ༷ʹɼn2 ҎԼͷΦʔμͷ‫ܭ‬ࢉ࣌ؒͱͳ͍ͬͯΔɽSNP ਺ͱςʔϒϧ਺ͷมԽͰ͸ͲͪΒ͕‫ʹؒ࣌ࢉܭ‬Ө‫͕ڹ‬େ͖͍͔Λௐ΂Δʹ͋ͨΓɼྫ͑͹ɼ(100,5)
ͱ (400,5)ɼ(100,5) ͱ (100,20) ͕ಉ͡ 4 ഒͷมԽʹͳ͍ͬͯΔ͕ɼর߹࣌ؒͰ͸ SNP ͷมԽͷํ͕ଟ͘ͳ͍ͬͯΔɽҰํͰ (100,5) ͱ (200,5)ɼ(100,5) ͱ (100,10) ͷ 2 ഒͷมԽͷ৔߹͸‫ʹٯ‬ςʔϒϧͷมԽͷํ͕র߹࣌ؒʹେ͖͍Ө‫ڹ‬Λ༩͍͑ͯΔɽͦͷଞͷ૊߹ͤͰ΋ͲͪΒ͔Ұํʹܾ·Βͳ͍ͷͰɼຊ࣮‫Ͱݧ‬͸൑அͰ͖ͣɼ΄΅ಉ͡ఔ౓ͷӨ‫͑ߟͱڹ‬ΒΕΔɽຊ࣮‫Ͱݧ‬͸ςʔϒϧ਺ͱ਍அ਺͕ಉ࣌ʹมԽ͍ͯ͠ΔͷͰɼྫ͑͹ςʔϒϧ਺͕ 10 ഒ ʹ૿͑Δͱ਍அ਺΋ 10 ഒʹ૿͑ɼσʔλϕʔεதͷςʔϒϧͱর߹͢Δճ਺͸ 100 ഒʹͳΔɽҰํͰ SNP ਺ͷมԽ͸ɼຊϓϩάϥϜͷϘτϧωοΫͰ͋Δଟ߲ࣜల։ͷॲཧʹӨ‫͠ڹ‬ɼ·֤ͨςʔϒϧ಺ͷཁૉ͕૿͑ΔͨΊ୅ೖ‫ࢉܭ‬ɼ෮߸ॲཧʹ΋Ө‫͢ڹ‬Δɽ

5. 3 ෮߸ॲཧΛল͘ޮ཰ԽΛՃ͑ͨ‫ޙ‬ͷύϥϝʔλΛมԽ࣮ͤͨ͞‫ݧ‬ຊߘͰఏҊ͢Δ SNP র߹ํ๏ʹ͸ɼ͋Δಛఆͷ਍அΛ͢ΔͨΊબ୒ͨ͠ SNP ηοτʹରͯؔ͠܎ͷͳ͍র߹ର৅ͷ SNPηοτͱর߹͢Δॲཧʹແବ͕͋Δɽ͔͠͠ɼ਍அ͢Δ SNPηοτʹରͯ͠ಛఆͷσʔλϕʔεͷςʔϒϧΛ‫ݻ‬ఆͯ͠͠·͏ͱɼσʔλϕʔε΁ͷΞΫηε΍σʔλετϦʔϜͷ‫ʹࢹ؂‬Αͬͯͦͷؔ࿈ੑΛ෼ੳ͞ΕΔ‫ڪ‬Ε͕ੜ͡Δɽස౓෼ੳʹର͢Δ଱ੑΛԼ͛ͣʹޮ཰Խ͢Δํ๏ͱͯ͠ɼ‫ࢉܭ‬΍ॲཧͷखॱͷলུ͕ߟ͑ΒΕΔɽͭ·Γຊདྷͷর߹ର৅ͱग़ձ͏ͱɼҎ߱͸ٖࣅతͳ΍ΓͱΓΛ͢Δ͚ͩͰ࣮ࡍͷ‫ࢉܭ‬Λল͘ͱ͍͏ޮ཰ԽͰ͋Δɽর߹ॲཧ͸ΫϥΠΞϯτɼαʔόͷͲͪΒͰ΋ߦ͏͕ɼαʔόଆʹٖࣅత‫ࢉܭ‬ΛߦΘͤΔʹ͸ͦͷλΠϛϯά΍‫ࢉܭ‬ෛՙͷมԽͳͲ͕ස౓෼ੳͷࡐྉͱͳΔͷͰෳࡶͳ޻෉͕ඞཁʹͳΔɽͦͷͨΊຊ࣮‫Ͱݧ‬͸ΫϥΠΞϯτଆͷ෮߸ॲཧΛল͘͜ͱͰޮ཰ԽΛਤͬͨɽ۩ମతʹ͸ɼຊདྷରԠ͍ͯ͠Δর߹ςʔϒϧ਺ʹؔ͢Δ͖͍͠஋Λઃఆͨ͠ɽ͖͍͠஋Λ௒͑ͨςʔϒϧΛΧ΢ϯτ͠ɼͦͷςʔϒϧ਺͕র߹ςʔϒϧ਺ʹୡ͢ΔͱҎ߱͸෮߸ॲཧΛߦΘͳ͍ɽຊ࣮‫Ͱݧ‬͸ɼຊདྷରԠ͍ͯ͠Δর߹ςʔϒϧ਺͸ 1 Ͱ͋Δɽ·ͨɼ͖͍͠஋͸র߹ SNP ηοτ਺ͱ౳͘͢͠ΔͱɼBloom ϑΟϧλ࡞੒࣌ʹিಥ͕‫͖ͨى‬৔߹ɼಘΒΕΔ഑ྻ൪߸͕ηοτ਺ʹຬͨͳ͘ͳΔͷͰ͜͜Ͱ͸ηοτ਺͔Β 1 ΛҾ͍ͨ஋ʹઃఆͨ͠ɽҎ্ͷ৚݅Ͱɼޮ཰ԽΛՃ͑ͨࡍͷ a, b, c ͷύϥϝʔλΛมԽ࣮ͤͨ͞‫ݧ‬Λߦͬͨɽ࣮‫ݧ‬ͷ݁ՌΛද 2 ʹࣔ͢ɽ஋͸ςʔϒϧ਺ 100ɼSNP ηοτ਺ 5 ͷ৔߹Λ‫ج‬४ͱͨ͠૬ର஋Ͱ͋ΔɽύϥϝʔλͷมԽͱॲཧ࣌ؒͷؔ܎Λௐ΂Δʹ͋ͨΓɼςʔϒϧ਺͓Αͼ਍அ਺ͷมԽʹண໨͢Δͱɼޮ཰Խલͷ࣮‫ͱݧ‬ಉ༷ɼn2 ҎԼͷΦʔμͰ‫͞ࢉܭ‬Ε͍ͯΔɽޮ཰Խલͷ૬ର஋ͱൺ
΂Δͱɼ(100,20) Λআ͍ͨදͷશମͰ‫ڞ‬௨ͯ͠஋͕খ͘͞ͳ͓ͬͯΓɼ෮߸‫ࢉܭ‬ͷলུʹΑͬͯม਺ͷมԽʹΑΓ૿͑Δ‫ࢉܭ‬ද 2 ޮ཰Խ‫ޙ‬ͷ a, b, c ͷύϥϝʔλมԽͱর߹࣌ؒͷ૬ର஋ςʔϒϧ਺ \ SNP ηοτ

51020
16.0

100

1.0

2.9

200

3.4

10.8

52.9

300

7.3

23.7

111.3

400

12.6

41.1

189.4

500

19.2

63.6

221.9

1,000

73.5 251.9 1111.8

ද 3 ޮ཰Խͷఔ౓ [%]ςʔϒϧ਺ \ SNP ηοτ

51020

100

165 187 163200

169 183 168300

172 183 172400

173 186 176500

174 187 233

1,000178 188 180͕࣌ؒॖখ͞Εͨͱ‫͑ݴ‬Δɽ
࣮ࡍʹશମͰͲͷఔ౓ͷޮ཰Խ͕Ͱ͖͍ͯΔ͔Λௐ΂ΔͨΊɼੑೳධՁͰ༻͍Δख๏ʹै͍ɼޮ཰ԽΛਤͬͨ‫ޙ‬ͷ࣌ؒͰલͷ࣌ؒΛׂͬͨ஋ʹ 100 Λֻ͚ͨ஋ [%] Λޮ཰Խͷई౓ͱ͢Δɽ
ද 3 ʹͦͷ݁ՌΛࣔ͢ɽද 3 ΑΓɼ(20,500) ͸ଞͷύϥϝʔλͷ૊߹ͤͱҟͳΓɼͦͷޮ཰Խఔ౓͕େ͖͍ͷͰ‫ܭ‬ଌ্ͷ‫ޡ‬ࠩͱߟ͑Δɽ͜ΕΛআ͍ͨશମͷฏ‫ۉ‬ΛऔΔͱ 176.6 [%] ͱͳΓɼ݁Ռͱͯ͠ɼ෮߸ॲཧলུͷ޻෉͸ޮ཰Խʹ༗ޮͰ͋ͬͨͱ‫͑ݴ‬Δɽ͜͜Ͱɼຊ࣮‫͚͓ʹݧ‬ΔΫϥΠΞϯτͷ෮߸ॲཧͷޮ཰Խͷ޻෉͸֤਍அʹ͓͍ͯর߹൑ఆ͕ཅੑͷςʔϒϧͱग़ձ͏ͱɼͦͷ‫ޙ‬ͷ෮߸ॲཧ͸ߦΘͳ͍ͱ͍͏΋ͷͰ͋ͬͨɽߋʹ࣮‫Ͱݧ‬࢖༻ٖͨ͠ࣅ SNP σʔλʹ͍ͭͯߟ͑Δͱɼ֤਍அͰҰ͚ͭͩর߹൑ఆ͕ཅੑͷςʔϒϧ͕ଘࡏ͢ΔΑ͏ʹ࡞੒ͨ͠ɽͭ·ਤ3ޮ཰Խલ‫Ͱޙ‬ͷর߹࣌ؒͷൺֱ

͋Δ SNP Λར༻࣬͠ප܏޲΍ੜମతಛ௃Λ਍அ͢ΔࡍʹϓϥΠόγʔอ‫ػޢ‬ೳΛඋ͑Δख๏ΛఏҊͨ͠ɽ·ͨ؆қϞσϧΛ࣮૷͠ɼσʔλͷՄมཁૉΛૢ࡞͢Δ͜ͱͰর߹ʹֻ͔Δ࣌ؒΛଌఆ͠ɼߋʹޮ཰ԽͷͨΊͷ޻෉Λߦ͍ൺֱͨ͠ɽࠓ‫ޙ‬͸ɼ·ͣଟ߲ࣜల։ͷߴ଎ΞϧΰϦζϜΛऔΓೖΕɼཧ࿦্ΑΓޮ཰తͳํ๏ͱ‫ࡏݱ‬ͷํ๏ͷॲཧ଎౓Λൺֱ͢Δɽ࣍ʹɼΑΓ༗๬ͳखॱͰαʔόΫϥΠΞϯτϞσϧͰ࣮ߦͰ͖ΔϓϩάϥϜΛ࡞੒͠ɼ࣮ࡍͷ SNP σʔλͰর߹Λߦ͏͜ͱΛ༧ఆ͍ͯ͠ΔɽΓɼ਍அΛશମͰ‫ݟ‬Δͱ൒෼ͷςʔϒϧ਺ͱͷর߹ͰͷΈ෮߸ॲཧ͕ߦΘΕ͓ͯΓɼ݁Ռͱͯ͠ɼ֤਍அͰϥϯμϜʹςʔϒϧͱর߹͍ͯ͘͠Α͏ͳϞσϧͱಉ༷ͷ࣮‫ͨͬ͋Ͱݧ‬ɽҰํɼઌ΄ͲͷੑೳධՁͷख๏ͱ‫ʹٯ‬ɼর߹͕࣌ؒ୹ॖ͞Εͨൺ཰Λ‫ٻ‬ΊΔͨΊɼޮ཰Խ‫ޙ‬ͷর߹࣌ؒΛલͷর߹࣌ؒͰׂͬͨ΋ͷͷ֎Ε஋Λআ͍ͨฏ‫ۉ‬͸ 0.546 ͱͳͬͨɽ͜ͷ͜ͱΛޮ཰Խͷ޻෉‫ޙ‬ͷ෮߸ॲཧͷςʔϒϧ਺ͱ߹Θͤͯߟ͑Δͱɼ෮߸ॲཧ͕ߦΘΕΔςʔϒϧ਺͕൒෼ʹͳΔͱɼর߹࣌ؒ͸໿ 0.546 ഒʹ୹ॖ͞ΕΔɽͭ·Γɼ‫ͳີݫ‬ධՁͰ͸ͳ͍͕ɼຊߘͰ࣮‫༻ݧ‬ʹॻ͔ΕͨϓϩάϥϜͰ͸෮߸ॲཧ͸ॲཧશମͷ 45% ఔ౓ʹ૬౰͢Δͱߟ͑ΒΕΔɽ࠷‫ʹޙ‬ɼޮ཰Խલͱ‫ޙ‬ͷর߹࣌ؒΛંΕઢάϥϑͰൺֱͨ͠
΋ͷΛਤ 3 ʹࣔ͢ɽάϥϑதͷ 6 ຊͷંΕઢ͸ɼ਍அͰ࢖༻͢Δ SNP ਺Λ‫ݻ‬ఆͨ͠ࡍͷςʔϒϧ਺ͷมԽʹର͢Δর߹࣌ؒͷมԽΛද͢ɽ·ͨɼ਺ࣈʹϓϥΠϜ͕෇͍ͨํ͕ޮ཰Խ‫ޙ‬ͷর߹࣌ؒͰ͋Δɽ

6. ͓ Θ Γ ʹຊߘͰ͸ɼ֎෦ʹҕୗͨ͠σʔλϕʔεΛ༻͍ɼ‫ݸ‬ਓ৘ใͰจ‫ݙ‬[1] M. Blanton and M. Aliasgari, Secure outsourcing of DNAsearching via finite automata, Proc. of the Data and Applications Security and Privacy XXIV (LNCS 6166), pp.
49–64, 2010.
[2] K. B. Frikken, Practical private DNA string searching andmatching through efficient oblivious automata evaluation,
Proc. of the Data and Applications Security and Privacy
XXIII (LNCS 5645), pp. 81–94, 2009.
[3] M. J. Freedman, K. Nissim, and B. Pinkas, Efficient private matching and set intersection, EUROCRYPT, pp. 1–19, 2004.
[4] H. Hacigümüs, B. Iyer, C. Li, and S. Mehrotra, ExecutingSQL over encrypted data in the database-service-provider
model, Proc. of the 2002 ACM SIGMOD Int’l Conf. on
Management of Data, pp. 216–227, 2002.
[5] S. Jha, L. Kruger, and V. Shmatikov, Towards practicalprivacy for genomic computation, Proc. of the IEEE Symposium on Security and Privacy, pp. 216–230, 2008.
[6] ࢈‫ٕۀ‬ज़૯߹‫ॴڀݚ‬, ൿີ‫ʹࢉܭ‬ΑΔԽ߹෺σʔλϕʔεͷ‫ٕࡧݕ‬ज़, http://www.aist.go.jp/aist_j/press_release/pr2011/pr20111101/pr20111101.html.