Безопасная агрегация с несколькими сообщениями с приватностью спроса

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

• ID статьи: 2504.20639
• Название: Multi-Message Secure Aggregation with Demand Privacy
• Авторы: Chenyi Sun, Ziting Zhang, Kai Wan (Хуачжунский технологический университет), Giuseppe Caire (Технический университет Берлина)
• Классификация: cs.IT math.IT
• Дата публикации: 13 октября 2025 г. (arXiv v2)
• Ссылка на статью: https://arxiv.org/abs/2504.20639

Аннотация

В данной работе исследуется задача безопасной агрегации с несколькими сообщениями с приватностью спроса, в которой сервер стремится вычислить Kc≥1 линейных комбинаций локальных входных данных от K распределённых пользователей. Задача решает две проблемы: (1) безопасность, гарантирующая, что сервер получает только требуемые линейные комбинации без утечки дополнительной информации о входных данных пользователей; (2) приватность, предотвращающая получение пользователями информации о вычислительных задачах сервера. Кроме того, рассматривается влияние отключения пользователей, когда до K-U пользователей могут отключиться, и их личности невозможно предсказать заранее. Авторы предлагают две схемы для случаев Kc=1 и 2≤Kc<U соответственно. Для Kc=1 вводится метод мультипликативного шифрования спроса сервера с использованием случайных величин; для 2≤Kc<U используется надёжное симметричное приватное вычисление для восстановления линейных комбинаций ключей во втором раунде.

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

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

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

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

1. Потребность в многозадачном обучении: По сравнению с однозадачным обучением, многозадачное обучение может использовать несколько результатов для повышения общей производительности обучения модели, улучшая эффективность обучения через обмен информацией и ресурсами.
2. Ограничения существующих методов:
   • Существующие работы по информационно-теоретической безопасной агрегации сосредоточены в основном на случае Kc=1
   • Отсутствует защита приватности вычислительных задач сервера
   • Требуется гарантировать безопасность и приватность при отключении пользователей
3. Практические требования: В реальных сценариях федеративного обучения сервер может требовать вычисления нескольких различных линейных комбинаций, при этом пользователи не должны знать конкретные вычислительные требования сервера.

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

1. Новая формализация задачи: Впервые предложена задача безопасной агрегации с несколькими сообщениями с приватностью спроса, расширяющая область исследований традиционной безопасной агрегации.
2. Оптимальная схема (Kc=1): Предложена схема безопасной агрегации, объединяющая мультипликативное шифрование спроса и аддитивное шифрование модели, достигающая оптимальной области скоростей передачи, равной ёмкости задачи безопасной агрегации без ограничений приватности.
3. Приближённо оптимальная схема (2≤Kc<U): Используя схемы симметричного приватного вычисления, значительно улучшена базовая схема прямого повторения первого метода Kc раз, с оптимальной скоростью в первом раунде и скоростью в пределах коэффициента 2 от оптимальной во втором раунде.
4. Теоретический анализ: Предоставлены полные доказательства достижимости и анализ обратных границ, устанавливающие теоретическую основу задачи.

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

Системная модель

Участники:

• 1 сервер и K некоалиционных пользователей (K≥2)
• Пользователь i владеет входным вектором Wi и ключом Pi
• Wi содержит L независимых одинаково распределённых равномерных символов, определённых на конечном поле Fq

Целевая функция: Сервер вычисляет линейное отображение: $g(W_1, \cdots, W_K) = F[W_1, \cdots, W_K]^T$

где F — матрица коэффициентов размерности Kc×K: $F = \begin{pmatrix} a_{1,1} & \cdots & a_{1,K} \\ \vdots & \ddots & \vdots \\ a_{K_c,1} & \cdots & a_{K_c,K} \end{pmatrix}$

Модель коммуникации:

• Первый раунд: Сервер отправляет запрос Q1,i пользователю i, пользователь i отправляет сообщение Xi
• Второй раунд: Сервер информирует множество активных пользователей U1, отправляет запрос Q^{U1}_{2,i}, пользователь i отправляет Y^{U1}_i

Ограничения

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

Схема для случая Kc=1

Основная идея

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

Подробные шаги

Этап 1 (Генерация запроса):

• Сервер случайно выбирает t ∈ Fq{0}
• Определяет запрос: $Q_{1,i} = \frac{1}{ta_{1,i}}$, i ∈ K

Этап 2 (Генерация ключа):

• Для каждого пользователя i генерируется Zi, равномерно распределённый на F^L_q
• Zi разбивается на U подключей: Zim ∈ F^{L/U}_q
• Используется матрица MDS для кодирования: $[\tilde{Z}_i]_j = ([Z_i]_1, \ldots, [Z_i]_U) \cdot M_{:,j}$

Этап 3 (Передача в первом раунде):

• Пользователь i отправляет: $X_i = W_i + Q_{1,i}Z_i$

Этап 4 (Передача во втором раунде):

• Пользователь j ∈ U1 отправляет агрегированные кодированные подключи: $\sum_{i \in U_1}[\tilde{Z}_i]_j$
• Сервер восстанавливает $\sum_{i \in U_1} Z_i$ через декодирование MDS

Процесс расшифровки

Сервер вычисляет: $\sum_{i \in U_1} \frac{1}{Q_{1,i}}X_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i + \sum_{i \in U_1} Z_i$

Поскольку $t \sum_{i \in U_1} a_{1,i}W_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i$, сервер может декодировать целевую линейную комбинацию.

Схема для случая 2≤Kc<U

Основная идея

Использование надёжного симметричного приватного вычисления для гарантирования безопасности и приватности при передаче во втором раунде.

Подробные шаги

Этап 1 (Генерация ключа):

• Для каждого i ∈ K случайно выбирается Zi из F^L_q
• Все пользователи совместно используют ключ: Pi = (Zi)i∈K
• Совместно используют L/(U-1) общих случайных величин в качестве маски ключа

Этап 2 (Передача в первом раунде):

• Пользователь i отправляет: $X_i = W_i + Z_i$

Этап 3 (Передача во втором раунде):

• Сервер требует восстановить Kc линейных комбинаций ключей: $\sum_{i \in U_1} a_{n,i}Z_i$, n ∈ Kc
• Каждый ключ Zi разбивается на подключи длины L' = U-1
• Используется схема симметричного приватного вычисления Kc раз для получения каждой линейной комбинации
• Через кодирование Лагранжа конструируются полиномы запроса для защиты приватности вычислительной задачи

Экспериментальные результаты

Теоретические результаты

Теорема 3 (Оптимальность при Kc=1): Для задачи безопасной агрегации с несколькими сообщениями (K,U,Kc), когда U≤K-1 и Kc=1, область ёмкости: $\mathcal{R}^* = \{(R_1,R_2) : R_1 \geq 1, R_2 \geq \frac{1}{U}\}$

Теорема 5 (Достижимость при 2≤Kc<U): Когда 2≤Kc<U≤K-1, кортеж скоростей $(R_1 = 1, R_2 = \frac{K_c}{U-1})$ достижим.

Теорема 6 (Обратная граница): Любая достижимая скорость должна удовлетворять: $R_1 \geq 1, R_2 \geq \frac{K_c}{U}$

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

1. Оптимальность: Случай Kc=1 достигает теоретического оптимума
2. Приближённая оптимальность: При 2≤Kc<U скорость в первом раунде оптимальна, скорость во втором раунде оптимальна в пределах коэффициента 2: $\frac{K_c/(U-1)}{K_c/U} = \frac{U}{U-1} \leq 2$
3. Сравнение с базовым методом: По сравнению с методом прямого повторения новая схема снижает скорость в первом раунде с Kc до 1, скорость во втором раунде увеличивает с Kc/U до Kc/(U-1)

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

Безопасная агрегация

• Информационно-теоретическая безопасная агрегация: Zhao и Sun впервые предложили информационно-теоретическую формализацию, достигнув области ёмкости {(R1,R2) : R1≥1, R2≥1/U}
• Практическая безопасная агрегация: LightSecAgg значительно сокращает требуемое количество ключей путём разделения процесса генерации ключей

Приватный поиск информации и вычисления

• Приватный поиск информации (PIR): Позволяет серверу приватно извлекать сообщения из распределённой базы данных
• Приватное вычисление (PC): Расширяет фреймворк PIR, включая линейные вычисления над сообщениями
• Симметричное приватное вычисление: Одновременно защищает приватность вычислительной задачи сервера и безопасность данных пользователей

Многозадачное обучение

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

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

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

1. Впервые формализована задача безопасной агрегации с несколькими сообщениями с приватностью спроса
2. Для Kc=1 достигнута оптимальная область скоростей передачи
3. Для 2≤Kc<U достигнута оптимальная производительность в первом раунде и приближённо оптимальная во втором раунде
4. Предоставлена полная теоретическая основа анализа

Ограничения

1. Открытые области: Характеризация области ёмкости при Kc≥U остаётся нерешённой
2. Размер ключа: Минимизация требуемого размера ключа не оптимизирована
3. Практичность: Теоретические схемы имеют высокую сложность реализации в реальных системах
4. Масштабируемость: Ограниченная расширяемость на нелинейные вычислительные задачи

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

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

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

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

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

Недостатки

1. Ограниченная область применения: Рассматриваются только линейные вычислительные задачи, реальные приложения могут требовать нелинейные операции
2. Высокая сложность реализации: Особенно для случая 2≤Kc<U, реализация симметричного приватного вычисления довольно сложна
3. Ограничения параметров: Требование Kc<U может быть слишком строгим в некоторых сценариях приложений
4. Отсутствие экспериментальной проверки: Недостаток практической системной реализации и тестирования производительности

Влияние

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

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

1. Федеративное обучение: Защита приватности агрегации в многозадачном федеративном обучении
2. Распределённая статистика: Системы, требующие вычисления нескольких статистических величин
3. Анализ с защитой приватности: Сценарии анализа данных в финансовом, медицинском и других секторах с высокими требованиями к приватности

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

Статья ссылается на множество важных источников, включая:

• Работы Zhao & Sun по информационно-теоретической безопасной агрегации
• Результаты Sun & Jafar по ёмкости приватного поиска информации и приватного вычисления
• Схемы Zhu и др. по симметричному приватному полиномиальному вычислению
• Классические результаты Shannon по информационно-теоретической безопасности

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