Algoritmo secreto de Santa que no depende de un tercero de confianza

Question

Con una confianza 3 ª parte, la ejecución de Santa Secreto es sencillo: La 3ª parte de las etiquetas de cada persona $1,\dotsc,n$, y, a continuación, elige al azar una alteración de entre todos los posibles alteraciones de $n$ números. Persona $i$ le dará un regalo para el número en la posición $i$ de la enajenación. La confianza 3ª parte es responsable de mantener la alteración seguro, y para decirle a cada persona con la que hacer un regalo.

La pregunta es: ¿existe un algoritmo que permita Santa Secreto para ser jugado sin una confianza 3ª parte?

Pensé que tal vez un inteligente uso de claves secretas y una función de hash podría lograrlo, pero he fallado en encontrar un algoritmo tan lejos.

Así que estoy buscando una descripción de un algoritmo válido o un (informal) de la prueba de que no existe.

EDITAR

Yo creo que mi problema es diferente de los posibles duplicados. Quiero una solución que funcione para distribuida grupo de jugadores. Es decir, usted no puede asumir que los jugadores están en la misma habitación y tienen la capacidad para mezclar los sobres o fichas ni nada de eso.

Para hacer este concreto, una solución válida debe trabajar a través de un grupo de instant messenger o a través de los correos electrónicos de grupo.

También, para aclarar de nuevo, debe ser un azar trastorno y no meramente aleatorio n-ciclo.

Answer 1

Cómo sobre esto:

1. Todo el mundo genera al azar público-privada del par de claves.

2. Todo el mundo publica su clave pública de forma anónima (ver más abajo).

3. En colaboración elegir una semilla aleatoria:

   una. Todo el mundo elige un número aleatorio de los componentes.
   b. Todo el mundo publica un hash de sus semillas componente abiertamente.
   c. Todo el mundo publica su semilla componente abiertamente.
   d. La semilla es la suma de los componentes publicado en el paso (c).

4. El uso de semillas para obtener una alteración de las claves públicas en forma determinística. (Todo el mundo ahora puede hacer esto por sí mismos).

5. Todos cifra de su nombre con su santa secreto de la clave pública y publica el texto cifrado.

6. Todo el mundo intenta descifrar todos los mensajes de el paso anterior con su propia clave privada. Cuando uno de los decryptions éxito, que han encontrado su destino.

Esto supone que "cifrado" con una clave pública utiliza cierta aleatoriedad a produce un no-determinista resultado, así que alguien que tiene sólo la clave pública no se puede saber si un determinado texto plano y texto cifrado coincidir o no. (Este es un estándar de la propiedad de bienes de clave pública, protocolos, aunque no de los libros de texto RSA).

El procedimiento es inherentemente hacer la estructura del ciclo de la alteración público. En particular, todos los que mutuamente santa con alguien va a saber. Es deseable restringir uno mismo a la "super-alteraciones" que no tienen ninguna $2$-ciclos.

Una variante que no revela la estructura del ciclo, en el costo de no tener un duro atado en el tiempo de ejecución sería:

1. Todo el mundo elige un número al azar y hashes para producir una "santa ID".

2. Todo el mundo publica su santa ID de forma anónima.

3. En colaboración elegir una semilla aleatoria.

4. El uso de la semilla de manera determinista elegir un bijection entre santa Id de destino y de nombres.

5. Si alguien tiene a sí mismos como de destino, se quejan abiertamente, demostrando que es así por revelar el número se mezclaron para obtener su ID. Todo el mundo empieza de nuevo desde el paso 1 con los nuevos números aleatorios para todo. En promedio, $e$ iteraciones serán necesarias antes de que un trastorno se encuentra.

---

Ambas necesitan de un sub-algoritmo para publicar cosas de forma anónima:

1. Todo el mundo genera una clave pública y clave privada pareja sólo para la publicación de la sub-algoritmo y publica la clave pública.

2. Todo el mundo se selecciona una al azar permutación $(K_i)_{1\le i\le n}$ de todas las claves públicas desde el paso 1.

3. Todo el mundo se envuelve su mensaje en una serie de cifrados: $$ M_0 = \text{el mensaje a publicar} \\ M_k = \operatorname{encypt}(K_k, M_{k-1}) \quad\text{para }1\le k\le $n$

4. Todo el mundo publica sus propios $M_n$.

5. Todo el mundo intenta descifrar todos los mensajes de la ronda anterior. Publicar todos los contenidos donde el descifrado se realiza correctamente.

6. Después de repetir el paso anterior $n$ tiempos, todo el mundo original de los mensajes sobre la mesa, y nadie sabe donde cualquiera de ellos proviene de (a excepción de su propia).

Una lo suficientemente grande como la colusión puede ser capaz de romper el anonimato de publicación de paso por el análisis de tráfico, pero si todo el mundo a excepción de un par de jugadores de la colusión, el juego ha perdido mucho de su significado, de todos modos.

Answer 2

He aquí una posible estrategia. Número de la gente $1, 2, \dots, n$. Que hacer las siguientes cosas en orden. (Cada vez que alguien elige un número al azar, supongo que es uniformemente al azar de algunas rango fijo,$[1,N]$, decir $[1,2n]$, con exclusión de todos los valores que hemos visto antes.)

1. Persona $1$ elige un número aleatorio $x_1$ y se lo pasa a la persona $2$.
2. Persona $2$ elige un número aleatorio $x_2$, codifica la lista de $(x_1,x_2)$, y lo pasa a la persona $3$.
3. Persona $3$ elige un número aleatorio $x_3$, codifica la lista de $(x_1,x_2,x_3)$, y lo pasa a la persona $4$.
4. Y así sucesivamente, con la persona $n$ recibir una permutación de la lista $(x_1, x_2, \dots, x_{n-1})$.
5. Persona $n$ elige un número aleatorio $x_n$, codifica la lista de $(x_1, \dots, x_n)$, y pasa que a la persona $1$.
6. Persona $1$ registra la posición de $x_1$ (que es su Santa secreto de destino), reemplaza $x_1$ por un nuevo número aleatorio $y_1$, y pasa a la lista resultante a la persona $2$.
7. Persona $2$ registra la posición de $x_2$ (que es su Santa secreto de destino), reemplaza $x_2$ por un nuevo número aleatorio $y_2$, y pasa a la lista resultante a la persona $3$.
8. Y así sucesivamente, hasta llegar a la persona $n$, cuyo objetivo es la posición de $x_n$.

Esto no garantiza que la permutación es un trastorno. Pero todo el mundo puede comprobar si tienen a sí mismos como un objetivo; si se quejan, podemos empezar de nuevo. (En promedio, vamos a tener que empezar de $e$ a veces).

No se comparte información acerca de otras personas objetivos: en los pasos 1 a 4 persona $k$ considera que los valores de $x_1, x_2, \dots, x_{k-1}$, que no son útiles, porque en los pasos 5 a 8, la persona $k$ le es dada una permutación de los valores de $y_1, y_2, \dots, y_{k-1}, x_k, \dots, x_n$: desde su perspectiva, estos son uniformemente elegido desde el complemento de $\{x_1,\dots, x_{k-1}\}$.

Otro momento incómodo, sin embargo, es que la persona $n$ recoge el final de permutación, para que ellos puedan elegir su Santa secreto de destino si hacen trampa y no al azar. Sin embargo, podemos tener la de otras personas de forma colaborativa elegir una semilla aleatoria para la persona $n$ a uso (decir, ellos les envían números de $r_1, \dots, r_{n-1}$, y, a continuación, $r_1 + \dots + r_{n-1}$ tiene que ser la semilla) y, a continuación, esta trampa puede ser expuesto después de que todo el mundo abre sus regalos.