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

       

Примитив «Забывающий обмен»


Пусть k

- фиксированное целое и пусть b1,b2,...,bkÎ{0,1} и iÎ{1,...,k}.

Тогда забывающий обмен OTk1

определяется как функциональная зависимость:

OTk1((b1,b2,...,bk),i)=(l,bi).

Эта вычислимая функция является в явном виде асимметричной и реализуется посредством протокола взаимодействия двух участников (процессоров). Обычно первый процессор, который содержит вход (b1,b2,...,bk), называется отправителем (илиS), а второй процессор, который содержит вход iÎ{1,...,k}, называется получателем (или R).

Интуитивно, цель забывающего обмена состоит в том, чтобы для отправителя обменяться i-тым битом с получателем так, чтобы не позволить последнему получить какую-либо информацию относительно значения любого другого своего бита и так, чтобы не позволить отправителю получить какую-либо информацию о бите, который был затребован получателем.

С использованием любой перестановки с секретом {fi}iÎI (см. Приложение), ниже описывается протокол для конфиденциально вычисления OTk1. Так как мы имеем дело с конечными вычислимыми функциями, безопасность будет рассматриваться в терминах некоторого дополнительного параметра n, именуемого далее параметром безопасности.

Протокол ОТПЧМ

Вход:

Отправитель R

имеет вход b1,b2,...,bkÎ{0,1}k, а получатель S имеет вход iÎ{1,...,k} и обе стороны имеют дополнительный параметр безопасности 1n.

1. Отправитель S равномерно выбирает пару односторонних функций с секретом (a,t) (см. Приложение), выполняя алгоритм их генерации G по входу 1n. Параметр a отсылается R.



2. Получатель R равномерно и независимо выбирает e1,...,ekÎR*Da, устанавливает yi=f(ei) и yj=ej для каждого j¹i и отсылает (y1,y2,...,yk) к отправителю S. Для этого:

2.1. Равномерно и независимо выбирает ejÎR*Da каждый раз, вызывая алгоритм генерации ej=D(a,rj), rjÎR*Z, j=1,...,k.


2.2. Вычисляет yi=f(ei).

2.3. Для j¹i присваивает yj=ej.

2.4. Получатель R отсылает (y1,y2,...,yk) к отправителю S. Таким образом, получатель знает fa-1(yi)=ei, однако не может предсказать b(fa-1(yi)) для j¹i.

3. После получения (y1,y2,...,yk), используя знание секрета для инвертирования односторонней функции с секретом, отправитель S вычисляет xj=fa-1(yj) для jÎ{1,...,k}. В свою очередь, S посылает (b1Åb(x1),b2Åb(x2),...,bkÅb(xk)) получателю R.

4. По получении (c1,c2,...,ck) получатель локально выдает ciÅb(ei).

Отметим сначала, что вышеупомянутый протокол корректно вычисляет OTk1 так как

ciÅb(ei)=biÅb(xi))Åb(ei)=biÅb(fa-1(fa(ei)))Åb(ei)=bi.

Аргументы для доказательства того, что протокол действительно конфиденциально вычисляет OTk1 следующие. Интуитивно, отправитель S не получает никакой информации при выполнении протокола, так как для любого возможного значения i все потенциальные отправители «видят» одно и то же распределение равномерно и независимо выбранных элементов из Da.

Интуитивно, получатель R не получает никакой (с вычислительной точки зрения) информации при выполнении протокола, так как для j¹i, единственные данные, которые могут «говорить» о bj

– это кортеж (a,ej,bjÅ(fa-1(ej))), из которого невозможно предсказать bj лучше, чем простым угадыванием.

Формальные аргументы даны в работе [Go1].


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