Схема Карнина — Грина — Хеллмана

Поделись знанием:
Перейти к: навигация, поиск

Схема Карнина — Грина — Хеллмана — пороговая схема разделения секрета на основе решения систем уравнений. Авторы — Эхуд Карнин (англ. Ehud D. Karnin), Джонатан Грин (Jonathan W. Greene) и Мартин Хеллман (Martin E. Hellman).





Введение

Пороговая схема разделения секрета на конечных полях — схема обмена секретного ключа <math>k</math> между <math>n</math> участниками таким образом, что любые <math>t</math> из них могут восстановить секрет, но любая группа из <math>t-1</math> или менее — не может. Схема состоит из двух фаз. В первой фазе — фазе распределения — некоторая сторона (называемая поставщиком) создаёт доли участия <math>s_1, s_2, \dots, s_n</math>, используя алгоритм распределения <math>D</math>. Для каждого <math>i</math> поставщик лично отдает долю участия <math>s_i</math> участнику <math>P_i</math>. Вторая фаза, называемая фазой восстановления, происходит, когда <math>t</math> участников <math>P_{i_1}, P_{i_2}, \dots, P_{i_t}</math> хотят восстановить секретный ключ <math>k</math>.

Типы пороговых схем

  • Пороговая схема разделения секрета называется совершенной, если по крайней мере <math> t </math> участников могут восстановить секрет, а любая группа из <math>t-1</math> или менее сторон — не может.
  • Пороговая схема разделения секрета называется линейной, если восстановление секрета <math> k </math> происходит путём взятия линейной комбинации <math> t </math> долей участия.
  • Пороговая схема разделения секрета называется идеальной, если размер долей участий такой же, как у секрета <math> k </math>.
  • Совершенная, идеальная и линейная пороговая схема разделения секрета называется PIL (perfect, ideal and linear) пороговой схемой разделения секрета.

Для PIL пороговой схемы можно задать требования в терминах свойств матрицы распределения <math>D:</math>

1.Полнота — любая группа, включающая не менее <math>t</math> участников, может вычислить секрет <math>k</math>. Таким образом, любые <math>t</math> строк матрицы распределения <math>D</math> должны иметь интервал, включающий строку

<math>\left[ 1, 0, 0, \dots, 0 \right]</math>.

2.Конфиденциальность — ни одна группа, включающая менее чем <math>t</math> участников, не может получить информацию о секретном ключе <math>k</math>. Инными словами, <math>t-1</math> или меньше строк матрицы распределения <math>D</math> не могут включать интервал, включающий строку

<math>\left[ 1, 0, 0, \dots, 0 \right]</math>.

Описание

Рассмотрим конечное поле <math>\mathrm{GF}(q^{m})</math>. Пусть <math>\alpha</math> простой элемент <math>\mathrm{GF}(q^{m})</math> и пусть

<math>\alpha_i \equiv \alpha^{i}, i = \overline{1,q^{m-1}}</math>.

Поставщик случайно выбирает <math>a_1, a_2, \dots, a_{t-1} </math> из <math>\mathrm{GF}(q^{m})</math>.

Затем он строит <math>n</math> долей участия <math>s_i</math> следующим образом

<math>\left[

\begin{array}{c} s_{1}\\s_{2}\\\vdots \\s_{r}\\s_{r+1} \\ \end{array}\right] =\quad\left[\begin{array}{ccccc} 1 & \alpha_{1} & \alpha_{1}^{2} & \cdots & \alpha_{1}^{t-1} \\ 1 & \alpha_{2} & \alpha_{2}^{2} & \cdots & \alpha_{2}^{t-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \alpha_{r} & \alpha_{r}^{2} & \cdots & \alpha_{r}^{t-1} \\ 0 & 0 & 0 & \cdots & 1 \end{array}\right] \left[ \begin{array}{c} k\\a_1\\a_2\\\vdots\\a_{t-1}\\ \end{array}\right]</math>

<math> n = r + 1, r \le q^{m} - 1 </math>.

Потом поставщик отправляет <math>s_i</math> участнику <math>P_i</math>, следя за тем, чтобы любые <math> t </math> строк матрицы <math> D </math>, обозначенные как <math> D_{i_1, i_2, \dots, i_t} </math>, составляли обратимую матрицу <math>t \times t</math>.

Отсюда, <math> \bar{y} = D_{i_1, i_2, \dots, i_t}^{-1} \cdot \bar{S}_{i_1, i_2, \dots, i_t}</math>, где <math> \bar{S}_{i_1, i_2, \dots, i_t} -</math> вектор - столбец, состоящий из <math> s_{i_1}, s_{i_2}, \dots, s_{i_t}</math>.

Таким образом, секрет <math> k </math> может быть вычислен.

Кроме того, для любых <math> t-1 </math> строк матрицы <math> D </math>, строка <math>[\begin{array}{ccccc}\gamma, 0, 0, \cdots, 0\\\end{array}]</math>, <math>\forall \gamma \in \mathrm{GF}(q^{m}) \setminus \{0\}</math> не будет входить в <math> D_{i_1, i_2, \dots, i_{t-1}} .</math>

Значит, <math> t - 1 </math> или менее участников не могут получить никакой информации о секрете <math> k </math>. Следовательно, можно построить пороговую схему разделения секрета для <math> r + 1 </math>, где <math> r + 1 = \mid \mathbb{F} \mid </math>, т.е. число участников <math> n </math> может быть равно размеру поля.

Таким образом, с точки зрения определения максимального <math> n </math> мы можем сказать, что схема Карнина — Грина — Хеллмана эффективней, чем схема Шамира.

Пример оптимальной схемы

  • <math> n_{max, t} </math> — это наибольшее <math> n </math>, для которого можно построить PIL <math> (t, n) -</math> пороговую схему разделения секрета над конечным полем <math> \mathbb{F} </math>.
  • <math> D </math> — матрица распределения PIL <math> (t, n) </math> - пороговой схемы разделения секрета над конечным полем <math> \mathbb{F} </math> записана в KGH нормальной форме, если удовлетворяет следующему равенству:
<math> D =

\quad\left[\begin{array}{ccccc} 1 & x_{12} & x_{13} & \cdots & x_{1t} \\ 1 & x_{22} & x_{23} & \cdots & x_{2t} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{r2} & x_{r3} & \cdots & x_{rt} \\ 1 & 1 & 1 & \cdots & 1 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1\\ \end{array}\right] </math>

Для любой PIL <math> (t, n) </math> - пороговой схемы разделения секрета над конечным полем <math> \mathbb{F} </math> матрицу распределения <math> D </math> можно записать в KGH нормальной форме.

Теорема 1. Допустим, у нас есть секретное пространство <math> \mathcal{S} </math> = <math> \mathbb{F} </math> = <math>\mathrm{GF}(q^{m})</math>

Тогда <math> n_{max, t} </math> удовлетворяет:

<math> \mid \mathbb{F} \mid \le n_{max, t} \le \mid \mathbb{F} \mid + t - 2</math>, <math>q^{m} > t</math>,
<math> n_{max,t} = t</math>, <math> q^{m} \le t </math>,

Теорема 2. Пусть <math>\mathbb{F} = \mathrm{GF}(2^{m})</math> — конечное поле и <math> n = \mid \mathbb{F} \mid+ 1</math>. Тогда существует надежная PIL <math> (3, n) </math> - пороговая схема разделения секрета над полем <math> \mathbb{F} </math>.

Доказательство. Характеристикой поля <math>\mathbb{F} = \mathrm{GF}(2^{m})</math> является <math> 2 </math>. Все нетривиальные элементы (элементы не равные <math> 0 </math> или <math> 1 </math>) поля <math> \mathbb{F} </math> имеют мультипликативный порядок больше, чем <math> 2 </math>. Пусть <math> x_{1}, x_{2}, \cdots, x_{\mid \mathbb{F} \mid - 2} </math> — элементы поля <math> \mathbb{F} </math> не равные <math> 0 </math> или <math> 1 </math>.

Тогда матрица распределения примет следующий вид:

<math> D =

\quad\left[\begin{array}{ccccc} 1 & x_{1} & x_{1}^{2} \\ \vdots & \vdots & \vdots \\ 1 & x_{\mid \mathbb{F} \mid - 2} & x_{\mid \mathbb{F} \mid - 2}^{2} \\ 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array}\right] </math>

Таким образом, <math> D </math> — это матрица PIL <math> (3, n) -</math> пороговой схемы разделения секрета размером <math> (\mid \mathbb{F} \mid + 1) \times 3 .</math>

Рассмотрим полноту.

Пронумеруем строки матрицы <math> D </math> от <math> 1 </math> до <math> n </math> сверху-вниз.

  • Случай I. Любые 3 строки из набора <math> \{1, \cdots, n - 2\} </math> могут восстановить секрет ввиду обратимости матрицы Вандермонда.
  • Случай II. Допустим даны строки <math>\left[ 0, 1, 0 \right]</math> и <math>\left[ 0, 0, 1\right]</math> и еще одна строка из набора <math> \{1, \cdots, n - 2\} </math>. Тогда очевидно, что можно восстановить секрет.
  • Случай III. Допустим одна из строк принадлежит набору <math>\{ \left[ 0, 1, 0\right], \left[ 0, 0, 1\right] \} </math>, а две остальные выбраны из <math> \{1, \cdots, n - 2\}. </math> Тогда с помощью элементарных преобразований строк можно убрать строку из набора <math>\{ \left[ 0, 1, 0\right], \left[ 0, 0, 1\right] \} </math>. В итоге, останется система Вандермонта размером <math> 2 \times 2 </math>, которая обратима.

Свойство полноты доказано. Доказательство конфиденциальности проходит похожим образом.

Для любого поля <math> \mathbb{F} </math> с характеристикой <math> 2 </math> получается, что:

<math> n_{max, 3} = \mid \mathbb{F} \mid + 1 = \mid \mathbb{F} \mid + 3 -2 = \mid \mathbb{F} \mid + t - 2 </math>.

Следовательно, для полей с характеристикой <math> 2 </math> в схеме Карнина — Грина — Хеллмана <math> n_{max, 3} </math> по теореме 1 достигает верхней границы.

Напишите отзыв о статье "Схема Карнина — Грина — Хеллмана"

Литература

  • Шнайер Б. 23.2 Алгоритмы разделения секрета. Karnin — Greene — Hellman // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 590. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  • Yvo Desmedt, Brian King, Berry Schoenmakers Revisiting the Karnin, Greene and Hellman Bounds // ICITS '08 Proceedings of the 3rd international conference on Information Theoretic Security. — 2008. — С. 183 - 198. — ISBN 978-3-540-85092-2. — DOI:10.1007/978-3-540-85093-9_18.
  • Karnin E.D., Greene J. , Hellman M.E. On secret sharing systems // Information Theory, IEEE Transactions on. — 2003. — С. 35 - 41. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0018-9448&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0018-9448]. — DOI:10.1109/TIT.1983.1056621.
  • Stinson, D. R. Cryptography: theory and practice. — Chapman and Hall/CRC, 2005. — ISBN 978-1584885085.

Отрывок, характеризующий Схема Карнина — Грина — Хеллмана

В Москве, как только он въехал в свой огромный дом с засохшими и засыхающими княжнами, с громадной дворней, как только он увидал – проехав по городу – эту Иверскую часовню с бесчисленными огнями свеч перед золотыми ризами, эту Кремлевскую площадь с незаезженным снегом, этих извозчиков и лачужки Сивцева Вражка, увидал стариков московских, ничего не желающих и никуда не спеша доживающих свой век, увидал старушек, московских барынь, московские балы и Московский Английский клуб, – он почувствовал себя дома, в тихом пристанище. Ему стало в Москве покойно, тепло, привычно и грязно, как в старом халате.
Московское общество всё, начиная от старух до детей, как своего давно жданного гостя, которого место всегда было готово и не занято, – приняло Пьера. Для московского света, Пьер был самым милым, добрым, умным веселым, великодушным чудаком, рассеянным и душевным, русским, старого покроя, барином. Кошелек его всегда был пуст, потому что открыт для всех.
Бенефисы, дурные картины, статуи, благотворительные общества, цыгане, школы, подписные обеды, кутежи, масоны, церкви, книги – никто и ничто не получало отказа, и ежели бы не два его друга, занявшие у него много денег и взявшие его под свою опеку, он бы всё роздал. В клубе не было ни обеда, ни вечера без него. Как только он приваливался на свое место на диване после двух бутылок Марго, его окружали, и завязывались толки, споры, шутки. Где ссорились, он – одной своей доброй улыбкой и кстати сказанной шуткой, мирил. Масонские столовые ложи были скучны и вялы, ежели его не было.
Когда после холостого ужина он, с доброй и сладкой улыбкой, сдаваясь на просьбы веселой компании, поднимался, чтобы ехать с ними, между молодежью раздавались радостные, торжественные крики. На балах он танцовал, если не доставало кавалера. Молодые дамы и барышни любили его за то, что он, не ухаживая ни за кем, был со всеми одинаково любезен, особенно после ужина. «Il est charmant, il n'a pas de seхе», [Он очень мил, но не имеет пола,] говорили про него.
Пьер был тем отставным добродушно доживающим свой век в Москве камергером, каких были сотни.
Как бы он ужаснулся, ежели бы семь лет тому назад, когда он только приехал из за границы, кто нибудь сказал бы ему, что ему ничего не нужно искать и выдумывать, что его колея давно пробита, определена предвечно, и что, как он ни вертись, он будет тем, чем были все в его положении. Он не мог бы поверить этому! Разве не он всей душой желал, то произвести республику в России, то самому быть Наполеоном, то философом, то тактиком, победителем Наполеона? Разве не он видел возможность и страстно желал переродить порочный род человеческий и самого себя довести до высшей степени совершенства? Разве не он учреждал и школы и больницы и отпускал своих крестьян на волю?
А вместо всего этого, вот он, богатый муж неверной жены, камергер в отставке, любящий покушать, выпить и расстегнувшись побранить легко правительство, член Московского Английского клуба и всеми любимый член московского общества. Он долго не мог помириться с той мыслью, что он есть тот самый отставной московский камергер, тип которого он так глубоко презирал семь лет тому назад.
Иногда он утешал себя мыслями, что это только так, покамест, он ведет эту жизнь; но потом его ужасала другая мысль, что так, покамест, уже сколько людей входили, как он, со всеми зубами и волосами в эту жизнь и в этот клуб и выходили оттуда без одного зуба и волоса.
В минуты гордости, когда он думал о своем положении, ему казалось, что он совсем другой, особенный от тех отставных камергеров, которых он презирал прежде, что те были пошлые и глупые, довольные и успокоенные своим положением, «а я и теперь всё недоволен, всё мне хочется сделать что то для человечества», – говорил он себе в минуты гордости. «А может быть и все те мои товарищи, точно так же, как и я, бились, искали какой то новой, своей дороги в жизни, и так же как и я силой обстановки, общества, породы, той стихийной силой, против которой не властен человек, были приведены туда же, куда и я», говорил он себе в минуты скромности, и поживши в Москве несколько времени, он не презирал уже, а начинал любить, уважать и жалеть, так же как и себя, своих по судьбе товарищей.
На Пьера не находили, как прежде, минуты отчаяния, хандры и отвращения к жизни; но та же болезнь, выражавшаяся прежде резкими припадками, была вогнана внутрь и ни на мгновенье не покидала его. «К чему? Зачем? Что такое творится на свете?» спрашивал он себя с недоумением по нескольку раз в день, невольно начиная вдумываться в смысл явлений жизни; но опытом зная, что на вопросы эти не было ответов, он поспешно старался отвернуться от них, брался за книгу, или спешил в клуб, или к Аполлону Николаевичу болтать о городских сплетнях.
«Елена Васильевна, никогда ничего не любившая кроме своего тела и одна из самых глупых женщин в мире, – думал Пьер – представляется людям верхом ума и утонченности, и перед ней преклоняются. Наполеон Бонапарт был презираем всеми до тех пор, пока он был велик, и с тех пор как он стал жалким комедиантом – император Франц добивается предложить ему свою дочь в незаконные супруги. Испанцы воссылают мольбы Богу через католическое духовенство в благодарность за то, что они победили 14 го июня французов, а французы воссылают мольбы через то же католическое духовенство о том, что они 14 го июня победили испанцев. Братья мои масоны клянутся кровью в том, что они всем готовы жертвовать для ближнего, а не платят по одному рублю на сборы бедных и интригуют Астрея против Ищущих манны, и хлопочут о настоящем Шотландском ковре и об акте, смысла которого не знает и тот, кто писал его, и которого никому не нужно. Все мы исповедуем христианский закон прощения обид и любви к ближнему – закон, вследствие которого мы воздвигли в Москве сорок сороков церквей, а вчера засекли кнутом бежавшего человека, и служитель того же самого закона любви и прощения, священник, давал целовать солдату крест перед казнью». Так думал Пьер, и эта вся, общая, всеми признаваемая ложь, как он ни привык к ней, как будто что то новое, всякий раз изумляла его. – «Я понимаю эту ложь и путаницу, думал он, – но как мне рассказать им всё, что я понимаю? Я пробовал и всегда находил, что и они в глубине души понимают то же, что и я, но стараются только не видеть ее . Стало быть так надо! Но мне то, мне куда деваться?» думал Пьер. Он испытывал несчастную способность многих, особенно русских людей, – способность видеть и верить в возможность добра и правды, и слишком ясно видеть зло и ложь жизни, для того чтобы быть в силах принимать в ней серьезное участие. Всякая область труда в глазах его соединялась со злом и обманом. Чем он ни пробовал быть, за что он ни брался – зло и ложь отталкивали его и загораживали ему все пути деятельности. А между тем надо было жить, надо было быть заняту. Слишком страшно было быть под гнетом этих неразрешимых вопросов жизни, и он отдавался первым увлечениям, чтобы только забыть их. Он ездил во всевозможные общества, много пил, покупал картины и строил, а главное читал.