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


Доказательство безопасности схемы АПРС - часть 4


Пусть I обозначает множество чередуемых последовательностей 2t полиномов степени t.

Лемма 3.7.

Пусть F – поле с |Fd

и пусть sÎF. Тогда для каждой чередуемой последовательности f1(·),...,fd(·), g1(·),...,gd(·) в I существует единственный полином h(·,·)ÎHs такой, что для каждого 1£i£d мы имеем h(·,i)=fi(·) и h(i,·)=gi(·).

Доказательство.

См. работу [BCG].

Далее предположим, что дилер честен и пусть s

– разделяемое значение. Тогда дилер имеет на шаге 1 протокола АРзПр полином h(·,·) с равномерным распределением вероятностей над Hs. Кроме того, вся необходимая информация о множестве из t

процессоров, полученная во время выполнения протокола АРзПр, является чередуемой последовательностью f1(·),...,ft(·), g1(·),...,gt(·) в I такой, что для каждого 1£i£t мы имеем h(·,i)=fi(·) и h(i,·)=gi(·).

Из леммы 3.7 следует, что для каждого разделяемого значения sÎF это соответствие между полиномами в Hs и чередуемыми последовательностями в I

– является взаимнооднозначным. Следовательно, равномерное распределение над полиномами из Hs индуцирует равномерное распределение вероятностей над чередуемыми последовательностями в I.       <




- Начало -  - Назад -  - Вперед -