- Квантовая локальная дифференциальная конфиденциальность и модель квантовых статистических запросов (arXiv)
Автор: Армандо Ангрисани, Эльхам Кашефи
Аннотация:Проблема частного обучения широко изучалась в классической компьютерной науке. Примечательно, что была показана поразительная эквивалентность между локальным дифференцированным частным обучением и обучением на основе статистических запросов. Кроме того, модель статистических запросов недавно была расширена до квантовых вычислений. В этой работе мы даем формальное определение квантовой локальной дифференциальной конфиденциальности и распространяем вышеупомянутый результат на квантовые вычисления.
2. IHOP: Улучшенное восстановление статистических запросов против симметричного шифрования с возможностью поиска посредством квадратичной оптимизации (arXiv)
Автор:Саймон Ойя, Флориан Кершбаум
Аннотация. Эффективные атаки с восстановлением запросов против схем симметричного шифрования с возможностью поиска (SSE) обычно основаны на вспомогательной достоверной информации о запросах или наборах данных. Восстановление запроса также возможно при более слабом допущении статистической вспомогательной информации, хотя атаки, основанные на статистике, достигают меньшей точности и не считаются серьезной угрозой. В этой работе мы представляем IHOP, основанную на статистике атаку восстановления запроса, которая формулирует восстановление запроса как задачу квадратичной оптимизации и достигает решения путем итерации задач линейного назначения. Мы проводим расширенную оценку с пятью реальными наборами данных и показываем, что IHOP превосходит все другие атаки с восстановлением запросов на основе статистики при различных конфигурациях параметров и утечек, включая случай, когда клиент использует некоторые средства защиты от обфускации шаблонов доступа. В некоторых случаях наша атака достигает почти идеальной точности восстановления запроса. Наконец, мы используем IHOP в настройке утечки только по частоте, когда запросы клиента коррелированы, и показываем, что наша атака может использовать зависимости запросов, даже когда применяется PANCAKE, недавняя защита от сокрытия частоты, разработанная Граббсом и др.. Наши результаты показывают, что атаки с восстановлением статистических запросов представляют серьезную угрозу для схем SSE, сохраняющих конфиденциальность.
3. Статистическая сложность запроса оценки многообразия (arXiv)
Автор: Эдди Амари, Александр Кноп
Аннотация: в этой статье изучается сложность статистического запроса (SQ) для оценки d-мерных подмногообразий в Rn. Мы предлагаем чисто геометрический алгоритм под названием «Распространение по многообразию», который сводит задачу к трем естественным геометрическим процедурам: проекция, оценка касательного пространства и обнаружение точки. Затем мы предоставляем конструкции этих геометрических процедур в рамках SQ. Учитывая состязательный оракул STAT(τ) и целевую точность расстояния Хаусдорфа ε=Ω(τ2/(d+1)), результирующий алгоритм реконструкции многообразия SQ имеет сложность запроса O(npolylog(n)ε−d/2), что оказывается почти оптимальным. В процессе мы устанавливаем результаты завершения матриц низкого ранга для SQ и нижние границы для рандомизированных оценок SQ в общих метрических пространствах.
4. Нижние границы статистического запроса для Tensor PCA(arXiv)
Автор: Ришаб Дудеджа, Даниэль Хсу
Аннотация: в проблеме Tensor PCA, представленной Ричардом и Монтанари (2014), дается набор данных, состоящий из nsвыборок T1:n i.i.d. Гауссовы тензоры порядка k с обещанием, что ET1 является тензором ранга 1 и ∥ET1∥=1. Цель состоит в том, чтобы оценить ET1. Эта проблема демонстрирует большую предполагаемую сложную фазу, когда k > 2: Когда d ≲ n ≪ dk2, теоретически возможно оценить ET1, но полиномиальная оценка времени неизвестна. Мы предоставляем четкий анализ оптимальной сложности выборки в модели статистического запроса (SQ) и показываем, что алгоритмы SQ с полиномиальной сложностью запроса не только не могут решить Tensor PCA в предполагаемой жесткой фазе, но также имеют строго субоптимальную сложность выборки. по сравнению с некоторыми полиномиальными оценщиками времени, такими как спектральная оценка Ричарда-Монтанари. Наш анализ показывает, что оптимальная сложность выборки в модели SQ зависит от того, является ли ET1 симметричным или нет. Для симметричных тензоров четного порядка мы также выделяем режим размера выборки, в котором можно проверить, является ли ET1 = 0 или ET1 ≠ 0 с полиномиальным количеством запросов, но не оценить ET1. Наши доказательства основаны на аналитическом подходе Фурье Фельдмана, Перкинса и Вемпалы (2018) для доказательства точных нижних оценок SQ.
