Проверка эквивалентности среди распределенных наборов

• У меня есть элементы из $\{0, 1\}^{n}$ (диапазон хэш-функции)
• Мастер $А$ может иметь любое подмножество этого диапазона.
• Есть клиенты, каждый из которых также имеет подмножество из пространства.
• Я хочу убедиться, что объединение наборов клиентов равно основному набору
• Общение должно быть как можно меньше.
• Элементы секретные. (это требование можно ослабить с помощью решения, которое потенциально может протекать)

спасибо @kelalaka за уточнение вопроса.

Потенциальным вариантом было бы использование Фильтры Блума идентифицировать потенциал дубликаты вероятностно, а затем проверьте, действительно ли они дубликаты, отправив несколько потенциалов. Если вы используете достаточно большие фильтры Блума, этого будет достаточно для любого размера.

В качестве альтернативы, что, возможно, не очень подходит, вы можете использовать мини-эскиз.

Из ридми,

Скетчи, создаваемые этой библиотекой, можно рассматривать как «установленные контрольные суммы» с двумя особыми свойствами:

1. Скетчи имеют предопределенную вместимость, и когда количество элементов в наборе не превышает вместимости, libminisketch всегда будет восстанавливать весь набор из скетча. Эскиз b-битных элементов разрядностью c может храниться в bc битах.
2. Эскизы двух наборов можно объединить, добавив их (исключающее ИЛИ), чтобы получить эскиз симметричной разницы между двумя наборами (т. Е. Все элементы, которые встречаются в одном, но не в обоих входных наборах).

Поэтому, если вы используете достаточно большую емкость, вы можете просто XOR эскизов, чтобы определить уникальные элементы и удалить остальные.