El problema de los millonarios socialistas

Problema criptográfico

En criptografía , el problema del millonario socialista ^[1] es aquel en el que dos millonarios quieren determinar si su riqueza es igual sin revelar ninguna información sobre sus riquezas entre sí. Es una variante del problema de los millonarios ^{[2] [3]} mediante el cual dos millonarios desean comparar sus riquezas para determinar quién tiene la mayor riqueza sin revelar ninguna información sobre sus riquezas entre sí.

A menudo se utiliza como protocolo criptográfico que permite a dos partes verificar la identidad de la parte remota mediante el uso de un secreto compartido, evitando un ataque de intermediario sin el inconveniente de comparar manualmente las huellas digitales de la clave pública a través de un protocolo externo. canal. De hecho, se puede utilizar una contraseña/frase de contraseña relativamente débil en lenguaje natural.

Motivación

Alice y Bob tienen valores secretos y , respectivamente. Alice y Bob desean saberlo sin permitir que ninguna de las partes sepa nada más sobre el valor secreto del otro. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x=y}$

Un atacante pasivo que simplemente espía los mensajes que intercambian Alice y Bob no aprende nada sobre ni siquiera si . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x=y}$

Incluso si una de las partes es deshonesta y se desvía del protocolo, esa persona no puede aprender nada más que si . ${\displaystyle x=y}$

Un atacante activo capaz de interferir arbitrariamente con la comunicación de Alice y Bob ( ataque de intermediario ) no puede aprender más que un atacante pasivo y no puede afectar el resultado del protocolo más que hacerlo fallar.

Por lo tanto, el protocolo se puede utilizar para autenticar si dos partes tienen la misma información secreta. El popular paquete de criptografía de mensajes instantáneos Off-the-Record Messaging utiliza el protocolo Socialist Millionaire para la autenticación, en el que los secretos contienen información sobre las claves públicas de autenticación a largo plazo de ambas partes, así como información ingresada por los propios usuarios. ${\displaystyle x}$ ${\displaystyle y}$

Protocolo de mensajería no registrada

Máquina de estado de implementación de un protocolo socialista millonario (SMP).

El protocolo se basa en la teoría de grupos .

Un grupo de orden primo y un generador se acuerdan a priori y, en la práctica, generalmente se fijan en una implementación determinada. Por ejemplo, en el protocolo de mensajería off-the-record, hay un valor fijo específico de 1.536 bits. es entonces un generador de un subgrupo de orden primo de , y todas las operaciones se realizan módulo , o en otras palabras, en un subgrupo del grupo multiplicativo , . ${\displaystyle p}$ ${\displaystyle h}$ ${\displaystyle p}$ ${\displaystyle h}$ ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$ ${\displaystyle p}$ ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$

Por , denota el cálculo multipartito seguro , intercambio de claves Diffie-Hellman-Merkle , que, para los números enteros , , devuelve a cada parte: ${\displaystyle \langle h|a,\,b\rangle }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle h^{ab}}$

• Alice calcula y se lo envía a Bob, quien luego calcula . ${\displaystyle h^{a}}$ ${\displaystyle \left(h^{a}\right)^{b}\equiv h^{ab}}$
• Bob calcula y se lo envía a Alice, quien luego calcula . ${\displaystyle h^{b}}$ ${\displaystyle \left(h^{b}\right)^{a}\equiv h^{ba}}$

${\displaystyle h^{ab}\equiv h^{ba}}$ya que la multiplicación en es asociativa. Tenga en cuenta que este procedimiento no es seguro frente a ataques de intermediario . ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$

El protocolo socialista millonario ^[4] sólo tiene unos pocos pasos que no forman parte del procedimiento anterior, y la seguridad de cada uno depende de la dificultad del problema del logaritmo discreto , tal como lo hace el anterior. Todos los valores enviados también incluyen pruebas de conocimiento cero de que fueron generados según el protocolo.

Parte de la seguridad también se basa en secretos aleatorios. Sin embargo, como se escribe a continuación, el protocolo es vulnerable al envenenamiento si Alice o Bob eligen que cualquiera de , , o sea cero. Para solucionar este problema, cada parte debe comprobar durante los intercambios Diffie-Hellman que ninguno de los , , , o que reciben sea igual a 1. También es necesario comprobar que y . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle h^{a}}$ ${\displaystyle h^{b}}$ ${\displaystyle h^{\alpha }}$ ${\displaystyle h^{\beta }}$ ${\displaystyle P_{a}\neq P_{b}}$ ${\displaystyle Q_{a}\neq Q_{b}}$

Tenga en cuenta que:

${\displaystyle {\begin{aligned}P_{a}{P_{b}}^{-1}&=\gamma ^{r}\gamma ^{-s}=\gamma ^{r-s}\\&=h^{\alpha \beta (r-s)}\end{aligned}}}$

y por lo tanto

${\displaystyle {\begin{aligned}c&=\left(Q_{a}Q_{b}^{-1}\right)^{\alpha \beta }\\&=\left(h^{r}g^{x}h^{-s}g^{-y}\right)^{\alpha \beta }=\left(h^{r-s}g^{x-y}\right)^{\alpha \beta }\\&=\left(h^{r-s}h^{ab(x-y)}\right)^{\alpha \beta }=h^{\alpha \beta (r-s)}h^{\alpha \beta ab(x-y)}\\&=\left(P_{a}{P_{b}}^{-1}\right)h^{\alpha \beta ab(x-y)}\end{aligned}}}$.

Debido a los valores aleatorios almacenados en secreto por la otra parte, ninguna de las partes puede obligar a ser iguales a menos que sean iguales , en cuyo caso . Esto prueba lo correcto. ${\displaystyle c}$ ${\displaystyle P_{a}{P_{b}}^{-1}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle h^{\alpha \beta ab(x-y)}=h^{0}=1}$

Ver también

• Prueba de conocimiento cero

Referencias

1. Markus Jakobsson , Moti Yung (1996). "Probar sin saber: sobre probadores inconscientes, agnósticos y con los ojos vendados". Avances en criptología - CRYPTO '96, volumen 1109 de Lecture Notes in Computer Science . Berlina. págs. 186-200. doi : 10.1007/3-540-68697-5_15 .
2. Andrés Yao (1982). «Protocolos para comunicaciones seguras» (PDF) . Proc. 23º Simposio IEEE sobre fundamentos de la informática (FOCS '82) . págs. 160-164. doi :10.1109/SFCS.1982.88.
3. Andrés Yao (1986). «Cómo generar e intercambiar secretos» (PDF) . Proc. 27º Simposio del IEEE sobre fundamentos de la informática (FOCS '86) . págs. 162-167. doi :10.1109/SFCS.1986.25.
4. Fabrice Boudot, Berry Schoenmakers, Jacques Traoré (2001). "Una solución justa y eficiente al problema de los socialistas millonarios" (PDF) . Matemática Aplicada Discreta . 111 (1): 23–36. doi :10.1016/S0166-218X(00)00342-5.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Enlaces externos

• Descripción del protocolo de mensajería OTR versión 2
• Explícalo como si tuviera cinco años: el problema de los socialistas millonarios y la computación multipartidista segura en Wayback Machine (archivado el 25 de diciembre de 2022)
• Goldbug Messenger, que utiliza una implementación del Protocolo Socialista Millonario