Поддающееся проверке обнаружение аномалий с использованием доказательств с нулевым разглашением
3 января 2024 г.:::информация Этот документ доступен на arxiv под лицензией CC BY-NC-SA 4.0 DEED.
Авторы:
(1) Shanshan Han & Qifan Zhang, UCI;
(2) Вэньсюань Ву, Техасский университет A&M;
(3) Baturalp Buyukates, Yuhang Yao & Weizhao Jin, USC;
(4) Салман Авестимер, USC & ФедМЛ.
:::
Таблица ссылок
Предлагаемое двухэтапное обнаружение аномалий
Проверяемое обнаружение аномалий с использованием ZKP
4 ПРОВЕРЯЕМОЕ ОБНАРУЖЕНИЕ АНОМАЛИЙ С ИСПОЛЬЗОВАНИЕМ ZKP
Существуют различные типы схем ЗКП. В этой статье мы используем краткие неинтерактивные аргументы знания с нулевым разглашением (zkSNARKs) для проверки обнаружения аномалий. zkSNARKS предлагает постоянный размер доказательства, а также постоянное время проверки независимо от объема вычислений. Это свойство имеет решающее значение для приложений, где ресурс верификатора (клиента) ограничен. Подробности реализации отложены до раздела B.
Язык, совместимый с ZKP. Первой задачей применения протоколов ZKP является преобразование вычислений в ZKP-совместимый язык. Протоколы ZKP моделируют вычисления как арифметические схемы с элементами сложения и умножения над простым полем. Однако наши расчеты по обнаружению аномалий основаны на реальных числах. Вторая проблема заключается в том, что некоторые вычисления, такие как извлечение квадратного корня, являются нелинейными, что затрудняет их соединение в виде схемы. Чтобы решить эти проблемы, мы реализуем класс операций, которые сопоставляют действительные числа с числами с фиксированной точкой. Для построения нашей схемы ZKP мы используем библиотеку circom (Circom Contributors, 2022). который может скомпилировать описание арифметической схемы на интерфейсном языке, похожем на C++, во внутренний протокол ZKP.
ZKP для обнаружения аномалий. Большинство вычислений в алгоритме 2 и алгоритме 3 являются линейными, и их можно легко скомпилировать в арифметическую схему. Например, для вычисления косинусного сходства между двумя матрицами размера n × n требуется схема с элементами умножения O(n 2 ) и одним делением. Хотя непосредственно вычислить деление на схеме сложно, это можно легко проверить с помощью доказывающего устройства, заранее вычислившего частное и остаток. Мы можем использовать эту идею и применить алгоритм Фрейвалдса (Freivalds, 1977) для проверки умножения матриц.
Умножение матриц составляет основу схем проверки, используемых для обнаружения аномалий. Простая проверка матричного умножения AB = C, где A, B, C имеют размер n×n, требует пошагового подтверждения вычислений, для чего требуется O(n 3 ) элементов умножения. При использовании алгоритма Фрейвальдса доказывающая программа сначала вычисляет результат вне схемы и фиксирует его. Затем верификатор генерирует случайный вектор v длины n и проверяет A(Bv) ?= Cv. Этот подход уменьшает размер схемы до O(n 2 ). Мы используем эту идею повторной проверки вычислений для разработки эффективного протокола
квадратный корень, который используется в алгоритме 3. Чтобы убедиться, что x = √y вычислено правильно, мы просим доказывающего предоставить ответ x в качестве свидетеля и проверить в ZKP, действительно ли x является квадратным корнем из y. Обратите внимание, что мы не можем проверить, что x 2 равен y, поскольку zkSNARK работает с простым полем, и квадратный корень входного числа может не существовать. Поэтому мы проверяем, близко ли x 2 к y, проверяя, что x 2 ≤ y и (x + 1)2 ≥ y. Этот подход сводит вычисление квадратного корня к 2 умножениям и 2 сравнениям.
Оригинал