Условие верифицируемости

Условие верифицируемости. Для всех возможных эффективных алгоритмов Прот, любой константы c>0 и для достаточно больших n вероятность

Prob((t*,(Да,u))ВсПр=(s=u)| (n,t,t*)РзПр=(Да,u)& t* < t & Д честный)<nc.

Условие неразличимости. Для секрета s* RS вероятность

Prob(s*=s |(n,t,t*)РзПр=(Да,s*) & Д честный)< 1/ |S|.

Свойство полноты означает, что если дилер Д честный и количество нечестных абонентов не больше t, тогда при любом выполнении протокола РзПр завершится корректно с вероятностью близкой к 1. Свойство верифицируемости означает, что все честные абоненты выдают в конце протокола ВсПр значение u, а если Д честный, тогда все честные абоненты восстановят секрет s=u. Свойство неразличимости говорит о том, что при произвольном выполнении протокола РзПр со случайно выбранным секретом s*, любой алгоритм Прот не может найти s*=s лучше, чем простым угадыванием.

Широковещательный примитив (Brсубпротокол). Введем следующее определение. Протокол называется tустойчивым широковещательным протоколом, если он инициализирован специальным участником (дилером Д), имеющим вход m (сообщение, предназначенное для распространения) и для каждого входа и коалиции нечестных участников (числом не более t) выполняются условия.

Условие завершения. Если дилер Д честный, то все честные участники обязательно завершат протокол. Кроме того, если любой честный участник завершит протокол, то все честные участники обязательно завершат протокол.

Условие корректности. Если честные участники завершат протокол, то они сделают это с общим выходом m*. Кроме того, если дилер честный, тогда m*=m.

Необходимо подчеркнуть, что свойство завершения является более слабым, чем свойство завершения в византийских соглашений. Для Brпротокола не требуется, чтобы несбоящие процессоры завершали протокол, в том случае, если дилер нечестен.

Brпротокол

Код для дилера (по входу m):

  1. Послать сообщение (сбщ,m) всем процессорам и завершить протокол с выходом m.
    Код для процессоров:
  2. После получения первых сообщений (сбщ,m) или (эхо,m), послать (эхо,m) ко всем процессорам и завершить протокол с выходом m.

Предложение 2.1. Brпротокол является tусточивым широковещательным протоколом для противников, которые могут приостанавливать отправку сообщений.

Доказательство. Если дилер честен, то все несбоящие процессоры получают сообщение (сбщ,m) и, таким образом, завершают протокол с выходом m. Если несбоящий процессор завершил протокол с выходом m, то он посылает сообщение (эхо,m) ко всем другим процессорам и, таким образом, каждый несбоящий процессор завершит протокол с выходом m. Ниже описывается устойчивый широковещательный протокол, который именуется BB. В протоколе принимается, что идентификатор дилера содержится в параметре m.


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

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


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

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