Wydajny wielostronny prywatny zbiór unii odporny na ataki maksymalnego sprzymierzenia

Dlaczego udostępnianie czarnych list bez ujawniania tajemnic ma znaczenie

Wiele organizacji musi współpracować na danych, nie ujawniając jednak wrażliwych szczegółów, które za nimi stoją. Pomyśl o bankach chcących połączyć swoje czarne listy podejrzanych kont albo firmach, które pragną skonsolidować wskaźniki oszustw, zachowując jednocześnie poufność informacji o klientach i wewnętrznych metodach. W artykule badane jest, jak kilka stron może obliczyć unię swoich prywatnych list — wszystko, co występuje przynajmniej na jednej liście — tak aby każdy poznał jedynie ostateczną połączoną listę, a nic więcej o danych pozostałych uczestników. Skupia się na osiągnięciu zarówno wysokiego poziomu bezpieczeństwa przed sprzymierzeniami, jak i efektywności wystarczającej dla bardzo dużych zbiorów danych.

Łączenie wielu prywatnych list

Zadanie opisane tutaj nosi nazwę wielostronnej prywatnej unii zbiorów. Każdy uczestnik posiada poufną kolekcję elementów, takich jak numery kont czy identyfikatory, i chce poznać unię wszystkich elementów wszystkich stron. Nikt nie powinien dowiedzieć się, która strona wniosła który element, ani zobaczyć elementu, który nie należy do ostatecznej unii. Istniejące podejścia opierają się albo na kosztownej kryptografii z kluczami publicznymi, albo na ogólnych ramach obliczeń bezpiecznych, które stają się niepraktyczne, gdy zbiory zawierają miliony wpisów lub gdy uczestników jest wielu. Niedawny protokół autorstwa Gao i współpracowników poprawił skalowalność i potrafił przeciwstawić się „maksymalnemu sprzymierzeniu”, czyli pozostać bezpiecznym nawet jeśli wszyscy poza jednym uczestnikiem potajemnie współpracowali, ale nadal wymagał przesyłania ogromnych ilości masywnych zaszyfrowanych komunikatów.

Obniżenie rachunku za przepustowość dzięki mądrzejszemu doborowi narzędzi

Autorzy proponują nowy protokół, który zachowuje silną odporność na sprzymierzenia z pracy Gao i wsp., a jednocześnie ostro zmniejsza komunikację i przyspiesza działanie. Ich kluczowy pomysł to zarezerwowanie kosztownego szyfrowania z kluczem publicznym tylko dla najistotniejszych części — elementów, które muszą pozostać zaszyfrowane i później być wspólnie odszyfrowane — przy jednoczesnym użyciu lżejszego, szybszego szyfrowania symetrycznego dla większości danych pośrednich. Projektują dwufazowy protokół „z jednym liderem”, w którym wszystkie strony przygotowują struktury danych oparte na skrótach dla swoich zbiorów, a następnie wchodzą w interakcję tak, by tylko wyznaczony lider ostatecznie poznał unię. Centralny element konstrukcji, zwany partiowym testem równości z nieuwalnianą losową generacją (batched equality-tested oblivious random generation), pozwala dwóm stronom generować dopasowane losowe maski zawsze, gdy ich ukryte elementy są równe, bez ujawniania, które elementy się dopasowały. To wspiera efektywne, zachowujące prywatność filtrowanie duplikatów w przepływie informacji przez protokół.

Od pojedynczego lidera do bardziej sprawiedecznego, współdzielonego wyniku

W niektórych współpracach posiadanie jednego lidera, który samodzielnie otrzymuje wynik, może być ryzykowne lub politycznie nieakceptowalne. Autorzy rozszerzają więc swoją konstrukcję do wersji „bez lidera”, w której każdy uczestnik otrzymuje unię bezpośrednio. Zachowują tę samą pracę przygotowawczą, lecz powtarzają fazę interakcji wielokrotnie, rotując, która strona pełni rolę lidera w każdej rundzie. Każda runda wytwarza unię dla innego uczestnika, używając wspólnego odszyfrowania i tasowania, tak by nikt nie mógł prześledzić elementów z powrotem do ich pierwotnych właścicieli. Ta bezliderowa konstrukcja poprawia odporność i sprawiedliwość — żadna pojedyncza strona nie może wstrzymać wyniku ani stać się wąskim gardłem — kosztem dodatkowej komunikacji, która jest mniej więcej mnożona przez liczbę uczestników.

Jak nowy protokół skaluje się w rzeczywistych warunkach

Zespół zaimplementował swoje protokoły i porównał je z najlepszym poprzednim schematem dla różnych rozmiarów zbiorów i liczby uczestników. Składają komponent publicznego klucza z progowym szyfrowaniem ElGamal i wykorzystują istniejące biblioteki do hashowania, testów równości oraz podstawowych prymitywów kryptograficznych. W realistycznych konfiguracjach parametrów ich protokół z jednym liderem redukuje objętość komunikacji około czterokrotnie do pięciokrotnie i przyspiesza czas działania o około 1,3–1,8 razy, w zależności od liczby stron i elementów. Protokół bez lidera naturalnie korzysta z większej przepustowości, lecz wciąż zyskuje dzięki tym samym efektywnościom projektowym, a jego kroki odszyfrowania można nakładać równolegle, tak że całkowity czas rośnie wolniej niż koszt komunikacji.

Co to oznacza dla współpracy zachowującej prywatność

Dla osoby niezajmującej się specjalistycznie tematem wniosek jest taki, że ta praca czyni bardziej praktycznym łączenie wrażliwych list przez wiele niezależnych organizacji bez ujawniania surowych danych, nawet jeśli niemal wszystkie z nich miałyby się sprzymierzyć. Poprzez staranny wybór momentów użycia „ciężkiej” kryptografii i momentów, gdy wystarczą lżejsze metody, autorzy dostarczają protokoły znacznie oszczędniejsze pod względem przepustowości, zachowując jednocześnie silne gwarancje bezpieczeństwa. Ich wariant bez lidera dodatkowo usuwa zależność od pojedynczej strony w przekazywaniu wyników. Razem te osiągnięcia przesuwają prywatno‑zachowującą unię danych z obszaru głównie teoretycznego w stronę narzędzia możliwego do wdrożenia w sektorach takich jak finanse, cyberbezpieczeństwo i analityka danych.

Cytowanie: Liu, Q., Lee, JW. Efficient multi-party private set union resistant to maximum collusion attacks. Sci Rep 16, 13230 (2026). https://doi.org/10.1038/s41598-026-41069-2

Słowa kluczowe: prywatna unia zbiorów, bezpieczna współpraca danych, obliczenia wielostronne, szyfrowanie zachowujące prywatność, protokoły odporne na sprzymierzenia