Эффективное многопартийное объединение приватных множеств, устойчивое к максимальным сговорным атакам

Почему важно делиться чёрными списками, не раскрывая секретов

Многим организациям нужно сотрудничать по данным, не раскрывая при этом чувствительные детали. Представьте банки, которые хотят объединить свои чёрные списки подозрительных аккаунтов, или компании, желающие совместно использовать индикаторы мошенничества, сохраняя в тайне информацию о клиентах и внутренние методы. В этой статье рассматривается, как несколько сторон могут вычислить объединение своих приватных списков — все элементы, которые встречаются хотя бы в одном списке — так, чтобы каждый узнал только итоговый объединённый список и ничего лишнего о данных других участников. Внимание уделяется обеспечению как высокой устойчивости к сговору, так и эффективности при очень больших наборах данных.

Как собрать вместе множество приватных списков

Задача, рассматриваемая здесь, называется многопартийное приватное объединение множеств. Каждый участник хранит конфиденциальную коллекцию элементов — например номера счётов или идентификаторы — и хочет узнать объединение всех элементов по всем сторонам. Никто не должен узнавать, какая сторона внесла тот или иной элемент, и никто не должен видеть элементы, отсутствующие в итоговом объединении. Существующие подходы опираются либо на тяжёлую криптографию с открытым ключом, либо на общие фреймворки безопасного вычисления, которые становятся непрактичными, когда множества содержат миллионы записей или участвует много сторон. Недавний протокол Гао и соавторов улучшил масштабируемость и мог противостоять «максимальному сговору», то есть оставаться безопасным даже если все, кроме одного участника, тайно сотрудничают, но при этом он по‑прежнему требовал передачи огромных объёмов объёмных зашифрованных сообщений.

Снижение затрат на пропускную способность с помощью более умного набора инструментов

Авторы предлагают новый протокол, который сохраняет сильную устойчивость к сговору, предложенную Гао и др., одновременно резко снижая объём коммуникаций и ускоряя время работы. Их ключевая идея — резервировать дорогое шифрование с открытым ключом только для самых критичных частей — элементов, которые должны оставаться зашифрованными и позже совместно расшифровываться — и использовать более лёгкое и быстрое симметричное шифрование для основной массы промежуточных данных. Они проектируют двухфазный «один лидер» протокол, в котором все стороны подготавливают структуры данных на основе хешей по своим множествам, а затем взаимодействуют так, что только назначенный лидер в конце узнаёт объединение. Центральный строительный блок, называемый пакетной генерацией случайных значений с проверкой равенства в режиме слепого обмена (batched equality‑tested oblivious random generation), позволяет двум сторонам генерировать совпадающие случайные маски тогда, когда их скрытые элементы равны, не раскрывая, какие именно элементы совпали. Это обеспечивает эффективную приватную фильтрацию дубликатов по мере прохождения информации через протокол.

От одного лидера к более справедливому совместному результату

В некоторых совместных проектах наличие единственного лидера, который один получает результат, может быть рискованным или политически неприемлемым. Авторы поэтому расширяют свою схему до «безлидерной» версии, в которой каждый участник получает объединение напрямую. Они сохраняют ту же подготовительную работу, но повторяют фазу взаимодействия несколько раз, по очереди меняя роль лидера в каждом прогоне. Каждый раунд производит объединение для разного участника, с использованием совместной расшифровки и перетасовки, так что никто не может отследить элементы до их исходных владельцев. Эта безлидерная конструкция повышает надёжность и справедливость — ни одна сторона не может удерживать результат или становиться узким местом — ценой дополнительной коммуникации, примерно умножающейся на число участников.

Как новый протокол масштабируется в реальных условиях

Команда реализовала свои протоколы и сравнила их с лучшей предыдущей схемой при различных размерах множеств и числе участников. Они инстанцируют компонент с открытым ключом с пороговым шифрованием ElGamal и подключают существующие библиотеки для хеширования, тестов на равенство и базовых криптографических примитивов. В реальных параметрах их протокол с одним лидером снижает объём коммуникаций примерно в 4–5 раз и ускоряет время выполнения примерно в 1.3–1.8 раза, в зависимости от числа участников и элементов. Безлидерный протокол естественно использует больше пропускной способности, но также выигрывает от тех же проектных улучшений, а его шаги расшифровки можно перекрывать, так что общее время выполнения растёт медленнее, чем объём коммуникаций.

Что это значит для конфиденциального совместного использования данных

Для неспециалиста вывод в том, что эта работа делает более практичным объединение чувствительных списков для многих независимых организаций без раскрытия их исходных данных, даже если почти все они решат сговориться. Тщательно выбирая, когда применять тяжёлое шифрование, а когда подходят более лёгкие методы, авторы предоставляют протоколы, которые существенно экономят пропускную способность, сохраняя при этом сильные гарантии безопасности. Их безлидерный вариант дополнительно устраняет зависимость от любой единственной стороны при распространении результатов. В совокупности эти достижения переводят приватное объединение данных из преимущественно теоретической задачи в инструмент, готовый к внедрению в секторах, таких как финансы, кибербезопасность и аналитика данных.

Цитирование: 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

Ключевые слова: объединение приватных множеств, безопасное совместное использование данных, многопартийные вычисления, шифрование с сохранением конфиденциальности, протоколы, устойчивые к сговору