Schema Asmuth-Bloom

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 24 iunie 2014; verificările necesită 4 modificări .

Schema Asmuth-Bloom este o schemă de partajare secretă de prag , construită folosind numere prime . Vă permite să împărtășiți secretul (numărul) între părți, astfel încât orice participant să îl poată recupera. $n$ $m$

Descriere

Să fie un secret de împărtășit. Alegeți un număr prim mai mare decât . Sunt alese numere relativ prime între ele , astfel încât: $M$ $p$ $M$ $n$ $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))$

Se alege și se calculează un număr aleatoriu $r$

M'=M+rp

Acțiunile se calculează:

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

Se acordă participanților ${\displaystyle \stânga\{p,d_{i},k_{i}\dreapta\))$

Acum, folosind teorema chineză a restului , este posibil să recuperați secretul deținând și mai multe acțiuni. $M$ $m$

Exemplu

Să presupunem că trebuie să împărtășim secretul între patru participanți în așa fel încât oricare trei dintre ei să poată recupera acest secret (și doi participanți nu au putut). Adică, este necesară implementarea unei scheme de prag (3,4). $M=2$

Ca număr prim, alegem , ca coprim - . Verificăm că: $p=3$ $11,13,17,19$

$\forall i:d_{i}>p$ $\forall i:i\in \{11,13,17,19\},i>p=3$
$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$

Alegeți un număr aleatoriu și calculați: $r=51$

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

Calculăm cotele:

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

Acum să încercăm să restabilim secretul inițial, având acțiunile , , . Să facem un sistem de ecuații: $\stanga\{3,11,1\dreapta\}$ $\stanga\{3,13,12\dreapta\}$ $\stanga\{3,17,2\dreapta\}$

1=M'\mod 11

12=M'\mod 13

2=M'\mod 17

Ne putem recupera folosind teorema chineză a restului . $M'$

Știind , recuperăm secretul. $M'$

M\equiv M'\mod p

M\equiv 155\mod 3\equiv 2

În acest exemplu (de la 155<17*19) doi participanți vor restabili secretul în liniște. M' trebuie să fie mai mare decât produsul acțiunilor participanților neautorizați.

O schemă generalizată Asmuth–Bloom într-un inel polinomial în mai multe variabile

Considerăm un inel polinomial în mai multe variabile peste un câmp Galois . Să fie fixată o ordine monomială. Atunci reducerea unui polinom modulo un ideal este definită în mod unic. Fie idealuri zero-dimensionale și niște polinoame. Atunci afirmația este adevărată: sistemul de comparații $\mathbb {F} _{q}[X]$ $X=(x_{1},\cdots,x_{n})$ $\mathbb {F} _{q}$ $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 {cazuri}}

este fie inconsecventă, fie are o soluție unică modulo cel mai mic multiplu comun (LCM) de idealuri . În cazul în care idealurile sunt coprime perechi, adică , avem teorema generalizată a restului chineză, iar soluția sistemului există întotdeauna. $I_{1},I_{2},\cdots,I_{t)$ $I_{i}+I_{j}=1,\forall i\neq j$

Luați în considerare mai întâi o generalizare a schemei Mignotte . Secretul va fi un polinom , participantului i se acordă un modul și un secret parțial . Pentru a implementa structura de acces, este necesar și suficient ca secretul să fie redus modulo LCM de idealuri de la orice subset permis de participanți și să nu fie astfel pentru subseturile interzise. $C(X)$ $i$ $eu_i$ $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ $C(X)$

În schema generalizată Asmuth-Bloom, există un modul suplimentar , iar secretul este . În această schemă , se numește secret intermediar. $I_0$ $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ $C(X)$

Perfecțiunea schemei

O schemă de partajare a secretelor este numită perfectă dacă subsetul interzis de participanți nu primește informații suplimentare despre secret, cu excepția a priori. Cu alte cuvinte, distribuția secretului rămâne uniformă chiar și în prezența secretelor parțiale ale participanților din subsetul interzis. Schema Asmuth-Bloom, spre deosebire de schema Mignotte, poate fi perfectă.

Pentru a dezvolta un criteriu de perfecțiune, examinăm schema Asmuth-Bloom din ring . Se notează prin mulțimea de monomii reduse modulo , și prin intervalul liniar al . Lasa si $\mathbb {F} _{q}[X]$ $RT(I)$ $eu$ $RP(I)$ $RT(I)$

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

este mulțimea de monomii care se află în intersecția idealurilor tuturor submulților permise. Rețineți că secretul intermediar . $RT$ $C(X)\in RP(M_{2})$

Teorema. Schema Asmuth-Bloom într-un inel este perfectă dacă și numai dacă sunt îndeplinite următoarele condiții: $\mathbb {F} _{q}[X]$

1) .

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

2) .

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

Dovada.

Nevoie. Să existe o schemă Asmuth-Bloom perfectă, dar prima condiție a teoremei nu este îndeplinită, adică . Apoi setul de posibile valori secrete pentru un astfel de participant poate fi restrâns: . Prin urmare, schema este imperfectă - avem o contradicție. $\exists I_{i}:I_{i}+I_{0}=D\neq 0$ $c(X)\equiv s_{i}(X)\ {\bmod {\ }}D$

Fie ca prima condiție să fie îndeplinită, dar a doua nu, adică există o submulțime interzisă astfel încât . Cu alte cuvinte, există un monom . Luați în considerare polinomul $A$ $RT(I^{A}I_{0})\nu \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) ,

unde este secretul parțial partajat recuperat de către participanți din subset . $s^{A}(X)$ $A$

Rețineți că polinomul îndeplinește următoarele condiții: $f_{m}(X)$

unu)

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

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

3) Conține monomul .

m

Prin urmare, . Lasă . Conform teoremei chineze a restului, pentru sistem $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}}

există o soluție unică în , dar prin construcție această soluție este un polinom . Pe de altă parte, , ceea ce înseamnă că valoarea secretului este imposibilă - din nou avem o contradicție. $RP(I^{A}I_{0})$ $g(X)$ $m\in g(X)\notin RP(M_{2})$ $c'(X)$

Adecvarea. Fie îndeplinite condițiile teoremei. Să arătăm că secretul rămâne uniform distribuit în prezența secretelor parțiale din subsetul interzis. Luați în considerare o submulțime interzisă arbitrară și mulțimea de polinoame $A\notin\Gamma$

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

este setul de valori posibile ale secretului intermediar.

Să stabilim o anumită valoare a secretului.Atunci există un polinom unic , astfel încât, conform teoremei chineze a restului $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}

Luați în considerare acum 2 cazuri:

1) Dacă , atunci fiecare valoare secretă corespunde unui singur secret intermediar din set , i.e. secretul rămâne uniform distribuit în prezența secretelor parțiale din submult . $RT(I^{A}I_{0})=M_{2}$ $V$ $A$

2) Lasă atunci . Fiecărui polinom care conține cel puțin un monom din , asociem polinomul $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

Este evident că . Apoi fiecare valoare secretă corespunde unui set de secrete intermediare ${\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

Evident, seturile sunt echivalente. Prin urmare, în setul pentru fiecare valoare a secretului există același număr de valori posibile ale secretului intermediar, ceea ce implică o distribuție uniformă a secretului chiar și în prezența secretelor parțiale din subsetul interzis. $C^{j)$ $V$

Teorema a fost demonstrată.

Literatură

Schneier B. Schema Asmuth-Bloom // Criptografie aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - S. 589-590. — 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .
Asmuth C. , Bloom J. O abordare modulară a protejării cheilor // IEEE Trans . inf. Teorie / 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. On ideal modular secret sharing schemes in polynomial rings in several variables // Congresul Internațional de Informatică: Sisteme și Tehnologii Informaționale : materiale ale Congresului Științific Internațional 31 oct. - Minsk : BGU , 2011. - V. 1. Articole ale Facultății de Matematică Aplicată și Informatică. - S. 169-173. — ISBN 978-985-518-563-6
Stinson, D. R. Criptografia: teorie și practică. - Chapman și Hall/CRC, 2005. - P. 512. - ISBN 978-1584885085 .