- •Конфиденциальные вычисления
- •Водные замечания по проблематике конфиденциальных вычислений
- •Описание используемых примитивов, схем и протоколов
- •Общие определения
- •Проверяемая схема разделения секрета
- •Широковещательный примитив (Br-протокол)
- •Протокол bb
- •Протокол византийского соглашения (ba-протокол)
- •Обобщенные модели для сети синхронно и асинхронно взаимодействующих процессоров
- •Вводные замечания
- •Обобщенные модели сбоев и противника
- •Получестные модели
- •Злонамеренные модели Действия процессоров в злонамеренной модели
- •Вычисления в идеальной модели
- •Вычисления в идеальной модели
- •Вычисления в реальной модели
- •Модель взаимодействия
- •Синхронная модель вычислений Общее описание модели
- •Идеальный и реальный сценарии
- •Асинхронная модель вычислений Общее описание модели
- •Асинхронные идеальный и реальный сценарии
- •Безопасность асинхронных вычислений
- •Конфиденциальное вычисление функции
- •Проверяемые схемы разделения секрета как конфиденциальное вычисление функции
- •Описание проверяемой схемы разделения секрета
- •Протокол РзПр
- •Протокол ВсПр
- •Доказательство безопасности схемы проверяемого разделения секрета
- •Описание работы моделирующего устройства m
- •Синхронные конфиденциальные вычисления
- •Примитив «Забывающий обмен»
- •Протокол отпчм
- •Двухсторонние вычисления Безопасные протоколы для получестной модели
- •Редукция к от41
- •Протокол вычислений на арифметической схеме над gf(2)
- •Редукция к мв
- •Основной результат для злонамеренной модели
- •Многосторонние протоколы Общая идея
- •Получестная модель
- •Конфиденциальное вычисление
- •Многосторонний протокол схемного вычисления
- •Редукция к кВm
- •Основной результат для злонамеренной модели
- •Асинхронные конфиденциальные вычисления
- •Вводные замечания
- •Примитив «Соглашение об аккумулируемом множестве» (соам-субпротокол)
- •Протокол соам
- •Алгоритм звз
- •Процедура скоп
- •Асинхронная схема проверяемого разделения секрета Общие определения
- •Протокол аРзПр
- •Протокол аВсПр
- •Доказательство безопасности схемы апрс
- •Асинхронная схема глобального проверяемого разделения секрета
- •Протокол агРз
- •Протокол агВс
- •Субпротокол агпрс
- •Вычисления на мультипликативном вентиле Вычисления при fs-сбоях
- •Вычисления на линейном вентиле
- •Вычисления на мультипликативном вентиле
- •Протокол мат (XI,a)
- •Субпротокол mul(ai,bi)
- •Основной протокол
- •Протокол авф
- •Вычисления при By-сбоях
- •Процедура соим
- •Протокол соим(Zi)
- •Протокол ByMul
Злонамеренные модели Действия процессоров в злонамеренной модели
Теперь будем рассматривать независимо возможное отклонение процессоров от предопределенных протоколом действий. Для этого необходимо сделать несколько замечаний. Во-первых, для противника не существует никакого способа принудить процессоры участвовать в выполнении каких-либо действий при выполнении протокола. То есть возможное злонамеренное поведение противника не может состоять в инициализации протокола, в его приостановке или прерывания работы в любой желательной точке в какое-либо время.
Во-вторых, необходимо отметить, что не существует никакого способа для противника зафиксировать корректный вход протокола. То есть, процессор всегда может модифицировать свой локальный вход и не существует никакого способа для противника, чтобы предотвратить это. Отметим, что оба подобных сценария не могут, по очевидной причине, произойти в получестной модели, так как предполагалось, что такие процессоры в такой модели не отклоняются указанным ниже образом от протокола:
процессоры могут отказаться участвовать в протоколе (когда инициируется протокол);
процессоры подменяют свои локальные входы (и могут участвовать в протоколе с входами других процессоров);
процессоры преждевременно прерывают протокол (например, перед посылкой своего последнего сообщения).
Вычисления в идеальной модели
Теперь перенесем все вышеупомянутые рассуждения в определения идеальной модели. Будем предполагать, что процессоры имеют в своем распоряжении доверенное третье лицо. Определим его как доверенный процессорилиTP-процессор. Однако даже такая сторона не может предотвращать специфические злонамеренные действия. В идеальной модели нечестному процессору позволяется отказаться участвовать в протоколе или подменять свои локальные входы. Таким образом, вычисления в идеальной модели для случая с двумя процессорами могут выполняться следующим образом. (Более подробно идеальный и реальный сценарии для различных моделей вычислений рассматриваются далее).
Вычисления в идеальной модели
Вход.Каждый из двух процессоров получает входz.
Посылка входов доверенному процессору. Несбоящий процессор всегда посылаетzдоверенному процессору. Сбоящий процессор может, в зависимости отz, или прервать, или послать некоторыйz{0,1}zдоверенному процессору.
Доверенный процессор «отвечает» первому процессору. В случае если была получена входная пара (x,y) доверенный процессор, вычисляяf, сначала отвечает первому процессоруf1(x,y). В противном случае (то есть, когда получен только один вход) доверенный процессор отвечает обеим сторонам с специальным символом.
Доверенный процессор «отвечает» второму процессору.В случае если первый процессор нечестен, то доверенный процессор посылаетвторому процессору и останавливается. В противном случае (то есть, если не останавливается) доверенный процессор посылаетf2(x,y) второй стороне.
Выход. Несбоящий процессор всегда выводит сообщение, которое было получено от доверенного процессора. Сбоящий процессор может выдавать значение независимой (полиномиально вычислимой) функции от начального входа и сообщения, полученное от доверенного процессора.