Externalización segura de cálculos de álgebra lineal

Presentamos protocolos mejorados para la externalización segura y privada de cálculos de álgebra lineal, que permiten a un cliente externalizar de manera segura cálculos algebraicos costosos (como la multiplicación de grandes matrices) a un servidor remoto, de tal manera que el servidor no aprenda nada sobre la entrada privada del cliente o el resultado del cálculo, y cualquier intento de corrupción de la respuesta por parte del servidor sea detectado con alta probabilidad. El trabajo computacional realizado en el cliente es lineal en el tamaño de su entrada y no requiere que el cliente realice localmente ninguna encriptación costosa de dicha entrada. La carga computacional en el servidor es proporcional a la complejidad temporal de los algoritmos actualmente utilizados en la práctica para resolver el problema algebraico (por ejemplo, proporcional a n³ para multiplicar dos matrices de n x n). Las mejoras que ofrecemos son: (i) mientras que el trabajo anterior requería más de un servidor remoto y asumía que no coludían, nuestra solución funciona con un solo servidor (pero se adapta fácilmente a muchos, para un mejor rendimiento); (ii) mientras que el trabajo anterior requería que un servidor realizara cálculos criptográficos costosos (por ejemplo, encriptaciones homomórficas), nuestra solución no utiliza ningún tipo de primitivo criptográfico costoso; y (iii) mientras que en trabajos anteriores la colusión de los servidores contra el cliente revelaba a estos las entradas del cliente, nuestro esquema es resistente a dicha colusión. Al igual que en trabajos anteriores, mantenemos la propiedad de que el esquema permite al cliente detectar cualquier intento de corrupción de la respuesta por parte de los servidores, incluso cuando el intento es colusivo y coordinado entre los servidores.