Juegos de cálculo seguro distribuido

En ECI 2018 hubo un curso de cripto donde mostraron varias maneras de que un grupo de adversarios puedan ejecutar cálculos con información que tienen sin compartirla, por ejemplo, empresas pueden calcular promedio de fraudes  sin que ninguna revele sus cifras.

Para mostrarlo de modo intuitivo tanto para charlas internas en el trabajo como para H4CKED 2019, he desarrollado dos juegos que paso a compartir.


En ambos casos se supone que la transmisión es completamente secreta.

Con azar

La idea es que hacemos una ronda de personas, donde la primera toma su número y le suma otro al azar, guardando ambos en secreto. El resultado se lo pasa a la siguiente participante, que le suma su número y así hasta dar la ronda completa. La primera persona le resta el número al azar a lo obtenido y tiene la sumatoria de todas las participantes, que ya puede compartir. Cualquiera divide por la cantidad de participantes y ya tenemos el promedio que queríamos.

La debilidad de este algoritmo es que cualquier par de participantes separadas por una sola persona puede atacar a esta, pues saben el valor de entrada y el de salida, cuya resta es el valor de la víctima.

Con descomposición

Una mejor versión invulnerable al ataque anterior consiste en que cada participante descompone su valor en tantos sumandos al azar como participantes hayan y envía uno a cada participantes. Cada participante toma los sumandos recibidos, los suma y comparte el resultado. Estos resultados se suman, se divide por la cantidad de participantes y nuevamente tenemos el promedio que buscábamos.

El escenario de ataque factible para este caso es que todas las participantes menos una se pongan de acuerdo para atacar a esa. Sabiendo el total, se le resta el acumulado por las atacantes y tenemos el valor de la víctima.

Multiplicación

Tambien se puede multiplicar de esta manera, con factores, salvo que si alguien tiene un cero, al menos una participante va a saberlo. Quizás habría que agregar algunas rondas de intercambio, pero para un juego ya se complica innecesariamente.

En el caso del primer juego, se puede multiplicar un cero cerca del comienzo es más identificable que al final.

Otras maneras

Hay otras maneras pero no son tan intuitivas, al menos para quienes no sabemos más que matemáticas básicas, así que no son candidatas para juegos didácticos como estos. Tampoco sé si resuelven el problema del cero en la multiplicación.

Acá tenés las tarjetas por si querés jugar