Estimar un percentil entre nodos distribuidos sin revelar valores

23

Tengo un problema bastante único que resolver y espero que alguien aquí pueda darme una idea de cómo abordarlo mejor.

Problema: suponga que una lista de N números se comparte entre un conjunto de participantes de tal manera que ningún participante en realidad sepa ninguno de los números que comparte. Todos los participantes saben N (el tamaño de la lista de números) y la suma de todos los números en la lista, pero nada más a priori.

Al trabajar juntos, es posible comparar dos números compartidos ayb de tal manera que los participantes aprendan si la afirmación "a <b" es verdadera, pero nada más. Sin embargo, esto es algo extremadamente costoso (lea: podría llevar muchos segundos, tal vez incluso minutos, completar una sola comparación). Vea el final de esta publicación para obtener un poco más de información sobre cómo es posible tal cosa.

Al final del día, las partes desean dar a conocer los índices de la lista que corresponden al "porcentaje K superior" (el K% que es el más grande) números compartidos en la lista. Por supuesto, esto se puede hacer clasificando o utilizando un algoritmo de selección "K principal". Sin embargo, estos tienden a utilizar una gran cantidad de comparaciones, lo que debe evitarse. (Estos son O (n log n) u O (n), con constantes ocultas bastante grandes).

Otra alternativa es "adivinar" un número X para el que (1-K)% son menores que X y K% son mayores. Luego puede comparar cada elemento con X y ver cuántos son más grandes y cuántos son más pequeños. Si su suposición fue incorrecta, revísela usando algo como una búsqueda binaria hasta que converja en una solución correcta. Esto requiere muchas menos comparaciones si su suposición es buena.

Entonces, mi pregunta es,

Dado solo N y la suma, ¿cuál es la mejor manera de "predecir" X?

Por supuesto, esto dependerá de la distribución subyacente. Para diferentes casos de uso, la distribución subyacente probablemente será diferente, pero se conocerá, por lo que estoy interesado en buenas soluciones para todos los comunes (normal, uniforme, exponencial, quizás algunos otros). También me encantaría escuchar sugerencias sobre la mejor manera de hacer una búsqueda "binaria" para minimizar el número de pasos dados una suposición sobre la distribución subyacente.

fififi(j)1≤i≤N. Dado este porcentaje, el participante no tiene información (en un sentido teórico de la información) sobre el número; de hecho, ningún subconjunto adecuado de participantes puede combinar el conocimiento para aprender información sobre los números compartidos. Sin embargo, utilizando una técnica sofisticada de cómputo seguro de múltiples partes, es posible determinar si un valor compartido es menor que otro sin revelar más información. Esta técnica implica que todos los participantes cooperen, por lo que es tan costoso de hacer y debe hacerse la menor cantidad de veces posible.

cr.crypto-security dc.distributed-comp st.statistics privacy Kaveh
fuente
MMNNa<b
1
Debido a que esta pregunta parece ser más algorítmica que estadística (una solicitud de aclaración a este respecto no obtuvo respuesta) y la comunidad estadística no ha ofrecido una respuesta viable, migremos a TCS para ver si genera algún interés allí.
whuber
66
La verdadera pregunta parece ser simplemente la siguiente: "Si conocemos la distribución, ¿cómo podemos explotar esta información en el diseño de un algoritmo de selección basado en la comparación ? El algoritmo debe usar la menor cantidad posible de comparaciones (en expectativa; los factores constantes importar)." ¿Lo entendí bien?
Jukka Suomela
2
¿Has considerado el problema de los millonarios de Yao ? Permite una comparación segura con mucho menos cómputo.
MS Dousti
3
(k,n) nk(n,n)k<<n
Massimo Cafaro

Respuestas:

1

Parece que haces dos preguntas relacionadas:

  1. "Qué índices en la lista corresponden a la parte superior"
  2. "Estimación de un percentil", "un número X para el que ... K% son mayores"

Estos pueden necesitar números muy diferentes de comparaciones por pares.

Otro aspecto que puede tener un impacto significativo es la información que se comparte. Todo el mundo sabe el número que recibió, conoce la suma y los resultados sí / no de las comparaciones en las que han participado. Sin embargo, usted también dice que "las partes desean obtener los índices de la lista que corresponden a la parte superior", por lo que sugiere que se compartirá alguna información sobre los índices. Dependiendo de lo que se comparta exactamente, puede obtener soluciones muy diferentes nuevamente.


fuente
Lo siento, no debo haber sido lo suficientemente claro. Nadie conoce un solo número en la lista; en cambio, cada uno tiene una lista de N "acciones de números" (usando el esquema de Compartir Secreto de Shamir, si no está familiarizado con los conceptos de acciones de un número). Entonces, la única información a priori que tiene un solo participante es N y la suma de todos los números en la lista. Cada uno tiene un poco de información sobre cada número, pero no suficiente información para saber cuál es ese número.
En cuanto a las dos preguntas relacionadas, la segunda pregunta implica una solución eficiente a la primera. Si puedo encontrar X usando pocas comparaciones (lo que puedo hacer si puedo llegar a una suposición inicial razonablemente buena), entonces encuentro los índices de todos los valores mayores que X usando solo N más comparaciones (estas comparaciones también son más baratas, ya que conocer X en lugar de tener una parte de X reduce el costo de una comparación en aproximadamente un tercio.) Los algoritmos de propósito general para encontrar el K superior generalmente usarán muchas más comparaciones para tamaños de lista grandes, suponiendo que pueda encontrar X usando ~ log ( X) comparaciones
Gracias por las respuestas al comentario y el apéndice de la pregunta original. Ahora el problema se ve diferente.