Схема Карнина — Грина — Хеллмана — пороговая схема разделения секрета на основе решения систем уравнений. Авторы — Эхуд Карнин (), Джонатан Грин () и Мартин Хеллман ().
Введение Пороговая схема разделения секрета на конечных полях — схема обмена секретного ключа между участниками таким образом, что любые из них могут восстановить секрет, но любая группа из или менее — не может. Схема состоит из двух фаз. В первой фазе — фазе распределения — некоторая сторона (называемая поставщиком) создаёт доли участия , используя алгоритм распределения . Для каждого поставщик лично отдает долю участия участнику . Вторая фаза, называемая фазой восстановления, происходит, когда участников хотят восстановить секретный ключ .
Типы пороговых схем Пороговая схема разделения секрета называется совершенной, если по крайней мере участников могут восстановить секрет, а любая группа из или менее сторон — не может. Пороговая схема разделения секрета называется линейной, если восстановление секрета происходит путём взятия линейной комбинации долей участия. Пороговая схема разделения секрета называется идеальной, если размер долей участий равен размеру секрета . Совершенная, идеальная и линейная пороговая схема разделения секрета называется PIL (perfect, ideal and linear) пороговой схемой разделения секрета.
Для PIL пороговой схемы можно задать требования в терминах свойств матрицы распределения
1.Полнота — любая группа, включающая не менее участников, может вычислить секрет . Таким образом, любые строк матрицы распределения должны иметь интервал, включающий строку .
2.Конфиденциальность — ни одна группа, включающая менее чем участников, не может получить информацию о секретном ключе . Инными словами, или меньше строк матрицы распределения не могут включать интервал, включающий строку .
Описание Рассмотрим конечное поле . Пусть простой элемент и пусть . Поставщик случайно выбирает из .
Затем он строит долей участия следующим образом
.
Потом поставщик отправляет участнику , следя за тем, чтобы любые строк матрицы , обозначенные как , составляли обратимую матрицу .
Отсюда, , где вектор — столбец, состоящий из .
Таким образом, секрет может быть вычислен.
Кроме того, для любых строк матрицы , строка , не будет входить в
Значит, или менее участников не могут получить никакой информации о секрете . Следовательно, можно построить пороговую схему разделения секрета для , где , то есть число участников может быть равно размеру поля.
Таким образом, с точки зрения определения максимального мы можем сказать, что схема Карнина — Грина — Хеллмана эффективней, чем схема Шамира.
Пример оптимальной схемы — это наибольшее , для которого можно построить PIL пороговую схему разделения секрета над конечным полем . — матрица распределения PIL — пороговой схемы разделения секрета над конечным полем записана в KGH нормальной форме, если удовлетворяет следующему равенству:
Для любой PIL — пороговой схемы разделения секрета над конечным полем матрицу распределения можно записать в KGH нормальной форме.
Теорема 1. Допустим, у нас есть секретное пространство = =
Тогда удовлетворяет: , , , ,
Теорема 2. Пусть — конечное поле и . Тогда существует надежная PIL — пороговая схема разделения секрета над полем .
Доказательство. Характеристикой поля является . Все нетривиальные элементы (элементы не равные или ) поля имеют мультипликативный порядок больше, чем . Пусть — элементы поля не равные или .
Тогда матрица распределения примет следующий вид:
Таким образом, — это матрица PIL пороговой схемы разделения секрета размером
Рассмотрим полноту.
Пронумеруем строки матрицы от до сверху вниз.
Случай I. Любые 3 строки из набора могут восстановить секрет ввиду обратимости матрицы Вандермонда. Случай II. Допустим даны строки и и ещё одна строка из набора . Тогда очевидно, что можно восстановить секрет. Случай III. Допустим одна из строк принадлежит набору , а две остальные выбраны из Тогда с помощью элементарных преобразований строк можно убрать строку из набора . В итоге, останется система Вандермонта размером , которая обратима.
Свойство полноты доказано. Доказательство конфиденциальности проходит похожим образом.
Для любого поля с характеристикой получается, что: .
Следовательно, для полей с характеристикой в схеме Карнина — Грина — Хеллмана по теореме 1 достигает верхней границы.
Литература
Категория:Разделение секрета