Problema de los criptógrafos comensales

En criptografía, el problema de los criptógrafos comensales estudia cómo realizar un cálculo seguro entre múltiples partes de la función booleana XOR. David Chaum propuso este problema a principios de la década de 1980 y lo utilizó como ejemplo ilustrativo para demostrar que era posible enviar mensajes anónimos con imposibilidad de rastrear al remitente y al destinatario de forma incondicional. Las redes de comunicación anónimas basadas en este problema se conocen a menudo como redes DC (donde DC significa "criptógrafos comensales"). ^{[ 1 ]}

A pesar de la palabra "comer" , el problema de los criptógrafos comensales no tiene relación con el problema de los filósofos comensales .

Tres criptógrafos se reúnen alrededor de una mesa para cenar. El camarero les informa que la cena ha sido pagada por alguien, que podría ser uno de los criptógrafos o la Agencia de Seguridad Nacional (NSA). Los criptógrafos respetan el derecho de cada uno a realizar un pago anónimo, pero quieren averiguar si fue la NSA quien pagó. Así que deciden ejecutar un protocolo de dos etapas.

En la primera etapa, cada par de criptógrafos establece un secreto compartido de un bit, por ejemplo, lanzando una moneda detrás de un menú de manera que solo dos criptógrafos vean el resultado por turno para cada par de criptógrafos. Supongamos, por ejemplo, que después del lanzamiento de la moneda, los criptógrafos A y B comparten un bit secreto.${\displaystyle 1}$, A y C comparten${\displaystyle 0}$y B y C comparten${\displaystyle 1}$.

En la segunda etapa, cada criptógrafo anuncia públicamente un bit, que es:

• si no pagaron la comida, el OR exclusivo (XOR) de los dos bits compartidos que tienen con sus dos vecinos,
• Si pagaron la comida, lo contrario de eso XOR.

Suponiendo que ninguno de los criptógrafos pagó, entonces A anuncia${\displaystyle 1\oplus 0=1}$, B anuncia${\displaystyle 1\oplus 1=0}$y C anuncia${\displaystyle 0\oplus 1=1}$Por otro lado, si A pagó, ella anuncia${\displaystyle \lnot (1\oplus 0)=0}$.

Los tres comunicados públicos, en conjunto, revelan la respuesta a su pregunta. Basta con calcular la operación XOR de los tres bits anunciados. Si el resultado es 0, implica que ninguno de los criptógrafos pagó (por lo que la NSA debe haber pagado la factura). De lo contrario, uno de los criptógrafos pagó, pero su identidad permanece desconocida para los demás.

David Chaum acuñó el término red de criptógrafos comensales , o DC-net, para este protocolo.

El protocolo DC-net es sencillo y elegante. Sin embargo, presenta varias limitaciones, algunas de las cuales se han explorado en investigaciones posteriores para encontrar soluciones (véase la sección de Referencias más abajo).

Colisión

Si dos criptógrafos pagaran la cena, sus mensajes se cancelarían entre sí y el resultado final de XOR sería:${\displaystyle 0}$Esto se denomina colisión y permite que solo un participante transmita a la vez mediante este protocolo. En un caso más general, se produce una colisión siempre que un número par de participantes envíe mensajes.

Ruptura

Cualquier criptógrafo malicioso que no desee que el grupo se comunique correctamente puede interferir con el protocolo para que el resultado final de la operación XOR sea inútil, simplemente enviando bits aleatorios en lugar del resultado correcto. Este problema surge porque el protocolo original se diseñó sin utilizar ninguna tecnología de clave pública y carece de mecanismos fiables para comprobar si los participantes siguen el protocolo con honestidad. ^{[ 2 ]}

Complejidad

El protocolo requiere claves secretas compartidas por pares entre los participantes, lo cual puede resultar problemático si hay muchos participantes. Además, si bien el protocolo DC-net es "incondicionalmente seguro", en realidad se basa en la suposición de que ya existen canales "incondicionalmente seguros" entre pares de participantes, lo cual no es fácil de lograr en la práctica.

Un algoritmo de red de veto anónimo relacionado calcula la OR lógica de las entradas de varios usuarios, en lugar de una XOR lógica como en las redes DC, lo que puede ser útil en aplicaciones para las que una operación de combinación OR lógica es naturalmente adecuada.

David Chaum pensó por primera vez en este problema a principios de la década de 1980. La primera publicación que describe las ideas básicas subyacentes es suya. ^{[ 3 ]} La versión de la revista apareció en el primer número del Journal of Cryptology . ^{[ 4 ]}

Las redes DC se pueden generalizar fácilmente para permitir transmisiones de más de un bit por ronda, para grupos de más de tres participantes y para "alfabetos" arbitrarios distintos de los dígitos binarios 0 y 1, como se describe a continuación.

La medida sugerida originalmente por David Chaum para evitar colisiones consiste en retransmitir el mensaje una vez detectada una colisión, pero el artículo no explica exactamente cómo organizar la retransmisión.

Dissent evita la posibilidad de colisiones no intencionadas mediante el uso de una mezcla verificable para establecer un programa de transmisión de DC-nets, de modo que cada participante sabe exactamente qué bits en el programa corresponden a su propio espacio de transmisión, pero no sabe quién posee otros espacios de transmisión. ^{[ 9 ]}

Herbivore divide una gran red de anonimato en grupos DC-net más pequeños, lo que permite a los participantes evadir los intentos de interrupción abandonando un grupo interrumpido y uniéndose a otro, hasta que encuentren un grupo libre de perturbadores. ^{[ 10 ]} Este enfoque de evasión introduce el riesgo de que un adversario que posee muchos nodos pueda interrumpir selectivamente solo los grupos que no ha comprometido por completo , "guiando" así a los participantes hacia grupos que pueden ser funcionales precisamente porque están completamente comprometidos. ^{[ 11 ]}

Dissent implementa varios esquemas para contrarrestar las interrupciones. El protocolo original ^{[ 9 ]} utilizaba una mezcla criptográfica verificable para formar un cronograma de transmisión de DC-net y distribuir "asignaciones de transmisión", lo que permitía verificar la corrección de los textos cifrados subsiguientes de DC-net mediante una simple comprobación de hash criptográfico . Sin embargo, esta técnica requería una nueva verificación antes de cada ronda de DC-net, lo que generaba altas latencias. Un esquema posterior, más eficiente, permite que una serie de rondas de DC-net se desarrollen sin mezclas intermedias en ausencia de interrupciones, pero en respuesta a un evento de interrupción utiliza una mezcla para distribuir acusaciones anónimas , lo que permite a la víctima de la interrupción exponer y probar la identidad del perpetrador. ^{[ 5 ]} Finalmente, las versiones más recientes admiten redes DC totalmente verificables, a un costo sustancial en eficiencia computacional debido al uso de criptografía de clave pública en la red DC, así como un modo híbrido que utiliza redes DC eficientes basadas en XOR en el caso normal y redes DC verificables solo en caso de interrupción, para distribuir acusaciones más rápidamente de lo que es factible utilizando barajados verificables. ^{[ 8 ]}