En criptografía , un esquema de intercambio de secretos es verificable si se incluye información auxiliar que permite a los jugadores verificar que sus acciones son consistentes. Más formalmente, el intercambio de secretos verificable garantiza que, incluso si el distribuidor es malicioso, existe un secreto bien definido que los jugadores pueden reconstruir más tarde. (En el intercambio de secretos estándar, se supone que el distribuidor es honesto). [1] El concepto de intercambio de secretos verificable (VSS) fue introducido por primera vez en 1985 por Benny Chor , Shafi Goldwasser , Silvio Micali y Baruch Awerbuch . [2]
En un protocolo VSS, el jugador distinguido que desea compartir el secreto se denomina "distribuidor". El protocolo consta de dos fases: una fase de intercambio y una fase de reconstrucción.
Reparto: inicialmente, el crupier mantiene el secreto como entrada y cada jugador tiene una entrada aleatoria independiente. La fase de reparto puede constar de varias rondas. En cada ronda, cada jugador puede enviar mensajes privados a otros jugadores y también puede transmitir un mensaje. Cada mensaje enviado o transmitido por un jugador está determinado por su entrada, su entrada aleatoria y los mensajes recibidos de otros jugadores en rondas anteriores.
Reconstrucción: En esta fase cada jugador proporciona su vista completa de la fase de compartición y se aplica una función de reconstrucción que se toma como salida del protocolo.
Una definición alternativa dada por Oded Goldreich define VSS como un protocolo multipartito seguro para calcular la funcionalidad aleatoria correspondiente a algún esquema de intercambio de secretos (no verificable). Esta definición es más sólida que las otras definiciones y es muy conveniente de usar en el contexto de la computación multipartita segura general.
El intercambio de secretos verificable es importante para la computación multipartidaria segura . La computación multipartidaria se logra generalmente compartiendo en secreto las entradas y manipulándolas para calcular alguna función. Para manejar adversarios "activos" (es decir, adversarios que corrompen nodos y luego los hacen desviarse del protocolo), el esquema de intercambio de secretos debe ser verificable para evitar que los nodos que se desvían del protocolo se salgan del protocolo.
Un ejemplo comúnmente utilizado de un esquema VSS simple es el protocolo de Paul Feldman, [3] que se basa en el esquema de intercambio de secretos de Shamir combinado con cualquier esquema de cifrado que satisfaga una propiedad homomórfica específica (que no necesariamente es satisfecha por todos los esquemas de cifrado homomórficos ).
La siguiente descripción da una idea general, pero no es segura tal como está escrita. (Tenga en cuenta, en particular, que el valor publicado g s filtra información sobre el secreto s del distribuidor ).
En primer lugar, se elige públicamente como parámetro del sistema un grupo cíclico G de orden primo q , junto con un generador g de G . El grupo G debe elegirse de forma que sea difícil calcular logaritmos discretos en este grupo. (Normalmente, se toma un subgrupo de orden q de ( Z / p Z ) × , donde q es un primo que divide a p − 1 .)
El distribuidor calcula entonces (y mantiene en secreto) un polinomio aleatorio P de grado t con coeficientes en Z q , de modo que P (0) = s , donde s es el secreto. Cada uno de los n accionistas recibirá un valor P (1), ..., P ( n ) módulo q . Cualquier accionista t + 1 puede recuperar el secreto s utilizando la interpolación polinómica módulo q , pero cualquier conjunto de como máximo t accionistas no puede. (De hecho, en este punto cualquier conjunto de como máximo t accionistas no tiene información sobre s .)
Hasta aquí, este es exactamente el esquema de Shamir. Para que estas acciones sean verificables, el distribuidor distribuye los compromisos según los coeficientes de P módulo q . Si P ( x ) = s + a 1 x + ... + a t x t , entonces los compromisos que deben entregarse son:
Una vez que se dan estos datos, cualquier parte puede verificar su parte. Por ejemplo, para verificar que v = P ( i ) módulo q , la parte i puede verificar que
.
Este esquema es, en el mejor de los casos, seguro contra adversarios con limitaciones computacionales, a saber, la imposibilidad de calcular logaritmos discretos. Pedersen propuso más tarde un esquema [4] en el que no se revela información sobre el secreto ni siquiera con un distribuidor con poder computacional ilimitado.
Una vez que se distribuyen n acciones a sus titulares, cada titular debería poder verificar que todas las acciones son colectivamente t -consistentes (es decir, cualquier subconjunto t de n acciones producirá el mismo polinomio correcto sin exponer el secreto).
En el esquema de compartición secreta de Shamir, las participaciones son t -consistentes si y sólo si la interpolación de los puntos produce un grado polinomial como máximo d = t − 1 .
Con base en esa observación, se puede demostrar que el protocolo de Benaloh permite a los accionistas realizar la validación requerida y al mismo tiempo verificar la autenticidad e integridad del distribuidor.
Una segunda observación es que, dado que el grado de la suma de dos polinomios F y G es menor o igual a t , o bien los grados de F y G son menores o iguales a t , o bien los grados de F y G son mayores que t . Esta afirmación es evidente debido a la propiedad homomórfica de la función polinómica, ejemplos:
Caso 1:
caso 2:
el caso que cancelamos:
Prueba interactiva:
Los siguientes 5 pasos verifican la integridad del distribuidor ante los accionistas:
El secreto permanece seguro y sin revelar.
Estos 5 pasos se realizarán en una pequeña cantidad de iteraciones para lograr un resultado de alta probabilidad sobre la integridad del distribuidor.
Diagnóstico 1: Debido a que el grado del polinomio es menor o igual a t y debido a que el Dealer revela los otros polinomios (paso 4), el grado del polinomio P debe ser menor o igual a t (segundo caso de observación 1, con alta probabilidad cuando estos pasos se repiten en diferentes iteraciones).
Diagnóstico 2: Uno de los parámetros del problema era evitar exponer el secreto que estamos intentando verificar. Esta propiedad se mantiene mediante el uso del homomorfismo algebraico para realizar la validación. (Un conjunto de polinomios aleatorios de grado t como máximo junto con un conjunto de sumas de P y otros polinomios de grado t como máximo no proporciona información útil sobre P ).
El intercambio de secretos verificables se puede utilizar para construir sistemas de votación auditables de extremo a extremo .
Utilizando la técnica de intercambio de secretos verificables se puede satisfacer el problema electoral que se describirá aquí.
En el problema de las elecciones, cada votante puede votar 0 (en contra) o 1 (a favor), y la suma de todos los votos determinará el resultado de las elecciones. Para que se lleven a cabo las elecciones, es necesario asegurarse de que se cumplan las siguientes condiciones:
Si se utiliza el sistema de compartición de secretos verificables, n escrutadores reemplazarán al administrador electoral único. Cada votante distribuirá una parte de su voto secreto a cada uno de los n escrutadores. De esta manera se preserva la privacidad del votante y se cumple la primera condición.
La reconstrucción del resultado de la elección es fácil, si existen suficientes k < n contadores para descubrir el polinomio P.
La prueba interactiva puede generalizarse ligeramente para permitir la verificación de los porcentajes de votos. Cada votante demostrará (en la fase de distribución de los porcentajes secretos) a los escrutadores que su voto es legítimo mediante los cinco pasos de la prueba interactiva.
La complejidad de ronda de un protocolo VSS se define como el número de rondas de comunicación en su fase de compartición; la reconstrucción siempre se puede realizar en una sola ronda. No existe un VSS de 1 ronda con t > 1 , independientemente del número de jugadores. Los límites de los protocolos VSS perfectamente seguros (sin depender de un supuesto de dureza computacional ) y eficientes ( tiempo polinomial ) se indican a continuación.
