Cálculo del salario máximo

Question

Para motivar mi pregunta, describiré un problema relacionado y luego daré una solución al mismo. Mi pregunta será entonces una variante de este problema.

N individuos se sientan alrededor de una mesa y quieren calcular la media de sus salarios. Quieren hacerlo de manera que no se filtre ninguna información privada. Es decir, nadie obtiene ninguna información (sobre los salarios de los demás) que no pueda deducir de la información pública.

Más formalmente, suponemos que (1) todos los salarios son enteros no negativos delimitados por B (2) todos se comportan honestamente y no intentan detener el proceso (3) ningún subconjunto de individuos se confabulará (4) hay líneas de comunicación privadas y seguras entre todos los participantes (5) toda esta información es bien conocida (6) no hay ninguna parte externa de confianza.

Pregunta 1: ¿Es posible que los N individuos calculen colectivamente la media sin filtrar ninguna información? Decimos que hay fuga de información si algún individuo tiene alguna información al final del proceso sobre el salario de los demás que no podría haber deducido al conocer su propio salario y la media.

La respuesta es sí. Basta con calcular la suma de los salarios. Fijemos S = 10*N*B. Ahora, la primera persona (Alice) elige un número aleatorio entre 0 y S-1 y lo añade a su salario mod S. A continuación, pasa la suma a su vecino, Bob, que añade su salario. Esto continúa alrededor de la mesa hasta que Zoey (la última participante) le pasa el número a Alice. Alice resta el número al azar y anuncia la suma al grupo.

Aquí hay dos preguntas relacionadas:

Pregunta 2: ¿Es posible que el grupo calcule el salario máximo (con las limitaciones anteriores) sin filtrar ninguna información?

Pregunta 3: ¿Podemos eliminar del algoritmo anterior la suposición de que se conoce de antemano el tamaño de los salarios?

Nota adicional: En la pregunta 2 queremos calcular sólo el máximo sin proporcionar ninguna otra información. Se puede observar que, por ejemplo, la distribución completa de los salarios podría calcularse y comunicarse al grupo calculando los momentos de la secuencia mediante el método anterior. Esto daría el máximo (aunque también mucha otra información).

Answer 1

Estas cuestiones (y muchas otras) se estudian en la literatura bajo el epígrafe de protocolos de intercambio de secretos o de conocimiento común. En el capítulo 4 de "Tracking the Automatic Ant", de David Gale, aparece una bonita pero breve revisión.

El "protocolo de suma" que has presentado se puede modificar para determinar cuántas personas tienen el sueldo x (sin revelar su identidad). Basta con que cada participante comunique 0 o 1 en función de si tiene o no el salario x, y escaneando todas las x en el rango (presumiblemente conocido) de salarios se puede conocer la distribución, así como el máximo (escaneando hacia abajo desde algún límite superior). Sin embargo, este protocolo no sólo revela el salario máximo, sino también cuántas personas ganan ese máximo.

Estos protocolos se denominan $t$ -privados si no revelan ninguna información adicional a menos que $t$ las personas se "confabulan" y discuten sus conocimientos entre sí. El protocolo que mencionas es, de hecho, $n$ -privado - a menos que todos cooperen, todos están en la oscuridad (EDIT: esto es falso, por supuesto, como se señala en los comentarios. Lo correcto es $n$ -(el protocolo privado se describe más adelante). La suma es, esencialmente, la única función que se puede calcular $n$ -de forma privada. Se puede calcular el máximo (sin el conocimiento adicional de cuántas personas lo ganan), el producto, etc. $t$ -privadamente para $t < n/2$ pero no para $t \geq n/2$ . La existencia está demostrada por Ben-Or, Goldwasser y Wigderson en STOC 1988; la no existencia por Chor y Kushilevitz (STOC 1989) para funciones booleanas y por Beaver para funciones generales de valor entero. Todo esto está extraído del libro de Gale.

Cómo calcular la suma $n$ -de forma privada: Cada persona divide su salario en una suma de $n$ números, elegidos al azar excepto por la restricción de que su suma sea $n$ . Cada persona comunica ahora el $j$ parte a la $j$ persona (incluso "comunicándose" una de las piezas a sí misma). A continuación, todos anuncian las sumas de todas las piezas que les fueron comunicadas. Es un ejercicio divertido para demostrar que no $k$ la gente puede averiguar algo que no sea lo que pueda derivarse de sus propios salarios, para cualquier $k < n$ .

Answer 2

Para la pregunta 3, me parece que el algoritmo descrito en la pregunta puede modificarse para no requerir conocer un límite en los salarios para empezar: en lugar de trabajar módulo 10*N*B, simplemente hacer todo sobre Z.

Ahora Alicia tiene que elegir un número aleatorio de Z. Por supuesto, no puede utilizar la distribución uniforme, pero lo único que hace falta es que no haga pública ninguna información sobre la distribución que utiliza. Si esa información no es pública, no veo cómo alguien podría deducir algo del único número que ve en el curso de la aplicación del algoritmo.

Answer 3

"Esto continúa alrededor de la mesa hasta que Zoey (la última participante) le pasa el número a Alice. Alice resta el número al azar y anuncia la suma al grupo".

Zoey entonces toma la suma y la resta del número que le dio a Alice, revelando así el número aleatorio de Alice. Luego se lo da a Bob, que ahora puede calcular el salario de Alice y así sucesivamente.

¿No?