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

       

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


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

Для вектора

Безопасность асинхронных вычислений
 и множества 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) идентично распределены (эквивалентны).


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