Cada una de las n personas roba una carta de un mazo barajado de $k$ tarjetas numeradas de $1$ a $k$ . Hay al menos tantas cartas como personas. El ganador es la persona que tiene la carta más grande. Si todo el mundo es honesto, ¿cómo pueden determinar mutuamente la identidad del ganador, sin que ninguna persona se entere de información adicional más allá de la que se puede inferir necesariamente de $n$ , $k$ ¿el valor de la propia tarjeta de esa persona, y la identidad del ganador? En la situación general con $k \gg n$ para cualquier persona, esta información incluye los valores de todas las cartas excepto la que tiene esa persona, y también el valor relativo de las cartas de dos personas no ganadoras. Si esto no es posible, ¿de qué manera se puede minimizar esta información?
Respuestas
¿Demasiados anuncios?
Si entiendo bien su pregunta, su problema puede verse como una extensión multipartidista del El problema de los millonarios . En el problema de los millonarios, dos millonarios quieren saber cuál de ellos es más rico sin revelar su riqueza. Existe un protocolo seguro de dos partes (debido a Andy Yao, 1982 ), y es posible que hoy en día existan algoritmos aún más sofisticados. Tal vez una simple extensión de este protocolo resuelva tu problema (cada compañero habla con todos los demás para saber que el otro tiene una tarjeta más alta). Sin embargo, no sé si esta simple extensión sigue siendo segura.
EDIT: Después de revisar el artículo de Yao, me doy cuenta de que él también aborda el problema de las múltiples partes. Así que debería encontrar su solución en su documento, o seguir algunas de las referencias dadas en este artículo en Wikipedia . Por supuesto, el reciente esquema de cifrado homomórfico también resolverá tu problema, como ya ha señalado el usuario Moron. Sin embargo, dado que el esquema de cifrado homomórfico es muy general, podría ser un poco demasiado complicado para tu problema en cuestión si estás buscando un esquema práctico.
Si alguna persona tira del $k$ tarjeta de valor, se identifican inmediatamente.
En caso de que esto no ocurra, después de un segundo el individuo con el $k-1$ tarjeta se identifica. Del mismo modo, el $k-t$ persona se identifica después de $t$ segundos si no se ha identificado a nadie previamente. Con esta estrategia, se tardaría como máximo $k-n$ segundos para que alguien se identifique como el poseedor de la carta más alta, sin que se transmita ninguna otra información además de que todos sepan que el valor de la carta más alta es $k-n$ y quién lo dibujó.
Debería poder utilizar un Esquema de cifrado totalmente homomórfico que recientemente ha demostrado ser posible por Craig Gentry de IBM (¡y fue un importante problema abierto en criptografía hasta 2009!)
Utilizando un esquema totalmente homomórfico, cualquier circuito puede ser evaluado de forma homomórfica, permitiendo efectivamente el cálculo en la entrada cifrada sin tener que descifrarla.
Para usarlo en su caso, cada uno puede encriptar el valor de su tarjeta y hacer una comparación homomórfica (por ejemplo vea esto: http://portal.acm.org/citation.cfm?id=1356047 (advertencia: sólo he leído el resumen). Podemos averiguar la persona con mayor valor (o clasificarla por orden) sin tener que divulgar ninguna información no codificada.
Por supuesto, esto es todavía teórico, podría pasar un tiempo antes de que sea práctico.
Consulte la página de la wiki para obtener más detalles.
Me parece que este rompecabezas, tal y como está planteado, se puede resolver con un contador público que cuente desde $n$ a $n - k$ en pasos de tiempo pares, cada uno de los cuales es más largo que el tiempo de reacción de cada jugador. Cada jugador pretende detener el contador cuando éste muestre un valor igual o inferior al de su propia carta; quien primero detenga el contador será el ganador. Esto no parece revelar nada que no esté ya disponible en $n$ , $k$ y el valor de la tarjeta del ganador.
Obviamente, esto es impracticable cuando $n \gg k$ pero incluso en ese caso se podría hacer una cuenta atrás del tiempo en incrementos lo suficientemente grandes como para que sea físicamente factible. Cuando el número de pasos es sustancialmente mayor que $k$ esto todavía tendría una buena oportunidad de identificar al ganador. Los aparentes empates en este procedimiento podrían resolverse mediante una segunda vuelta rápida utilizando la misma tecnología (manteniendo el anonimato de los jugadores en la segunda vuelta), lo que daría un procedimiento casi seguro para encontrar un único ganador correctamente.
