Secret sharing

Secret Sharing is een methode van gegevensversleuteling die het mogelijk maakt om (binnen een groep personen/systemen) gegevens slechts beschikbaar te maken indien voldoende sleutelhouders samenwerken. Zo kan bijvoorbeeld een contract zo worden versleuteld dat de sleutels van een minimaal drie uit de groep van alle sleutels -zeg zes- voldoende is om de inhoud te ontsleutelen. Men spreekt in dit geval van een zogenaamd '(3,6)-threshold scheme'.

Eenvoudige methoden voor secretsharing worden ook vaak aangeduid als secretsplitting, hierbij wordt de boodschap gesplitst met simpele methoden als het schrijven van de boodschap als som van de deelsleutels, of met behulp van een op het one-time-pad gelijkend proces verdelen van 'het geheim'. Bij secretsplitting wordt het geheim dus ondergebracht in delen, die allemaal bij elkaar moeten worden gebracht om de boodschap te ontcijferen. Gaat een deel verloren dan is ook de boodschap verloren. In deze zin is secret sharing anders, slechts een gedeelte van de versleutelde berichten is voldoende voor de reconstructie. In de loop der tijd is een aantal methoden bedacht om secretsharing te implementeren.

Een door Adi Shamir bedachte methode maakt gebruik van een Lagrange-polynoom, voor een (m,n)-threshold toepassing wordt een polynoom gekozen van graad (m-1). Voor een drie uit zes versleuteling gebruikt men dus een tweedegraadspolynoom.

V ( x ) = a 1 x 2 + a 2 x + B   m o d   p {\displaystyle V(x)=a_{1}x^{2}+a_{2}x+B~mod~p}

Hierin is B de boodschap, en p een priem, groot en onraadbaar. Constanten a₁ en a₂ zijn alleen voor het genereren van de versleutelde boodschap belangrijk, ook zij dienen aselect te zijn gekozen en geheim te blijven. De versleutelde versies bekomt men uit de evaluatie van de polynoom voor het gewenste aantal willekeurige waarden van x. Voor een drie uit zes schema worden zes uitkomsten van V(x) bepaald, bijvoorbeeld voor x waarden {1,2,3,4,5,6}.

Voor het ontsleutelen zijn drie van deze uitkomsten voldoende om een stelsel van drie vergelijkingen op te lossen en B -en in feite dus ook de constanten a₁ en a₂- te herkrijgen.

Deze methode gebruikt matrices op een manier analoog aan de polynoommethode.

Een ander type secretsharing bedacht door Blackley is de vectormethode. De wiskunde hierachter is simpel, en kan makkelijkst worden uitgelegd aan de hand van een voorbeeld; Gegeven een groep van 15 personen; Hoe gegevens te versleutelen zodat deze slechts vrijkomen als 3 personen samenwerken?

Stel de unieke ontsleutelde versie van de gegevens voor als een punt in het driedimensionaal vlak. Dit punt is het unieke snijpunt van 3 vlakken alfa, beta en gamma. Indien elke persoon een vergelijking krijgt van een van deze vlakken, dan ontstaat bij het samenleggen een stelsel met 3 onbekenden en 3 vergelijkingen. Oplossen van dit stelsel resulteert in voornoemd uniek punt. Verscheidene variaties zijn mogelijk indien men gebruikmaakt van multidimensionale ruimten.

De secretsharingtechnieken hierboven kunnen worden uitgebreid door niet één, maar twee of meer sleutels uit te delen aan een persoon. Hierdoor kan een hiërarchie worden opgebouwd zodat veel complexere autorisatieschema's kunnen worden gebruikt. Andere technieken bieden bijvoorbeeld bescherming tegen 'sabotage' door insiders, waarbij iemand -ongedetecteerd- het uitpakken van de boodschap kan verhinderen door een onzinsleutel in te leveren.