Plan de compromiso

Supongamos que Alice y Bob quieren resolver una disputa lanzando una moneda al aire . Si se encuentran físicamente en el mismo lugar, un procedimiento típico podría ser:

1. Alice "dice" el resultado del lanzamiento de la moneda,
2. Bob lanza la moneda,
3. Si Alice acierta, gana; de lo contrario, gana Bob.

Si Alice y Bob no se encuentran en el mismo lugar, surge un problema. Una vez que Alice ha "anunciado" el resultado del lanzamiento de la moneda, Bob puede estipular que dicho resultado sea el que más le convenga. Del mismo modo, si Alice no le comunica su "anunciación" a Bob, después de que este lance la moneda y anuncie el resultado, Alice puede informar que acertó con el resultado que más le convenga. Alice y Bob pueden utilizar compromisos en un procedimiento que les permita a ambos confiar en el resultado.

1. Alice "llama" al lanzamiento de la moneda pero solo le comunica a Bob su compromiso con su llamada,
2. Bob lanza la moneda y comunica el resultado.
3. Alice revela a qué se comprometió,
4. Bob verifica que la llamada de Alice coincide con su compromiso,
5. Si la revelación de Alice coincide con el resultado de la moneda que Bob informó, Alice gana.

Para que Bob pueda manipular los resultados a su favor, debe comprender la implicación oculta en el compromiso de Alice. Si el esquema de compromiso es adecuado, Bob no podrá alterar los resultados. Del mismo modo, Alice no podrá influir en el resultado si no puede modificar el valor al que se compromete.

Existe una aplicación práctica de este problema cuando las personas (a menudo en los medios de comunicación) se comprometen a tomar una decisión o dan una respuesta en un "sobre sellado", que luego se abre. "Veamos si eso es lo que respondió el candidato", por ejemplo, en un concurso de televisión, puede servir como modelo de este sistema.

Un ejemplo particularmente motivador es el uso de esquemas de compromiso en pruebas de conocimiento cero . Los compromisos se utilizan en pruebas de conocimiento cero con dos propósitos principales: primero, para permitir que el probador participe en pruebas de "corte y elección", donde al verificador se le presenta la opción de elegir qué aprender, y el probador solo revela lo que corresponde a la elección del verificador. Los esquemas de compromiso permiten al probador especificar toda la información por adelantado y revelar únicamente lo que debe revelarse posteriormente en la prueba. ^{[ 10 ]} Segundo, los compromisos también son utilizados en pruebas de conocimiento cero por el verificador, quien a menudo especifica sus elecciones con anticipación en un compromiso. Esto permite que las pruebas de conocimiento cero se compongan en paralelo sin revelar información adicional al probador. ^{[ 11 ]}

El esquema de firma Lamport es un sistema de firma digital que se basa en mantener dos conjuntos de paquetes de datos secretos , publicar hashes verificables de dichos paquetes y, posteriormente, revelar selectivamente partes de paquetes de datos secretos de forma que se ajusten específicamente a los datos que se van a firmar. De este modo, el compromiso público previo con los valores secretos se convierte en una parte fundamental del funcionamiento del sistema.

Dado que el sistema de firmas Lamport no puede utilizarse más de una vez, se desarrolló un sistema para combinar varios conjuntos de claves Lamport bajo un único valor público que puede vincularse a una persona y ser verificado por terceros. Este sistema utiliza árboles de hashes para comprimir numerosos conjuntos de claves Lamport publicadas en un único valor hash que puede asociarse con el posible autor de datos posteriormente verificados.

Otra aplicación importante de los compromisos se encuentra en el reparto verificable de secretos , un componente fundamental de la computación multipartita segura . En un esquema de reparto de secretos , cada una de las partes recibe "partes" de un valor que debe permanecer oculto para todos. Si suficientes partes se reúnen, sus partes pueden utilizarse para reconstruir el secreto, pero incluso un grupo malicioso de tamaño insuficiente no debería obtener ninguna información. El reparto de secretos es la base de muchos protocolos para la computación segura : para calcular de forma segura una función de una entrada compartida, se manipulan las partes del secreto. Sin embargo, si las partes maliciosas van a generar partes, puede ser importante que estas puedan verificarse. En un esquema de reparto verificable de secretos, la distribución de un secreto va acompañada de compromisos con las partes individuales. Los compromisos no revelan nada que pueda ayudar a un grupo deshonesto, pero las partes permiten a cada participante comprobar si sus partes son correctas. ^{[ 12 ]}

Sea abierto elegido de un conjunto de tamaño${\displaystyle 2^{k}}$, es decir, se puede representar como una cadena de k bits, y dejemos ${\displaystyle {\text{Comprometer}}_{k}}$sea ​​el esquema de compromiso correspondiente. Como el tamaño de k determina la seguridad del esquema de compromiso, se le llama parámetro de seguridad .

Entonces, para todos los algoritmos de tiempo polinomial probabilístico no uniformes que generan${\displaystyle x,x'}$y${\displaystyle abierto, abierto'}$de longitud creciente k , la probabilidad de que${\displaystyle x\neq x'}$y${\displaystyle {\text{Commit}}_{k}(x,open)={\text{Commit}}_{k}(x',open')}$es una función insignificante en k .

Esta es una forma de análisis asintótico . También es posible enunciar el mismo requisito utilizando seguridad concreta : Un esquema de compromiso Commit es${\displaystyle (t,\epsilon )}$seguro, si para todos los algoritmos que se ejecutan en tiempo t y la salida${\displaystyle x,x',open,open'}$la probabilidad de que${\displaystyle x\neq x'}$y${\displaystyle {\text{Commit}}(x,open)={\text{Commit}}(x',open')}$es como máximo${\displaystyle \epsilon }$.

Dejar${\displaystyle U_{k}}$sea ​​la distribución uniforme sobre el${\displaystyle 2^{k}}$valores de apertura para el parámetro de seguridad k . Un esquema de compromiso es respectivamente perfecto, estadístico o de ocultación computacional, si para todos${\displaystyle x\neq x'}$los conjuntos de probabilidad${\displaystyle \{{\text{Commit}}_{k}(x,U_{k})\}_{k\in \mathbb {N} }}$y${\displaystyle \{{\text{Commit}}_{k}(x',U_{k})\}_{k\in \mathbb {N} }}$son iguales, estadísticamente similares o computacionalmente indistinguibles .

Es imposible implementar esquemas de compromiso en el marco de la componibilidad universal (UC). La razón es que el compromiso UC debe ser extraíble , como lo demostraron Canetti y Fischlin ^{[ 13 ]} y se explica a continuación.

La funcionalidad de compromiso ideal, denotada aquí por F , funciona aproximadamente de la siguiente manera. El emisor C envía el valor m a F , que lo almacena y envía "recibo" al receptor R. Posteriormente, C envía "abrir" a F , que envía m a R.

Ahora bien, supongamos que tenemos un protocolo π que implementa esta funcionalidad. Supongamos que el confirmador C está corrompido. En el marco de UC, esto significa esencialmente que C ahora está controlado por el entorno, que intenta distinguir la ejecución del protocolo del proceso ideal. Consideremos un entorno que elige un mensaje m y luego le indica a C que actúe según lo prescrito por π , como si se hubiera comprometido con m . Nótese que para implementar F , el receptor debe, después de recibir un compromiso, emitir un mensaje de "recibo". Después de que el entorno ve este mensaje, le indica a C que abra el compromiso.

El protocolo solo es seguro si este escenario es indistinguible del caso ideal, donde la funcionalidad interactúa con un simulador S. Aquí, S controla C. En particular, cada vez que R emite "receipt", F debe hacer lo mismo. La única forma de lograrlo es que S le indique a C que envíe un valor a F. Sin embargo, cabe señalar que, en este punto, S desconoce m . Por lo tanto, cuando se abre el compromiso durante la ejecución del protocolo, es improbable que F se abra a m , a menos que S pueda extraer m de los mensajes recibidos del entorno antes de que R emita el recibo.

Sin embargo, un protocolo que se puede extraer en este sentido no puede ocultarse estadísticamente. Supongamos que existe un simulador S de este tipo. Ahora consideremos un entorno que, en lugar de corromper C , corrompe R. Además , ejecuta una copia de S. Los mensajes recibidos de C se envían a S , y las respuestas de S se reenvían a C.

El entorno inicialmente le indica a C que se comprometa con un mensaje m . En algún momento de la interacción, S se comprometerá con un valor m′ . Este mensaje se le entrega a R , quien emite m′ . Nótese que, por hipótesis, tenemos m' = m con alta probabilidad . Ahora bien, en el proceso ideal, el simulador debería generar m . Pero esto es imposible, porque en este punto el compromiso aún no se ha abierto, por lo que el único mensaje que R puede haber recibido en el proceso ideal es un mensaje de "recibo". Por lo tanto, tenemos una contradicción.

Los esquemas de compromiso de bits son triviales de construir en el modelo de oráculo aleatorio . Dada una función hash H con una salida de 3k bits, para comprometer el mensaje de k bits m , Alice genera una cadena aleatoria de k bits R y envía a Bob H( R || m ). La probabilidad de que existan cualesquiera R′ , m′ donde m′ ≠ m tales que H( R′ || m′ ) = H( R || m ) es ≈ 2 ^{− k} , pero para probar cualquier suposición del mensaje m Bob necesitará hacer 2 ^k (para una suposición incorrecta) o 2 ^{k -1} (en promedio, para una suposición correcta) consultas al oráculo aleatorio. ^{[ 16 ]} Observamos que los esquemas anteriores basados ​​en funciones hash, esencialmente pueden considerarse esquemas basados ​​en la idealización de estas funciones hash como oráculos aleatorios.

Se puede crear un esquema de asignación de bits a partir de cualquier función unidireccional que sea inyectiva . El esquema se basa en el hecho de que toda función unidireccional puede modificarse (mediante el teorema de Goldreich-Levin ) para que posea un predicado computacionalmente complejo (manteniendo la propiedad de inyectividad).

Sea f una función inyectiva unidireccional, con h un predicado de núcleo duro. Entonces, para comprometerse con un bit b, Alice elige una entrada aleatoria x y envía la tripleta

${\displaystyle (h,f(x),b\oplus h(x))}$

a Bob, donde${\displaystyle \oplus }$denota XOR, es decir , suma bit a bit módulo 2. Para desvincularse, Alice simplemente envía x a Bob. Bob verifica calculando f ( x ) y comparándolo con el valor vinculado. Este esquema es oculto porque para que Bob recupere b debe recuperar h ( x ). Dado que h es un predicado computacionalmente difícil, recuperar h ( x ) de f ( x ) con una probabilidad mayor a un medio es tan difícil como invertir f . La vinculación perfecta se deduce del hecho de que f es inyectiva y, por lo tanto, f ( x ) tiene exactamente una preimagen.

Cabe señalar que, dado que no sabemos cómo construir una permutación unidireccional a partir de ninguna función unidireccional, esta sección reduce la solidez del supuesto criptográfico necesario para construir un protocolo de compromiso de bits.

En 1991, Moni Naor demostró cómo crear un esquema de compromiso de bits a partir de un generador de números pseudoaleatorios criptográficamente seguro . ^{[ 17 ]} La construcción es la siguiente. Si G es un generador pseudoaleatorio tal que G toma n bits a 3 n bits, entonces si Alice quiere comprometerse con un bit b :

• Bob selecciona un vector aleatorio de 3n bits , R , y se lo envía a Alice.
• Alice selecciona un vector aleatorio de n bits Y y calcula el vector de 3 n bits G ( Y ).
• Si b = 1, Alice envía G ( Y ) a Bob; de lo contrario, envía el OR exclusivo bit a bit de G ( Y ) y R a Bob.

Para desvincularse, Alice envía Y a Bob, quien luego puede verificar si inicialmente recibió G ( Y ) o G ( Y ).${\displaystyle \oplus }$R.​

Este esquema es estadísticamente vinculante, lo que significa que incluso si Alice no tiene límites computacionales, no puede hacer trampa con una probabilidad mayor que 2 ^{− n} . Para que Alice haga trampa, necesitaría encontrar un Y' tal que G ( Y' ) = G ( Y )${\displaystyle \oplus }$R. Si pudiera encontrar tal valor, podría desvincularse enviando la verdad y Y , o enviar la respuesta opuesta y Y' . Sin embargo, G ( Y ) y G ( Y' ) solo pueden producir 2n ^valores posibles cada uno (es decir, ^{2²ⁿ )} , mientras que ^{R se elige de entre 2³ⁿ} valores . ^Ella no elige R , por lo que hay una probabilidad ^{de 2²ⁿ /} 2³ⁿ = 2 ^{− n de} que exista un Y' que satisfaga la ecuación requerida para hacer trampa.

La propiedad de ocultación se deriva de una reducción estándar: si Bob puede saber si Alice se comprometió a un cero o a un uno, también puede distinguir la salida del generador pseudoaleatorio G de la de un generador verdaderamente aleatorio, lo que contradice la seguridad criptográfica de G.

Alice elige un grupo de orden primo p , con generador g .

Alice elige aleatoriamente un valor secreto x entre 0 y p − 1 para comprometerse con él, calcula c = g ^x y publica c . El problema del logaritmo discreto dicta que, a partir de c , es computacionalmente inviable calcular x , por lo que, bajo esta suposición, Bob no puede calcular x . Por otro lado, Alice no puede calcular un x ′ <> x , tal que g ^{x ′} = c , por lo que el esquema es vinculante.  

Este esquema no oculta perfectamente el compromiso, ya que alguien podría descubrirlo si logra resolver el problema del logaritmo discreto . De hecho, este esquema no oculta nada con respecto al juego de ocultación estándar, donde un adversario no debería poder adivinar a cuál de los dos mensajes elegidos corresponde el compromiso, de forma similar al juego IND-CPA . Una consecuencia de esto es que, si el espacio de valores posibles de x es pequeño, un atacante podría simplemente probarlos todos y el compromiso no estaría oculto.

Un mejor ejemplo de un esquema de compromiso perfectamente vinculante es aquel en el que el compromiso es el cifrado de x bajo un esquema de cifrado de clave pública semánticamente seguro con completitud perfecta, y el descompromiso es la cadena de bits aleatorios utilizada para cifrar x . Un ejemplo de un esquema de compromiso que oculta la información teóricamente es el esquema de compromiso de Pedersen, ^{[ 18 ]} que es computacionalmente vinculante bajo la suposición del logaritmo discreto. ^{[ 19 ]} Además del esquema anterior, utiliza otro generador h del grupo primo y un número aleatorio r . El compromiso se establece${\displaystyle c=g^{x}h^{r}}$. ^{[ 20 ]}

Estas construcciones están estrechamente relacionadas con las propiedades algebraicas de los grupos subyacentes y se basan en ellas, y la noción originalmente parecía estar muy relacionada con el álgebra. Sin embargo, se demostró que es posible basar esquemas de compromiso estadísticamente vinculantes en supuestos generales no estructurados, a través de la noción de hash interactivo para compromisos a partir de supuestos de complejidad general (específicamente y originalmente, basados ​​en cualquier permutación unidireccional) como en ^{[ 21 ] .}

Alice selecciona${\displaystyle N}$de tal manera que${\displaystyle N=p\cdot q}$, dónde${\displaystyle p}$y${\displaystyle q}$son grandes números primos secretos. Además, ella selecciona un primo${\displaystyle e}$de tal manera que${\displaystyle e>N^{2}}$y${\displaystyle gcd(e,\phi (N^{2}))=1}$Alice calcula entonces un número público.${\displaystyle g_{m}}$como elemento de orden máximo en el${\displaystyle \mathbb {Z} _{N^{2}}^{*}}$grupo. ^{[ 22 ]} Finalmente, Alice se compromete con su secreto${\displaystyle m}$generando primero un número aleatorio.${\displaystyle r}$de${\displaystyle \mathbb {Z} _{N^{2}}^{*}}$y luego mediante computación${\displaystyle c=m^{e}g_{m}^{r}}$.

La seguridad del compromiso anterior se basa en la dificultad del problema RSA y tiene ocultación perfecta y vinculación computacional. ^{[ 23 ]}

El esquema de compromiso de Pedersen introduce una interesante propiedad homomórfica que permite realizar sumas entre dos compromisos. Más específicamente, dados dos mensajes${\displaystyle m_{1}}$y${\displaystyle m_{2}}$y aleatoriedad${\displaystyle r_{1}}$y${\displaystyle r_{2}}$, respectivamente, es posible generar un nuevo compromiso tal que:${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}+m_{2},r_{1}+r_{2})}$Formalmente:

${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=g^{m_{1}}h^{r_{1}}\cdot g^{m_{2}}h^{r_{2}}=g^{m_{1}+m_{2}}h^{r_{1}+r_{2}}=C(m_{1}+m_{2},r_{1}+r_{2})}$

Para abrir el compromiso de Pedersen mencionado anteriormente a un nuevo mensaje${\displaystyle m_{1}+m_{2}}$, la aleatoriedad${\displaystyle r_{1}}$y${\displaystyle r_{2}}$debe añadirse.

De manera similar, el compromiso basado en RSA mencionado anteriormente tiene una propiedad homomórfica con respecto a la operación de multiplicación. Dados dos mensajes${\displaystyle m_{1}}$y${\displaystyle m_{2}}$con aleatoriedad${\displaystyle r_{1}}$y${\displaystyle r_{2}}$, respectivamente, se puede calcular:${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}\cdot m_{2},r_{1}+r_{2})}$Formalmente: ${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=m_{1}^{e}g_{m}^{r_{1}}\cdot m_{2}^{e}g_{m}^{r_{2}}=(m_{1}\cdot m_{2})^{e}g_{m}^{r_{1}+r_{2}}=C(m_{1}\cdot m_{2},r_{1}+r_{2})}$.

Para abrir el compromiso anterior a un nuevo mensaje${\displaystyle m_{1}\cdot m_{2}}$, la aleatoriedad${\displaystyle r_{1}}$y${\displaystyle r_{2}}$debe agregarse. Este compromiso recién generado se distribuye de manera similar a un nuevo compromiso a${\displaystyle m_{1}\cdot m_{2}}$.

El hash vectorial es un esquema de revelación parcial de compromiso vectorial ingenuo basado en el compromiso de bits. Valores${\displaystyle m_{1},m_{2},...m_{n}}$se eligen aleatoriamente. Los compromisos individuales se crean mediante hash.${\displaystyle y_{1}=H(x_{1}||m_{1}),y_{2}=H(x_{2}||m_{2}),...}$El compromiso total se calcula como

${\displaystyle C=H(y_{1}||y_{2}||...||y_{n})}$

Para probar un elemento del vector${\displaystyle X}$, el probador revela los valores

${\displaystyle (i,y_{1},y_{2},...,y_{i-1},x_{i},m_{i},y_{i+1},...,y_{n})}$

El verificador es capaz de calcular${\displaystyle y_{i}}$de${\displaystyle x_{i}}$y${\displaystyle m_{i}}$y luego puede verificar que el hash de todos${\displaystyle y}$Los valores son el compromiso${\displaystyle C}$. Desafortunadamente la prueba es${\displaystyle O(n)}$en tamaño y tiempo de verificación. Alternativamente, si${\displaystyle C}$es el conjunto de todos${\displaystyle y}$valores, entonces el compromiso es${\displaystyle O(n)}$en tamaño, y la prueba es${\displaystyle O(1)}$en tamaño y tiempo de verificación. De cualquier manera, el compromiso o la prueba se escalan con${\displaystyle O(n)}$lo cual no es óptimo.

Un ejemplo común de un esquema práctico de revelación parcial es un árbol Merkle , en el que se crea un árbol hash binario de los elementos de${\displaystyle X}$Este esquema crea compromisos que son${\displaystyle O(1)}$en tamaño y pruebas que son${\displaystyle O(\log _{2}{n})}$en tamaño y tiempo de verificación. El hash raíz del árbol es el compromiso.${\displaystyle C}$Para probar que una revelación${\displaystyle x_{i}}$es parte del árbol original, solo${\displaystyle \log _{2}{n}}$Los valores hash del árbol, uno de cada nivel, deben revelarse como prueba. El verificador puede seguir el camino desde el nodo hoja reclamado hasta la raíz, aplicando el hash a los nodos hermanos en cada nivel y, finalmente, llegando a un valor de nodo raíz que debe ser igual a${\displaystyle C}$. ^{[ 25 ]}

Un compromiso Kate-Zaverucha-Goldberg (KZG) utiliza criptografía basada en emparejamientos para construir un esquema de revelación parcial con${\displaystyle O(1)}$tamaños de compromiso, tamaños de prueba y tiempo de verificación de prueba. En otras palabras, como${\displaystyle n}$, el número de valores en${\displaystyle X}$, los aumentos, los compromisos y las pruebas no aumentan, y las pruebas no requieren más esfuerzo para verificarse.

Un compromiso KZG requiere un conjunto predeterminado de parámetros para crear un emparejamiento y un elemento de puerta trasera de confianza. Por ejemplo, se puede utilizar un emparejamiento Tate . Supongamos que${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}}$son los grupos aditivos y${\displaystyle \mathbb {G} _{T}}$es el grupo multiplicativo del emparejamiento. En otras palabras, el emparejamiento es el mapa${\displaystyle e:\mathbb {G} _{1}\times \mathbb {G} _{2}\rightarrow \mathbb {G} _{T}}$. Dejar${\displaystyle t\in \mathbb {F} _{p}}$ser el elemento de trampilla (si${\displaystyle p}$es el orden primo de${\displaystyle \mathbb {G} _{1}}$y${\displaystyle \mathbb {G} _{2}}$), y dejar${\displaystyle G}$y${\displaystyle H}$ser los generadores de${\displaystyle \mathbb {G} _{1}}$y${\displaystyle \mathbb {G} _{2}}$respectivamente. Como parte de la configuración de parámetros, asumimos que${\displaystyle G\cdot t^{i}}$y${\displaystyle H\cdot t^{i}}$son valores conocidos y compartidos para una cantidad arbitraria de valores enteros positivos de${\displaystyle i}$, mientras que el valor de la trampilla${\displaystyle t}$En sí misma es descartada y desconocida para todos.