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

Постановка задачи

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

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

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

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

Задача конфиденциального вычисления была впервые сформулирована А.Яо для случая с двумя участниками в 1982 г. В 1987 г. О. Голдрайх, С. Микали и А. Вигдерсон показали, как безопасно вычислить любую функцию, аргументы которой распределены среди участников в вычислительной установке (то есть в конструкции, где потенциальный противник ограничен в действиях вероятностным полиномиальным временем). В их работе рассматривалась синхронная сеть связи из n участников, где каналы связи небезопасны и стороны, также как и противник, ограниченны в своих действиях вероятностным полиномиальным временем. В своей модели вычислений они показали, что в предположении существования односторонних функций с секретом можно построить многосторонний протокол (с n участниками) конфиденциальных вычислений любой функции в присутствие пассивных противников (т.е., противников, которым позволено только "прослушивать" коммуникации). Для некоторых типов противников (для византийских сбоев) авторы привели протокол для конфиденциального вычисления любой функции, где ( n/2 1) участников протокола являются нечестными (или ( n/2 1)протокол конфиденциальных вычислений).

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

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

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

Определение односторонней функции, описание используемых примитивов, схем и протоколов

В качестве одного из основных математических объектов в данной работе используются односторонние функции, то есть вычислимые функции, для которых не существует эффективных алгоритмов инвертирования. Необходимо отметить, что односторонняя функция гипотетический объект, поэтому называть конкретные функции односторонними математически некорректно. Впервые такую гипотетическую конструкцию для конкретного криптографического приложения, открытого распределения ключей, предложили У. Диффи и М. Хеллман в 1976 г. (см, например, определения в работе [6]). Они показали, что вычисление степеней в мультипликативной группе вычетов над конечным полем является простой задачей с точки зрения состава необходимых вычислений, в то время как извлечение дискретных логарифмов над этим полем предположительно сложная вычислительная задача.

Неформально говоря, для двух независимых множеств X и Y функция f:X > Y называется односторонней, если для каждого x X можно легко вычислить f(x), в то время как почти для всех y Y вычислительно трудно получить такой x X, что f(x)=y, при условии, что такой x существует.

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

Функция f называется односторонней, если существует полиномиальная машина Тьюринга T, которая на любом входе x вычисляет f(x) и для любого полиномиального алгоритма A справедливо следующее.

Пусть x R n и слово y=f(x) подано на вход алгоритма A. Тогда для любого полинома p и для всех достаточно больших n вероятность Prob(f(A(y))=y)<1/p(n).

Вероятность берется по выбору значения x из n и, если A это вероятностная машина Тьюринга, по вырабатываемым ею случайным величинам.


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок