Crt китайская теорема об остатках

From Wikipedia, the free encyclopedia

Secret sharing consists of recovering a secret S from a set of shares, each containing partial information about the secret. The Chinese remainder theorem (CRT) states that for a given system of simultaneous congruence equations, the solution is unique in some Z/nZ, with n > 0 under some appropriate conditions on the congruences. Secret sharing can thus use the CRT to produce the shares presented in the congruence equations and the secret could be recovered by solving the system of congruences to get the unique solution, which will be the secret to recover.

Secret sharing schemes: several types[edit]

There are several types of secret sharing schemes. The most basic types are the so-called threshold schemes, where only the cardinality of the set of shares matters. In other words, given a secret S, and n shares, any set of t shares is a set with the smallest cardinality from which the secret can be recovered, in the sense that any set of t-1 shares is not enough to give S. This is known as a threshold access structure. We call such schemes (t,n) threshold secret sharing schemes, or t-out-of-n scheme.

Threshold secret sharing schemes differ from one another by the method of generating the shares, starting from a certain secret. The first ones are Shamir’s threshold secret sharing scheme, which is based on polynomial interpolation in order to find S from a given set of shares, and George Blakley’s geometric secret sharing scheme, which uses geometric methods to recover the secret S. Threshold secret sharing schemes based on the CRT are due to Mignotte and Asmuth-Bloom, they use special sequences of integers along with the CRT.

Chinese remainder theorem[edit]

Let $kgeqslant 2,m_{1},...,m_{k}geqslant 2$ , and $b_{1},...,b_{k}in {mathbf {Z}}$ . The system of congruences

${begin{cases}xequiv &b_{1} {bmod }m_{1}\&vdots \xequiv &b_{k} {bmod }m_{k}\end{cases}}$

has solutions in Z if and only if $b_{i}equiv b_{j}{bmod (}m_{i},m_{j})$ for all , where $(m_{i},m_{j})$ denotes the greatest common divisor (GCD) of m_i and m_j. Furthermore, under these conditions, the system has a unique solution in Z/nZ where $n=[m_{1},...,m_{k}]$ , which denotes the least common multiple (LCM) of $m_{1},...,m_{k}$ .

Secret sharing using the CRT[edit]

Since the Chinese remainder theorem provides us with a method to uniquely determine a number S modulo k-many relatively prime integers , given that $S < prod_{i=1}^k m_i$ , then, the idea is to construct a scheme that will determine the secret S given any k shares (in this case, the remainder of S modulo each of the numbers m_i), but will not reveal the secret given less than k of such shares.

Ultimately, we choose n relatively prime integers $m_{1}<m_{2}<...<m_{n}$ such that S is smaller than the product of any choice of k of these integers, but at the same time is greater than any choice of k-1 of them. Then the shares $s_{1},s_{2},...,s_{n}$ are defined by $s_{i}=S{bmod }m_{i}$ for . In this manner, thanks to the CRT, we can uniquely determine S from any set of k or more shares, but not from less than k. This provides the so-called threshold access structure.

This condition on S can also be regarded as

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

Since S is smaller than the smallest product of k of the integers, it will be smaller than the product of any k of them. Also, being greater than the product of the greatest k − 1 integers, it will be greater than the product of any k − 1 of them.

There are two Secret Sharing Schemes that utilize essentially this idea, Mignotte’s and Asmuth-Bloom’s Schemes, which are explained below.

Mignotte’s threshold secret sharing scheme[edit]

As said before, Mignotte’s threshold secret sharing scheme uses, along with the CRT, special sequences of integers called the (k,n)-Mignotte sequences which consist of n integers, pairwise coprime, such that the product of the smallest k of them is greater than the product of the k − 1 biggest ones. This condition is crucial because the scheme is built on choosing the secret as an integer between the two products, and this condition ensures that at least k shares are needed to fully recover the secret, no matter how they are chosen.

Formally, let 2 ≤ k ≤ n be integers. A (k,n)-Mignotte sequence is a strictly increasing sequence of positive integers $m_{1}<cdots <m_{n}$ , with $(m_{i},m_{j})=1$ for all 1 ≤ i < j ≤ n, such that $m_{{n-k+2}}cdots m_{n}<m_{1}cdots m_{k}$ . Let ${displaystyle alpha =m_{n-k+2}cdots m_{n}}$ and ${displaystyle beta =m_{1}cdots m_{k}}$ ; we call the integers lying strictly between alpha and beta the authorized range. We build a (k,n)-threshold secret sharing scheme as follows: We choose the secret S as a random integer in the authorized range. We compute, for every 1 ≤ i ≤ n, the reduction modulo m_i of S that we call s_i, these are the shares. Now, for any k different shares $s_{{i_{1}}},ldots ,s_{{i_{k}}}$ , we consider the system of congruences:

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

By the Chinese remainder theorem, since $m_{{i_{1}}},ldots ,m_{{i_{k}}}$ are pairwise coprime, the system has a unique solution modulo $m_{{i_{1}}}cdots m_{{i_{k}}}$ . By the construction of our shares, this solution is nothing but the secret S to recover.

Asmuth-Bloom’s threshold secret sharing scheme[edit]

This scheme also uses special sequences of integers. Let 2 ≤ k ≤ n be integers. We consider a sequence of pairwise coprime positive integers $m_{0}<...<m_{n}$ such that ${displaystyle m_{0}cdot m_{n-k+2}cdots m_{n}<m_{1}cdots m_{k}}$ . For this given sequence, we choose the secret S as a random integer in the set Z/m₀Z.

We then pick a random integer α such that ${displaystyle S+alpha cdot m_{0}<m_{1}cdots m_{k}}$ . We compute the reduction modulo m_i of ${displaystyle S+alpha cdot m_{0}}$ , for all 1 ≤ i ≤ n, these are the shares $I_{i}=(s_{i},m_{i})$ . Now, for any k different shares $I_{{i_{1}}},...,I_{{i_{k}}}$ , we consider the system of congruences:

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

By the Chinese remainder theorem, since $m_{{i_{1}}},...,m_{{i_{k}}}$ are pairwise coprime, the system has a unique solution S₀ modulo $m_{{i_{1}}}cdots m_{{i_{k}}}$ . By the construction of our shares, the secret S is the reduction modulo m₀ of S₀.

It is important to notice that the Mignotte (k,n)-threshold secret-sharing scheme is not perfect in the sense that a set of less than k shares contains some information about the secret. The Asmuth-Bloom scheme is perfect: α is independent of the secret S and

$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}}}$

Therefore α can be any integer modulo

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

This product of k − 1 moduli is the largest of any of the n choose k − 1 possible products, therefore any subset of k − 1 equivalences can be any integer modulo its product, and no information from S is leaked.

Example[edit]

The following is an example on the Asmuth-Bloom’s Scheme. For practical purposes we choose small values for all parameters. We choose k=3 and n=4. Our pairwise coprime integers being $m_{0}=3,m_{1}=11,m_{2}=13,m_{3}=17$ and $m_{4}=19$ . They satisfy the Asmuth-Bloom required sequence because .

Say our secret S is 2. Pick , satisfying the required condition for the Asmuth-Bloom scheme. Then and we compute the shares for each of the integers 11, 13, 17 and 19. They are respectively 1, 12, 2 and 3. We consider one possible set of 3 shares: among the 4 possible sets of 3 shares we take the set {1,12,2} and show that it recovers the secret S=2. Consider the following system of congruences:

${begin{cases}xequiv &1 {bmod }11\xequiv &12 {bmod }13\xequiv &2 {bmod }17\end{cases}}$

To solve the system, let . From a constructive algorithm for solving such a system, we know that a solution to the system is $x_{0}=1cdot e_{1}+12cdot e_{2}+2cdot e_{3}$ , where each e_i is found as follows:

By Bézout’s identity, since $(m_{i},M/m_{i})=1$ , there exist positive integers r_i and s_i, that can be found using the Extended Euclidean algorithm, such that $r_{i}.m_{i}+s_{i}.M/m_{i}=1$ . Set ${displaystyle e_{i}=s_{i}cdot M/m_{i}}$ .

From the identities , we get that $e_{1}=221,e_{2}=-935,e_{3}=715$ , and the unique solution modulo is 155. Finally, .

References[edit]

Oded Goldreich, Dana Ron and Madhu Sudan, Chinese Remaindering with Errors, IEEE Transactions on Information Theory, Vol. 46, No. 4, July 2000, pages 1330-1338.
Mignotte M. (1983) How to Share a Secret. In: Beth T. (eds) Cryptography. EUROCRYPT 1982. Lecture Notes in Computer Science, vol 149. Springer, Berlin, Heidelberg.
C.A. Asmuth and J. Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory, IT-29(2):208-210, 1983.
Sorin Iftene. General Secret Sharing Based on the Chinese Remainder Theorem with Applications in E-Voting. Electronic Notes in Theoretical Computer Science (ENTCS). Volume 186, (July 2007). Pages 67–84. Year of Publication: 2007. ISSN 1571-0661.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.5: The Chinese remainder theorem, pages 873-876.
Ronald Cramer. Basic Secret Sharing (Lectures 1-2), Class Notes. October 2008, version 1.1.

External links[edit]

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

Источник

Secret sharing consists of recovering a secret S from a set of shares, each containing partial information about the secret. The Chinese remainder theorem (CRT) states that for a given system of simultaneous congruence equations, the solution is unique in some , with under some appropriate conditions on the congruences.
Secret sharing can thus use the CRT to produce the shares presented in the congruence equations and the secret could be recovered by solving the system of congruences to get the unique solution, which will be the secret to recover.

Secret sharing schemes: several types[]

Main article: Secret sharing

Threshold secret sharing schemes differ from one another by the method of generating the shares, starting from a certain secret. The first ones are Shamir’s threshold secret sharing scheme, which is based on polynomial interpolation in order to find S from a given set of shares, and George Blakley‘s geometric secret sharing scheme, which uses geometric methods to recover the secret S. Threshold secret sharing schemes based on the CRT are due to Mignotte and Asmuth-Bloom, they use special sequences of integers along with the CRT.

Main article: Chinese remainder theorem

Let , ${displaystyle m_{1},...,m_{k}geqslant 2}$ , and ${displaystyle b_{1},...,b_{k}in mathbb {Z} }$ . The system of equations

${displaystyle {begin{cases}xequiv &b_{1} {bmod { }}m_{1}\&.\&.\&.\xequiv &b_{k} {bmod { }}m_{k}\end{cases}}}$

has solutions in if and only if ${displaystyle b_{i}equiv b_{j}{bmod {(}}m_{i},m_{j})}$ for all , where ${displaystyle (m_{i},m_{j})}$ denotes the greatest common divisor (GCD) of ${displaystyle m_{i}}$ and ${displaystyle m_{j}}$ . Furthermore, under these conditions, the system has a unique solution in where ${displaystyle n=[m_{1},...,m_{k}]}$ , which denotes the least common multiple (LCM) of ${displaystyle m_{1},...,m_{k}}$ .

Secret sharing using the CRT[]

Since the Chinese remainder theorem provides us with a method to uniquely determine a number S modulo k many relatively prime integers ${displaystyle m_{1},m_{2},...,m_{k}}$ , given that ${displaystyle S<prod _{i=1}^{k}m_{i}}$ , then, the idea is to construct a scheme that will determine the secret S given any k shares (in this case, the remainder of S modulo each of the numbers ${displaystyle m_{i}}$ ), but will not reveal the secret given less than k of such shares.

Ultimately, we choose n relatively prime integers ${displaystyle m_{1}<m_{2}<...<m_{n}}$ such that S is smaller than the product of any choice of k of these integers, but at the same time is greater than any choice of k-1 of them. Then the shares ${displaystyle s_{1},s_{2},...,s_{n}}$ are defined by ${displaystyle s_{i}=S{bmod { }}m_{i}}$ for . In this manner, thanks to the CRT, we can uniquely determine S from any set of k or more shares, but not from less than k. This provides the so-called threshold access structure.

This condition on S can also be regarded as ${displaystyle prod _{i=n-k+2}^{n}m_{i}<S<prod _{i=1}^{k}m_{i}}$ . Since S is smaller than the smallest product of k of the integers, it will be smaller than the product of any k of them. Also, being greater than the product of the greatest k-1 integers, it will be greater than the product of any k-1 of them.

There are two Secret Sharing Schemes that utilize essentially this idea, Mignotte’s and Asmuth-Bloom’s Schemes, which are explained below.

Mignotte’s threshold secret sharing scheme[]

As said before, Mignotte’s threshold secret sharing scheme uses, along with the CRT, special sequences of integers called the (k,n)-Mignotte sequences which consist of n integers, pairwise coprime, such that the product of the smallest k of them is greater than the product of the k-1 biggest ones. This condition is crucial because the scheme is built on choosing the secret as an integer between the two products, and this condition ensures that at least k shares are needed to fully recover the secret, no matter how they are chosen.

Formally, let be an integer, and k be an integer such that . A (k,n)-Mignotte sequence is a strictly increasing sequence of positive integers ${displaystyle m_{1}<...<m_{n}}$ , with ${displaystyle (m_{i},m_{j})=1}$ for all , such that ${displaystyle m_{n-k+2}...m_{n}<m_{1}...m_{k}}$ . We call this range the authorized range. Now, the scheme works as follows: We build a (k,n)-threshold secret sharing scheme. We choose the secret S as a random integer in the authorized range. We compute, for every , the reduction modulo ${displaystyle m_{i}}$ of S that we call ${displaystyle s_{i}}$ , these are the shares. Now, for any k different shares ${displaystyle s_{i_{1}},...,s_{i_{k}}}$ , we consider the system of congruences:
${displaystyle {begin{cases}xequiv &s_{i_{1}} {bmod { }}m_{i_{1}}\&.\&.\&.\xequiv &s_{i_{k}} {bmod { }}m_{i_{k}}\end{cases}}}$

By the Chinese remainder theorem, since ${displaystyle m_{i_{1}},...,m_{i_{k}}}$ are pairwise coprime, the system has a unique solution modulo ${displaystyle m_{i_{1}}...m_{i_{k}}}$ . By the construction of our shares, this solution is nothing but the secret S to recover.

Asmuth-Bloom’s threshold secret sharing scheme[]

This scheme also uses special sequences of integers. Let be an integer, and k be an integer such that . We consider a sequence of pairwise coprime positive integers ${displaystyle m_{0}<...<m_{k}}$ such that ${displaystyle m_{0}.m_{n-k+2}...m_{n}<m_{1}...m_{k}}$ . For this given sequence, we choose the secret S as a random integer in the set ${displaystyle mathbb {Z} /m_{0}mathbb {Z} }$ .

We then pick a random integer such that ${displaystyle S+alpha .m_{0}<m_{1}...m_{k}}$ . We compute the reduction modulo ${displaystyle m_{i}}$ of ${displaystyle S+alpha .m_{0}}$ , for all , these are the shares ${displaystyle I_{i}=(s_{i},m_{i})}$ . Now, for any k different shares ${displaystyle I_{i_{1}},...,I_{i_{k}}}$ , we consider the system of congruences:

${displaystyle {begin{cases}xequiv &s_{i_{1}} {bmod { }}m_{i_{1}}\&.\&.\&.\xequiv &s_{i_{k}} {bmod { }}m_{i_{k}}\end{cases}}}$

By the Chinese remainder theorem, since ${displaystyle m_{i_{1}},...,m_{i_{k}}}$ are pairwise coprime, the system has a unique solution ${displaystyle S_{0}}$ modulo ${displaystyle m_{i_{1}}...m_{i_{k}}}$ . By the construction of our shares, the secret S is the reduction modulo ${displaystyle m_{0}}$ of ${displaystyle S_{0}}$

It is important to notice that the Mignotte and Asmuth-Bloom (k,n)-threshold secret-sharing schemes are not perfect schemes, in the sense that a set of less than k shares contains some information about the secret. Nevertheless, by a suitable choice of the sequences and the parameters ( in the Asmuth-Bloom case), one can get a reasonable security factor. This is why the Asmuth-Bloom scheme is more secure, for it involves more random parameters.

Example[]

The following is an example on the Asmuth-Bloom’s Scheme. For practical purposes we choose small values for all parameters. We choose k=3 and n=4. Our pairwise coprime integers being ${displaystyle m_{0}=}$ 3, ${displaystyle m_{1}=}$ 11, ${displaystyle m_{2}=}$ 13, ${displaystyle m_{3}=}$ 17 and ${displaystyle m_{4}=}$ 19. They satisfy the Asmuth-Bloom required sequence because .

${displaystyle {begin{cases}xequiv &1 {bmod { }}11\xequiv &12 {bmod { }}13\xequiv &2 {bmod { }}17\end{cases}}}$

To solve the system, let . From a constructive algorithm for solving such a system, we know that a solution to the system is ${displaystyle x_{0}=1cdot e_{1}+12cdot e_{2}+2cdot e_{3}}$ , where each ${displaystyle e_{i}}$ is found as follows:

By Bezout’s identity, since ${displaystyle (m_{i},M/m_{i})=1}$ , there exist positive integers ${displaystyle r_{i}}$ and ${displaystyle s_{i}}$ , that can be found using the Extended Euclidean algorithm, such that ${displaystyle r_{i}.m_{i}+s_{i}.M/m_{i}=1}$ . Set ${displaystyle e_{i}=s_{i}cdot M_{i}/m_{i}}$ .

From the identities , we get that ${displaystyle e_{1}=221,e_{2}=-935,e_{3}=715}$ , and the unique solution modulo is 155. Finally, .

References[]

O. Goldreich, D. Ron and M. Sudan, Chinese Remaindering with Errors, IEEE Transactions on Information Theory, Vol. 46, No. 4, July 2000, pages 1330-1338.
C.A. Asmuth and J. Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory, IT-29(2):208-210, 1983.
Sorin Iftene. General Secret Sharing Based on the Chinese Remainder Theorem with Applications in E-Voting. Electronic Notes in Theoretical Computer Science (ENTCS). Volume 186 , (July 2007). Pages 67–84. Year of Publication: 2007. ISSN:1571-0661.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.5: The Chinese remainder theorem, pages 873-876.
Ronald Cramer. Basic Secret Sharing (Lectures 1-2), Class Notes. October 2008, version 1.1.

External links[]

http://www.cryptolounge.org/wiki/Ronald_Cramer

ru:Схема Миньотта
ru:Схема Асмута — Блума

Источник

Совместное использование секрета с использованием китайской теоремы об остатках — Secret sharing using the Chinese remainder theorem

Секрет разделение состоит из восстановления секрета S из набора общих ресурсов, каждый из которых содержит частичную информацию о секрете. Китайская теорема об остатках (CRT) утверждает, что для данной системы одновременных уравнений сравнения решение является единственным в некотором Z/nZ, с n>0 при некоторых подходящих условиях на сравнения. Совместное использование секрета может, таким образом, использовать CRT для получения долей, представленных в уравнениях сравнения, и секрет может быть восстановлен путем решения системы сравнений для получения уникального решения, которое будет секретом для восстановления.

Содержание

1 Схемы совместного использования секретов: несколько типов
2 Китайская теорема об остатках
3 Совместное использование секрета с использованием CRT
- 3.1 Схема порогового разделения секрета Mignotte
- 3.2 Схема порогового разделения секрета Асмута-Блума
- 3.3 Пример
4 См. Также
5 Ссылки
6 Внешние ссылки

Схемы совместного использования секрета: несколько типов

Существует несколько типов совместного использования секрета схемы. Самыми основными типами являются так называемые схемы пороговых значений, в которых имеет значение только мощность набора общих ресурсов. Другими словами, учитывая секрет S и n общих ресурсов, любой набор из t общих ресурсов является набором с наименьшей мощностью, из которой может быть восстановлен секрет, в том смысле, что любой набор t-1 общих недостаточно для предоставления S. Это известно как пороговая структура доступа. Мы называем такие схемы (t, n) пороговыми схемами разделения секрета или схемой t-out-of-n.

Порог разделения секрета схемы отличаются друг от друга методом генерации общих ресурсов, начиная с определенного секрета. Первые — это пороговая схема совместного использования секрета Шамира, которая основана на полиномиальной интерполяции для нахождения S из заданного набора долей, и Джордж Блейкли ‘ геометрическая схема разделения секрета, которая использует геометрические методы для восстановления секрета S. Threshold секретный обмен схемы, основанные на CRT, созданы Миньоттом и Асмутом-Блумом, они используют специальные последовательности целые числа вместе с CRT.

Китайская теорема об остатках

Пусть k ⩾ 2, m 1,…, м К ⩾ 2 { displaystyle k geqslant 2, m_ {1},…, m_ {k} geqslant 2} $k geqslant 2, m_ {1},..., m_ {k} geqslant 2$ и b 1,…, б К ∈ Z { Displaystyle B_ {1},…, b_ {k} in mathbf {Z}} $b_ {1 },..., b_ {k} in { mathbf {Z}}$ . Система сравнений

{x ≡ b 1 mod m 1 ⋮ x ≡ bk mod mk { displaystyle { begin {cases} x Equiv b_ {1} { bmod {}} m_ {1} vdots \ x Equiv b_ {k} { bmod {}} m_ {k} \ end {cases}}} ${ begin {cases} x Equiv b_ {1} { bmod } m_ { 1} \ vdots \ x Equiv b_ {k} { bmod } m_ {k} \ end {case}}$

имеет решения в Z тогда и только тогда если би ≡ bj mod (mi, mj) { displaystyle b_ {i} Equiv b_ {j} { bmod {(}} m_ {i}, m_ {j})} $b_ {i} Equiv b_ {j} { bmod (} m_ {i}, m_ {j})$ для всех 1 ⩽ я, j ⩽ к { displaystyle 1 leqslant i, j leqslant k}, где (mi, mj) { displaystyle (m_ {i}, m_ {j})} $(m_ {i}, m_ {j})$ обозначает наибольший общий делитель (НОД) m i и m j. Кроме того, в этих условиях система имеет единственное решение в Z/nZ, где n = [m 1,…, mk] { displaystyle n = [m_ {1},…, m_ {k}]} $n = [m_ {1},..., m_ {k}]$ , что обозначает наименьшее общее кратное (НОК) для м 1,…, mk { displaystyle m_ {1},…, m_ {k}} $m_ {1},..., m_ {k}$ .

Совместное использование секретов с использованием CRT

Поскольку китайская теорема об остатках предоставляет нам метод однозначно определить число S по модулю k-многие относительно простых целых чисел m 1, m 2,…, mk { displaystyle m_ {1}, m_ {2},…, m_ {k}}, учитывая, что S < ∏ i = 1 k m i {displaystyle S<prod _{i=1}^{k}m_{i}} $S < prod_ {i = 1} ^ k m_i$ , тогда идея состоит в том, чтобы построить схему, которая будет определять секрет S для любых k долей (в данном случае остаток от S по модулю каждого из чисел m i), но не раскроет секрет, если дано менее k таких долей.

В конечном итоге мы выбираем n относительно простых целых чисел m 1 < m 2 <… < m n {displaystyle m_{1} $m_ {1} <m_ {2} <... <m_ {n}$ таких, что S меньше, чем произведение любого выбора k этих целых чисел, но при то же время больше, чем любой выбор k-1 из них. Тогда акции s 1, s 2,…, sn { displaystyle s_ {1}, s_ {2},…, s_ {n}} $s_ {1}, s_ {2},..., s_ {n}$ определяются как si = S mod mi { displaystyle s_ {i} = S { bmod {}} m_ {i}} $s_ {i} = S { bmod } m_ {i}$ для i = 1, 2,…, n { displaystyle i = 1,2,…, n}. Таким образом, благодаря CRT, мы можем однозначно определить S из любого набора из k или более долей, но не из менее чем k. Это обеспечивает так называемую пороговую структуру доступа.

Это условие на S также можно рассматривать как

∏ i = n — k + 2 nmi < S < ∏ i = 1 k m i. {displaystyle prod _{i=n-k+2}^{n}m_{i} $prod _ {{i = n-k + 2}} ^ {n} m_ {i} <S < prod _ {{i = 1}} ^ {k} m_ {i}.$

Поскольку S меньше, чем наименьшее произведение k целых чисел, оно будет меньше произведения любого k из них. Кроме того, будучи большим, чем произведение наибольших k — 1 целых чисел, оно будет больше, чем произведение любого k — 1 из них.

Существуют две схемы совместного использования секретов, которые по существу используют эту идею, схемы Миньотта и Асмута-Блума, которые объясняются ниже.

Схема разделения секрета Mignotte с пороговым значением

Как было сказано ранее, схема Mignotte threshold совместного использования секрета использует, наряду с CRT, специальные последовательности целых чисел, называемые (k, n) -последовательности Миньота, которые состоят из n целых чисел, попарно взаимно простых, так что произведение наименьших k из них больше, чем произведение k — 1 самых больших. Это условие имеет решающее значение, потому что схема построена на выборе секрета в виде целого числа между двумя продуктами, и это условие гарантирует, что для полного восстановления секрета требуется не менее k долей, независимо от того, как они выбраны.

Формально, пусть 2 ≤ k ≤ n целые числа. A (k, n) -Последовательность Миньота — это строго возрастающая последовательность натуральных чисел m 1 < ⋯ < m n {displaystyle m_{1}<cdots $m_ {1} < cdots <m_{n}$ , где (mi, mj) = 1 { displaystyle (m_ {i}, m_ {j}) = 1} $(m_ {i}, m_ {j}) = 1$ для всех 1 ≤ i < j ≤ n, such that mn — k + 2 ⋯ mn < m 1 ⋯ m k {displaystyle m_{n-k+2}cdots m_{n} $m _ {{n-k + 2}} cdots m_ {n} <m_ {1} cdots m_ {k}$ . Мы называем этот диапазон разрешенным диапазоном. Мы строим схему (k, n) — порог совместного использования секрета следующим образом: мы выбираем секрет S как случайное целое число в разрешенном диапазоне. Мы вычисляем для каждого 1 ≤ i ≤ n сокращение по модулю m i числа S, которое мы называем s i, это доли. Теперь для любых k различных долей si 1,…, sik { displaystyle s_ {i_ {1}}, ldots, s_ {i_ {k}}} $s _ {{i_ {1}}}, ldots, s _ {{i_ {k}}}$ , мы рассматриваем систему конгруэнции:

{x ≡ si 1 mod mi 1 ⋮ x ≡ sik mod mik { displaystyle { begin {cases} x Equiv s_ {i_ {1}} { bmod {}} m_ {i_ { 1}} \ vdots \ x Equiv s_ {i_ {k}} { bmod {}} m_ {i_ {k}} \ end {cases}}} ${ begin {case} x Equiv s _ {{i_ {1}}} { bmod } m _ {{i_ {1}}} \ vdots \ x Equiv s _ {{i_ {k}}} { bmod } m _ {{i_ {k}}} \ end {case}}$

К 60>Китайская теорема об остатках, поскольку mi 1,…, mik { displaystyle m_ {i_ {1}}, ldots, m_ {i_ {k}}} $m _ {{i_ {1}}}, ldots, m _ {{i_ {k}}}$ равны попарно взаимно простое, система имеет уникальное решение по модулю mi 1 ⋯ mik { displaystyle m_ {i_ {1}} cdots m_ {i_ {k}}} $m _ {{i_ {1}}} cdots m _ {{i_ {k}}}$ . По конструкции наших акций, это решение является не чем иным, как секретом S.

Пороговая схема разделения секрета Асмута-Блума

В этой схеме также используются специальные последовательности целых чисел. Пусть 2 ≤ k ≤ n целые числа. Мы рассматриваем последовательность попарно взаимно простых натуральных чисел m 0 <… < m n {displaystyle m_{0}<… $m_ {0} <... <m_ {n}$ таких, что m 0. м н — к + 2… m n < m 1… m k {displaystyle m_{0}.m_{n-k+2}…m_{n} $m_ {0}.m _ {{n-k + 2}}... m_ {n} <m_ {1}... m_ {k}$ . Для данной последовательности мы выбираем секрет S как случайное целое число в наборе Z/m0Z.

Затем мы выбираем случайное целое число α такое, что S + α ⋅ m 0 < m 1… m k {displaystyle S+alpha cdot m_{0} ${ displaystyle S + alpha cdot m_ {0} <m_ {1}... m_ {k}}$ . Мы вычисляем сокращение по модулю m i из S + α ⋅ m 0 { displaystyle S + alpha cdot m_ {0}} ${ displaystyle S + alpha cdot m_ {0}}$ для всех 1 ≤ i ≤ n, это акции I i = (si, mi) { displaystyle I_ {i} = (s_ {i}, m_ {i})} $I_ {i} = (s_ {i}, m_ {i})$ . Теперь для любых k различных долей I i 1,…, I ik { displaystyle I_ {i_ {1}},…, I_ {i_ {k}}} $I _ {{i_ {1}}},..., I_ { {i_ {k}}}$ , мы рассматриваем систему сравнений:

{x ≡ si 1 mod mi 1 ⋮ x ≡ sik mod mik { displaystyle { begin {cases} x Equiv s_ {i_ {1}} { bmod {}} m_ {i_ {1}} \ vdots \ x Equ s_ {i_ {k}} { bmod {}} m_ {i_ {k}} \ end {cases}}} ${ begin {case} x Equiv s _ {{i_ {1}}} { bmod } m _ {{i_ {1}}} \ vdots \ x Equiv s _ {{i_ {k}}} { bmod } m _ {{i_ {k}}} \ end {case}}$

По китайской теореме об остатках, поскольку ми 1,…, mik { displaystyle m_ {i_ {1}},…, m_ {i_ {k}}} $m _ {{i_ {1}}},..., m _ {{i_ {k}}}$ являются попарно взаимно простыми, система имеет единственное решение S 0 по модулю mi 1… м я К { Displaystyle м_ {я_ {1}}… м_ {я_ {к}}} $m _ {{i_ {1} }}... m _ {{i_ {k}}}$ . При построении наших долей секрет S представляет собой уменьшение по модулю m 0 числа S 0.

. Важно отметить, что Mignotte (k, n) — порог Схема разделения секрета не идеальна в том смысле, что набор из менее k общих ресурсов содержит некоторую информацию о секрете. Схема Асмута-Блума идеальна: α не зависит от секрета S и

∏ i = n — k + 2 nmi α} < ∏ i = 1 k m i m 0 {displaystyle 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}}}} $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}}}$

Следовательно, α может быть любым целым числом по модулю

∏ i = n — k + 2 миль. { displaystyle prod _ {i = n-k + 2} ^ {n} m_ {i}.} $prod _ {{i = n -k + 2}} ^ {n} m_ {i}.$

Это произведение модулей k — 1 является наибольшим из всех n выбранных k — 1 возможных продуктов, поэтому любое подмножество k — 1 эквивалентов может быть любым целым числом по модулю своего произведения, и никакая информация из S не просачивается.

Пример

Ниже приведен пример схемы Асмута-Блума. Для практических целей мы выбираем небольшие значения для всех параметров. Выберем k = 3 и n = 4. Наши попарно взаимно простые целые числа равны m 0 = 3, m 1 = 11, m 2 = 13, m 3 = 17 { displaystyle m_ {0} = 3, m_ {1} = 11, m_ {2} = 13, m_ {3} = 17} $m_ {0} = 3, m_ {1} = 11, m_ {2} = 13, m_ {3} = 17$ и m 4 = 19 { displaystyle m_ {4} = 19} $m_ {4} = 19$ . Они удовлетворяют требуемой последовательности Асмута-Блума, потому что 3 ⋅ 17 ⋅ 19 < 11 ⋅ 13 ⋅ 17 {displaystyle 3cdot 17cdot 19<11cdot 13cdot 17}.

Скажем, наш секрет S равен 2. Выберите α = 51 { displaystyle alpha = 51}, удовлетворяя необходимое условие для схемы Асмута-Блума. Затем 2 + 51 ⋅ 3 = 155 { displaystyle 2 + 51 cdot 3 = 155}, и мы вычисляем доли для каждого из целых чисел 11, 13, 17 и 19. Они соответственно равны 1, 12, 2 и 3. Мы рассматриваем один возможный набор из 3 долей: среди 4 возможных наборов 3 долей мы берем набор {1,12,2} и показываем, что он восстанавливает секрет S = 2. Рассмотрим следующую систему сравнений:

{x ≡ 1 mod 11 x ≡ 12 mod 13 x ≡ 2 mod 17 { displaystyle { begin {cases} x Equiv 1 { bmod {}} 11 \ x Equiv 12 { bmod {}} 13 \ x Equiv 2 { bmod {}} 17 \ end {cases}}} ${ begin {case} x Equiv 1 { bmod } 11 \ x Equiv 12 { bmod } 13 \ x Equiv 2 { bmod } 17 \ end {case}}$

Чтобы решить систему, пусть M Знак равно 11 ⋅ 13 ⋅ 17 { Displaystyle M = 11 cdot 13 cdot 17}. Из конструктивного алгоритма решения такой системы мы знаем, что решение этой системы: x 0 = 1 ⋅ e 1 + 12 ⋅ e 2 + 2 ⋅ e 3 { displaystyle x_ {0} = 1 cdot e_ {1} +12 cdot e_ {2} +2 cdot e_ {3}} $x_ {0} = 1 cdot e_ {1} +12 cdot e_ {2} +2 cdot e_ {3}$ , где каждый e i находится следующим образом:

По личность Безу, поскольку (mi, M / mi) = 1 { displaystyle (m_ {i}, M / m_ {i}) = 1} $(m_ {i}, M / m_ {i}) = 1$ , существует положительные целые числа r i и s i, которые можно найти с помощью Расширенного алгоритма Евклида, такие что ri. м я + с я. M / m я знак равно 1 { displaystyle r_ {i}.m_ {i} + s_ {i}.M / m_ {i} = 1} $r_ {i}.m_ {i} + s_ {i}.M / m_ {i} = 1$ . Установить ei = si ⋅ M / mi { displaystyle e_ {i} = s_ {i} cdot M / m_ {i}} ${ displaystyle e_ {i} = s_ {i} cdot M / m_ {i}}$ .

Из тождеств 1 = 1 ⋅ 221 — 20 ⋅ 11 Знак равно (- 5) ⋅ 187 + 72 ⋅ 13 знак равно 5 ⋅ 143 + (- 42) ⋅ 17 { displaystyle 1 = 1 cdot 221-20 cdot 11 = (- 5) cdot 187 + 72 cdot 13 = 5 cdot 143 + (- 42) cdot 17}, получаем, что e 1 = 221, e 2 = — 935, e 3 = 715 { displaystyle e_ {1} = 221, e_ {2} = — 935, e_ {3} = 715} $e_ {1} = 221, e_ {2} = - 935, e_ {3} = 715$ , и уникальное решение по модулю 11 ⋅ 13 ⋅ 17 { displaystyle 11 cdot 13 cdot 17}равно 155. Наконец, S = 155 ≡ 2 mod 3 { displaystyle S = 155 Equiv 2 mod 3}.

См. Также

Разделение секретов
Схема разделения секретов Шамира
Китайская теорема об остатках
Структура доступа

Ссылки

Одед Голдрайх, Дана Рон и Мадху Судан, Китайские оставшиеся с ошибками, транзакции IEEE по теории информации, Vol. 46, No. 4, июль 2000 г., страницы 1330-1338.
Миньотт М. (1983) Как поделиться секретом. В: Бет Т. (ред.) Криптография. EUROCRYPT 1982. Lecture Notes in Computer Science, vol 149. Springer, Berlin, Heidelberg.
C.A. Асмут и Дж. Блум. Модульный подход к защите ключей. IEEE Transactions по теории информации, IT-29 (2): 208-210, 1983.
Сорин Ифтен. Общий секретный обмен на основе китайской теоремы об остатках с приложениями в электронном голосовании. Электронные заметки по теоретической информатике (ENTCS). Том 186 (июль 2007 г.). Страницы 67–84. Год публикации: 2007. ISSN 1571-0661.
Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Стейн. Введение в алгоритмы, второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 31.5: Китайская теорема об остатках, страницы 873-876.
Рональд Крамер. Основы обмена секретами (лекции 1-2), заметки для занятий. Октябрь 2008 г., версия 1.1.

Внешние ссылки

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

Источник

Secret sharing schemes: several types[edit]

Chinese remainder theorem[edit]

Secret sharing using the CRT[edit]

Mignotte’s threshold secret sharing scheme[edit]

Asmuth-Bloom’s threshold secret sharing scheme[edit]

Example[edit]

See also[edit]

References[edit]

External links[edit]

Secret sharing schemes: several types[]

Secret sharing using the CRT[]

Mignotte’s threshold secret sharing scheme[]

Asmuth-Bloom’s threshold secret sharing scheme[]

Example[]

See also[]

References[]

External links[]

Совместное использование секрета с использованием китайской теоремы об остатках — Secret sharing using the Chinese remainder theorem

Содержание

Схемы совместного использования секрета: несколько типов

Китайская теорема об остатках

Совместное использование секретов с использованием CRT

Схема разделения секрета Mignotte с пороговым значением

Пороговая схема разделения секрета Асмута-Блума

Пример

См. Также

Ссылки

Внешние ссылки

Добавить комментарий Отменить ответ