Асинхронный ТРсценарий

Асинхронный ТРсценарий

В начале вычислений процессоры посылают свои входы ТРпроцессору. В то же время, существует планировщик D, который доставляет сообщения участников некоторому базовому подмножеству процессоров, мощностью не меньше nt, обозначаемому как C и являющемуся независимым от входов честных процессоров. ТРпроцессор по получению входов аргументов функции (возможно некорректных) из множества C, предопределенно оценивает значение вычисляемой функции, основываясь на C и входах участников из С. (Здесь для корректности может использоваться следующее предопределенное оценивание: установить входы из C в 0 и вычислить данную функцию). Затем ТРпроцессор посылает значение оценочной функции обратно участникам совместно с базовым множеством С. Наконец честные процессоры вычислений выдают то, что они получили от ТРучастника. Нечестные участники выдают значение некоторой независимой функции, информацию о которой они "собирали" в процессе вычислений. Эта информация может состоять из их собственных входов, случайных значений, используемых при вычислениях и значения оценочной функции.

Так же как и в синхронной модели, вычисления в реальной асинхронной модели безопасны, если эти вычисления "эквивалентны" вычислениям в ТРсценарии.

Далее в соответствии с работой [61] сделаем попытку формализовать понятия полноты и безопасности протокола асинхронных конфиденциальных вычислений.

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

Для удобства мы унифицируем коалицию нечестных процессоров и планировщика. Это не увеличит мощность противника в ТРсценарии, так как и нечестные участники, и планировщик имеют неограниченную вычислительную мощность.

Для вектора =x1,...,x2 и множества, пусть C определяет вектор, спроектированный на индексы из C. Для подмножества B [n] и вектора |B| vector, пусть определяет вектор, полученный из подстановкой входов из B соответствующими входами из. Используя эти определения, можно определить оценочную функцию f с базовым множеством C [n] как

Пусть A область возможных входов процессоров и пусть R область случайных входов. ТРпротивник это кортеж А=(B,h,c,O), где B [n] множество нечестных участников, h:A|B| x R > A |B| функция подстановки входов, с:A |B| x R > {C [n] | |C| nt} функция выбора базового множества и O:A |B| x R x A > {0,1}* функция выхода для нечестных процессоров.

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

Пусть f:An > A для некоторой области A. Выход функции вычисления f в ТРсценарии по входу и с ТРпротивником А=(B,h,c,O) это nvector τ(,A) = τ1(,A)...τn(,A) случайных переменных, удовлетворяющих для каждого 1 i n:

где r объединенный случайный вход нечестных процессоров, C= (B,r) и

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

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

  1. Пусть B=(B,β) коалиция нечестных процессоров, где B [n] множество нечестных процессоров и β их совместная стратегия.
  2. Пусть πi(,B,D) определяет выход процессора Pi после выполнения протокола πi по входу, с планировщиком D и коалиции B. Пусть также π (,B,D)= π1(,B,D)... πn(,B,D).

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

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

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


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

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


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

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