Verifiable secret sharing and applications

De vraag wie je kunt vertrouwen, is essentieel voor iedere persoon in elke situatie, maar is van het grootste belang als veiligheid vereist is. Er zijn veel voorbeelden waar zelfs welbekende, betrouwbare partijen kwaadwillend worden. De motieven kunnen verschillen,maar het uiteindelijke resultaat is steeds hetzelfde: zij kunnen niet langer vertrouwd worden. Een bekende oplossing voor dit probleem, vooral als de belangen groot zijn, is om in plaats van je vertrouwen aan ´e´en (betrouwbare) instantie te schenken, je vertrouwen te verdelen over een groep van instanties. Dit moet dan zo gedaan worden dat bepaalde, wel gedefinieerde groepen in staat zijn een handeling uitte voeren, maar kleinere, mogelijk kwaadwillende deelgroeperingen geen schade kunnen betrokkenen aan het systeem. Er zijn verschillende bekende cryptografische ideeen die de vraag hoe vertrouwen te delen aan de orde stellen. We noemen hier secret sharing schema’s (schema’s die geheimen delen), controleerbare secret sharing schema’s en multi-party berekeningen (berekeningen met meerdere partijen).Shamir en Blakley hebben onafhankelijk van elkaar secret sharing schema’s ontwikkeld als een instrument om een geheim te beschermen; hierbij deelt de zgn. gever het geheim over de spelers. Het delen wordt op een zodanige manier uitgevoerd dat alleen bepaalde welomschreven deelgroepen van de spelers in staat zijn het geheim te reconstrueren, terwijl kleinere deelgroepen absoluut geen informatie over het geheim hebben. Een krachtigere versie, die controleerbare secret sharing schema’s heet, is bestand tegen corrupte spelers. Multi-party berekeningen vormen een bouwsteen die een groep van deelnemers,ieder met geheime invoer, in staat stelt een berekening uit te voeren op al die invoer,maar op een dusdanige manier dat ieder van hun het resultaat van die berekening verwerft maar niets anders. In theorie zou elke invoer over een geheim kanaal naar een betrouwbare partij gestuurd kunnen worden, die dan het gewenste resultaat berekent en dat weer terugstuurt naar alle deelnemers. Het doel van multi-party berekeningen is de spelers de berekening te laten uitvoeren zonder die betrouwbare partij en tegelijkertijd de veiligheid van dit theoretische model in stand te houden, zelfs als sommige deelnemers oneerlijk worden.Dit proefschrift bestaat uit twee delen. In het eerste deel beschrijven we grondbegrippen en -beginselen, zoals een toegangsstructuur, tegenstandersstructuur en secret sharing schema’s. Dan worden lineaire secret sharing schema’s ingevoerd door middel van het equivalente algebraische concept van monotone span programs. Het laatste hoofdstuk behandelt controleerbare secret sharing schema’s die garanderen dat het delenbestand is tegen oneerlijke spelers en die dit zelfs kunnen ontdekken en corrigeren.Deze eigenschappen maken controleerbare secret sharing schema’s een gewilde bouwsteen in meer geavanceerde protocollen.Het tweede deel is gewijd aan diverse toepassingen van de technieken van het eerste deel. Proactieve controleerbare secret sharing schema’s worden ontworpen voor een krachtigere tegenstander dan in de gewone secret sharing schema’s, namelijk een mobiele tegenstander die in staat is om in verloop van de tijd te bewegen over de spelers met dien verstande dat er op elk gegeven tijdstip een beperking is aan het aantal onder zijn controle staande spelers. Vervolgens wordt aangetoond hoe een proactief secret sharing schema gebruikt kan worden om een opgedeeld sleutelverdeelcentrum te ontwerpen. Andere toepassingen van secret sharing schema’s zijn afmeet schema’s en opgedeelde oblivious transfer. In het laatste hoofdstuk beschrijven we een van de meest geavanceerde algoritmes in de cryptografie, namelijk multi-party berekeningen.