Распределенная точечная функция

В криптографии распределенная точечная функция — это криптографический примитив , который позволяет двум распределенным процессам совместно использовать часть информации и вычислять функции их общей информации, не раскрывая саму информацию ни одному из процессов. Это форма секретного обмена . ^[1]

При наличии любых двух значений можно определить точечную функцию (вариант дельта -функции Кронекера) следующим образом:${\displaystyle а}$${\displaystyle б}$ ${\displaystyle P_{a,b}(x)}$

${\displaystyle P_{a,b}(x)={\begin{cases}b\qquad {\text{for }}x=a\\0\qquad {\text{for }}x\neq a\end{cases}}}$

То есть, он равен нулю везде, кроме точки , где его значение равно . ^[1]${\displaystyle а}$${\displaystyle б}$

Распределенная точечная функция состоит из семейства функций , параметризованных ключами , и метода вывода двух ключей и из любых двух входных значений и , такого, что для всех ,${\displaystyle f_{k}}$${\displaystyle к}$${\displaystyle д}$${\displaystyle r}$${\displaystyle а}$${\displaystyle б}$${\displaystyle x}$

${\displaystyle P_{a,b}(x)=f_{q}(x)\oplus f_{r}(x),}$

где обозначает побитовое исключающее или двух значений функции. Однако, если задан только один из этих двух ключей, значения для этого ключа должны быть неотличимы от случайных. ^[1]${\displaystyle \oplus}$${\displaystyle f}$

Известно, как построить эффективную распределенную точечную функцию из другого криптографического примитива — односторонней функции . ^[1]

В другом направлении, если известна распределенная точечная функция, то можно выполнить поиск частной информации . В качестве упрощенного примера этого можно проверить, принадлежит ли ключ реплицированной распределенной базе данных, не раскрывая серверам базы данных (если они не сговариваются друг с другом), какой ключ искали. Чтобы найти ключ в базе данных, создайте распределенную точечную функцию для и отправьте полученные два ключа и на два разных сервера, содержащих копии базы данных. Каждая копия применяет свою функцию или ко всем ключам в своей копии базы данных и возвращает исключительное или результатов. Два возвращенных значения будут отличаться, если принадлежит базе данных, и будут равны в противном случае. ^[1]${\displaystyle а}$${\displaystyle а}$${\displaystyle P_{a,1}(x)}$${\displaystyle д}$${\displaystyle r}$${\displaystyle f_{q}}$${\displaystyle f_{r}}$${\displaystyle а}$