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



         

Протокол вычислений на арифметической схеме над GF(


Теперь мы покажем, что процесс вычисления любой детерминированной вычислимой функции, которая вычисляется посредством арифметической схемы над GF(2), конфиденциально сводим к вычислению функции в соответствии с уравнениями(3.1) - (3.2). Напомним, что последняя вычислимая функция соответствует частному вычислению на мультипликативных вентилях для входов, общедоступных обоим процессорам. Таким образом, можно констатировать, что эта вычислимая функция может рассматриваться как эмулирование мультипликативного вентиля, как это описано выше. В частности разделение битового значения v

между обоими процессорами означает равномерно выбранную пару битов (v1,v2) так, что v=v1+v2, где первый процессор содержит v1, второй - v2. Наша цель заключается в разделении, через частные вычисления, долей входных линий схемы на доли всех линий схемы так, чтобы, в конце концов, мы получили бы доли выходных линий схемы.

В начале мы рассмотрим нумерацию всех линий схемы. Входные линии схемы (n) для каждого процессора будут пронумерованы 1,2,...,2n так, что для j=1,...,n j-тый вход процессора i соответствует ((i-1)n+j)-той линии. Линии будут пронумерованы так, чтобы выходные линии каждого вентиля имеют большую нумерацию, чем его входные линии. Для простоты предположим, что каждый процессор получает n выходных битов, и что выходные биты второго процессора соответствуют последним n

линиям схемы.

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

Редукция к МВ

Вход.

Процессор i

содержит строку битов xi1...xinÎ{0,1}n, i=1,2.

1. Разделение входов. Каждый процессор делит каждый из своих входных битов с другим процессором. То есть для каждого i=1,2 и j=1,...,n

процессор i равномерно выбирает бит rij и посылает его другому процессору, как долю входной линии (с нумерацией ((i-1)n+j) последнего. Процессор i устанавливает свою собственную долю на входной линии с нумерацией (i-1)n+j в значение xij+rij.




Содержание  Назад  Вперед