Szacowanie percentylu między rozproszonymi węzłami bez ujawniania wartości

Mam dość unikalny problem do rozwiązania i mam nadzieję, że ktoś tutaj da mi wgląd w to, jak najlepiej go rozwiązać.

Problem: Załóżmy, że lista N liczb jest dzielona między zestawem uczestników w taki sposób, że żaden pojedynczy uczestnik nie zna żadnej z dzielonych przez siebie liczb. Wszyscy uczestnicy znają N (wielkość listy liczb) i sumę wszystkich liczb na liście, ale nic więcej a priori.

Współpracując, można porównać dwie wspólne liczby aib w taki sposób, aby uczestnicy dowiedzieli się, czy stwierdzenie „a <b” jest prawdziwe, ale nic więcej. Jest to jednak bardzo kosztowna rzecz (przeczytaj: wykonanie pojedynczego porównania może zająć wiele sekund, a może nawet minut). Zobacz koniec tego postu, aby uzyskać więcej informacji na temat tego, jak to możliwe.

Na koniec dnia strony chcą przedstawić dane wyjściowe, które indeksy na liście odpowiadają „najwyższym K procentom” (największy procent K) na wspólnej liczbie na liście. Można to oczywiście zrobić przez sortowanie lub użycie algorytmu wyboru „najwyższego K”. Jednak zwykle używają okropnych porównań, których należy unikać. (Są to O (n log n) lub O (n), z dość dużymi ukrytymi stałymi.)

Inną alternatywą jest „odgadnięcie” liczby X, dla której (1-K)% jest mniejsze niż X, a K% jest większe. Następnie możesz porównać każdy element z X i zobaczyć, ile jest większych, a ile mniejszych. Jeśli twoje domysły były błędne, popraw je, używając czegoś w rodzaju wyszukiwania binarnego, dopóki nie zbiegniesz na właściwym rozwiązaniu. To wymaga znacznie mniej porównań, jeśli twoje przypuszczenia są dobre.

Moje pytanie brzmi:

Biorąc pod uwagę tylko N i sumę, jaki jest najlepszy sposób na „przewidzenie” X?

Oczywiście będzie to zależeć od podstawowej dystrybucji. W przypadku różnych przypadków użycia podstawowa dystrybucja będzie prawdopodobnie inna, ale będzie znana, dlatego interesują mnie dobre rozwiązania dla wszystkich popularnych (normalne, jednolite, wykładnicze, może kilka innych). Bardzo chciałbym usłyszeć sugestie dotyczące najlepszego wyszukiwania typu „binarnego”, aby zminimalizować liczbę kroków przy założeniu, że rozkład leży u podstaw.

$f_i$ $f_i$ $f_i(j)$ $1\leq i\leq N$ . Biorąc pod uwagę ten udział, uczestnik nie ma informacji (w sensie teoretycznym) na temat liczby; w rzeczywistości żaden odpowiedni podzbiór uczestników nie może połączyć wiedzy, aby uzyskać informacje na temat wspólnych numerów. Jednak stosując wyrafinowaną bezpieczną technikę obliczeń wielostronnych, można ustalić, czy jedna wspólna wartość jest mniejsza niż inna, bez ujawniania jakichkolwiek informacji. Ta technika wymaga współpracy wszystkich uczestników, dlatego jest tak kosztowna i powinna być wykonywana jak najmniej razy.

cr.crypto-security dc.distributed-comp st.statistics privacy Kaveh
źródło

M

$M$

M

$M$

N

$N$

N

$N$

a < b

$a < b$

Ponieważ to pytanie wydaje się być bardziej algorytmiczne niż statystyczne (prośba o wyjaśnienie w tym zakresie nie otrzymała odpowiedzi), a społeczność statystyczna nie zaoferowała realnej odpowiedzi, migrujmy do TCS, aby zobaczyć, czy wzbudzi jakieś zainteresowanie.

whuber

Prawdziwe pytanie wydaje się po prostu następujące: „Jeśli znamy rozkład, w jaki sposób możemy wykorzystać tę informację w projekcie algorytmu wyboru opartego na porównaniu ? Algorytm powinien wykorzystywać jak najmniej porównań (w oczekiwaniu; czynniki stałe materia)." Czy dobrze to zrozumiałem?

Jukka Suomela,

Czy zastanawiałeś się nad problemem milionerów Yao ? Umożliwia bezpieczne porównanie przy znacznie mniejszej liczbie obliczeń.

MS Dousti,

(k, n)

$(k, n)$

n

$n$

k

$k$

(n, n)

$(n, n)$

k << n

$k << n$

Massimo Cafaro,

Wydaje się, że zadajesz dwa powiązane pytania:

„Które indeksy na liście odpowiadają górze”
„Oszacowanie percentyla”, „liczba X, dla której… K% jest większe”

Mogą one wymagać bardzo różnej liczby porównań parami.

Innym aspektem, który może mieć znaczący wpływ, są informacje, które są udostępniane. Wszyscy znają liczbę, którą otrzymał, znają sumę i wyniki porównań, w których brali udział. Tak / nie. Mówisz jednak również, że „strony chcą podać, które wskaźniki na liście odpowiadają górnej”, dlatego sugerujesz że niektóre informacje o indeksach zostaną udostępnione. W zależności od tego, co dokładnie jest udostępniane, możesz ponownie uzyskać bardzo różne rozwiązania.

źródło

Przepraszam, nie mogłem być wystarczająco jasny. Nikt nie zna ani jednego numeru na liście; zamiast tego każdy z nich ma listę N „udziałów liczb” (używając tajnego schematu Shamir's Sharing, jeśli nie znasz koncepcji udziałów w liczbie). Tak więc jedyną informacją a priori, którą ma każdy uczestnik, jest N i suma wszystkich liczb na liście. Każdy z nich ma trochę informacji o każdej liczbie, ale za mało informacji, aby wiedzieć, co to jest liczba.

Jeśli chodzi o dwa powiązane pytania, drugie pytanie oznacza skuteczne rozwiązanie pierwszego. Jeśli mogę znaleźć X za pomocą kilku porównań (co mogę zrobić, jeśli mogę wymyślić dość dobre początkowe domysły), to znajduję wskaźniki wszystkich wartości większych niż X, używając tylko N więcej porównań (te porównania są również tańsze, ponieważ znajomość X zamiast udziału X obniża koszt porównania o około jedną trzecią.) Algorytmy ogólnego przeznaczenia do znalezienia najlepszego K zwykle używają znacznie więcej porównań dla dużych rozmiarów list, zakładając, że mogę znaleźć X używając ~ log ( X) porównania

Dzięki za odpowiedzi na komentarz i dodatek do pierwotnego pytania. Teraz problem wygląda inaczej.

Szacowanie percentylu między rozproszonymi węzłami bez ujawniania wartości

Odpowiedzi: