Función de punto distribuido

En criptografía , una función de punto distribuida es una primitiva criptográfica que permite que dos procesos distribuidos compartan una pieza de información y calculen funciones de su información compartida, sin revelar la información en sí a ninguno de los procesos. Es una forma de compartir secretos . ^[1]

Dados dos valores cualesquiera , se puede definir una función puntual (una variante de la función delta de Kronecker ) mediante ${\displaystyle a}$ ${\displaystyle b}$ ${\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}}}$

Es decir, es cero en todas partes excepto en , donde su valor es . ^[1] ${\displaystyle a}$ ${\displaystyle b}$

Una función de punto distribuida consta de una familia de funciones , parametrizadas por claves , y un método para derivar dos claves y a partir de dos valores de entrada cualesquiera y , de modo que para todos , ${\displaystyle f_{k}}$ ${\displaystyle k}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle x}$

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

donde denota el bit a bit exclusivo o de los dos valores de la función. Sin embargo, dada solo una de estas dos claves, los valores de para esa clave deberían ser indistinguibles de los aleatorios. ^[1] ${\displaystyle \oplus }$ ${\displaystyle f}$

Se sabe cómo construir una función puntual distribuida eficiente a partir de otra primitiva criptográfica, una función unidireccional . ^[1]

En la otra dirección, si se conoce una función de punto distribuida, entonces es posible realizar una recuperación de información privada . Como ejemplo simplificado de esto, es posible probar si una clave pertenece a una base de datos distribuida replicada sin revelar a los servidores de la base de datos (a menos que coludan entre sí) qué clave se buscó. Para encontrar la clave en la base de datos, cree una función de punto distribuida para y envíe las dos claves resultantes y a dos servidores diferentes que tengan copias de la base de datos. Cada copia aplica su función o a todas las claves en su copia de la base de datos y devuelve el o exclusivo de los resultados. Los dos valores devueltos serán diferentes si pertenece a la base de datos y serán iguales en caso contrario. ^[1] ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle P_{a,1}(x)}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle f_{q}}$ ${\displaystyle f_{r}}$ ${\displaystyle a}$

Referencias

1. Gilboa, Niv; Ishai, Yuval (2014), "Funciones de punto distribuidas y sus aplicaciones", en Nguyen, Phong Q.; Oswald, Elisabeth (eds.), Avances en criptología – EUROCRYPT 2014: 33.ª Conferencia internacional anual sobre la teoría y las aplicaciones de las técnicas criptográficas, Copenhague, Dinamarca, 11-15 de mayo de 2014, Actas (PDF) , Lecture Notes in Computer Science, vol. 8441, Springer, págs. 640–658, doi : 10.1007/978-3-642-55220-5_35