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

       

Общие определения


Следующее определение формализует требования к схеме проверяемого разделения секрета, но в асинхронной установке[BCG].

Определение 3.1. Пусть (АРзПр,АВсПр) - пара многосторонних протоколов таких, что каждый несбоящий процессор, который завершает протокол АРзПр

впоследствии вызывает протокол АВсПр

с локальным выходом протокола АРзПр

как локальным входом. Схема (АРзПр,АВсПр) называется t-устойчивой схемой асинхронного разделения секрета – АПРС для n процессоров, если для каждой коалиции из не более, чем t процессоров и каждого планировщика выполняются следующие условия.

Условие завершения.

1. Если дилер честен, тогда каждый несбоящий процессор, в конечном счете, завершит протокол АРзПр. 2. Если некоторый несбоящий процессор завершил протокол АРзПр, то все несбоящие процессоры, в конечном счете, завершат протокол АРзПр. 3. Если несбоящий процессор завершил протокол АРзПр, то он завершит и протокол АВсПр.

Условие корректности. Как только несбоящий процессор завершил протокол АРзПр, тогда существует уникальное значение r такое, что: 1. все несбоящие процессоры выдают r (а, именно, r - восстанавливаемый секрет); 2. если дилер честен и делит секрет s, тогда r=s.

Условие конфиденциальности.

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

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

неудачно.


В качестве одного из основных математических объектов в данной работе используются односторонние функции, то есть вычислимые функции, для которых не существует эффективных алгоритмов инвертирования. Необходимо отметить, что односторонняя функция - гипотетический объект, поэтому называть конкретные функции односторонними математически некорректно. Впервые такую гипотетическую конструкцию для конкретного криптографического приложения, - открытого распределения ключей, предложили У.Диффи и М. Хеллман в 1976 г. [DH]. Они показали, что вычисление степеней в мультипликативной группе вычетов над конечным полем является простой задачей с точки зрения состава необходимых вычислений, в то время как извлечение дискретных логарифмов над этим полем – предположительно сложная вычислительная задача.

Неформально говоря, для двух независимых множеств X и Y функция f:X®Y называется односторонней, если для каждого xÎX можно легко вычислить f(x), в то время как почти для всех yÎY вычислительно трудно получить такой xÎX, что f(x)=y, при условии , что такой x

существует.

Все формальные определения односторонних функций в терминах теории сложности вычислений даны в приложении.



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