title: Protocolo seguro
text: # Protocolo seguro
  
  Los protocolos seguros, también llamados protocolos de preservación de la privacidad o protocolos de preservación de la confidencialidad, son protocolos que usan técnicas criptográficas y cuyo objetivo es conseguir que entidades colaboren con su información preservando su privacidad y confidencialidad. Por tanto el objetivo es realizar cómputos (computar una función) que necesitan de la información de las distintas entidades, revelando solo el resultado de dicho computo (no la información privada de cada entidad).
  
  Al problema de computar cualquier función de una forma segura se le llama computación segura multipartita o SMC (del inglés Secure Multiparty Protocol). Cuando hay exactamente dos entidades se dice que se trata de Computación segura bipartita o 2PC (siglas del inglés Secure Two-Party Computation)
  
  ## Adversarios
  
  Hay diferentes tipos de adversarios que tienen que ser considerados cuando se crean protocolos seguros. Los básicos son:
  
  * Adversario honesto pero curioso o HBC (siglas del inglés Honest-But-Curious), también llamados adversarios semi-honestos o adversarios pasivos. El adversario sigue fielmente el protocolo especificado, pero después de que el protocolo se ha completado intentará aprender información adicional sobre otras entradas. Este modelo no es realista en muchas ocasiones sin embargo si un protocolo no puede ser desarrollado para este modelo simplificado, entonces hay muy pocas posibilidades de que el protocolo pueda ser desarrollado para un modelo de adversarios más realista.
  * Adversario malicioso, también llamado adversario activo. Es un tipo de adversario más realista que se desvía arbitrariamente del protocolo para obtener alguna ventaja sobre alguno de los participantes. Las ventajas que el adversario puede obtener pueden ser por ejemplo:
     * Aprender información adicional sobre la información privada de las otras entidades
     * Modificar el resultado del protocolo
     * Abortar el protocolo prematuramente (quizá después de que el adversario aprenda un resultado parcial para así evitar que otros aprendan el resultado)
  
  ## Formalización de 2PC en modelo HBC
  
  Es difícil formalizar de forma general los protocolos segurros. Como ejemplo vamos a dar la formalización de este tipo de protocolos más simple, los protocolo seguros bipartitos en el modelo de adversarios HBC.
  
  Para que el protocolo sea seguro todo lo que puede ser computado desde el protocolo debe poder ser deducido desde la salida y uno de los valores de entrada (la información privada de una entidad). Supongamos que A y B están interesados en realizar un protocolo para computar un función $f$. Este protocolo involucar uno o más intercambio de mensajes entre A y B. Vamos a llamar a estos mensajes el transcript del protocolo. Este transcript permite verificar que no se revela la información que se privada de cada entidad. Más específicamente, el transcript de los envíos de A a B deberían ser computable desde el resultado del protocolo y la información de B. En otro caso el protocolo podría revelar más información a B que los resultados (análogas conclusiones podemos hacer de las transmisiones de B a A). Una forma para conseguir esto es requerir que el transcript de comunicación sea exactamente generable desde la salida del protocolo, pero esto es una limitación grande. Sin embargo, si el adversario es computacionalmente limitado, entonces es suficiente generar un transcript que sea tan cercano al transcript real (computacionalmente indistinguible) que el adversario no pueda distinguir entre el real y el transcript simulado.
  
  Supongamos que A y B tienen respectivas entradas $x_{A}$ y $x_{B}$ y que al final del protocolo A debería aprender $f_{A}(x_{A},x_{B})$ y B debería aprender $f_{B}(x_{A},x_{B})$. Notar que en muchos casos $f_{A}$ y $f_{B}$ son iguales, sin embargo se pone para tener una definición lo más general posible. Dado un protocolo $\Pi$, la vista que A tiene del protocolo (todos los mensajes que recibe de B) es denotada por $\{view_{B}^{\Pi }(x_{A},x_{B})\}_{x_{A},x_{B}\in \{0,1\}^{*}}$ y la vista que B tiene del protocolo es denotada por $\{view_{A}^{\Pi }(x_{A},x_{B})\}_{x_{A},x_{B}\in \{0,1\}^{*}}$.
  
  El protocolo $\Pi$ se dice que es seguro en el modelo HBC si existen algoritmos de simulación con tiempo polinomial probabilístico, $S_{A}$ y $S_{B}$, tal que:
  
  * $\{S_{A}(x_{A},f_{A}(x_{A},x_{B}))\}_{x_{A},x_{B}\in \{0,1\}^{*}}$ y $\{view_{A}^{\Pi }(x_{A},x_{B})\}_{x_{A},x_{B}\in \{0,1\}^{*}}$ son computacionalmente indistinguibles.
  * $\{S_{B}(x_{B},f_{B}(x_{A},x_{B}))\}_{x_{A},x_{B}\in \{0,1\}^{*}}$ y $\{view_{B}^{\Pi }(x_{A},x_{B})\}_{x_{A},x_{B}\in \{0,1\}^{*}}$ son computacionalmente indistinguibles.
  
  Observar que esta definición establece que existe un algoritmo eficiente que puede simular todos los mensajes enviados por B cuando solo se tiene las entradas de A y la salida. Análoga conclusión se puede sacar la para el otro sentido. Así que cualquier cosa aprendida del protocolo tiene que ser también aprendible desde el resultado, y por tanto el protocolo revela solo el resultado e inferencias derivadas desde el propio resultado
  
  