Sikker distribueret beregning

Fra Wikipedia, den frie encyklopædi

Sikker distribueret beregning (eng. secure multiparty computation, MPC) er en særlig disciplin inden for kryptologien, der beskæftiger sig med beregninger, hvor flere parter samarbejder, men de enkelte parter ikke ønsker at afsløre deres input for de andre.

Problemstillingen blev oprindeligt introduceret en artikel af Andrew C. Yao i 1982. I artiklen introduceredes millionærproblemet: Alice og Bob er to millionærer, der ønsker at finde ud af hvem der er den rigeste, men ikke vil afsløre deres formue. Yao foreslog en løsning, der tillader Alice og Bob at stille deres nysgerrighed, samtidig med at begrænsningerne respekteres. Problemstillingen og løsningen banede vejen for en generalisering med navnet multiparty computation (MPC) protokoller.

I en MPC har vi N deltagere p1, p2, ..., pN, der hver har private data, der kaldes henholdsvis d1, d2, ..., dN. Deltagerne ønsker at beregne værdien af en offentligt kendt funktion F af de N variable. En MPC protokol kaldes sikker hvis ingen deltager kan få mere at vide, end denne kan slutte ud fra kendskab til sit eget bidrag, beskrivelsen af funktionen og resultatet af beregningen (under specifikke betingelser afhængig af den anvendte model).

Som mange andre kryptografiske protokoller, kan sikkerheden af en MPC protokol være af beregningsnatur (dvs. baseret på et matematisk problem som faktorisering), eller ubetinget (som regel med en fejlsandsynlighed der kan gøres vilkårligt lille). Metoden beskrives i en model hvori deltagerne anvender et synkroniseret netværk, med sikre kommunikationskanaler mellem hvert par af deltagere (en modstander kan ikke læse, ændre eller skabe besker i kanalen), osv... Den centralt kontrollerede modstander kan være passiv (dvs. kan kun læse data fra et vist antal deltagere) eller aktiv (kan forstyrre udførelsesprotokollen eller et vist antal deltagere). En modstander kan være statisk (vælger sin ofre før start af beregningen) eller dynamisk (kan vælge sine ofre under udførelse af beregningen). At opnå sikkerhed over for en dynamisk modstander er ofte langt sværere end mod en statisk. En modstander kan være defineret som en tærskel struktur (eng.threshold structure, dvs. denne kan læse hukommelsen hos et antal deltagere op til en vis grænse), eller den kan defineres som en mere kompleks sktruktur (f.eks. påvirke en forudbestemt delmængde af deltagere, som model for forskellige mulige sammansværgelser).

Sikker distribueret beregning er tæt forbundet med problemstillingen Secret Sharing (deling af hemmeligheder), og mere specifikt verificérbar secret sharing (eng. verifiable secret sharing VSS); enhver MPC protokol anvender en VSS.

Sikker MPC giver løsninger til forskellige problemer fra det virkelige liv, som f.eks. distribueret stemmeafgivning, private budgivning og auktioner, deling af signatur- eller krypteringsfunktioner, privat informationssøgning, osv.

[redigér] Eksterne links

• Helger Lipmaa's links om distribueret beregning
• The Fairplay Project — en pakke med sikker to-parts beregning i fuld skala (baseret på et funktionsbeskrivelsessprog). anvender sikker boosk boolean kredsløbsevaluering.