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

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

Учитывая любые два значения $a$ и $b$ можно определить точечную функцию $P_{a,b}(x)$ (вариант дельта-функции Кронекера ) по

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

То есть оно равно нулю везде, кроме точки $a$, где его значение $b$.

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

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

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

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

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