Многосторонний приватный поиск пересечений множеств с превышением порога для совместного обнаружения сетевых вторжений

Основная информация

• ID статьи: 2510.12045
• Название: Over-Threshold Multiparty Private Set Intersection for Collaborative Network Intrusion Detection
• Авторы: Onur Eren Arpaci, Raouf Boutaba, Florian Kerschbaum (Университет Ватерлоо)
• Классификация: cs.CR (Криптография и безопасность), cs.NI (Сетевые архитектуры и интернет)
• Дата публикации: 14 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.12045

Аннотация

Важной функцией совместного обнаружения сетевых вторжений является анализ сетевых журналов участников для выявления общих IP-адресов. Однако открытый обмен IP-адресами является конфиденциальной информацией и может быть ограничен законодательством о защите приватности, поскольку представляет собой персональные идентификационные данные. В данной работе предлагается метод приватного сбора IP-адресов с использованием протокола многостороннего приватного поиска пересечений множеств с превышением порога для одного агрегатора. В этом протоколе N участников выявляют IP-адреса, присутствующие в множествах по крайней мере t участников, без раскрытия информации о других IP-адресах. Благодаря новой схеме хеширования вычислительная сложность предыдущего передового решения снижена с $O(M(N \log{M}/t)^{2t})$ до $O(t^2M\binom{N}{t})$, где M обозначает размер набора данных. Это снижение делает применение протокола к реальным сетевым журналам практически осуществимым.

Исследовательский контекст и мотивация

Определение проблемы

Основная проблема совместного обнаружения сетевых вторжений заключается в выявлении атак на несколько организаций при сохранении конфиденциальности. Исследования показывают, что 75% атак на несколько организаций распространяются на вторую организацию в течение одного дня, а более 40% распространяются в течение одного часа. Злоумышленники обычно используют небольшое количество внешних IP-адресов для одновременной атаки на несколько организаций. Если внешний IP-адрес подключается по крайней мере к t организациям в определённом временном окне, его можно классифицировать как вредоносный с полнотой 95%.

Проблемы конфиденциальности

Традиционные методы требуют от организаций открытого обмена сетевыми журналами, что создаёт серьёзные риски конфиденциальности:

1. Соответствие законодательству: IP-адреса классифицируются как персональные идентификационные данные в соответствии с GDPR, PIPEDA, CCPA и другими законами
2. Чувствительность данных: Исходные сетевые данные более чувствительны, чем оповещения о безопасности, и содержат большой объём посторонней конфиденциальной информации
3. Масштаб данных: Исходные данные на несколько порядков больше оповещений о безопасности, что делает существующие решения вычислительно неосуществимыми

Ограничения существующих методов

• Kissner и Song 26: Требует O(N) раундов коммуникации, вычислительная сложность O(N³M³)
• Mahdavi et al. 34: Хотя улучшена сложность коммуникации, вычислительные затраты остаются чрезмерными, сложность O(M(N logM/t)²ᵗ)

Основные вклады

1. Новая схема хеширования: Предложен инновационный алгоритм хеширования, снижающий вычислительную сложность с O(M(N logM/t)²ᵗ) до O(t²M(N choose t)), достигая линейной сложности по M
2. Повышение практичности: Протокол может обрабатывать сетевые журналы реального масштаба, завершая обнаружение за 170 секунд при 33 участвующих организациях и максимум 144 045 IP-адресах
3. Двойной вариант развёртывания:
   • Развёртывание, устойчивое к сговору: обеспечивает более сильные гарантии безопасности, но с большими накладными расходами на коммуникацию
   • Неинтерактивное развёртывание: предполагает честного агрегатора, значительно снижая затраты на коммуникацию
4. Доказательство безопасности: Доказана безопасность протокола в модели полусчестного многостороннего вычисления
5. Практическая проверка: Оценка проведена с использованием реальных сетевых журналов проекта CANARIE IDS

Подробное описание методов

Определение задачи

Многосторонний приватный поиск пересечений множеств с превышением порога (OT-MP-PSI):

• Входные данные: N участников, каждый обладающий множеством Si из максимум M элементов
• Выходные данные: Выявление элементов, присутствующих по крайней мере в t множествах, без раскрытия информации о элементах ниже порога
• Ограничения: Модель полусчестной безопасности, участники следуют протоколу, но могут пытаться получить дополнительную информацию

Основные технические компоненты

1. Схема секретного разделения Шамира

Используется пороговая схема (t,n), где любые t сторон могут восстановить секрет V, а менее t сторон не получают никакой информации:

P(x) = c_{t-1}x^{t-1} + c_{t-2}x^{t-2} + ... + c_1x + V

2. Забывчивая псевдослучайная функция (OPRF)

Участники узнают H_K(x), не зная ключ K, а держатель ключа не узнаёт входные данные x или выходные значения.

3. Забывчивое псевдослучайное секретное разделение (OPR-SS)

Объединяет свойства безопасности секретного разделения и OPRF, позволяя участникам получить уникальную долю секрета от держателя ключа.

Архитектура протокола

Неинтерактивное развёртывание

1. Создание долей: Каждый участник создаёт секретные доли для каждого элемента в его множестве
2. Отображение хеширования: Использует новую схему хеширования для отображения долей в корзины размером 1
3. Восстановление: Агрегатор пытается выполнить интерполяцию Лагранжа для всех комбинаций t участников
4. Уведомление о результатах: Агрегатор уведомляет участников об индексах успешного восстановления

Развёртывание, устойчивое к сговору

Использует протокол OPR-SS вместо общего ключа, вычисляя функцию хеширования через многоключевой протокол OPRF, обеспечивая более сильную защиту от сговора.

Технические инновации

Новая схема хеширования

Основная идея: Использование корзин размером 1 для избежания коллизий хеширования вместо их размещения:

1. Обработка коллизий: Когда несколько элементов отображаются в одну корзину, используется псевдослучайная сортировка для выбора наименьшего
2. Стратегия нескольких таблиц: Каждый участник создаёт несколько таблиц, обеспечивая появление потерянных значений в других таблицах
3. Контроль вероятности отказа: Использование 20 таблиц снижает вероятность отказа ниже 2⁻⁴⁰

Ключевые преимущества:

• Агрегатору нужно пробовать только комбинации участников, а не комбинации долей
• Сложность снижена с экспоненциальной до линейной (по M)
• Избегаются большие постоянные коэффициенты традиционных методов распределения по корзинам

Методы оптимизации

1. Обращение сортировки: Последовательные две таблицы используют одну и ту же функцию сортировки, чётные таблицы используют обратную сортировку
2. Использование пустых корзин: Второе размещение использует пустые корзины после первого размещения

Экспериментальная установка

Набор данных

• Реальные данные: Журналы сетевых соединений 54 организаций проекта CANARIE IDS
• Временной диапазон: 1-8 ноября 2023 г., примерно 8 миллиардов записей журнала в день
• Масштаб данных: Примерно 700 ГБ в день (сжато gzip)
• Способ обработки: Обработка почасовыми партиями, извлечение соединений внешних IP-адресов к внутренним IP-адресам

Метрики оценки

• Время восстановления: Время, необходимое агрегатору для завершения восстановления
• Время генерации долей: Время, необходимое отдельному участнику для создания долей
• Сложность коммуникации: Общие накладные расходы на коммуникацию протокола
• Корректность: Проверка вероятности отказа

Методы сравнения

• Mahdavi et al. 34: Текущее передовое решение OT-MP-PSI
• Теоретические границы: Сравнение с вычисленными верхними границами вероятности отказа

Детали реализации

• Язык программирования: Julia, 430 строк кода
• Криптографическая библиотека: SHA.jl, Nettle.jl
• Конечное поле: 61-битное простое число Мерсенна
• Аппаратная среда: 8×Intel Xeon E7-8870, 80 физических ядер, 1 ТБ памяти

Результаты экспериментов

Основные результаты

Сравнение производительности

По сравнению с Mahdavi et al. 34:

• Ускорение: По крайней мере на два порядка, максимум в 23 066 раз
• Масштабируемость: При M=10⁵ данный метод требует сотни секунд, в то время как метод сравнения требует дней

Производительность на реальных данных

Производительность на данных CANARIE:

• Среднее время восстановления: 170 секунд
• Максимальное время восстановления: 438 секунд (40 организаций, 220 011 IP-адресов)
• Среднее количество участвующих организаций: 33
• Средний максимальный размер множества: 144 045 IP-адресов

Анализ сложности

Вычислительная сложность

• Агрегатор: O(t²M(N choose t))
• Участники (неинтерактивное): O(tM)
• Частные случаи: N=t=2 даёт O(M), N=t даёт O(N²M)

Сложность коммуникации

• Неинтерактивное развёртывание: O(tMN)
• Развёртывание, устойчивое к сговору: O(tkMN), 5 раундов коммуникации

Проверка корректности

• Теоретическая вероятность отказа: 2⁻⁴⁰
• Экспериментальная проверка: При 10⁷ испытаниях фактическое количество отказов значительно ниже теоретической границы
• Оптимизация количества таблиц: Оптимизировано с теоретических 28 таблиц до практических 20 таблиц

Связанные работы

Решения OT-MP-PSI

1. Kissner и Song 26: Первое решение, использующее полиномиальные кольца, сложность O(N³M³)
2. Mahdavi et al. 34: Постоянное количество раундов, сложность O(M(N logM/t)²ᵗ)
3. Ma et al. 33: Применимо к малым входным множествам и малым полям, сложность O(N|S|)

Связанные проблемы

• Приватный поиск пересечений множеств с пороговым значением (TPSI): Изучение пересечения тогда и только тогда, когда размер пересечения превышает порог
• Quorum-PSI: Частный случай OT-MP-PSI, где только определённые участники имеют выходные данные

Методы хеширования

• Хеширование с кукушкой: Используется для избежания коллизий хеширования, широко применяется в протоколах PSI
• Двумерное хеширование с кукушкой: Разработано для двусторонних PSI, достигает сложности O(M)

Заключение и обсуждение

Основные выводы

1. Прорыв в практичности: Впервые сделано OT-MP-PSI практически осуществимым на масштабах реальных сетевых журналов
2. Повышение эффективности: Новая схема хеширования обеспечивает производительность на несколько порядков выше
3. Гибкое развёртывание: Предусмотрены два варианта развёртывания, адаптированные к различным требованиям безопасности
4. Практическая проверка: Протокол проверен в реальной многоорганизационной сетевой среде

Ограничения

1. Модель полусчестной безопасности: Хотя может быть расширена на модель враждебных действий, остаётся уязвимой к атакам на замену входных данных
2. Утечка размера множества: Основной протокол не рассматривает размер множества участников как приватную информацию
3. Доверие к агрегатору: Неинтерактивное развёртывание требует доверия к агрегатору, что он не будет сговариваться с участниками
4. Ограничения порога: Когда t близко к N/2 и N велико, преимущество в сложности может быть незначительным

Направления будущих исследований

1. Безопасность против враждебных действий: Расширение протокола для защиты от активных злоумышленников
2. Динамические пороги: Поддержка вычисления нескольких пороговых значений без дополнительных затрат на клиентской стороне
3. Оптимизация в большом масштабе: Дальнейшая оптимизация обработки комбинаций участников
4. Повышение конфиденциальности: Исследование методов дифференциальной приватности для защиты информации о размере множества

Глубокая оценка

Преимущества

1. Значительный теоретический вклад: Новая схема хеширования представляет собой важный прорыв в существующих технологиях, снижая экспоненциальную сложность до линейной
2. Высокая практическая ценность: Решает ключевую проблему конфиденциальности в совместном обнаружении вторжений в реальном мире
3. Достаточные эксперименты: Включает как теоретический анализ, так и проверку на реальных данных, с разумной экспериментальной установкой
4. Полная инженерная реализация: Предоставляет открытую реализацию, повышая воспроизводимость
5. Строгая безопасность: Предоставляет формальные доказательства безопасности и два варианта развёртывания

Недостатки

1. Ограничения модели безопасности: Модель полусчестной безопасности может быть недостаточно сильной в некоторых практических сценариях
2. Выбор параметров: Выбор 20 таблиц основан на эмпирической оптимизации, теоретическое руководство недостаточно
3. Границы масштабируемости: Применимость к экстремально большим масштабам (например, на уровне глобального интернета) недостаточно изучена
4. Ограниченные базы сравнения: Основное сравнение проводится с одним базовым методом, отсутствует более полное сравнение производительности

Влияние

1. Академическая ценность: Предоставляет новый технический путь для области многостороннего безопасного вычисления
2. Практическое значение: Непосредственно решает реальные потребности в области сетевой безопасности
3. Распространение технологии: Схема хеширования может быть применима к другим проблемам многостороннего вычисления
4. Потенциал стандартизации: Может стать стандартным протоколом для совместного обнаружения вторжений

Применимые сценарии

1. Многоорганизационная сетевая безопасность: Совместная защита однотипных организаций, таких как университеты и больницы
2. Облачные услуги безопасности: Анализ журналов с сохранением конфиденциальности в центрах безопасности
3. Обмен информацией об угрозах: Обмен индикаторами угроз при соблюдении ограничений конфиденциальности
4. Требования соответствия: Совместная работа с данными в соответствии с нормативными требованиями GDPR и другими законами о защите приватности

Библиография

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

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