Sikker distribueret beregning

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. Verdens første større anvendelse af sikker MPC fandt sted i Danmark i januar 2008 som beskrevet af Bogetoft et al.[1].

Fodnoter

  1. ^ Peter Bogetoft and Dan Lund Christensen and Ivan Damgård and Martin Geisler and Thomas Jakobsen and Mikkel Krøigaard and Janus Dam Nielsen and Jesper Buus Nielsen and Kurt Nielsen and Jakob Pagter and Michael Schwartzbach and Tomas Toft: Multiparty Computation Goes Live, Cryptology ePrint Archive: Report 2008/068

Eksterne links

  • The Fairplay Project – en pakke med sikker to-parts beregning i fuld skala (baseret på et funktionsbeskrivelsessprog). anvender sikker boosk boolean kredsløbsevaluering.
  • The SIMAP project Arkiveret 7. marts 2016 hos Wayback Machine; Secure Information Management and Processing (SIMAP) er et forskningprojekt som gennemføres med støtte fra Forskningsstyrelsens programkomite or Nanovidenskab og –teknologi, Bioteknologi og IT (NABIIT).
  • Secure Multiparty Computation Language – et projekt som udvikler domænespecifikke sprog for sikre distribuerede beregninger ovenpå et kryptografisk runtimesystem.
  • VIFF: Virtual Ideal Functionality Framework Arkiveret 5. februar 2008 hos Wayback Machine – et framework til asynkronedistribuerede beregninger (kildekode tilgængelige under GPL). Tilbyder aritmetik på delte hemmeligheder herunder sammenligning.