Теория и практика защиты программ


Доказательство безопасности схемы проверяемого разделения секрета - часть 4


Если дилер нечестен после

1-ого раунда противник и моделирующее устройство получит из оракула истинный вход s дилера. В этом случае моделирующее устройство передает управление от дилера к противнику и меняет полином, используемый для разделения на новый полином f" такой, что f"(0)=s и f"(i)=f'(i) для всех процессоров Pi, которые были «подкуплены» противником. Изменения моделирующего устройства в соответствии со случайным полиномом fi, используемым для доказательств с нулевым разглашением (см, например, [Ка14,КУ4] и приложение) делает их совместимыми с любым широковещательным каналом. Моделирующее устройство может всегда сделать это, так как противник имеет не более t точек полинома степени t+1. Далее моделирующее устройство использует полином f"

для работы несбоящих процессоров, все еще находящихся под его управлением. Можно утверждать, что для противника эти вычисления не отличимы от реальных вычислений. Единственный момент, отличающийся от реальных вычислений, - это тот факт, что доли секрета, которые противник получает до того, как дилер становится нечестным, созданы с использованием другого полинома. Но благодаря свойствам полиномов – это не является проблемой для моделирующего устройства, в том случае, если дилер нечестен.   -

Лемма 3.4. Пусть функция h имеет вид

h((s1,...,sn-1),(

,...,
))=((s,s,...,s,wn),(
,...,
)).

Тогда h конфиденциально вычислима в отношение секрета s.

Доказательство. Работа моделирующего устройства M

сводится к следующему.

Описание работы моделирующего устройства M

1. В раунде 1, M

моделирует процессор Pi, выбирая случайный полином h'i степени t+1 и посылает h'i(j) к Pj. В этом месте моделирующему устройству позволено получить из оракула выход функции, так что M будет изучать истинный секрет s. Если такой процессор является «подкупленным» противником Прот в конце этого раунда (или в следующих раундах), то и M, и Прот узнают истинную долю sl и M должен изменить полином h'l в соответствии с тем, что h'l(0)=sl, но без изменения значения в точках, уже известных противнику.


- Начало -  - Назад -  - Вперед -