Intercambio de secretos verificables

El intercambio de secretos verificables ( VSS ) es un esquema de intercambio de secretos que permite a los miembros del grupo verificar que sus compartidos son consistentes (en inglés consistente ) [1] , es decir, que recrean el mismo secreto . En otras palabras, este esquema garantiza la existencia de un secreto que los participantes pueden recuperar más tarde, incluso si la distribución se cambió deliberadamente. (El esquema habitual supone que la asignación se realiza correctamente). El concepto de compartir secretos verificables fue introducido por primera vez por Benny Chor, Shafi Goldwasser , Silvio Micali y Baruch Averbuch en 1985 [2] .

Un miembro del grupo que comparte un secreto se denomina distribuidor en el protocolo VSS [ 3 ] . El protocolo se divide en dos etapas: separación y recuperación.

Dividir: Inicialmente, cada participante tiene entradas aleatorias independientes. El distribuidor utiliza un secreto como entrada. La separación consta de varias etapas. En cada etapa, cualquier miembro puede enviar mensajes privados a otros o enviar mensajes públicamente a todos. Cada mensaje de este tipo está determinado por los datos de entrada y los mensajes recibidos previamente.

Recuperación: En esta etapa, cada participante aporta la información obtenida durante la etapa de separación. A continuación, se aplica la función de recuperación y su resultado se utiliza como salida del protocolo.

En la informática multipartita segura, la entrada se divide en fracciones secretas, que se utilizan para calcular alguna función. Hay actores maliciosos que corrompen los datos y se desvían del protocolo. VSS [4] se utiliza para evitar su influencia .

Esquema de Feldman

El protocolo de Paul Feldman se basa en el esquema de intercambio secreto de Shamir combinado con cualquier esquema de cifrado homomórfico . Considere el circuito de umbral ( t , n ). Los cálculos se realizan con elementos del grupo cíclico G de orden p con generador g . El grupo G se elige porque la obtención del valor del logaritmo discreto en este grupo tiene una alta complejidad computacional. Luego, el repartidor establece (y mantiene en secreto) un polinomio P de grado t − 1 con coeficientes de Z p , incl. P (0)= s , donde s es el secreto. Cada uno de los n participantes recibirá el valor P (1), …, P ( n ) módulo p [5] .

Todo lo anterior es una implementación del intercambio secreto de Shamir. Para que este esquema sea verificable, el distribuidor envía valores de prueba a los coeficientes P . Si P ( x ) = s + a 1 x + ... + a t − 1 x t − 1 , entonces los valores son:

c 0 = gramo s ,
c 1 \ u003d g a 1 ,
…
do t - 1 = gramo un t - 1 .

Además, el repartidor envía la enmienda z i = g y i , donde y i = P ( i ) , al i -ésimo participante. Una vez hecho esto, cualquier miembro puede verificar la consistencia de su parte verificando la siguiente igualdad:

g^{v}=c_{0}c_{1}^{i}c_{2}^{i^{2}}\cdots c_{t-1}^{i^{(t-1 )}}=\prod_{j=0}^{t-1}c_{j}^{i^{j}}=\prod_{j=0}^{t-1}g^{a_{ j}i^{j}}=g^{\sum _{j=0}^{t-1}a_{j}i^{j}}=g^{y_{i}}

Después de asegurarse, el participante informa al respecto. Como resultado, todos saben que todas las partes corresponden a un polinomio y, por lo tanto, son conjuntas [6] .

Esquema de Benalo

El esquema de Benalo es también un desarrollo del esquema de Shamir . Una vez que se han repartido n acciones entre los participantes, cada uno de ellos debe poder verificar que todas las acciones son t - consistentes , es decir , cualquier subgrupo de t participantes de n recupera el mismo secreto [1] . En el esquema de Shamir, las partes s 1 , s 2 , …, s n son t - conjuntas si y solo si el grado del polinomio de interpolación construido a partir de los puntos (1, s 1 ), (2, s 2 ), …, (n, s n ) no excede d = t − 1 [7] . Además, si el grado de la suma de dos polinomios F y G es menor o igual que t , entonces ambos grados de los polinomios F y G son menores o iguales que t , o ambos son mayores que t . Esto se sigue de la propiedad homomórfica de la función polinomial.

Ejemplos:

caso 1:
${\ estilo de visualización f_ {1} = 3x}$ . . ${\displaystyle f_{2}=11x^{6))$ ${\ estilo de visualización t = 6}$
caso 2:
${\ estilo de visualización f_ {1} = 18x ^ {7}}$ . . ${\displaystyle f_{2}=-18x^{7))$ ${\ estilo de visualización t = 6}$

La propiedad del esquema de Shamir descrita anteriormente impone una restricción en el grado del polinomio de interpolación cuando se confirma la consistencia t . Basado en esto y en la propiedad homomórfica de los polinomios, el esquema de Benalo permite a los participantes realizar la verificación requerida mientras confirman la consistencia de sus acciones [8] [7] .

La consistencia se puede verificar usando el siguiente algoritmo:

El distribuidor especifica un polinomio P de grado t − 1 y asigna acciones (como en el esquema de Shamir )
El repartidor crea un número muy grande ( k ) de polinomios aleatorios de grado t − 1 y también distribuye sus acciones. ${\displaystyle P_{1},...,P_{k))$
El propietario de la acción elige un conjunto aleatorio de m polinomios ( m < k ).
El repartidor revela las acciones de m polinomios seleccionados , suma los k − m polinomios restantes y comparte el resultado. $P_{i_{1}},...,P_{i_{m}}$ $P+\textstyle \sum _{j={m+1}}^{k}P_{j}$
Cada participante comprueba que todos los polinomios expandidos de grado t − 1 corresponden a la fracción que conoce.

Si el comerciante sigue honestamente este algoritmo, entonces los grados de los polinomios y los grados de los polinomios de interpolación recuperados de sus partes corresponden al grado t − 1 del polinomio secreto P por la propiedad homomórfica. Por lo tanto, conociendo las acciones y , cualquier participante puede estar convencido de la t -compatibilidad por la propiedad del esquema Shamir. Además, la distribución de polinomios aleatorios no conduce a la revelación del secreto [9] . $P_{i_{1}},...,P_{i_{m}}$ $P+\textstyle \sum _{j={m+1}}^{k}P_{j}$ $P_{i_{1}},...,P_{i_{m}}$ $P+\textstyle \sum _{j={m+1}}^{k}P_{j}$

Elecciones secretas

VSS es aplicable para elecciones secretas [10] . Cada votante puede votar a favor (1) o en contra (0), y la suma de todos los votos determina el resultado de la votación. Debe asegurarse de que se cumplan las siguientes condiciones:

La privacidad de los votantes no debe verse comprometida.
El observador debe verificar que ningún elector haya cometido fraude.

Al usar VSS, un observador reemplazará n contadores de votos. Cada votante distribuirá partes de su secreto entre todos los n contadores. En este caso, se preserva la privacidad de los votantes y se cumple la primera condición. Para restaurar el resultado de la elección, es necesario tener suficientes k<n contadores para restaurar el polinomio P . Para validar los votos, cada votante puede aplicar la verificación de consistencia de distribución descrita en la sección anterior [11] .

Eficiencia VSS

La complejidad del protocolo VSS se define como la cantidad de etapas de intercambio de mensajes en la etapa dividida, es decir, la cantidad de acciones secretas enviadas por el distribuidor, valores de verificación (en el esquema de Feldman), polinomios aleatorios, etc. La recuperación siempre se puede realizar en un solo paso. Esto se puede lograr con la ayuda de la transmisión simultánea (emisión simultánea en inglés ) [12] . Por lo tanto, no hay VSS de 1 etapa con t>1 , independientemente del número de participantes. Además, se dice que un protocolo VSS es eficiente si tiene una complejidad polinomial que depende de n . Condiciones para un protocolo VSS efectivo [13] [14] :

Número de etapas	Opciones
una	t = 1, n > 4
2	n > 4t
3	n > 3t

Notas

↑ 1 2 Josh Cohen Benaloh, 1987 , pág. 256.
↑ B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, 1985 .
↑ B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, 1985 , p. 387.
↑ Oded Goldreich, 2004 .
↑ P. Feldman, 1987 , pág. 429.
↑ P. Feldman, 1987 , pág. 433.
↑ 1 2 Josh Cohen Benaloh, 1987 , pág. 256-257.
↑ Josh Cohen Benaloh, 1987 , pág. 252-253.
↑ Josh Cohen Benaloh, 1987 , pág. 256-258.
↑ Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He, 2004 .
↑ Josh Cohen Benaloh, 1987 , pág. 258.
↑ B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, 1985 , p. 383-387.
↑ Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan y Kannan Srinathan, 2006 , p. 331-332.
↑ Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan y Kannan Srinathan, 2006 , p. 340.

Literatura

B. Chor, S. Goldwasser, S. Micali, B. Awerbuch. Compartir secretos verificables y lograr la simultaneidad en presencia de fallas // IEEE. - 1985. - S. 383-395 .
P. Feldman. Un esquema práctico para compartir secretos verificables no interactivos // IEEE. - 1987. - S. 427-437 .
T. Rabin y M. Ben-Or. Intercambio de secretos verificables y protocolos multipartidistas con mayoría honesta // STOC '89 Actas del vigésimo primer simposio anual de ACM sobre Teoría de la computación. - 1989. - S. 79 .
Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He. Intercambio de secretos verificables públicamente seguros no interactivos y teóricos de la información // Archivo ePrint de criptología de IACR. — 2004.
Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin. La complejidad redonda del intercambio de secretos verificables y la multidifusión segura // Actas de STOC '01 del trigésimo tercer simposio anual de ACM sobre teoría de la computación. - 2001. - S. 580-589 .
Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan y Kannan Srinathan. Intercambio de secretos verificables redondos, óptimos y eficientes . - Springer-Verlag Berlín Heidelberg, 2006. - S. 330-342.
Oded Goldreich. Los fundamentos de la criptografía - Volumen 2. - Cambridge University Press, 2004.
Josh Cohen Benaloh. Homomorfismos para compartir secretos: Mantener acciones de un secreto secreto // Procedimientos sobre avances en criptología --- CRYPTO '86. — 1987.