Примитив «Забывающий обмен»
Пусть 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].