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

       

Водные замечания по проблематике конфиденциальных вычислений


www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

В последнее время появилась насущная необходимость в создании новых информационных технологий разработки ПО, исходно ориентированных на создание безопасных программных продуктов относительно заданного класса решаемых задач. В этом случае проблема исследований сводится к разработке таких математических моделей, которые представляются адекватной формальной основой для создания методов защиты программного обеспечения на этапе его проектирования и разработки. При этом изначально предполагается, что:

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

·     в процессе эксплуатации злоумышленник может вносить в программы изменения (например, внедрение компьютерных вирусов, внесение программных закладок);

·     средства вычислительной техники, на которых выполняются программы, не свободны от аппаратных закладок.

Тогда, исходя из этих допущений, формулируется следующая неформальная постановка задачи: «Требуется разработать программное обеспечение таким образом, что, несмотря на указанные выше «помехи», оно функционировало бы правильно». Одно из основных достоинств здесь состоит в том, что одни и те же методы позволяют защищаться от злоумышленника, действующего как на этапе разработки, так и на этапе эксплуатации программного обеспечения. Однако, это достигается за счет некоторого замедления вычислений, а также повышения затрат на разработку программного обеспечения.

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



Задачу конфиденциального вычисления функции, которая решается посредством многостороннего интерактивного протокола можно описать в следующей постановке. Имеется n


участников протокола или n

процессоров вычислительной системы, соединенных сетью связи. Изначально каждому процессору известна своя «часть» некоторого входного значения x. Требуется вычислить f(x), f - некоторая известная всем участникам вычислимая функция, таким образом, чтобы выполнились следующие требования:

·     корректности,

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

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

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

процессоров и распределенного алгоритма для вычисления f. В системе имеется еще один абсолютно надежный участник, который имеет доступ к секретному значению x и имеет возможность выделить каждому участнику свою «долю» x. Название протоколы «конфиденциальное вычисление функции» отражает тот факт, что требование конфиденциальности является основным, то есть значение x не должно попасть в руки злоумышленника.

Задача конфиденциального вычисления была впервые сформулирована А. Яо для случая с двумя участниками в 1982 г. [Y1]. В 1987 г. О. Голдрайх, С. Микали и А. Вигдерсон показали [GMW], как безопасно вычислить любую функцию, аргументы которой распределены среди участников в вычислительной установке (то есть в конструкции, где потенциальный противник ограничен в действиях вероятностным полиномиальным временем).


В их работе рассматривалась синхронная сеть связи из n

участников, где каналы связи небезопасны и стороны, также как и противник, ограниченны в своих действиях вероятностным полиномиальным временем. В своей модели вычислений они показали, что в предположении существования односторонних функций с секретом можно построить многосторонний протокол (с n участниками) конфиденциальных вычислений любой функции в присутствие пассивных противников (т.е., противников, которым позволено только «прослушивать» коммуникации). Для некоторых типов противников (для византийских сбоев) авторы привели протокол для конфиденциального вычисления любой функции, где (én/2ù-1) участников протокола являются нечестными (или (én/2ù-1)-протокол конфиденциальных вычислений).

В дальнейшем изучались многосторонние протоколы конфиденциальных вычислений в модели с защищенными каналами. Было показано, что если противник пассивный, то существует (én/2ù-1)-протокол для конфиденциального вычисления любой функции. Если противник активный (т.е., противник, которому позволено вмешиваться в процесс вычислений), тогда любая функция может быть вычислена посредством (én/3ù-1)-протокола конфиденциальных вычислений. Эти протоколы являются безопасными в присутствие неадаптивных противников (т.е., противников, действующих в схеме вычислений, в которой множество участников независимо, но фиксировано).

В последнее время исследуются вычисления для случая активных противников, ограниченных в работе вероятностным полиномиальным временем, где часть участников вычислений может быть «подкуплена» противником и многосторонние конфиденциальные вычисления при наличии незащищенных каналов и с вычислительно неограниченным противником, а также исследовались многосторонние конфиденциальные вычисления с нечестным большинством участников при наличии защищенных каналов. Кроме того, изучаются многосторонние протоколы конфиденциальных вычислений при наличии защищенных каналов и динамического противника (т.е., противника, который может «подкупать» различных участников в разные моменты времени).В фундаментальной работе [MR] предложены определения для многосторонних конфиденциальных вычислений при наличии защищенных каналов и в присутствии адаптивных противников.

В работе [BCG], авторы начали комплексные исследования асинхронных конфиденциальных вычислений. Они рассмотрели полностью асинхронную сеть (т.е., сеть, где не существует глобальных системных часов), в которой стороны соединены защищенными каналами связи. Авторы привели первый асинхронный протокол византийских соглашений с оптимальной устойчивостью, где противник может «подкупать» én/3ù-1 из n участников вычислений.


Содержание раздела