10.3. Разделение секрета

Протоколы разделения секрета (secret splitting) используются для снижения риска компрометации некоторых критичных данных.

Допустим, необходимо защитить некоторую банковскую тайну (возможно, секрет – код доступа к зашифрованным счетам). С некоторой вероятностью в банке работает «агент конкурирующей фирмы».

Для обеспечения безопасности секрета определяется несколько сотрудников, которые получают свои части секрета. Допустим, что секрет делится между четырьмя сотрудниками и используем следующий протокол.

1. Администратор генерирует три случайные строки той же длины, что и сам секрет.

2. Далее вычисляется .

3. Администратор поручает хранение первому сотруднику,– второму сотруднику и т.д., до.

4. При необходимости восстановления секрета:

В этом протоколе администратор – главное лицо, его мошенничество уже никак не контролируется вплоть до момента восстановления секрета. Недостатком схемы является то, что утеря одним из участников протокола своей части приведет к невозможности восстановления секрета.

Более эффективным на практике является протокол распределения секрета (secret sharing), предложенный Шамиром. В этой схеме некоторая информация (секрет) делится на частей, называемых тенями (shadows) или долями секрета так, чтобы любыхдолей было достаточно для восстановления секрета. Схема носит название-пороговой схемы (threshold scheme).

Схема Шамира использует т.н. интерполяционный полином Лагранжа для системы различных пар точек.

Этот полином среди полиномов степени не выше определяется однозначно и принимает в точкахзначения.

Выберем случайным образом секретный набор вычетов ,по большому модулюи образуем полином, где(наш секрет).

Для каждого из участников протокола выберем соответственно попарно различные несекретные вычеты. Вычислим значенияи распределим между пользователями в виде долей секрета пары вида,. Здесь мы пользуемся тем, что степень полинама () не ограничивает количество точек (), в которых мы желаем вычислить значения полинома.

Для восстановления секрета воспользуемся формулой Лагранжа, согласно которой многочлен степени можно восстановить с помощьюпопарно различных точек, при этом свободный член вычисляется по формуле:

Данное выражение позволяет произвольной группе из пользователей вычислить секрет, а группы, состоящие из меньшего числа пользователей, этой процедуры выполнить не могут.

Рассмотрим конструкцию протокола проверяемого разделения секрета из работы [42]. Конструкция основана на сложности дискретного логарифмирования.

По аналогии со схемой Шамира, дилер формирует секретный случайный полином , степени, где(наш секрет).

Затем он публикует значения ,, где– элемент большого порядка по модулю. Для каждогодилер пересылает значениепроцессорупо защищенному каналу.

Процессор процессор может (не зная) проконтролировать выполнение равенства, поскольку для

.

Конструкцию протокола для фазы восстановления секрета рассмотрим в наиболее простом случае, когда дилер честный.

На этой фазе каждый процессор пересылает по защищенному каналу каждому другому процессору свою долю.

Всякий честный участник , получив некоторое значениеот, проверяет это значение (как описано выше) и отбрасывает все доли секрета, не прошедшие проверку.

Поскольку честных участников не менее ,получит по крайней мереправильных долей секрета. Используя процедуру восстановления секрета из схемы Шамира,восстановит значение.