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


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


Моделирующее устройство M

может всегда cделать это, потому что противник имеет не более t точек полинома степени t+1.

2-8. В течение раундов 2-8 моделирующее устройство полностью следует явно командам процессоров. Так как все что делают процессоры в этих раундах полностью случайно и нет влияния на их входы, M будет всегда способно создать неразличимые распределения.

10.                 Моделирующее устройство M выбирает полином g степени t+1 такой, что g(0)=s и затем для каждого процессора Pi, устройство M

распространяет g(i)+pi(i)+...+pn(i), где pj - полином, распределенный процессором Pj

в течение раундов 2-8 моделирования. Интерполяция Рида-Соломона этих значений даст как результат секрет s. Если процессор Pl является сбоящим в конце этого раунда, тогда и M, и Прот узнают из оракула истинную долю входа sl. Если sl¹g(l), тогда M только изменит значение pl в точке l так, чтобы сделать полную сумму соответствующей такой широковещательной передаче.

 

Моделирование неотличимо от реального выполнения с точки зрения противника. Фактически, в раундах 2-8 все сообщения случайны и не связаны с входом, так что моделирующее устройство может легко играть роль несбоящих процессоров. В раунде 1 противник просматривает не более t долей реального входа несбоящих процессоров. В соответствии со свойствами схемы разделения секрета Шамира, эти доли полностью случайны и, таким образом, могут моделироваться даже без знания реального входа (как и в случае с моделирующим устройством). В раунде  9 реальная доля распространена «скрытым образом» как случайный «мусор», а это позволит моделирующему устройству распространять сообщение несбоящих процессоров с необходимым распределением даже без знания реального входа.       -

С доказательством лемм 3.1 – 3.4 доказательство теоремы 3.1 следует считать законченным.               -

Здесь уместно сделать следующее замечание.Схемы (протоколы) конфиденциальных вычислений являются чрезвычайно сложным объектом исследований. Как видно из сказанного выше, даже описание и доказательство безопасности одного из базовых примитивов в протоколах конфиденциального вычисления функции, - схемы проверяемого разделения секрета являются чрезвычайно громоздкими и сложными.




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