Estimation d'un centile parmi les nœuds distribués sans révéler de valeurs

J'ai un problème assez unique à résoudre et j'espère que quelqu'un ici pourra me donner un aperçu de la meilleure façon de le résoudre.

Problème: supposons qu'une liste de N nombres soit partagée entre un ensemble de participants de telle manière qu'aucun participant ne connaisse réellement aucun des nombres qu'ils partagent. Tous les participants connaissent N (la taille de la liste des nombres) et la somme de tous les nombres de la liste, mais rien de plus a priori.

En travaillant ensemble, il est possible de comparer deux nombres partagés a et b de telle manière que les participants apprennent si l'énoncé "a <b" est vrai, mais rien de plus. Cependant, c'est une chose extrêmement coûteuse à faire (lire: cela pourrait prendre plusieurs secondes, voire quelques minutes, pour effectuer une seule comparaison). Voir la fin de ce post pour un peu plus d'informations sur la façon dont une telle chose est possible.

À la fin de la journée, les parties souhaitent afficher les indices de la liste qui correspondent aux "K% supérieurs" (le K% qui est le plus grand) des nombres partagés dans la liste. Cela peut bien sûr être fait par tri, ou en utilisant un algorithme de sélection "top K". Cependant, ceux-ci ont tendance à utiliser beaucoup de comparaisons, ce qui est à éviter. (Ce sont soit O (n log n) ou O (n), avec des constantes cachées assez grandes.)

Une autre alternative consiste à "deviner" un nombre X pour lequel (1-K)% sont plus petits que X et K% sont plus grands. Ensuite, vous pouvez comparer chaque élément avec X et voir combien sont plus grands et combien sont plus petits. Si votre supposition était fausse, révisez-la en utilisant quelque chose comme une recherche binaire jusqu'à ce que vous convergiez vers une solution correcte. Cela prend beaucoup moins de comparaisons si votre estimation est bonne.

Donc, ma question est,

Étant donné seulement N et la somme, quelle est la meilleure façon de "prédire" X?

Bien sûr, cela dépendra de la distribution sous-jacente. Pour différents cas d'utilisation, la distribution sous-jacente sera probablement différente mais sera connue, donc je suis intéressé par de bonnes solutions pour toutes les plus courantes (normales, uniformes, exponentielles, peut-être quelques autres). J'aimerais aussi entendre des suggestions sur la meilleure façon de faire la recherche "binaire" pour minimiser le nombre d'étapes étant donné une hypothèse sur la distribution sous-jacente.

ANNEXE: Chaque valeur de la liste est partagée entre les participants à l'aide du schéma de partage secret de Shamir. Supposons qu'il y ait M participants et que la liste soit de longueur N. Ensuite, le i-ème nombre sur la liste est représenté par un polynôme de degré M-1 sur un champ fini F. Le terme constant de est le nombre qui est partagé, tous les autres coefficients sont choisis uniformément au hasard parmi F. Les parts du j-ième participant sont alors , $f_i$ $f_i$ $f_i(j)$ $1\leq i\leq N$ . Compte tenu de cette part, le participant n'a aucune information (au sens théorique de l'information) sur le nombre; en fait, aucun sous-ensemble de participants ne peut combiner les connaissances pour apprendre des informations sur les numéros partagés. Cependant, en utilisant une technique de calcul multipartite sécurisée sophistiquée, il est possible de déterminer si une valeur partagée est inférieure à une autre sans révéler plus d'informations. Cette technique implique la coopération de tous les participants, c'est pourquoi il est si coûteux de le faire et devrait être fait le moins de fois possible.

cr.crypto-security dc.distributed-comp st.statistics privacy Kaveh
la source

M

$M$

M

$M$

N

$N$

N

$N$

a < b

$a < b$

Étant donné que cette question semble être plus algorithmique que statistique (une demande d'éclaircissement à cet égard n'a reçu aucune réponse) et que la communauté des statistiques n'a pas proposé de réponse viable, migrons vers TCS pour voir si cela y suscite un intérêt.

2011

La vraie question semble être simplement la suivante: "Si nous connaissons la distribution, comment pouvons-nous exploiter ces informations dans la conception d'un algorithme de sélection basé sur la comparaison ? L'algorithme devrait utiliser le moins de comparaisons possible (dans l'attente; les facteurs constants matière)." Ai-je bien compris?

Jukka Suomela

Avez-vous considéré le problème des millionnaires de Yao ? Il permet une comparaison sécurisée avec beaucoup moins de calculs.

MS Dousti

(k, n)

$(k, n)$

n

$n$

k

$k$

(n, n)

$(n, n)$

k << n

$k << n$

Massimo Cafaro

Vous semblez poser deux questions connexes:

"Quels indices de la liste correspondent au top"
"Estimation d'un centile", "un nombre X pour lequel ... K% sont plus grands"

Ceux-ci peuvent nécessiter des nombres très différents de comparaisons par paires.

Un autre aspect qui peut avoir un impact significatif est la nature des informations partagées. Tout le monde connaît le nombre qu'il a reçu, connaît la somme et les résultats oui / non des comparaisons auxquelles ils ont participé. Cependant, vous dites également que «les parties souhaitent afficher les indices de la liste qui correspondent au sommet», vous suggérez donc que certaines informations sur les indices seront partagées. Selon ce qui est exactement partagé, vous pouvez à nouveau obtenir des solutions très différentes.

la source

Désolé, je n'ai pas dû être suffisamment clair. Personne ne connaît un seul numéro sur la liste; au lieu de cela, ils ont chacun une liste de N "partages de nombres" (en utilisant le schéma de partage secret de Shamir, si vous n'êtes pas familier avec les concepts de partages d'un nombre). Ainsi, la seule information a priori dont dispose un seul participant est N et la somme de tous les nombres de la liste. Ils ont chacun un peu d'informations sur chaque numéro, mais pas assez d'informations pour savoir quel est ce nombre.

En ce qui concerne les deux questions connexes, la deuxième question implique une solution efficace à la première. Si je peux trouver X en utilisant peu de comparaisons (ce que je peux faire si je peux faire une supposition initiale raisonnablement bonne), alors je trouve les indices de toutes les valeurs plus grands que X en utilisant seulement N comparaisons supplémentaires (ces comparaisons sont également moins chères, car connaître X au lieu d'avoir une part de X réduit le coût d'une comparaison d'environ 1 tiers.) Les algorithmes à usage général pour trouver le top K utiliseront généralement beaucoup plus de comparaisons pour les grandes listes, en supposant que je puisse trouver X en utilisant ~ log ( X) Comparaisons

Merci pour les réponses aux commentaires et l'annexe à la question d'origine. Maintenant, le problème semble différent.

Estimation d'un centile parmi les nœuds distribués sans révéler de valeurs

Réponses: