:strip_icc():strip_exif()/u/12461/crop65b195553d948.jpg?f=community)
Dit is een wat meer theoretische vraag waarin ik me voor de lol gewoon in aan het verdiepen ben.
Ik kwam erop vanwege deze stackexchange post. De vraag daar is hoe je het best een bitcoin wallet seed kan verdelen over N plekken/mensen, waarbij er tenminste K deelsleutels nodig zijn om de seed te recoveren. Even ter achtergrond, dit doe je bijvoorbeeld om je wallet seed (die toegang geeft tot al je coins) veilig te verdelen over verschillende plekken, zodat je niet alles kwijt bent op het moment dat een deel verloren raakt, en een dief ook niet aan de haal kan gaan met slechts 1 deel. Met een 2-out-of-3 verdeling verdeel je de seed dus over 3 plekken, waarbij er tenminste 2 nodig zijn om de juiste informatie te reconstrueren.
Welnu, het gaat me niet zozeer om dat specifieke probleem en ik ben bekend met Shamir Secret Sharing om dat probleem op te lossen. In het antwoord waarnaar ik zojuist verwees wordt een alternatief voor SSS aangedragen, namelijk het verzinnen van een aantal sets van K-1 random deelsleutels dmv een one time pad, die samen met het berekende K'e deel het geheim onthullen (bijvoorbeeld door de boel bij elkaar te XOR'en). In de betreffende post wordt uitgegaan van S combinaties van K mensen uit in totaal N (met S = (NK) = N! / K! / (N-K)!), waarbij je dus S sets van K deelsleutels maakt die je uitdeelt aan iedere combinatie van mensen.
In het geval van 2-out-of-3, dus K=2 en N=3, dan heb je dus 3 personen: P1, P2 en P3, en in totaal 3 combinaties van 2 personen: { P1, P2 }, { P1, P3 }, { P2, P3 }. Voor elke combinatie maak je twee deelsleutels Ai en Bi, die je uitdeelt aan de mensen in elke combinatie.
Hier is duidelijk te zien dat elke combinatie van 2 mensen hun eigen set met deelsleutels krijgt, waardoor er dus 3 sets nodig zijn. Echter, dit is niet de meest efficiente oplossing. Het kan ook met 2:
In dit specifieke voorbeeld hoeft P3 niet eens A1 te weten, maar laten we dat negeren want het is wel handig dat hij die A1 heeft op het moment dat er een P4 bij komt. Want voor K=2 is gemakkelijk aan te tonen dat het aantal sets dat je nodig hebt gelijk is aan S = ⌈2log N⌉. Het patroon dat ontstaat is het welbekende bitpatroon. Je kunt het aantal personen verdubbelen door simpelweg de huidige verdeling 2x te herhalen, en dan het eerste deel alleen A te geven van een extra set, en het tweede deel alleen B.
Voorbeeld:
Wat hier gebeurt is natuurlijk vrij simpel te beschrijven. Elk groepje van twee krijgt zijn twee deelsleutels A en B uit de eerste set. Om ervoor te zorgen dat twee paren die samen een kwartet vormen ook altijd kunnen combineren, maak je een extra set waarbij de twee in het eerste paar beide A krijgen, en de andere beide B. Op die manier kunnen elke twee willekeurige mensen uit het kwartet met elkaar combineren. Dat een stapje verder naar een octet, door het eerste kwartet een A te geven van een nieuwe set sleutels, en het tweede kwartet een B. Dit kun je blijven herhalen, en elke keer wordt de groep 2x zo groot. Voor 2 uit de N mensen heb je dus ⌈2log N⌉ sets nodig.
En nu gaan we een beetje richting mijn vraag: wat nu als K=3. Elke set heeft dan natuurlijk 3 deelsleutels, A, B en C. In hetzelfde stackexchange topic staat een post die voorborduurt op de eerdere aangehaalde post en komt met een voorbeeld van 3-out-of-5. Er zijn dan 10 combinaties van mensen mogelijk, en hij komt dan ook met een oplossing die 10 sets van deelsleutels vereist, waarbij elke persoon 6 deelsleutels krijgt.
Hieraan is al snel te zien dat dit veel efficienter kan door dubbelen te collapsen. Zo krijgen P1 en P2 allebei resp. de A en de B van sets 1, 2 en 3. Dan kun je daar ook wel 1 set van maken, door P4 en P5 ook een C1 te geven ipv resp. een C2 en een C3. Deze reductiemethode kun je blijven herhalen totdat er zoiets uitkomt:
Tadaa, in totaal zijn er maar 3 sets nodig.
Hier ontstaat ook meteen een mooi patroon. Zie die diagonaal van de B. En inderdaad, dit idee is uit te breiden naar elke N. Het schaalt echter lineair ipv logaritmisch: S = N - 2.
Ik heb een programmaatje geschreven dat zoekt naar de minimale S gegeven K en N. Hieruit blijkt dat bovenstaande oplossing niet efficienter kan voor N=4 en N=5. Maar het zou ook betekenen dat bij N=6 je 4 sets nodig hebt, en dat is dus niet zo. Hier is een gevonden oplossing voor N=6 met 3 sets:
Verder blijkt dat voor N=7 t/m 9 er minimaal 4 sets nodig zijn. Hier is de oplossing voor N=9
Ik heb verder een oplossing voor N=10 met 5 sets, maar ik heb nog niet bewezen dat het niet kan met 4 sets; hij staat nog te rekenen. Ik vermoed echter dat dat niet mogelijk is.
Welnu, dan mijn daadwerkelijke vragen:
Wat is een systematische manier om een oplossing met minimale S te construeren bij willekeurige N bij K=3?
En in het verlengde daarvan, kun je dat doortrekken naar een willekeurige K?
Ik kwam erop vanwege deze stackexchange post. De vraag daar is hoe je het best een bitcoin wallet seed kan verdelen over N plekken/mensen, waarbij er tenminste K deelsleutels nodig zijn om de seed te recoveren. Even ter achtergrond, dit doe je bijvoorbeeld om je wallet seed (die toegang geeft tot al je coins) veilig te verdelen over verschillende plekken, zodat je niet alles kwijt bent op het moment dat een deel verloren raakt, en een dief ook niet aan de haal kan gaan met slechts 1 deel. Met een 2-out-of-3 verdeling verdeel je de seed dus over 3 plekken, waarbij er tenminste 2 nodig zijn om de juiste informatie te reconstrueren.
Welnu, het gaat me niet zozeer om dat specifieke probleem en ik ben bekend met Shamir Secret Sharing om dat probleem op te lossen. In het antwoord waarnaar ik zojuist verwees wordt een alternatief voor SSS aangedragen, namelijk het verzinnen van een aantal sets van K-1 random deelsleutels dmv een one time pad, die samen met het berekende K'e deel het geheim onthullen (bijvoorbeeld door de boel bij elkaar te XOR'en). In de betreffende post wordt uitgegaan van S combinaties van K mensen uit in totaal N (met S = (NK) = N! / K! / (N-K)!), waarbij je dus S sets van K deelsleutels maakt die je uitdeelt aan iedere combinatie van mensen.
In het geval van 2-out-of-3, dus K=2 en N=3, dan heb je dus 3 personen: P1, P2 en P3, en in totaal 3 combinaties van 2 personen: { P1, P2 }, { P1, P3 }, { P2, P3 }. Voor elke combinatie maak je twee deelsleutels Ai en Bi, die je uitdeelt aan de mensen in elke combinatie.
P1: A1, A2 P2: B1, A3 P3: B2, B3
Hier is duidelijk te zien dat elke combinatie van 2 mensen hun eigen set met deelsleutels krijgt, waardoor er dus 3 sets nodig zijn. Echter, dit is niet de meest efficiente oplossing. Het kan ook met 2:
P1: A1, A2 P2: B1, A2 P3: A1, B2
In dit specifieke voorbeeld hoeft P3 niet eens A1 te weten, maar laten we dat negeren want het is wel handig dat hij die A1 heeft op het moment dat er een P4 bij komt. Want voor K=2 is gemakkelijk aan te tonen dat het aantal sets dat je nodig hebt gelijk is aan S = ⌈2log N⌉. Het patroon dat ontstaat is het welbekende bitpatroon. Je kunt het aantal personen verdubbelen door simpelweg de huidige verdeling 2x te herhalen, en dan het eerste deel alleen A te geven van een extra set, en het tweede deel alleen B.
Voorbeeld:
P1: A1 -> P1: A1, A2 -> P1: A1, A2, A3
P2: B1 P2: B1, A2 P2: B1, A2, A3
P3: A1, B2 P3: A1, B2, A3
P4: B1, B2 P4: B1, B2, A3
P5: A1, A2, B3
P6: B1, A2, B3
P7: A1, B2, B3
P8: B1, B2, B3Wat hier gebeurt is natuurlijk vrij simpel te beschrijven. Elk groepje van twee krijgt zijn twee deelsleutels A en B uit de eerste set. Om ervoor te zorgen dat twee paren die samen een kwartet vormen ook altijd kunnen combineren, maak je een extra set waarbij de twee in het eerste paar beide A krijgen, en de andere beide B. Op die manier kunnen elke twee willekeurige mensen uit het kwartet met elkaar combineren. Dat een stapje verder naar een octet, door het eerste kwartet een A te geven van een nieuwe set sleutels, en het tweede kwartet een B. Dit kun je blijven herhalen, en elke keer wordt de groep 2x zo groot. Voor 2 uit de N mensen heb je dus ⌈2log N⌉ sets nodig.
En nu gaan we een beetje richting mijn vraag: wat nu als K=3. Elke set heeft dan natuurlijk 3 deelsleutels, A, B en C. In hetzelfde stackexchange topic staat een post die voorborduurt op de eerdere aangehaalde post en komt met een voorbeeld van 3-out-of-5. Er zijn dan 10 combinaties van mensen mogelijk, en hij komt dan ook met een oplossing die 10 sets van deelsleutels vereist, waarbij elke persoon 6 deelsleutels krijgt.
P1: A1, A2, A3, A4, A5, A6 P2: B1, B2, B3, A7, A8, A9 P3: C1, B4, B5, B7, B8 A10 P4: C2, C4, B6, C7, B9, B10 P5: C3 C5, C6, C8, C9, C10
Hieraan is al snel te zien dat dit veel efficienter kan door dubbelen te collapsen. Zo krijgen P1 en P2 allebei resp. de A en de B van sets 1, 2 en 3. Dan kun je daar ook wel 1 set van maken, door P4 en P5 ook een C1 te geven ipv resp. een C2 en een C3. Deze reductiemethode kun je blijven herhalen totdat er zoiets uitkomt:
P1: A1, A2, A3 P2: B1, A2, A3 P3: C1, B2, A3 P4: C1, C2, B3 P5: C1, C2, C3
Tadaa, in totaal zijn er maar 3 sets nodig.
Hier ontstaat ook meteen een mooi patroon. Zie die diagonaal van de B. En inderdaad, dit idee is uit te breiden naar elke N. Het schaalt echter lineair ipv logaritmisch: S = N - 2.
Ik heb een programmaatje geschreven dat zoekt naar de minimale S gegeven K en N. Hieruit blijkt dat bovenstaande oplossing niet efficienter kan voor N=4 en N=5. Maar het zou ook betekenen dat bij N=6 je 4 sets nodig hebt, en dat is dus niet zo. Hier is een gevonden oplossing voor N=6 met 3 sets:
P1: A1, A2, A3 P2: A1, B2, B3 P3: B1, A2, C3 P4: B1, C2, B3 P5: C1, B2, C3 P6: C1, C2, A3
Verder blijkt dat voor N=7 t/m 9 er minimaal 4 sets nodig zijn. Hier is de oplossing voor N=9
P1: A1, A2, A3, A4 P2: B1, B2, B3, A4 P3: C1, C2, C3, A4 P4: B1, C2, A3, B4 P5: B1, A2, C3, C4 P6: C1, A2, B3, B4 P7: A1, C2, B3, C4 P8: A1, B2, C3, B4 P9: C1, B2, A3, C4
Ik heb verder een oplossing voor N=10 met 5 sets, maar ik heb nog niet bewezen dat het niet kan met 4 sets; hij staat nog te rekenen. Ik vermoed echter dat dat niet mogelijk is.
Welnu, dan mijn daadwerkelijke vragen:
Wat is een systematische manier om een oplossing met minimale S te construeren bij willekeurige N bij K=3? En in het verlengde daarvan, kun je dat doortrekken naar een willekeurige K?
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
/u/249034/arrow.png?f=community){kind=icon}