Que es el más antiguo? (no revelen)

Question

¿Cómo puede un grupo de personas que averiguar quién es el más antiguo, sin revelar cualquier otra información?

Revelar todas las edades a un tercero de confianza no está permitido. Preferiblemente estoy buscando soluciones donde nadie se pone otra información, ni siquiera una tercera parte.

Preferiblemente estoy buscando una solución que funciona para los grandes (por ejemplo, o de 64 bits 1024 bits) edad de valores. (Incluso aunque el uso de la palabra la edad no es intuitiva para los grandes números).

Estoy buscando un bajo costo de lápiz-y-papel de la solución, o una solución en la que cada par de personas que tiene un seguro de canal bidireccional de comunicación (es decir, el equivalente digital de: cualquiera puede escribir cualquier mensaje a una hoja de papel, doblarlo, y pasar a nadie). Yo no estoy buscando soluciones que requieren la construcción de otro tipo de dispositivos físicos.

(Hay un libro o una página web que describe tal de no revelar los algoritmos?)

Esta pregunta no es un duplicado de No revelar máximo , debido a que esta pregunta no pide el máximo valor de edad: incluso explícitamente prohíbe revelar la edad máxima de valor, porque eso sería demasiada información compartida. Tener una solución a esta pregunta no nos da una solución a la otra pregunta. Tener una solución a la otra pregunta no nos da una solución a esta pregunta.

La solución a Yao Millonarios del' Problema puede ser usado para resolver esta pregunta cuando el tamaño del grupo es de 2. Pero en esta pregunta, estoy interesado en la respuesta de los grupos más grandes también.

Answer 1

Ok, vamos a probar esto. Estamos asumiendo que todos los participantes honestamente seguir el protocolo. Supongamos también que los participantes tienen distintas edades que son enteros entre 2 y 99.

A cada participante se le entrega 100 pequeñas cajas, con una cremallera que se puede mantener el 100 cajas en un orden lineal, y 100 de naranja mármoles y 100 amarillo canicas. A cada participante se inicializa sus rack de cajas de la siguiente manera: si su edad es $A$, luego se puso de color naranja a las canicas en el primer $A$ cajas y amarillo canicas en los últimos $(100-A)$ cajas. Las cajas se cierran para que nadie pueda decir que el color es de mármol en el interior de cualquier cuadro. Tenga en cuenta que todos los del cuadro #1 contiene una naranja de mármol; todos del cuadro #100 contiene un mármol amarillo; y existe al menos un índice $n$ para que el $n$th cajas contienen exactamente una naranja de mármol, y para cada índice, es el más antiguo participante cuya caja contiene la naranja de mármol.

A continuación, el grupo genera una permutación aleatoria de $\{1,\dots,100\}$ que ninguno de ellos individualmente saber, y que aplica de permutación para cada participante del rack. (La manera más fácil de hacer esto: uno de los participantes elige en secreto una permutación aleatoria de $\{1,\dots,100\}$ y se aplica a todo el mundo del rack en privado, y luego un segundo participante hace lo mismo.) Después de la permutación se aplica, cada participante privado abre el cuadro #1. Cualquiera que sea el color de mármol que ver, el que se puso de mármol del mismo color en una zona comunitaria con bolsa (cada participante puede colocar sus mármol en secreto, sin que nadie lo vea y sin ver ningún otro canicas).

El comunal de la bolsa se abrió. Si contiene exactamente una naranja de mármol, a continuación, la persona que coloca la naranja de mármol, admite, y todo el mundo se entera de que esta persona es la más antigua. Si no contiene naranja canicas o, al menos, dos de naranja a las canicas, a continuación, la comunal, la bolsa se vacía y volvemos a la permutación aleatoria de paso. Con el tiempo (con probabilidad exponencial cerca de $1$), una de las permutaciones al azar el resultado será exactamente una naranja de mármol entre los participantes de la #1 de las cajas.

Answer 2

1. Tiene un equipo generar dos secreta listas de $q_1,\dots,q_{1000}$ $r_1,\dots,r_{1000}$ de números aleatorios.
2. Cada persona privada de darle al equipo su edad $A$; el equipo revela $q_1,\dots,q_A$ $r_1,\dots,r_A$ a esa persona.
3. Cualquiera de las dos personas ahora pueden comparar su edad, por el siguiente protocolo: persona #1, cuya edad es $A_1$, selecciona un número $j$ al azar de $1$$A_1$. Él consultas persona #2 revelando el número de $q_j$. Si la persona #2 no puede identificar correctamente $r_j$, entonces la persona #1 es el de mayor edad. De lo contrario, la persona #2 ahora selecciona un número $k$ al azar de $1$ a de su edad $A_2$. Ella consultas persona #1 revelando $q_k$; si la persona #1 no se puede identificar a $r_k$, entonces la persona #2 es mayor. Ir hacia atrás y adelante hasta que una persona se revela a ser mayores.
4. Una vez que usted puede decidir a cual de las dos personas es más, usted puede de forma iterativa decidir cual de un grupo de personas es la más antigua.

De hecho, usted podría tener las consultas/respuestas entre todas las personas de manera simultánea, para acelerar las cosas. También te gustaría agregar algo al protocolo para prevenir bucles infinitos debido a los lazos de edad.