Pille Pullonen-Raudvere kaitseb doktoritööd „Foundations of efficient and secure algorithm development for secure multiparty computation“
13. augustil kell 13.00 kaitseb Pille Pullonen-Raudvere informaatika erialal doktoritööd „Foundations of efficient and secure algorithm development for secure multiparty computation“ („Turvalise ühisarvutuse kiire ja turvalise algoritmiarenduse alused“).
Juhendajad:
kaasprofessor Sven Laur, Tartu Ülikool
Dan Bogdanov, Cybernetica AS
Oponendid:
kaasprofessor Mayank Varia, Bostoni Ülikool (USA)
kaasprofessor Bernardo Machado David, Kopenhaageni IT Ülikool (Taani)
Kokkuvõte
Turvaline ühisarvutus on meetod, mille abil on võimalik kasutada poolte privaatseid andmeid nii, et neist sisendite privaatsust säilitades saada ühiseid tulemusi. Intuitiivselt tagab turvalisus selle, et sisendite kohta ei leki muud kui planeeritud arvutuse tulemus ning arvutamise meetod on alati korrektne. Turvalise ühisarvutuse jaoks on olemas erinevaid krüptograafilisi protokolle, mis võimaldavad kas konkreetseid arvutusi teha või defineerivad meetodi, et arvutada kõikvõimalikke algoritme. Doktoritöö keskendub just sellele viimasele juhule, mida võime nimetada ka programmeeritavaks turvaliseks ühisarvutuseks. Eri pooled saavad anda oma privaatseid sisendeid ja ühiselt defineerida algoritmi, mida nende sisendite peal rakendatakse. On ka võimalik, et järgmised arvutussammud sõltuvad vahepeal saadud tulemustest.
Kui teoreetiliselt on võimalik teha kõiki arvutusi, on kriitiline õigesti mõtestada, mida turvalisus selles kontekstis tähendab. Alati on vaja läbi mõelda, kas see väljund, mis arvutustest tuleb, on ikkagi see, mida soovitakse ja mis on lubatud. Samuti on vaja tagada, et arvutusprotsessi käigus ei lekiks rohkem informatsiooni, kui see väljund annab. Just teine küsimus algoritmi leketest on selle töö fookuses.
Klassikaline meetod algoritmi turvalisuse tõestamisel põhineb sellel, et algoritmi tööd on võimalik simuleerida, teades vaid korrumpeeritud pooltele kättesaadavaid sisendeid ja väljundeid. Loogika on, et kui algoritmi käiku saab sedasi jäljendada, ei saa need pooled saada algoritmi jooksutamise ajal rohkem informatsiooni, kui neile niikuinii on arvutuse käigus ette nähtud. Formaalselt defineeritakse ideaalne funktsionaalsus, mis kujutab endast algoritmi turvadefinitsiooni. Töö defineerib turvalise ühisarvutuse jaoks kanoonilise ideaalse funktsionaalsuse, mis kogub kokku kõik sisendid, arvutab soovitud funktsiooni ning tagastab väljundi vastavatele pooltele. Nii sisend- kui ka väljundandmed võivad olla kuidagi salastatud. Sellisel juhul eemaldab ideaalne funktsionaalsus kõigepealt privaatsuskaitse ning arvutab seejärel tulemuse ning rakendab väljundile ettenähtud privaatsuskaitset. Programmeeritav turvalise ühisarvutuse raamistik koosneb paljudest protokollidest ning andmete turvaliselt hoiustamise viisidest. Näiteks võivad andmed olla ühissalastatud või krüpteeritud ja neil võib, aga ei pruugi olla terviklikkuse kaitse. Töös defineeritakse erinevad omadused, mis turvalise arvutuse raamistikul võivad olla, ning seejärel kasutatakse üldistatud formalisatsiooni, et arutleda algoritmide omaduste üle.
Turvalise arvutamise raamistik ise defineerib üldiselt palju olulisi alusprotokolle, näiteks liitmise ja korrutamise, millest omakorda saab ehitada keerukaid algoritme. Paljud algoritmid on lihtsad ja opereerivad ainult salastatud andmetega ning garanteerivad, et nende käigus midagi ei leki. Teisalt annavad paljud teised algoritmid kas avalikke väljundeid või avalikustavad töö käigus vahetulemusi, mistõttu vajab nende turvalisus detailset analüüsi ka siis, kui algoritm ise kasutab turvalisi komponente, et arvutusi teha. See töö vaatleb eraldi kahte algoritmi disainil ettetulevat juhtu. Esiteks seda, et vahel on võimalik suuremas algoritmis kasutada komponente, mis tagavad küll sisendite privaatsuse ent pole turvalised. Teiseks seda, kuidas tõestada algoritmi turvalisust nii, et saaks keskenduda huvitavamatele osadele ning palju formaalseid detaile oleksid automaatselt tagatud.
Kanoonilise ideaalse funktsionaalsuse definitsiooni järgi saavad turvalised olla ainult protokollid, mis tagavad, et väljund on värskelt salastatud. Samas on tegelikkuses võimalik defineerida protokolle, millel seda omadust ei ole, kuid mis samas oma sisendite kohta midagi ei leki. Töös nimetatakse selliseid protokolle sisendi privaatsust säilitavateks protokollideks. Selle protokolli väljundid on alati kas privaatsed või ei sõltu protokolli sisenditest. Kui kõik sisendi privaatsust säilitava protokolli väljundid on omakorda sisendid mõne turvalise protokolli jaoks ning komponeeritud protokolli väljundid tulevad kõik turvalisest protokollist, on ka komponeeritud protokoll turvaline. Lisaks on mitmest sisendi privaatsust säilitavast protokollist komponeeritud protokoll omakorda ka sisendi privaatsust säilitav. Seetõttu on võimalik sisendi privaatsust säilitavaid protokolle algoritmide arenduses kasutada. See aga on kasulik, sest sellised protokollid võivad olla nii lihtsamad disainida kui ka efektiivsemad kasutada.
Turvalisuse korrektne formaalne tõestamine on üldiselt keerukas ja nõuab paljude detailide läbimõtlemist. Teisalt on paljude algoritmide puhul üsna lihtne sõnastada intuitiivset põhjust, miks nad on turvalised. Näiteks eelnevast kirjeldusest käis läbi idee, et algoritm kasutab ainult salastatud andmeid ilma midagi avalikustamata ning kõik arvutused tehakse protokollidega, mille turvalisus on juba eelnevast teada. Teises doktoritöö osas tegeletaksegi sellega, et defineerida abstraktne mudel, milles on võimalik teha intuitsioonile hästi vastavaid tõestusi. Need tõestused keskenduvad sellele, milliseid avalikustatud andmeid protokolli käigus näha võib olla. Abstraktne mudel ja detailne formaalne mudel protokolli jooksutamisest on samaväärsed paljude turvalise ühisarvutuse raamistike jaoks. Töös defineeritakse erinevaid omadusi, mis peavad kas raamistiku või protokolli jaoks kehtima, et samaväärsus kehtiks. Seeläbi kaardistatakse töös ka eeldusi, mis turvalisest ühisarvutusest rääkides sageli implitsiitselt tehakse.