En criptografía , el intercambio de secretos homomórficos es un tipo de algoritmo de intercambio de secretos en el que el secreto se cifra mediante cifrado homomórfico . Un homomorfismo es una transformación de una estructura algebraica en otra del mismo tipo para que la estructura se conserve. Es importante destacar que esto significa que para cada tipo de manipulación de los datos originales, existe una manipulación correspondiente de los datos transformados. [1]
Técnica
El intercambio de secretos homomórficos se utiliza para transmitir un secreto a varios destinatarios de la siguiente manera:
- Transforma el "secreto" usando un homomorfismo. Esto a menudo pone el secreto en una forma que es fácil de manipular o almacenar. En particular, puede haber una forma natural de 'dividir' el nuevo formulario como lo requiere el paso (2).
- Divida el secreto transformado en varias partes, una para cada destinatario. El secreto debe dividirse de tal manera que solo se pueda recuperar cuando se combinen todas o la mayoría de las partes. (Ver intercambio secreto )
- Distribuya las partes del secreto a cada uno de los destinatarios.
- Combine cada una de las partes de los destinatarios para recuperar el secreto transformado, quizás en un momento específico.
- Invierte el homomorfismo para recuperar el secreto original.
Ejemplos de
Supongamos que una comunidad quiere realizar una elección, utilizando un protocolo de votación descentralizado, pero quiere asegurarse de que los contadores de votos no mientan sobre los resultados. Usando un tipo de intercambio secreto homomórfico conocido como intercambio secreto de Shamir , cada miembro de la comunidad puede agregar su voto a un formulario que se divide en partes, cada parte se envía luego a un contador de votos diferente. Las piezas están diseñadas para que los contadores de votos no puedan predecir cómo las alteraciones de cada pieza afectarán al conjunto, desalentando así a los contadores de votos de manipular sus piezas. Cuando se han recibido todos los votos, los contadores de votos los combinan, lo que les permite recuperar los resultados electorales agregados.
En detalle, supongamos que tenemos una elección con:
- Dos posibles resultados, sí o no . Representaremos esos resultados numéricamente por +1 y -1, respectivamente.
- Varias autoridades, k , que contarán los votos.
- Un número de votantes, n , que presentarán sus votos.
- De antemano, cada autoridad genera una clave numérica disponible públicamente, x k .
- Cada votante codifica su voto en un polinomio p n de acuerdo con las siguientes reglas: El polinomio debe tener grado k-1 , su término constante debe ser +1 o -1 (correspondiente a votar "sí" o votar "no"), y sus otros coeficientes deben generarse aleatoriamente.
- Cada votante calcula el valor de su polinomio p n en la clave pública x k de cada autoridad .
- Esto produce k puntos, uno para cada autoridad.
- Estos k puntos son las "piezas" del voto: si conoce todos los puntos, puede averiguar el polinomio p n (y por lo tanto puede averiguar cómo votó el votante). Sin embargo, si solo conoce algunos de los puntos, no podrá averiguar el polinomio. (Esto se debe a que necesita k puntos para determinar un polinomio de grado -k-1 . Dos puntos determinan una línea, tres puntos determinan una parábola, etc.)
- El votante envía a cada autoridad el valor que se produjo utilizando la clave de la autoridad.
- Cada autoridad recoge los valores que recibe. Dado que cada autoridad solo obtiene un valor de cada votante, no puede descubrir el polinomio de ningún votante dado. Además, no puede predecir cómo la alteración de las presentaciones afectará la votación.
- Una vez que los votantes han enviado sus votos, cada autoridad k calcula y anuncia la suma A k de todos los valores que ha recibido.
- Hay k sumas, A k ; cuando se combinan, determinan un polinomio único P (x) --- específicamente, la suma de todos los polinomios de votantes: P (x) = p 1 (x) + p 2 (x) +… + p n ( X).
- El término constante de P (x) es de hecho la suma de todos los votos, porque el término constante de P (x) es la suma de los términos constantes del individuo p n .
- Por tanto, el término constante de P (x) proporciona el resultado total de la elección: si es positivo, más personas votaron por +1 que por -1; si es negativo, más personas votaron por -1 que por +1.
Características
Este protocolo funciona siempre que no todos los Las autoridades son corruptas; si lo fueran, podrían colaborar para reconstruir para cada votante y también modificar posteriormente los votos.
El protocolo requiere que se completen las autoridades t + 1, por lo tanto, en caso de que haya autoridades N> t + 1, las autoridades Nt-1 pueden estar corrompidas, lo que le da al protocolo un cierto grado de robustez.
El protocolo gestiona las identificaciones de los votantes (las identificaciones se enviaron con las papeletas) y, por lo tanto, puede verificar que solo los votantes legítimos hayan votado.
Bajo los supuestos de t:
- Una boleta no puede retroceder hasta la identificación, por lo que se preserva la privacidad de los votantes.
- Un votante no puede probar cómo votó.
- Es imposible verificar un voto.
El protocolo previene implícitamente la corrupción de las papeletas. Esto se debe a que las autoridades no tienen ningún incentivo para cambiar la boleta, ya que cada autoridad tiene solo una parte de la boleta y no tiene conocimiento de cómo el cambio de esta parte afectará el resultado.
Vulnerabilidades
- El votante no puede estar seguro de que su voto se haya registrado correctamente.
- Las autoridades no pueden estar seguras de que los votos fueran legales e iguales, por ejemplo, el votante puede elegir un valor que no es una opción válida (es decir, no en {-1, 1}) como -20, 50, lo que inclinará los resultados en su favor.
Ver también
- Sistemas de votación auditables de un extremo a otro
- Voto electronico
- Certificación de máquinas de votación
- Técnicas de posible fraude electoral a través de la manipulación física de las máquinas de votación.
- Prevención del fraude electoral: prueba y certificación del voto electrónico
- Sistema de recuento de votos
- E-democracia
- Computación multipartita segura
- Póquer mental
Referencias
- ^ Schoenmakers, Berry (1999). "Un simple esquema de intercambio de secretos públicamente verificable y su aplicación al voto electrónico". Avances en criptología . 1666 : 148-164. CiteSeerX 10.1.1.102.9375 .