MOSIF: Modeller og Teknikker til Sikre Flerepartsberegninger

Den stigende brug af internettet stiller nye krav til udviklingen af sikre programmer, som bl.a. skal yde en effektiv beskyttelse af vores private information, såsom pin-koder og sundhedsinformation, og tillade os at bevare kontrol over de digitale aktiviteter som vi ønsker kun selv at kunne udføre, såsom hævning på vores konti via web-bank. Den kryptografiske protokolteori beviste i 1980'erne at alt hvad man kan forestille sig at gøre på internettet også kan gøres sikkert, i det mindste i teorien. MOSIF-projektets hovedmål er at udvikle den kryptografiske protokolteorien henimod et stadie, hvor vi kan udmønte denne teori i praktiske værktøjer, som tillader automatisk, nemt og billigt at løse et vilkårligt sikkerhedsproblem alene ud fra en beskrivelse af hvad problemet er.


Kryptografisk Protokolteori

"Alt hvad der kan gøres på internettet kan også gøres sikkert på internettet!" Sådan lyder en af hovedkonklusionerne fra forskningen i den såkaldte kryptografisk protokolteori. Dette opmuntrende resultat har været kendt siden 1980'erne, hvor det blev opdaget af et internationalt samarbejde som havde forskere fra datalogisk institut ved Århus universitet som centrale bidragsydere. Resultatet gav desværre ikke umiddelbart udslag i praktisk anvendelige værktøjer, da de var af en meget teoretisk natur.

Forskere ved Århus universitet var med til op gennem 90'erne og 00'erne at publicere flere resultater som indikerede at 1980'ernes teori kunne blive fremtidens praksis, og et af MOSIF-projektets hovedmål er at bidrage til at udvikle protokolteorien til et punkt hvor den bidrager med praktiske værktøjer.

Det ultimative mål for projektets forskning er at udvikle såkaldte sikre protokolkompilere, som er computerprogrammer der bruger en beskrivelse af en opgave som input og producerer en sikker protokol der løser den beskrevne opgave som output. Sikre protokolkompilere ville dramatisk reducerer omkostningerne forbundet med at udvikle sikre protokoller, da en protokoludvikler efter at havde beskrevet et sikkerhedsproblem automatisk vil kunne få genereret en færdig protokol der løser problemet. I dag er udviklingen af sikre protokoller en tidskrævende opgave som kræver programmører med et indgående kendskab til protokolteori.

I protokolteorien har vi i dag til en lang række protokol-byggeklodser, kendt under så eksotiske navne som secret sharing, zero-knowledge beviser, commitment schemes og oblivious transfer. Vi kender desuden til flere bud på hvordan man med disse byggeklodser kan konstruere sikre protokoller. Disse konstruktioner er generelle, og virker for en vilkårligt opgave. Der er dog en del praktiske problemer i vejen for at bruge disse konstruktioner i praksis. Dels er de versioner af byggeklodserne som et sikre nok til at kunne bruges på internettet typisk meget ineffektive, dels ville de kendte generelle konstruktioner, selv hvis byggeklodserne havde været gode, i sig selv være ret ineffektive.

En realisering af praktiske sikre protokolkompilere kræver derfor både en forbedring af kendte byggeklodser, opfindelsen af nye effektive byggeklodser og en udvikling af nye effektive generelle konstruktioner af protokoller. MOSIF-projektets primære fokus er på en sådan grundforskning i protokolteori.

Protokol: En protokol til løsning af en opgave på internettet består af et computerprogram til hver af deltagerne i opgaven (fx banken og brugerne i en web-bank løsning) samt en beskrivelse af hvordan disse computerprogrammer kommunikerer sammen.

Sikker protokol: En sikker protokol er en protokol som bl.a. beskytter deltagernes data og kun tillader de rette deltagere at tilgå protokollens muligheder.

Eksempel: Secret Sharing

En vigtig byggeklods i protokolteorien er secret sharing, som tillader en deltager at lade en hemmelig værdi indgå i en beregning foretaget sammen med andre deltagere, uden at disse andre parter lærer noget om hemmeligheden.

Vi kan forestille os tre deltagere Astrid, Bo og Charles som hver kender et hemmelig beløb, fx. 42, 117 hhv. 27. Opgaven er at beregne summen (186) af disse beløb uden at de hemmelige beløb røbes.

Astrid vælger to tilfældige beløb, som er meget større end hendes hemmelighed, lad os sige 73541 og 17463. Så sender hun 73541 sikkert til Bo og sender 17463 sikkert til Charles. Lokalt gemmer hun -90962, der er beregnet som 42-73541-17463 (hendes hemmelige beløb minus de to tilfældige beløb). De tre store tal som nu gemmes af deltagerne kaldes hemmelige dele af Astrids hemmelighed. Bemærk at summen af de hemmelige dele naturligvis er lig hemmeligheden: 73541+17463+(-90962) = 42. Pointen er at de hemmelige dele som Bo og Charles modtog intet røber om Astrids hemmelige værdi 42, da disse hemmelige dele jo var tilfældigt valgte.

På samme måde uddeler Bo og Charles hemmelige dele af deres hemmelige beløb uden at røbe beløbet. Lad os fx. sige at Bo vælger tilfældige tal 43457 og 36842 som han sender til Astrid henholdsvis Charles og selv gemme tallet -80182 = 117-43457-36842, hvorved Bos input er repræsenterer som 117=43457+(-80182)+36842, og lad os sige at Charles vælger tilfældige tal 28376 og 41465 som sendes til Astrid og Bo og dermed selv gemmer -69814 = 27-28376-41465, så hans input er repræsenterer som 27=28376+41466+(-69814).

Indtil nu er det lykkedes alle tre parter at får deres input gjort klart til brug uden at lække nogen information om deres inputs.

Nu lægger hver af parterne så deres hemmelige dele sammen og får dermed en hemmelig del af resultatet. Alice holder fx. den hemmelige del -90962 af sit eget input, den hemmelige den 43457 af Bos input og den hemmelige den 28376 af Charles' input. Hun lægger disse hemmelige dele sammen og får en hemmelig del -19129 = (-90962) + 43457 + 28376 af resultatet. Bo og Charles beregner på lignende vis hemmelige del 34824 henholdsvis -15509 af resultatet.

Nu offentligøres så de hemmelige dele af resultatet, og ved at lægge dem sammen finder alle deltagere den ønskede værdi, da -19129+34824+(-15509)=186. Dette er naturligvis ikke et tilfælde, men et resultat af at det er lige meget i hvilken rækkefølge man lægge en mængde tal sammen. Det kan desuden bevises at offentliggørelsen af de hemmelige dele af resultatet ikke røber noget om de hemmelige beløb, 42, 117 og 27. Dvs., deltagerene har nu beregnet det samlede beløb uden at røbe de enkelte hemmelige beløb.

Hvis deltagerne vil beregne noget mere avanceret end lige summen af deres hemmelige værdier, så bliver protokollen meget mere kompleks, men en vilkårlig beregning på hemmelige værdier er mulig i teorien. Det er altså muligt at lade sin private information indgår i en kompleks beregning uden at man behøver offentligegøre sin private information.