This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. Authors: (1) Shanshan Han & Qifan Zhang, UCI; (2) Wenxuan Wu, Texas A&M University; (3) Baturalp Buyukates, Yuhang Yao & Weizhao Jin, USC; (4) Salman Avestimehr, USC & FedML. Table of Links Abstract and Introduction Problem Setting The Proposed Two-Stages Anomaly Detection Verifiable Anomaly Detection using ZKP Evaluations Related Works Conclusion & References 4 VERIFIABLE ANOMALY DETECTION USING ZKP There exists various type of ZKP schemes. In this ppaer, we utilize zero-knowledge Succinct Noninteractive Arguments of Knowledge (zkSNARKs) to verify anomaly detection. zkSNARKS offers constant proof size as well as constant verification time regardless of the size of the computation. This property is crucial for applications where verifier’s (client) resource is limited. Details of implementations are deferred to Section B. The first challenge of applying ZKP protocols is to convert the computation into a ZKP-compatible language. ZKP protocols model computations as arithmetic circuits with addition and multiplication gates over a prime field. However, our computations for anomaly detection are over real numbers. The second challenge is that some computations such as square root are nonlinear, making it difficult to wire them as a circuit. To address these issues, we implement a class of operations that map real numbers to fixed-point numbers. To build our ZKP scheme, we use circom library (Circom Contributors, 2022). which can compile the description of an arithmetic circuit in a front-end language similar to C++ to back-end ZKP protocol. ZKP-Compatible Language. Most of the computations in Algorithm 2 and Algorithm 3 are linear, which can be compiled into an arithmetic circuit easily. For instance, computing cosine similarity between two matrices of size n × n requires a circuit with O(n 2 ) multiplication gates and one division. While it is difficult to directly compute division on a circuit, it can be easily verified with prover providing the pre-computed quotient and remainder beforehand. We can utilize this idea and apply Freivalds’ algorithm (Freivalds, 1977) to verify matrix multiplication. ZKP for Anomaly Detection. Matrix multiplication constitutes the basis of the verification schemes used for anomaly detection. Naively verifying a matrix multiplication AB = C where A, B, C are of size n×n requires proving the computation step by step, which requires O(n 3 ) multiplication gates. With Freivalds’ algorithm, the prover first computes the result off-circuit and commits to it. Then, the verifier generates a random vector v of length n, and checks A(Bv) ?= Cv. This approach reduces the size of the circuit to O(n 2 ). We exploit this idea of verifying the computation again to design an efficient protocol for square-root, which is used in Algorithm 3. To verify that x = √y is computed correctly, we ask the prover to provide the answer x as witness and check in the ZKP is x is indeed the squreroot of y. Note that we cannot check x 2 is equal to y because zkSNARK works over prime field and the square root of an input number might not exist. Therefore, we check if x 2 is close to y by checking that x 2 ≤ y and (x + 1)2 ≥ y. This approach reduces the computation of squareroot to 2 multiplication and 2 comparison.

Augmentastic || Augmented Reality

Verifiable Anomaly Detection using Zero-Knowledge Proofs

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Comprehensive Look at Solar Radiation Predictions through Bayesian Hierarchical Models

The Noonification: Anomaly Detection with Privileged Information—Part 1 (12/13/2023)

The Noonification: Craig Wright is Satoshi Nakamoto (12/24/2023)

3 Types of Anomalies in Anomaly Detection

A Zero-Knowledge Anomaly Detection Approach for Robust Federated Learning

A Comprehensive Look at Solar Radiation Predictions through Bayesian Hierarchical Models

The Noonification: Anomaly Detection with Privileged Information—Part 1 (12/13/2023)

The Noonification: Craig Wright is Satoshi Nakamoto (12/24/2023)

3 Types of Anomalies in Anomaly Detection

A Zero-Knowledge Anomaly Detection Approach for Robust Federated Learning

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps