Asmuth-Bloom-schema

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 juni 2014; kontroller kräver 4 redigeringar .

Asmuth-Bloom- schemat är ett hemligt delningsschema med tröskelvärden byggt med primtal . Låter dig dela hemligheten (numret) mellan parterna på ett sådant sätt att alla deltagare kan återfå den. $n$ $m$

Beskrivning

Låt vara en hemlighet att dela. Välj ett primtal större än . Tal som är relativt primtal till varandra väljs , så att: $M$ $sid$ $M$ $n$ ${\displaystyle d_{1},d_{2},\dots ,d_{n))$

$\forall i:d_{i}>p$
$\forall i:d_{i}<d_{i+1}$
${\displaystyle d_{1}*d_{2}*\dots d_{m}>p*d_{n-m+2}*d_{n-m+3}*\dots *d_{n))$

Ett slumpmässigt tal väljs och beräknas $r$

M'=M+rp

Andelar beräknas:

{\displaystyle k_{i}=M'\mod d_{i))

Deltagare ges ${\displaystyle \left\{p,d_{i},k_{i}\right\))$

Nu, med hjälp av den kinesiska restsatsen , är det möjligt att återställa hemligheten genom att ha och fler aktier. $M$ $m$

Exempel

Anta att vi behöver dela hemligheten mellan fyra deltagare på ett sådant sätt att tre av dem kan återfå denna hemlighet (och två deltagare kunde inte). Det vill säga, det är nödvändigt att implementera ett (3,4)-tröskelsystem. $M=2$

Som ett primtal väljer vi , som coprime - . Vi kontrollerar att: $p=3$ $11,13,17,19$

$\forall i:d_{i}>p$ $\forall i:i\in \{11,13,17,19\},i>p=3$
${\displaystyle d_{1}<d_{2}<d_{3}<d_{4))$ $11<13<17<19$
${\displaystyle d_{1}*d_{2}*\dots d_{m}>p*d_{n-m+2}*d_{n-m+3}*\dots *d_{n))$ ${\displaystyle d_{1}*d_{2}*d_{3}>p*d_{3}*d_{4))$ $11*13*17>3*17*19$

Välj ett slumpmässigt tal och beräkna: $r=51$

M'=M+rp=2+51*3=155

Vi beräknar andelarna:

{\displaystyle k_{i}=M'\mod d_{i))

k_{1}=155\mod 11=1

k_{2}=155\mod 13=12

k_{3}=155\mod 17=2

k_{4}=155\mod 19=3

Låt oss nu försöka återställa den ursprungliga hemligheten, med aktierna , , . Låt oss göra ett ekvationssystem: $\left\{3,11,1\right\}$ $\left\{3,13,12\right\}$ $\left\{3,17,2\right\}$

1=M'\mod 11

12=M'\mod 13

2=M'\mod 17

Vi kan återhämta oss med den kinesiska restsatsen . $M'$

Att veta , vi återfinner hemligheten. $M'$

M\equiv M'\mod p

M\equiv 155\mod 3\equiv 2

I detta exempel (sedan 155<17*19) återställer två deltagare tyst hemligheten. M' måste vara större än produkten av andelar från obehöriga deltagare.

Ett generaliserat Asmuth–Bloom-schema i en polynomring i flera variabler

Betrakta en polynomring i flera variabler över ett Galois-fält . Låt någon monomiell ordning fastställas. Då är reduktionen av ett polynom modulo ett ideal unikt definierad. Låta vara nolldimensionella ideal och vara några polynom. Då är påståendet sant: jämförelsesystemet $\mathbb {F} _{q}[X]$ $X=(x_{1},\cdots ,x_{n})$ $\mathbb {F} _{q}$ ${\displaystyle I_{1},I_{2},\cdots ,I_{t))$ $s_{1}(X),s_{2}(X),\cdots ,s_{t}(X)\in \mathbb {F} _{q}[X]$

{\begin{cases}c(X)&\equiv s_{1}(X)\ {\bmod {\ }}I_{1}\\c(X)&\equiv s_{2}(X )\ {\bmod {\ }}I_{2}\\&\vdots \\c(X)&\equiv s_{t}(X)\ {\bmod {\ }}I_{t}\\\end {fall}}

är antingen inkonsekvent eller har en unik lösning modulo minsta gemensamma multipel (LCM) av ideal . I fallet när idealen är parvis coprime, dvs. , vi har den generaliserade kinesiska restsatsen, och systemets lösning finns alltid. ${\displaystyle I_{1},I_{2},\cdots ,I_{t))$ $I_{i}+I_{j}=1,\forall i\neq j$

Överväg först en generalisering av Mignotte - systemet . Hemligheten kommer att vara något polynom , deltagaren får en modul och en partiell hemlighet . För att implementera åtkomststrukturen är det nödvändigt och tillräckligt att hemligheten reduceras modulo LCM av ideal från vilken som helst tillåten delmängd av deltagare och inte är sådan för förbjudna delmängder. $C(X)$ $i$ $I_i$ $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ $C(X)$

I det generaliserade Asmuth-Bloom-schemat finns det en extra modul och hemligheten är . I detta schema kallas det en mellanliggande hemlighet. $I_0$ $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ $C(X)$

Perfektion av schemat

Ett hemligt delningsschema kallas perfekt om den förbjudna delmängden av deltagare inte får någon ytterligare information om hemligheten, förutom a priori. Med andra ord förblir distributionen av hemligheten enhetlig även i närvaro av partiella hemligheter för deltagare från den förbjudna delmängden. Asmuth-Bloom-schemat, till skillnad från Mignotte-schemat, kan vara perfekt.

För att utveckla ett kriterium för perfektion undersöker vi Asmuth-Bloom-schemat i ringen . Beteckna med mängden monomials reducerad modulo , och med den linjära spännvidden av . Låt också $\mathbb {F} _{q}[X]$ $RT(I)$ $jag$ $RP(I)$ $RT(I)$

I^{B}={\mbox{HOK}}[I_{i},i\in B],\ M_{2}=\bigcap _{B\in \Gamma }RT(I^{B })

är uppsättningen av monomialer som ligger i skärningspunkten mellan idealen för alla tillåtna delmängder. Observera att den mellanliggande hemligheten . $RT$ $C(X)\in RP(M_{2})$

Sats. Asmuth-Bloom-schemat i en ring är perfekt om och bara om följande villkor är uppfyllda: $\mathbb {F} _{q}[X]$

1) .

I_{0}+I_{i}=1,\forall i\in J

2) .

{\displaystyle \forall A\notin \Gamma :RT(I^{A}I_{0})\subseteq M_{2))

Bevis.

Behöver. Låt det finnas ett perfekt Asmuth-Bloom-schema, men det första villkoret i satsen är inte uppfyllt, dvs. Sedan kan uppsättningen av möjliga hemliga värden för en sådan deltagare begränsas: . Därför är schemat ofullkomligt - vi fick en motsägelse. $\exists I_{i}:I_{i}+I_{0}=D\neq 0$ $c(X)\equiv s_{i}(X)\ {\bmod {\ }}D$

Låt det första villkoret vara uppfyllt, men det andra inte, det vill säga det finns en förbjuden delmängd så att . Det finns med andra ord en monomial . Tänk på polynomet $A$ $RT(I^{A}I_{0})\not \subset M_{2}$ $m\in RT(I^{A}I_{0})\backslash M_{2}$

g(X)=s^{A}(X)+(mm({\bmod {I}}^{A}))=s^{A}(X)+f_{m}(X) ,

var är den delade partiella hemligheten som återhämtats av deltagarna från delmängden . $s^{A}(X)$ $A$

Observera att polynomet då uppfyller följande villkor: $f_{m}(X)$

ett)

f_{m}(X)\in I^{A}

f_{m}(X)\in RP(I^{A}I_{0})

3) Innehåller monomialen .

m

Därför, . Låt . Enligt den kinesiska restsatsen, för systemet $g(X)\in RP(I^{A}I_{0})$ $c'=g(X)\ {\bmod {\ }}I_{0}$

{\begin{cases}C(X)\equiv s^{A}(X)\ {\bmod {\ }}I^{A}\\C(X)\equiv c'(X)\ {\bmod {\ }}I_{0}\\\end{cases}}

det finns en unik lösning i , men till sin konstruktion är denna lösning ett polynom . Å andra sidan, , vilket betyder att värdet för hemligheten är omöjligt - återigen fick vi en motsägelse. $RP(I^{A}I_{0})$ $g(X)$ $m\in g(X)\notin RP(M_{2})$ $c'(X)$

Lämplighet. Låt villkoren för satsen vara uppfyllda. Låt oss visa att hemligheten förblir jämnt fördelad i närvaro av partiella hemligheter från den förbjudna delmängden. Betrakta en godtycklig förbjuden delmängd och mängden polynom $A\notin\Gamma$

{\displaystyle V=\{s^{A}(X)+f(X)|f(X)\in I^{A},f(X)\i LP(M_{2})\))

är uppsättningen av möjliga värden för den mellanliggande hemligheten.

Låt oss fixa något värde på hemligheten . Sedan finns det ett unikt polynom , så att enligt den kinesiska restsatsen $c^{j}(X)\in RP(I_{0})$ $g^{j}(X)\in LP(I^{A}I_{0})$

g^{j}(X)\equiv s^{A}(X)\ {\bmod {\ }}I^{A}

g^{j}(X)\equiv c^{j}(X)\ {\bmod {\ }}I_{0}

Tänk nu på 2 fall:

1) Om , då motsvarar varje hemligt värde en enda mellanliggande hemlighet från mängden , dvs. hemligheten förblir jämnt fördelad i närvaro av partiella hemligheter från delmängden . $RT(I^{A}I_{0})=M_{2}$ $V$ $A$

2) Låt sedan . Till varje polynom som innehåller minst ett monom från , associerar vi polynomet ${\displaystyle RT(I^{A}I_{0})\subset M_{2))$ $f(X)\in RP(M_{2})$ $M_{2}\setminus RT(I^{A}I_{0})$

{\overline {f))(X)=f(X)-f(X)\ {\bmod {\ }}RT(I^{A}I_{0})\neq 0

Det är uppenbart att . Då motsvarar varje hemligt värde en uppsättning mellanliggande hemligheter ${\overline {f}}(X)\in I^{A}I_{0}$ $c^{j}(X)\in RP(I_{0})$

C^{j}=\{g^{j}(X),g^{j}(X)+{\overline {f}}(X)|{\overline {f}}(X) \in I^{A}I_{0},{\overline {f}}(X)\in RP(M_{2})\}\subset V

Uppenbarligen är uppsättningarna likvärdiga. Därför finns det i uppsättningen för varje värde av hemligheten samma antal möjliga värden för den mellanliggande hemligheten, vilket innebär en enhetlig fördelning av hemligheten även i närvaro av partiella hemligheter från den förbjudna delmängden. ${\displaystyle C^{j))$ $V$

Teoremet har bevisats.

Litteratur

Schneier B. Asmuth-Bloom-schema // Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code i C. - M . : Triumph, 2002. - S. 589-590. — 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .
Asmuth C. , Bloom J. Ett modulärt tillvägagångssätt för nyckelskydd // IEEE Trans . inf. Theory / F. Kschischang - IEEE , 1983. - Vol. 29, Iss. 2. - P. 208-210. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056651
Shenets N. N. Om idealiska modulära hemlighetsdelningsscheman i polynomringar i flera variabler // International Congress on Informatics: Information Systems and Technologies : material of the International Scientific Congress 31 okt. - Minsk : BGU , 2011. - V. 1. Artiklar från fakulteten för tillämpad matematik och informatik. - S. 169-173. — ISBN 978-985-518-563-6
Stinson, D. R. Kryptografi: teori och praktik. - Chapman och Hall/CRC, 2005. - P. 512. - ISBN 978-1584885085 .