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

       

Безопасность асинхронных вычислений


Сначала напомним, что как и сбоящие процессоры, так и планировщик имеют неограниченную вычислительную мощность.

Для вектора

 и множества CÍ[n]@{1,...,n}, пусть
 определяет вектор
, спроектированный на индексы из C. Для подмножества BÍ[n] и вектора
, пусть
 определяет вектор, полученный из
 подстановкой входов из B соответствующими входами из
. Используя эти определения, можно определить оценочную функцию f с базовым множеством CÍ[n] как
@
.

Пусть A – область возможных входов процессоров и пусть R

– область случайных входов. ТР-противник

это кортеж А=(B,h,c,O), где BÍ[n] – множество сбоящих процессоров, h:AïBï´R®AïBï - функция подстановки входов, с:AïBï´R®{CÍ[n]½ôCô³n-t} – функция выбора базового множества и O:AïBï´R´A®{0,1}* - функция выхода для сбоящих процессоров.

Функции h

и O представляют собой программы сбоящих процессоров, а функция c – комбинацию планировщика и программ сбоящих процессоров.

Пусть f:An®A для некоторой области A. Выход функции вычисления f в ТР-сценарии по входу

 и с ТР-противником А=(B,h,c,O) – это

n-размерный вектор 

=
...
 случайных переменных, удовлетворяющих для каждого 1£i£n:

=
       ,

где r - объединенный случайный вход сбоящих процессоров, C=

 и

Акцентируем внимание на то, что выход сбоящих процессоров и выход несбоящих процессоров вычисляется на одном и том же значении случайного входаr.

Далее формализуем понятие вычисления «в реальной жизни».

1. Пусть B=(B,b) – коалиция нечестных процессоров, где BÌ[n] – множество нечестных процессоров и b

- их совместная стратегия.

2. Пусть pi(

,B,D) определяет выход процессора Pi

после выполнения протокола pi по входу

, с планировщиком D и коалиции B. Пусть также P(
,B,D)=p1(
,B,D)...pn(
,B,D).

Кроме того, пусть f:An®A для некоторой области A и пусть P


- протокол для n процессоров. Будем говорить, что P безопасно t-вычисляет функцию f в асинхронной модели для каждой коалиции B с не более, чем из t сбоящих процессоров, если выполняются следующие условия.

Условие завершения (условие полноты).

По всем входам все честные процессоры завершают протокол с вероятностью 1.

Условие безопасности. Существует ТР-противник A такой, что для каждого входа
 векторы t(
,A) и P(
,B,D) идентично распределены (эквивалентны).


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