ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.06.2021
Просмотров: 3581
Скачиваний: 3
346
Глава
18.
Криптографическая
защита
торов
изучались
в
геометрии
как
N
-
множества
(
N = n + 1
)
в
конечной
проективной
геометрии
PG(k–1, q)
,
в
комбинаторике
—
как
ортогональные
таблицы
силы
k
и
ин
-
декса
λ
= 1
,
в
теории
кодирования
—
как
проверочные
матрицы
МДР
кодов
.
В
подраз
-
деле
“
Линейное
разделение
секрета
”
мы
приведем
известную
конструкцию
таких
множеств
с
N = q + 1
.
Существует
довольно
старая
гипотеза
о
том
,
что
это
и
есть
мак
-
симально
возможное
N
,
за
исключением
двух
случаев
:
случая
q < k
,
когда
N = k + 1
,
и
случая
q = 2m
,
k = 3
или
k = q – 1
,
когда
N = q + 2
.
Разделение
секрета
для
произвольных
структур
доступа
Начнем
с
формальной
математической
модели
.
Имеется
n+1
множество
S
0
,
S
1
,
…
,
S
n
и
(
совместное
)
распределение
вероятностей
P
на
их
декартовом
произведении
S
= S
0
*
…* S
n
.
Соответствующие
случайные
величины
обозначаются
через
S
i
.
Имеется
также
некоторое
множество
Г
подмножеств
множества
{1, …, n}
,
называемое
структурой
дос
-
тупа
.
Определение
18.1
Пара
(P,S)
называется
совершенной
вероятностной
СРС
,
реализующей
структуру
доступа
Г
,
если
P(S
0
= c
0
| S
i
= c
i
, i
∈
A)
∈
{0, 1}
для
A
∈
Г
,
(18.1)
P(S0 = c0 | Si = ci, i
∈
A) = P(S0 = c0)
для
A
∉
Г
(18.2)
Это
определение
можно
истолковать
следующим
образом
.
Имеется
множество
S
0
всех
возможных
секретов
,
из
которого
секрет
s
0
выбирается
с
вероятностью
p(s
0
)
,
и
имеется
СРС
,
которая
“
распределяет
”
секрет
s
0
между
n
участниками
,
посылая
“
про
-
екции
”
s
1
,
…
,
s
n
секрета
с
вероятностью
P
S0
(s
1
, …, s
n
)
.
Отметим
,
что
і
-
ый
учасник
получает
свою
“
проекцию
”
s
i
∈
S
i
и
не
имеет
информации
о
значениях
других
“
проек
-
ций
”,
однако
знает
все
множества
S
i
,
а
также
оба
распределения
вероятностей
p(s
0
)
и
P
S0
(s
1
,
…,
s
n
)
.
Эти
два
распределения
могут
быть
эквивалентны
заменене
на
одно
:
P(s
0
,
s
1
, …, s
n
) = p(
S0
)P
S0
(s
1
, …, s
n
)
,
что
и
было
сделано
выше
.
Цель
СРС
,
как
указывалось
во
введении
,
состоит
в
том
,
чтобы
:
•
участники
из
разрешенного
множества
A
(
т
.
е
.
A
∈
Г
)
вместе
могли
бы
однозначно
восстановить
значение
секрета
—
это
отражено
в
свойстве
(18.1);
•
участники
,
образующие
неразрешенное
множество
А
(
А
∉
Г
),
не
могли
бы
получить
дополнительную
информацию
об
s
0
,
т
.
е
.,
чтобы
вероятность
того
,
что
значение
сек
-
рета
S
0
= c
0
,
не
зависела
от
значений
“
проекций
”
S
i
при
і
∈
А
—
это
свойство
(18.2).
Замечание
о
терминологии
.
В
англоязычной
литературе
для
обозначения
“
порции
”
информации
,
посылаемой
участнику
СРС
,
были
введены
термины
share
(
А
.
Шамир
)
и
shadow
(
Г
.
Блейкли
).
Первый
термин
оказался
наиболее
популярным
,
но
неадек
-
ватная
(
во
всех
смыслах
)
замена
в
данной
работе
акции
на
проекцию
может
быть
несколько
оправдана
следующим
примером
.
Математика
разделения
секрета
347
Пример
18.1
.
Множество
S
0
всех
возможных
секретов
состоит
из
0
,
1
и
2
, “
представ
-
ленных
”,
соответственно
:
шаром
;
кубом
,
ребра
которого
параллельны
осям
координат
;
цилиндром
,
образующие
которого
параллельны
оси
Z
.
При
этом
диаметры
шара
и
осно
-
вания
цилиндра
,
и
длины
ребра
куба
и
образующей
цилиндра
,
равны
.
Первый
участник
получает
в
качестве
своей
“
доли
”
секрета
его
проекцию
на
плоскость
XY
,
а
второй
—
на
плоскость
XZ
.
Ясно
,
что
вместе
они
однозначно
восстановят
секрет
,
а
порознь
—
нет
.
Однако
эта
СРС
не
является
совершенной
,
так
как
любой
из
участников
получает
ин
-
формацию
о
секрете
,
оставляя
только
два
значения
секрета
как
возможные
при
данной
проекции
(
например
,
если
проекция
—
квадрат
,
то
шар
невозможен
).
Еще
одно
замечание
.
Элемент
(
участник
)
x
∈
{1, …, n}
называется
несущественным
(
относительно
Г
),
если
для
любого
неразрешенного
множества
А
множество
А
∪
x
также
неразрешенное
.
Очевидно
,
что
несущественные
участники
настолько
несущественны
для
разделения
секрета
,
что
им
просто
не
нужно
посылать
никакой
информации
.
Поэтому
да
-
лее
,
без
ограничения
общности
,
рассматриваются
только
такие
структуры
доступа
Г
,
для
которых
все
элементы
являются
существенными
.
Кроме
того
,
естественно
предполагать
,
что
Г
является
монотонной
структурой
,
т
.
е
.
из
А
⊂
В
,
А
∈
Г
следует
В
∈
Г
.
Пример
18.2
.
Рассмотрим
простейшую
структуру
доступа
—
(n,n)
-
пороговую
схему
,
т
.
е
.
все
участники
вместе
могут
восстановить
секрет
,
а
любое
подмножество
участников
не
может
получить
дополнительной
информации
о
секрете
.
Будем
строить
идеальную
СРС
,
выбирая
и
секрет
,
и
его
проекции
из
группы
Z
q
вычетов
по
модулю
q
,
т
.
е
.
S
0
= S
1
= … = S
n
= Z
q
.
Дилер
генерирует
n–1
независимых
равномерно
распределенных
на
Z
q
случайных
величин
х
i
и
посылает
і
-
му
учаснику
(
і
= 1, ... , n-1)
его
“
проекцию
”
s
i
= x
i
,
а
n
-
му
участнику
—
s
n
= s
0
– (s
1
+ … + s
n-1
)
.
Кажущееся
“
неравноправие
”
n
-
ого
участни
-
ка
тут
же
исчезает
,
если
мы
выпишем
распределение
P
S0
(
s
1
,
…
,
s
n
),
которое
очевидно
равно
1/qn–1
,
если
s
0
=
s
1
+ … + s
n
,
а
в
остальных
случаях
равно
0
.
Теперь
легко
про
-
веряется
и
свойство
(18.2),
означающее
в
данном
случае
независимость
случайной
вели
-
чины
S
0
от
случайных
величин
{
S
i
:
і
∈
А
}
при
любом
собственном
подмножестве
А
.
Данное
выше
определение
СРС
,
оперирующее
понятием
распределение
вероятно
-
стей
,
ниже
переведено
,
почти
без
потери
общности
,
на
комбинаторный
язык
,
который
представляется
более
простым
для
понимания
.
Произвольная
M * (n + 1)
-
матрица
V
,
строки
которой
имеют
вид
v = (v
0
, v
1
, …, v
n
)
,
где
v
i
∈
S
i
,
называется
матрицей
комби
-
наторной
СРС
,
а
ее
строки
—
правилами
распределения
секрета
.
Для
заданного
значе
-
ния
секрета
s
0
дилер
СРС
случайно
и
равновероятно
выбирает
строку
v
из
тех
строк
матрицы
V
,
для
которых
значение
нулевой
координаты
равно
s
0
.
Определение
18.2
Матрица
V
задает
совершенную
комбинаторную
СРС
,
реализующую
структуру
дос
-
тупа
Г
,
если
,
во
-
первых
,
для
любого
множества
А
∈
Г
нулевая
координата
любой
стро
-
ки
матрицы
V
однозначно
определяется
значениями
ее
координат
из
множества
А
,
и
,
во
-
вторых
,
для
любого
множества
А
∉
Г
и
любых
заданных
значений
координат
из
множе
-
ства
А
число
строк
матрицы
V
с
данным
значением
α
нулевой
координаты
не
зависит
от
α
.
348
Глава
18.
Криптографическая
защита
Сопоставим
совершенной
вероятностной
СРС
,
задаваемой
парой
(P, S)
,
матрицу
V
,
состоящую
из
строк
s
∈
S
,
таких
что
P(s) > 0
.
Заметим
,
что
если
в
определении
1
поло
-
жить
все
ненулевые
значения
P
одинаковыми
,
а
условия
(18.1)
и
(18.2)
переформулировать
на
комбинаторном
языке
,
то
получится
определение
2.
Это
комбинаторное
определение
несколько
обобщается
,
если
допустить
в
матрице
V
повторяющиеся
строки
,
что
эквива
-
лентно
вероятностному
определению
1,
когда
значения
вероятностей
P(s)
—
рациональ
-
ные
числа
.
Продолжение
примера
18.2
(
из
предыдущего
раздела
).
Переформулируем
данную
выше
конструкцию
(n,n)
-
пороговой
СРС
на
комбинаторном
языке
.
Строками
матрицы
V
являются
все
векторы
s
такие
,
что
s
0
+ s
1
+ … + s
n
= 0
.
Очевидно
,
что
матрица
V
за
-
дает
совершенную
комбинаторную
СРС
для
Г
={1, …, n}
,
так
как
для
любого
собствен
-
ного
подмножества
А
⊂
{1, …, n}
и
любых
заданных
значений
координат
из
множества
А
число
строк
матрицы
V
с
данным
значением
нулевой
координаты
равно
q
n–1 – |A|
.
Удивительно
,
но
простой
схемы
примера
2
оказывается
достаточно
,
чтобы
из
нее
,
как
из
кирпичиков
,
построить
совершенную
СРС
для
произвольной
структуры
доступа
.
А
именно
,
для
всех
разрешенных
множеств
,
т
.
е
.
для
А
∈
Г
,
независимо
реализуем
описан
-
ную
только
что
пороговую
(|A|, |A|)
-
СРС
,
послав
тем
самым
і
-
му
учаснику
c
только
“
проекций
”
s
i
A
,
скольким
разрешенным
множествам
он
принадлежит
.
Это
словесное
описание
несложно
перевести
на
комбинаторный
язык
свойств
матрицы
V
и
убедиться
,
что
эта
СРС
совершенна
.
Как
это
часто
бывает
, “
совершенная
”
не
значит
“
экономная
”,
и
у
данной
СРС
размер
“
проекции
”
оказывается
,
как
правило
,
во
много
раз
больше
,
чем
размер
секрета
.
Эту
схему
можно
сделать
более
экономной
,
так
как
достаточно
реализо
-
вать
пороговые
(|A|, |A|)
-
СРС
только
для
минимальных
разрешенных
множеств
А
,
т
.
е
.
для
А
∈
Г
min
,
где
Г
min
—
совокупность
минимальных
(
относительно
включения
)
мно
-
жеств
из
Г
.
Тем
не
менее
,
для
пороговой
(n, n/2)
-
СРС
размер
“
проекции
” (
измеренный
,
например
,
в
битах
)
будет
в
C
n
n/2
~ 2n/ 2
π
n
раз
больше
размера
секрета
(
это
наихудший
случай
для
рассматриваемой
конструкции
).
С
другой
стороны
,
как
мы
убедимся
чуть
позже
,
любая
пороговая
структура
доступа
может
быть
реализована
идеально
,
т
.
е
.
при
совпадающих
размерах
“
проекции
”
и
секрета
.
Поэтому
естественно
возникает
вопрос
о
том
,
каково
максимально
возможное
превышение
размера
“
проекции
”
над
размером
секрета
для
наихудшей
структуры
доступа
при
наилучшей
реализации
.
Формально
,
R(n)
= max R(
Г
)
,
где
max
берется
по
всем
структурам
доступа
Г
на
n
участниках
,
а
R(
Г
) =
min max
log |S
i
|
log |S
0
|
,
где
min
берется
по
всем
СРС
,
реализующим
данную
структуру
доступа
Г
,
а
max
—
по
і
= 1, ..., n
.
Приведенная
конструкция
показывает
,
что
R(n)
≤
C
n
n/2n
.
С
другой
стороны
,
R(n)
≥
n/log n
.
Такой
огромный
“
зазор
”
между
верхней
и
нижней
оценкой
дает
достаточный
простор
для
исследований
(
предполагается
,
что
R(n)
зависит
от
n
экспоненциально
).
Линейное
разделение
секрета
Начнем
с
предложенной
Шамиром
элегантной
схемы
разделения
секрета
для
порого
-
вых
структур
доступа
.
Пусть
К
= GF(q)
—
конечное
поле
из
q
элементов
(
например
,
q
= p
—
простое
число
и
К
= Z
p
)
и
q > n
.
Сопоставим
участникам
n
различных
ненуле
-
Математика
разделения
секрета
349
вых
элементов
поля
{a
1
, …, a
n
}
и
положим
a
0
= 0
.
При
распределении
секрета
s
0
дилер
СРС
генерирует
k–1
независимых
равномерно
распределенных
на
GF(q)
случайных
ве
-
личин
f
j
(j = 1, …, k–1)
и
посылает
і
-
му
учаснику
(
і
= 1, ..., n)
“
его
”
значение
s
i
=
f(a
i
)
многочлена
f(x) = f
0
+ f
1
x + … + f
k-1
x
k-1
,
где
f
0
= s
0
.
Поскольку
любой
много
-
член
степени
k-1
однозначно
восстанавливается
по
его
значениям
в
произвольных
k
точках
(
например
,
по
интерполяционной
формуле
Лагранжа
),
то
любые
k
участников
вместе
могут
восстановить
многочлен
f(x)
и
,
следовательно
,
найти
значение
секрета
как
s
0
= f(0)
.
По
этой
же
причине
для
любых
k–1
участников
,
любых
полученных
ими
зна
-
чений
проекций
s
i
и
любого
значения
секрета
s
0
существует
ровно
один
“
соответст
-
вующий
”
им
многочлен
,
т
.
е
.
такой
,
что
s
i
= f(a
i
)
и
s
0
= f(0)
.
Следовательно
,
эта
схема
является
совершенной
в
соответствии
с
определением
2. “
Линейность
”
данной
схемы
становится
ясна
,
если
записать
“
разделение
секрета
”
в
векторно
-
матричном
виде
:
s = fH
,
(18.3)
где
s = (s
0
, …, s
n
), f = (f
0
, …, f
k–1
), k × (n+1)
—
матрица
H = (h
ij
) = (a
i
j-1
)
и
h
00
= 1
.
Заметим
,
что
любые
k
столбцов
этой
матрицы
линейно
независимы
,
а
максимально
воз
-
можное
число
столбцов
матрицы
H
равно
q
,
чтобы
добиться
обещанного
значения
q+1
надо
добавить
столбец
,
соответствующий
точке
“
бесконечность
”.
Возьмем
в
(18.3)
в
качестве
H
произвольную
r × (n + 1)
-
матрицу
с
элементами
из
поля
K
.
Получаемую
СРС
,
будем
называть
одномерной
линейной
СРС
.
Она
является
со
-
вершенной
комбинаторной
СРС
со
структурой
доступа
Г
,
состоящей
из
множеств
А
та
-
ких
,
что
вектор
h
0
представим
в
виде
линейной
комбинации
векторов
{h
j
: j
∈
A}
,
где
h
j
—
это
j
-
ый
столбец
матрицы
H
.
Строками
матрицы
V
,
соответствующей
данной
СРС
,
являются
,
как
видно
из
(18.3),
линейные
комбинации
строк
матрицы
H
.
Перепишем
(18.3)
в
следующем
виде
s
j
= (f, h
j
)
для
j = 0, 1, …, n
,
где
(f, h
j
)
—
скалярное
произведение
векторов
f
и
h
j
.
Если
А
∈
Г
,
т
.
е
.
если
h
0
=
Σλ
j
h
j
,
то
s
0
= (f, h
0
) =
(
)
f,
Σλ
j
h
j
=
Σλ
j
(f, h
j
) =
Σλ
j
s
j
и
,
следовательно
,
значение
секрета
однозначно
находится
по
его
“
проекциям
”.
Рассмот
-
рим
теперь
случай
,
когда
вектор
h
0
не
представим
в
виде
линейной
комбинации
векто
-
ров
{h
j
: j
∈
A}
.
Нам
нужно
показать
,
что
в
этом
случае
для
любых
заданных
значений
координат
из
множества
А
число
строк
матрицы
V
с
данным
значением
любой
коорди
-
наты
не
зависит
от
этого
значения
.
В
этом
не
трудно
убедится
,
рассмотрев
(18.3)
как
систему
линейных
уравнений
относительно
неизвестных
f
i
и
воспользовавшись
тем
,
что
система
совместна
тогда
и
только
тогда
,
когда
ранг
матрицы
коэффициентов
равен
рангу
расширенной
матрицы
,
а
число
решений
у
совместных
систем
одинаково
и
равно
числу
решений
однородной
системы
.
Указание
.
Рассмотрите
две
системы
: c “
нулевым
”
уравнением
и
без
него
(
т
.
е
.
со
сво
-
бодным
членом
).
Так
как
вектор
h
0
не
представим
в
виде
линейной
комбинации
векто
-
350
Глава
18.
Криптографическая
защита
ров
{h
j
: j
∈
A}
,
то
ранг
матрицы
коэффициентов
второй
системы
на
1
больше
ранга
матрицы
коэффициентов
первой
системы
.
Отсюда
немедленно
следует
,
что
если
первая
система
совместна
,
то
совместна
и
вторая
при
любом
s
0
.
Эта
конструкция
подводит
нас
к
определению
общей
линейной
СРС
.
Пусть
секрет
и
его
“
проекции
”
представляются
как
конечномерные
векторы
s
i
= (s
i
1
, …, s
i
mi
)
и
генериру
-
ются
по
формуле
s
i
= fH
i
,
где
H
i
—
некоторые
r × m
i
-
матрицы
.
Сопоставим
каждой
матрице
H
i
линейное
пространство
L
i
ее
столбцов
(
т
.
е
.
состоящее
из
всех
линейных
комбинаций
вектор
-
столбцов
матрицы
H
i
).
Несложные
рассуждения
,
аналогичные
при
-
веденным
выше
для
одномерного
случая
(
все
m
i
= 1
),
показывают
,
что
данная
конструк
-
ция
дает
совершенную
СРС
тогда
и
только
тогда
,
когда
семейство
линейных
подпро
-
странств
{L
0
, …, L
n
}
конечномерного
векторного
пространства
K
r
удовлетворяет
упо
-
мянутому
выше
свойству
“
все
или
ничего
”.
При
этом
множество
А
является
разрешенным
{L
a
: a
∈
A}
содержит
подпространство
L
0
целиком
.
С
другой
стороны
,
множество
А
является
неразрешенным
(
А
∉
Г
),
если
и
только
если
линейная
оболочка
подпространств
{La: a
∈
A}
пересекается
с
подпространством
L
0
только
по
вектору
0
.
Отметим
,
что
если
бы
для
некоторого
А
пересечение
L
0
и
линейной
оболочки
{L
a
: a
∈
A}
было
нетривиальным
,
то
участники
А
не
могли
бы
восстановить
секрет
однозначно
,
но
получали
бы
некоторую
информацию
о
нем
,
т
.
е
.
схема
не
была
бы
совершенной
.
Пример
18.3
.
Рассмотрим
следующую
структуру
доступа
для
случая
четырех
участ
-
ников
,
задаваемую
Г
min
= {{1,2}, {2,3}, {3,4}}
.
Она
известна
как
первый
построенный
пример
структуры
доступа
,
для
которой
не
существует
идеальной
реализации
.
Более
то
-
го
,
было
доказано
,
что
для
любой
ее
совершенной
реализации
R(
Г
)
≥
3/2
.
С
другой
сто
-
роны
,
непосредственная
проверка
показывает
,
что
выбор
матриц
H
0
,
H
1
, ...,
H
4
,
приве
-
денных
на
рис
. 18.2,
дает
совершенную
линейную
СРС
с
R = 3/2
,
реализующую
эту
структуру
,
которая
,
следовательно
,
является
и
оптимальной
(
наиболее
экономной
)
СРС
.
Рис
. 18.2.
Матрицы
,
реализующие
совершенную
линейную
СРС
Идеальное
разделение
секрета
и
матроиды
Начнем
с
определения
идеальных
СРС
.
Для
этого
вернемся
к
комбинаторному
опре
-
делению
совершенной
СРС
.
Следующее
определение
совершенной
СРС
является
даже
более
общим
,
чем
вероятностное
определение
1,
поскольку
условие
(18.2)
заменено
в
нем
на
более
слабое
.
Для
произвольного
множества
В
⊆
{0, 1, …, n}
обозначим
через
V
B
M × |B|
-
матрицу
,
полученную
из
матрицы
V
удалением
столбцов
,
номера
которых
не
принадле
-
жат
множеству
В
.
Пусть
||W||
обозначает
число
различных
строк
в
матрице
W
.