Hemlig delning med den kinesiska restsatsen

Hemlig delning består av att återställa ett hemligt S från en uppsättning aktier, som var och en innehåller partiell information om hemligheten. Den kinesiska restsatsen (CRT) säger att för ett givet system av samtidiga kongruensekvationer är lösningen unik i vissa $Z / n Z$ , med $n > 0$ under vissa lämpliga förhållanden på kongruenserna. Hemlig delning kan alltså använda CRT för att producera andelarna som presenteras i kongruensekvationerna och hemligheten skulle kunna återvinnas genom att lösa systemet med kongruenser för att få den unika lösningen, som kommer att vara hemligheten att återhämta sig.

Hemliga delningsscheman: flera typer

Det finns flera typer av hemliga delningsscheman . De mest grundläggande typerna är de så kallade tröskelsystemen , där endast uppsättningen aktiers kardinalitet spelar roll. Med andra ord, givet en hemlig S , och n aktier, är varje uppsättning av t- aktier en uppsättning med den minsta kardinalitet från vilken hemligheten kan återvinnas, i den meningen att någon uppsättning av t-1- aktier inte räcker för att ge S . Detta är känt som en tröskelåtkomststruktur . Vi kallar sådana scheman ( t , n ) tröskelhemlighetsdelningsscheman , eller t -out-of- n -schema .

för delning av tröskelhemligheter skiljer sig från varandra genom metoden för att generera aktierna, utgående från en viss hemlighet. De första är Shamirs tröskelhemlighetsdelningsschema , som är baserat på polynominterpolation för att hitta S från en given uppsättning aktier, och George Blakleys geometriska hemlighetsdelningsschema, som använder geometriska metoder för att återställa det hemliga S. Tröskelhemlighetsdelningsscheman baserade på CRT beror på Mignotte och Asmuth-Bloom, de använder speciella sekvenser av heltal tillsammans med CRT .

Kinesisk restsats

Låt ${\displaystyle k\geqslant 2,m_{1},...,m_{k}\geqslant 2} ,$ och $b_{1},...,b_{k}\in \mathbf {Z}$ . Systemet av kongruenser

{\begin{cases}x\equiv &b_{1}\ {\bmod {\ }}m_{1}\\&\vdots \ \x\equiv &b_{k}\ {\bmod {\ }}m_{k}\\\end{cases}}

har lösningar i $Z$ om och bara om $b_{i}\equiv b_{j}{\bmod {(}}m_{i},m_{j} )$ för alla $1\leqslant i,j\leqslant k$ , där $(m_{i},m_{j})$ anger största gemensamma divisor (GCD) av $m i$ och $m j$ . Vidare, under dessa förhållanden, har systemet en unik lösning i $Z / n Z$ där $n=[m_{1},...,m_{k}]$ , som betecknar den minsta gemensamma multipeln (LCM) av $m_{1},...,m_{k}$ .

Hemlig delning med hjälp av CRT

Eftersom den kinesiska restsatsen ger oss en metod för att unikt bestämma ett tal S modulo k - många relativt primtal heltal $m_{1},m_{2},...,m_{k}$ , givet att $S<\prod _{i=1} ^{k}m_{i}}$ , då är tanken att konstruera ett schema som kommer att bestämma hemligheten S givet alla k andelar (i det här fallet, resten av S modulo vart och ett av talen $m i$ ), men kommer inte avslöja hemligheten som ges mindre än k för sådana aktier.

I slutändan väljer vi n relativt primtal heltal $m_{1}<m_{2}<...<m_{n}$ så att S är mindre än produkten av ett val av k av dessa heltal, men samtidigt är större än valfritt val av k-1 av dem. Sedan aktierna $s_{1},s_{2},...,s_{n}$ definieras av $s_{i}=S{\bmod {\ } }m_{i}$ för $i=1,2,...,n$ . På detta sätt, tack vare CRT, kan vi unikt bestämma S från vilken som helst uppsättning av k eller fler andelar, men inte från mindre än k . Detta ger den så kallade tröskelåtkomststrukturen .

Detta villkor på S kan också betraktas som

\prod _{i=n-k+2}^{n}m_{i}<S<\prod _{i=1}^{k}m_{i}.

Eftersom S är mindre än den minsta produkten av k av heltal, kommer den att vara mindre än produkten av någon k av dem. Dessutom, eftersom den är större än produkten av de största $k - 1$ heltal, kommer den att vara större än produkten av någon $k - 1$ av dem.

Det finns två hemliga delningsscheman som i huvudsak använder denna idé, Mignottes och Asmuth-Blooms system, som förklaras nedan.

Mignottes hemliga delningsschema för tröskelvärde

Som tidigare nämnts använder Mignottes hemlighetsdelningsschema för tröskelvärden , tillsammans med CRT, speciella sekvenser av heltal som kallas ( k , n )-Mignotte-sekvenser som består av n heltal, parvis coprime , så att produkten av den minsta k av dem är större än produkten av $k - 1$ största. Detta villkor är avgörande eftersom systemet bygger på att välja hemligheten som ett heltal mellan de två produkterna, och detta villkor säkerställer att minst k aktier behövs för att helt återställa hemligheten, oavsett hur de väljs.

Formellt, låt $2 \leq k \leq n$ vara heltal. En ( k , n )-Mignottesekvens är en strikt ökande sekvens av positiva heltal $m_{1}<\cdots <m_{n}$ , med $(m_{i},m_{j})=1$ för alla $1 \leq i < j \leq n$ , så att $m_{ n-k+2}\cdots m_{n}<m_{1}\cdots m_{k}$ . Låt $\alpha =m_{n-k+2}\cdots m_{n}$ och $\beta =m_{1 }\cdots m_{k}$ ; vi kallar de heltal som ligger strikt mellan $\alpha$ och $\beta$ det auktoriserade området. Vi bygger ett ( k , n )- tröskelhemlighetsdelningsschema enligt följande: Vi väljer det hemliga S som ett slumpmässigt heltal $\alpha <S<\beta$ i det auktoriserade området. Vi beräknar, för varje $1 \leq i \leq n$ , reduktionsmodulo $m i$ för S som vi kallar $s i$ , dessa är andelarna. Nu, för alla k olika andelar ${\displaystyle s_{i_{1}},\ldots ,s_{i_{k}}} ,$ betraktar vi systemet med kongruenser:

{\begin{cases}x\equiv &s_{i_{1}}\ {\bmod {\ }}m_{i_ {1}}\\&\vdots \\x\equiv &s_{i_{k}}\ {\bmod {\ }}m_{i_{k}}\\\end{cases}}

Enligt den kinesiska restsatsen , eftersom $m_{i_{1}},\ldots,m_{i_{k}}$ är parvis coprime , har systemet en unik lösning modulo $m_{i_{1}}\cdots m_{i_{k}}$ . Genom konstruktionen av våra aktier är denna lösning inget annat än det hemliga S att återhämta sig.

Asmuth-Blooms hemliga delningsschema för tröskelvärde

Detta schema använder också speciella sekvenser av heltal. Låt $2 \leq k \leq n$ vara heltal. Vi betraktar en sekvens av parvisa coprime positiva heltal $m_{0}<...<m_{n}$ så att $m_{0}\cdot m_{ n-k+2}\cdots m_{n}<m_{1}\cdots m_{k}$ . För denna givna sekvens väljer vi det hemliga S som ett slumpmässigt heltal i mängden $0 Z / m Z$ .

Vi väljer sedan ett slumpmässigt heltal $α$ så att $S+\alpha \cdot m_{0}<m_{1}\cdots m_{k}$ . Vi beräknar reduktionsmodulen $m i$ för ${\displaystyle S+\alpha \cdot m_{0}} ,$ för alla $1 \leq i \leq n$ , dessa är andelarna $I_{i}=(s_{i},m_{i})$ . Nu, för alla k olika aktier $I_{i_{1}},...,I_{i_{k}}$ , betraktar vi systemet med kongruenser:

${\begin{cases}x\equiv &s_{i_{1}}\ {\bmod {\ }}m_{i_ {1}}\\&\vdots \\x\equiv &s_{i_{k}}\ {\bmod {\ }}m_{i_{k}}\\\end{cases}}$

Enligt den kinesiska restsatsen , eftersom $m_{i_{1}},...,m_{i_{k}}$ är parvis coprime , systemet har en unik lösning $S 0$ modulo $m_ {i_{1}}\cdots m_{i_{k}}$ . Genom konstruktionen av våra aktier är det hemliga S $reduktionsmodulen 0$ för $S 0$ .

Det är viktigt att notera att Mignotte ( k , n ) -tröskelhemlighetsdelningsschemat inte är perfekt i den meningen att en uppsättning av mindre än k aktier innehåller viss information om hemligheten. Asmuth-Bloom-schemat är perfekt: $α$ är oberoende av det hemliga $S$ och

$\left.{\begin{array}{r}\prod _{i=n-k+2}^ {n}m_{i}\\\alpha \end{array}}\right\}<{\frac {\prod _{i=1}^{k}m_{i}}{m_{0}}}$

Därför kan $α$ vara vilket heltalsmodul som helst

\prod _{i=n-k+2}^{n}m_{i}.

Denna produkt av $k - 1$ moduli är den största av någon av de n välj $k - 1$ möjliga produkterna, därför kan varje delmängd av $k - 1$ ekvivalenser vara vilken heltal som helst modulo dess produkt, och ingen information från $S$ läcker.

Exempel

Följande är ett exempel på Asmuth-Blooms schema. För praktiska ändamål väljer vi små värden för alla parametrar. Vi väljer k=3 och n=4 . Våra parvisa coprime heltal är $m_{0}=3,m_{1}=11,m_{2}=13,m_{3 }=17$ och $m_{4}=19$ . De uppfyller den sekvens som krävs för Asmuth-Bloom eftersom $3\cdot 17\cdot 19<11\cdot 13\cdot 17$ .

Säg att vårt hemliga $S$ är 2. Välj ${\displaystyle \alpha =51} ,$ som uppfyller kraven för Asmuth-Bloom-schemat. Sedan $2+51\cdot 3=155$ och vi beräknar andelarna för vart och ett av heltalen 11, 13, 17 och 19. De är respektive 1, 12, 2 och 3. Vi överväga en möjlig uppsättning av 3 andelar: bland de fyra möjliga uppsättningarna av 3 andelar tar vi uppsättningen {1,12,2} och visar att den återställer den hemliga S=2. Tänk på följande system av kongruenser:

{\begin{cases}x\equiv &1\ {\bmod {\ }}11\\x\equiv &12\ {\bmod {\ }}13\\x\equiv &2\ {\bmod {\ }}17\\\end{cases}}

För att lösa systemet, låt $M=11\cdot 13\cdot 17$ . Från en konstruktiv algoritm för att lösa ett sådant system vet vi att en lösning till systemet är $x_{0}=1\cdot e_{1} +12\cdot e_{2}+2\cdot e_{3}$ , där varje $e i$ hittas enligt följande:

Genom Bézouts identitet , eftersom $(m_{i},M/m_{i})=1$ , finns det positiva heltal $r i$ och $s i$ , som kan hittas med hjälp av den utökade euklidiska algoritmen , så att $r_{i}.m_{i}+s_{i}.M/m_{i}=1$ . Ställ $e_{i}=s_{i}\cdot M/m_{i}$ .

Från identiteterna ${\displaystyle 1=1\cdot 1022=1\cdot 1022 -5)\cdot 187+72\cdot 13=5\cdot 143+(-42)\cdot 17} ,$ vi får att $e_{1 }=221,e_{2}=-935,e_{3}=715$ och den unika lösningen modulo $11\cdot 13\cdot 17$ är 155. Slutligen, $S=155\equiv 2\mod 3$ .

Se även

Oded Goldreich , Dana Ron och Madhu Sudan , Chinese Remaindering with Errors, IEEE Transactions on Information Theory, Vol. 46, nr 4, juli 2000, sid 1330-1338.
Mignotte M. (1983) Hur man delar en hemlighet. I: Beth T. (red) Cryptography. EUROCRYPT 1982. Lecture Notes in Computer Science, vol 149. Springer, Berlin, Heidelberg.
CA Asmuth och J. Bloom. Ett modulärt tillvägagångssätt för nyckelskydd. IEEE Transactions on Information Theory, IT-29(2):208-210, 1983.
Sorin Iftene. Allmän hemlighetsdelning baserat på den kinesiska restsatsen med tillämpningar i elektronisk röstning. Electronic Notes in Theoretical Computer Science (ENTCS). Volym 186, (juli 2007). Sidorna 67–84. Utgivningsår: 2007. ISSN 1571-0661 .
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest och Clifford Stein . Introduktion till algoritmer, andra upplagan. MIT Press och McGraw-Hill, 2001. ISBN 0-262-03293-7 . Avsnitt 31.5: Den kinesiska restsatsen, sidorna 873-876.
Ronald Cramer . Grundläggande hemlighetsdelning (föreläsningar 1-2), klassanteckningar. Oktober 2008, version 1.1.

externa länkar

https://web.archive.org/web/20091209071915/http://www.cryptolounge.org/wiki/Ronald_Cramer