Homomorfisk hemlighetsdelning

Inom kryptografi är homomorf hemlighetsdelning en typ av hemlig delningsalgoritm där hemligheten krypteras via homomorf kryptering . En homomorfism är en transformation från en algebraisk struktur till en annan av samma typ så att strukturen bevaras. Viktigt är att detta betyder att för varje typ av manipulation av originaldata finns det en motsvarande manipulation av den transformerade datan.

Metod

Homomorf hemlighetsdelning används för att överföra en hemlighet till flera mottagare enligt följande:

  1. Förvandla "hemligheten" med en homomorfism. Detta sätter ofta hemligheten i en form som är lätt att manipulera eller lagra. I synnerhet kan det finnas ett naturligt sätt att "dela upp" det nya formuläret som krävs i steg (2).
  2. Dela upp den förvandlade hemligheten i flera delar, en för varje mottagare. Hemligheten måste delas på ett sådant sätt att den bara kan återställas när alla eller de flesta delarna är kombinerade. (Se Hemlig delning .)
  3. Dela ut hemlighetens delar till var och en av mottagarna.
  4. Kombinera var och en av mottagarnas delar för att återställa den förvandlade hemligheten, kanske vid en viss tidpunkt.
  5. Vänd om homomorfismen för att återställa den ursprungliga hemligheten.

Exempel

Anta att ett samhälle vill genomföra ett val med hjälp av ett decentraliserat röstningsprotokoll, men de vill se till att rösträknarna inte ljuger om resultatet. Genom att använda en typ av homomorfisk hemlighetsdelning som kallas Shamirs hemliga delning , kan varje medlem av communityn lägga till sin röst i ett formulär som är uppdelat i bitar, varje del skickas sedan till en annan rösträknare. Bitarna är designade så att rösträknarna inte kan förutsäga hur eventuella ändringar av varje bit kommer att påverka helheten, vilket avskräcker rösträknare från att manipulera sina bitar. När alla röster har mottagits slår rösträknarna samman dem, så att de kan återfå det sammanlagda valresultatet.

Anta i detalj att vi har ett val med:

  • Två möjliga resultat, antingen ja eller nej . Vi kommer att representera dessa utfall numeriskt med +1 respektive −1.
  • Ett antal myndigheter, k , som ska räkna rösterna.
  • Ett antal väljare, n , som kommer att lämna röster.
  1. I förväg genererar varje myndighet en allmänt tillgänglig numerisk nyckel, x k .
  2. Varje väljare kodar sin röst i ett polynom p n enligt följande regler: Polynomet ska ha graden k − 1 , dess konstanta term ska vara antingen +1 eller −1 (motsvarande att rösta "ja" eller rösta "nej"), och dess andra koefficienter bör genereras slumpmässigt.
  3. Varje väljare beräknar värdet av sitt polynom p n vid varje myndighets publika nyckel x k .
    • Detta ger k poäng, en för varje myndighet.
    • Dessa k punkter är "delarna" av rösten: Om du känner till alla punkter kan du räkna ut polynomet p n (och därmed kan du räkna ut hur väljaren röstade). Men om du bara känner till några av punkterna kan du inte räkna ut polynomet. (Detta beror på att du behöver n punkter för att bestämma ett grad- ( n − 1) polynom. Två punkter bestämmer en linje, tre punkter bestämmer en parabel, etc.)
  4. Väljaren skickar till varje myndighet det värde som tagits fram med hjälp av myndighetens nyckel.
  5. Varje myndighet samlar in de värden som han får. Eftersom varje myndighet bara får ett värde från varje väljare, kan han inte upptäcka någon given väljares polynom. Dessutom kan han inte förutsäga hur en förändring av bidragen kommer att påverka omröstningen.
  6. När väljarna har lämnat in sina röster, beräknar varje myndighet k och tillkännager summan A k av alla värden han har fått.
  7. Det finns k summor, A k ; när de kombineras bestämmer de ett unikt polynom P ( x ) – specifikt summan av alla väljarpolynom: P ( x ) = p 1 ( x ) + p 2 ( x ) + ... + p n ( x ).
    • Den konstanta termen av P ( x ) är i själva verket summan av alla röster, eftersom den konstanta termen av P ( x ) är summan av de konstanta termerna för den individuella p n .
    • Således ger den konstanta termen P ( x ) det sammanlagda valresultatet: om det är positivt röstade fler på +1 än på −1; om det är negativt röstade fler på −1 än på +1.
A table illustrating the voting protocol
En illustration av röstningsprotokollet. Varje kolumn representerar delarna av en viss väljares röst. Varje rad representerar de pjäser som tagits emot av en viss myndighet.

Funktioner

Det här protokollet fungerar så länge som inte alla k- myndigheter är korrupta – om de var det, skulle de kunna samarbeta för att rekonstruera P ( x ) för varje väljare och även därefter ändra rösterna.

Protokollet kräver att t + 1 auktoriteter är kompletta, därför om det finns N > t + 1 auktoriteter kan N − t − 1 auktoriteter vara korrupta , vilket ger protokollet en viss grad av robusthet.

Protokollet hanterar väljarnas ID (ID:n lämnades in med röstsedlarna) och kan därför verifiera att endast legitima väljare har röstat.

Under antagandena om t :

  1. En omröstning kan inte spåras tillbaka till ID så integriteten för väljarna bevaras.
  2. En väljare kan inte bevisa hur de röstat.
  3. Det är omöjligt att verifiera en röst.

Protokollet förhindrar implicit korruption av valsedlar . Det beror på att myndigheterna inte har några incitament att ändra omröstningen eftersom varje myndighet bara har en del av valsedeln och inte vet hur en förändring av denna andel kommer att påverka resultatet.

Sårbarheter

  • Väljaren kan inte vara säker på att deras röst har registrerats korrekt.
  • Myndigheterna kan inte vara säkra på att rösterna var lagliga och lika, till exempel kan väljaren välja ett värde som inte är ett giltigt alternativ (dvs inte i {−1, 1}) som −20, 50, vilket kommer att luta resultaten i deras tjänst.

Se även

Hämtad från " https://en.wikipedia.org/w/index.php?title=Homomorphic_secret_sharing&oldid=1135147072 "