# pvCNN: Privacy-Preserving and Verifiable Convolutional Neural Network
Testing

Jiasi Weng, Jian Weng∗, , Gui Tang, Anjia Yang, Ming Li, Jia-Nan Liu J.s.
Weng, J. Weng, G. Tang, A. Yang, M. Li and J.n. Liu are with the College of
Cyber Security, Jinan University, Guangzhou 510632, China. E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Jian Weng is the corresponding author.

###### Abstract

We propose a new approach for privacy-preserving and verifiable convolutional
neural network (CNN) testing in a distrustful multi-stakeholder environment.
The approach is aimed to enable that a CNN model _developer_ convinces a
_user_ of the truthful CNN performance over non-public data from _multiple
testers_ , while respecting model and data privacy. To balance the security
and efficiency issues, we appropriately integrate three tools with the CNN
testing, including collaborative inference, homomorphic encryption (HE) and
zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK).

We start with strategically partitioning a CNN model into a private part kept
locally by the model developer, and a public part outsourced to an outside
server. Then, the private part runs over the HE-protected test data sent by a
tester, and transmits its outputs to the public part for accomplishing
subsequent computations of the CNN testing. Second, the correctness of the
above CNN testing is enforced by generating zk-SNARK based proofs, with an
emphasis on optimizing proving overhead for two-dimensional (2-D) convolution
operations, since the operations dominate the performance bottleneck during
generating proofs. We specifically present a new quadratic matrix program
(QMP)-based arithmetic circuit with _a single multiplication gate_ for
expressing 2-D convolution operations between multiple filters and inputs in a
batch manner. Third, we aggregate multiple proofs with respect to a same CNN
model but different testers’ test data (_i.e._ , different statements) into
one proof, and ensure that the validity of the aggregated proof implies the
validity of the original multiple proofs. Lastly, our experimental results
demonstrate that our QMP-based zk-SNARK performs nearly $13.9\times$ faster
than the existing QAP-based zk-SNARK in proving time, and $17.6\times$ faster
in Setup time, for high-dimension matrix multiplication. Besides, the
limitation on handling a bounded number of multiplications of QAP-based zk-
SNARK is relieved.

##  I INTRODUCTION

Convolutional neural networks (CNNs) [1, 2] have been widely applied in
various application scenarios, such as healthcare analysis, autonomous vehicle
and face recognition. But real-life reports demonstrate that neural networks
often exhibit erroneous decisions, leading to disastrous consequences, _e.g._
, self-driving crash due to the failure of identifying unexpected driving
environments [3], and prejudice due to racial biases embedded in face
recognition systems [4]. The reports emphasize that when applying CNN models
in security-critical scenarios, model users should be sufficiently cautious of
benchmarking the CNN models to obtain the truthful multi-faceted performance,
like robustness and fairness, not limited to natural accuracy. For example,
when a CNN model is deployed in a self-driving car for identifying camera
images, a user should be assured that the CNN model is always highly accurate,
even for perturbed images; for face recognition applications, users want to
know that the underlying CNN models can accurately recognize face images
without discrimination.

A widely adopted approach to benchmarking a CNN model is black-box testing [5,
6]. Black-box testing enables users to have a black-box access to the CNN
model, that is, feeding the model with a batch of test data and merely
observing its outputs, _e.g._ , the proportion of correct predictions. Such
approach is suitable for the setting where model users and model developers
are not the same entities. The main reasons are that the parameters of CNN
models are intellectual properties and are vulnerable to privacy attacks, such
that developers are unwilling to reveal the parameters. We are also aware that
existing excellent white-box testing approaches[7] can test CNN models in a
fine-granularity fashion using model parameters, but black-box testing is
preferred in the above setting where model parameters are inaccessible.

Starting by black-box testing, two essential issues need consideration to
probe a CNN model’s truthful and multi-faceted performance. (_i_) Black-box
testing strongly relies on the test dataset[7], which in turn requires multi-
source data support in reality. In order to support testing a model’s multi-
faceted performance, the available test dataset should be as various as
possible. One evidence is that multiple benchmarks are built by embedding
dozens of types of noises into ImageNet to measure the robustness of CNN
models[8]. Despite the necessity, building such benchmarks consumes many
manpower and multi-party efforts, even for large companies, _e.g._ , a recent
project named Crowdsourcing Adverse Test Sets for Machine Learning (CATS4ML)
launched by Google AI. Thus, the off-the-shelf test datasets for supporting
multi-faceted CNN testing are likely from multiple sources. (_ii_) Black-box
testing opens a door for untrusted model developers to cheat in testing. They
might forge untruthful outputs without correctly running the processes of CNN
testing on given test datasets. Additionally, if developers can in advance
learn a given test dataset, they might craft a CNN which typically adapts to
the test dataset, which deviates from our initial goal of testing their
truthful multi-faceted performance. From this point, test datasets cannot be
public, not merely due to that datasets themselves are privacy-sensitive in
many security-critical scenarios. Motivated by the two issues above, there
needs an approach for users to validate the correctness of the black-box CNN
testing over multi-source test datasets, in which test datasets are not public
and the CNN model is privacy-preserving.

Figure 1: Scenario example ($m_{1},m_{2}$ refer to CNN models, and
$d_{1},d_{2}$ refer to test datasets; Des means non-private descriptions for
the CNN models or test datasets).

While many awesome efforts have been done to make CNN prediction/testing
verifiable [9, 10, 11, 12, 13, 14, 15, 16] using cryptographic proof
techniques [17, 18, 19, 20, 21, 22], we still need a new design satisfying our
scenario requirements. We now clarify our scenario requirements, which cannot
be fully satisfied by the previous work (see explanation in Section II). As
shown in Fig. 1, a publicly accessible platform (in gray color), _e.g._ ,
ModelZoo[23] and Kaggle[24], can allow third-party _developers_ to advertise
their CNN models towards users for earning profits. For _users_ who will pay
for a CNN model, they have a natural concern on the CNN model’s truthful
performance, taking into account the aforementioned reports. To address the
concern, the platform can announce a crowdsourcing task to test the CNN model,
such that _testers_ participate in probing the model performance using their
test datasets. Note that both the model parameters and test datasets are not
revealed on the platform while the model architectures can be public.
Considering the presence of an untrusted CNN developer, our design empowers
him/her with a proving ability to convince a later-coming user of the truthful
CNN performance over given multi-tester test datasets, satisfying three
requirements as follows:

(a) _Public verifiability and no need of interaction._ Since the user is
later-coming and not pre-designated, proof generation and verification w.r.t
the CNN testing should not share private information between the developer
(_i.e._ , prover) and the user (_i.e._ , verifier), and thereby requiring
public verifiability. The proving ability should also be non-interactive, due
to that the CNN developer, the user and testers are not always simultaneously
online.

(b) _Privacy preservation._ During the CNN testing, model parameters should
not be exposed to users, since they may be intellectual properties for
profits, and the parameters memorize sensitive training data[25]. Also, the
test data should also be protected against the CNN developer, considering the
CNN developer might strategically craft the CNN model based on the test data.
Besides, any verifier should fail to learn private information from the final
CNN performance and proofs.

(c) _Batch proving and verification._ A CNN model usually receives test data
in batches, so it is a natural requirement to support batch operations in
proof generation. In terms of verification in our scenario, a later-coming
user has to verify multiple proofs w.r.t a single CNN model which is tested
with the multi-tester test data. Hence, enabling the user to verify multiple
proofs in a batch manner can be another desirable requirement.

###  I-A Our Designs

To satisfy the three requirements, we populate our designs by strategically
integrating fully homomorphic encryption (FHE), zero-knowledge Succinct Non-
interactive ARgument of Knowledge (zk-SNARK) and an idea of collaborative
inference [26, 27]. We adopt zk-SNARK-based proof systems, mainly due to that
the class of proof technique supports many properties like public
delegatability and public verifiability which suit our scenario involving
multiple distrustful entities. To summarize, our designs include three
components: (1) privacy-preserving CNN testing based on an FHE algorithm and
collaborative inference, (2) generating zk-SNARK proofs for the above privacy-
preserving CNN testing, with an emphasis on proposing a new quadratic matrix
programs (QMP)-based zk-SNARK for proving 2-D convolutional relations, and (3)
enabling zk-SNARK proof aggregation for verifying multiple proofs in a batch
manner.

Firstly, we start by letting a developer locally run the CNN testing process
over the FHE-protected test data from every tester. While FHE can provide
stronger data confidentiality, compared to other secure computing techniques,
such as secure multi-party computation and differential privacy [28], the
straightforward adoption is computation-expensive, nearly 4 to 5 orders slower
than computing on plaintext data. Moreover, proving overhead on encrypted data
(in ring field $\mathcal{R}_{q}$) and encoded CNN parameters (in ring field
$\mathcal{R}_{t}$) is unaffordable and impractical. We hence find a middle
point by introducing a strategy of collaborative inference, so as to balance
privacy and efficiency. Particularly, the CNN developer can split his CNN
model into two parts: one is private, called PriorNet, and another one is less
private, called LaterNet. Then, the developer can locally evaluate PriorNet on
the FHE-protected test data, and delegate LaterNet to the computation-powerful
cloud for accomplishing the subsequent computation by feeding it with the
plaintext outputs of PriorNet. Next, due to that the plaintext outputs of
PriorNet might be susceptible to model inversion attacks [26] by a malicious
cloud, an off-the-shelf and generic adversarial training strategy [27] is able
to protect the PriorNet’s outputs against the attacks.

The second step is to prove the correctness of the above splitting CNN testing
on FHE-encrypted test data (_i.e._ , polynomial ring elements). We concretely
adopt a proving roadmap recently proposed by Fiore _et al._[21], in which Step
1 is to prove the simultaneous evaluation of multiple polynomial ring elements
in the same randomly selected point (for PriorNet), and Step 2 is to prove the
satisfiability of quadratic arithmetic program (QAP)-based arithmetic circuits
(for PriorNet and LaterNet) whose inputs and outputs are committed.

But we do not directly apply Step 2 into our case, since the direct adoption
causes high proving and storage overhead due to a large number of
multiplication gates for handling convolutional relations[11]. We thus present
a new method to reduce the number of multiplication gates during proof
generation, for improving the proving time of the convolutional relations. At
first, we represent the 2-D convolution operations between $M$ filters which
are $m\times m$ matrices and $Mn^{2}$ test inputs which are $n\times n$
matrices into _a single matrix multiplication (MM)_ computation. The MM
computation is conducted between a $Mn^{2}\times Mn^{2}$ filter matrix which
is strategically assigned with the $M$ filters and zeros as padding for
operation correctness, and another $Mn^{2}\times Mn^{2}$ input matrix which is
assigned with the $Mn^{2}$ test inputs. After that, we start from QAP-based
zk-SNARK and present a new QMP formula[29]. We then express the above single
MM computation as a circuit over $Mn^{2}\times Mn^{2}$ matrices _by only one-
degree QMP_. As a result, the number of multiplication gates always is $1$ and
the proving time linearly increases by the matrix dimension, _i.e._ ,
$Mn^{2}\times Mn^{2}$. With the effort, we prove the satisfiability of the
QMP-based circuits via checking the divisibility in randomly selected point of
the set of matrix polynomials of the QMP. Note that there are heterogeneous
operations in each neural network layer during CNN testing. We express the
convolution and full connection operations as QMP-based circuits, while
expressing the activation and max pooling functions as QAP-based circuits, and
then separately generate specialized proofs for them. Furthermore, we add
_commit-and-prove_ (CaP) components based on LegoSNARK [20] for gluing the
separately generated specialized proofs, aiming to prove that the current
layer indeed takes as inputs the previous layer’s outputs.

Thirdly, we enable batch verification via proof aggregation, and only a single
proof is generated for a CNN model tested by multi-tester inputs. We aggregate
multiple proofs with regard to the same CNN but different test inputs from
multiple testers based on Snarkpack[30]. We note that the aggregation
computation and proof validation can be delegated to computation-powerful
parties in a competition manner, _e.g._ , decentralized nodes who run a secure
consensus protocol to maintain the publicly accessible platform previously
described in Fig. 1. The validation result will be elected according to the
consensus protocol, and then uploaded to the public platform and attached to
the corresponding CNN model. To the end, a future user who is interested in
the CNN model can enjoy a lightweight verification by merely checking the
validation result, via browsing the platform.

###  I-B Contribution

In summary, this work makes the following contributions:

  * •

We generate zk-SNARK proofs for the CNN testing based on FHE and collaborative
inference, which protects both of the model and data privacy and ensures the
integrity.

  * •

We present a new QMP-based arithmetic circuit to express convolutional
relations for efficiency improvement.

  * •

We aggregate multiple proofs respective to a same CNN model and different
testers’ inputs for reducing the entire verification cost.

  * •

We give a proof-of-concept implementation, and the experimental results
demonstrate that our QMP-based method for matrix multiplication performs about
$17.6\times$ faster than the existing QAP-based method in Setup time, and
$13.9\times$ faster in proving time. The code is available at
https://github.com/muclover/pvCNN.

###  I-C Organization

In Section II, we revisit related work. In Section III, we introduce intrinsic
preliminaries. Section IV elaborates the scenario problem this work is
concerned about. Section V presents our solutions with customized proof
designs. In Section VI and Section VII, we show the security analysis and
experimental results, respectively.

##  II RELATED WORK

TABLE I: Comparison of verifiable CNN prediction/testing schemes. Consider
applying a two-dimensional (2-D) convolution to a filter matrix of $m\times m$
and a test data matrix of $n\times n$. The column of Proving Time is for such
2-D convolutions on $M$ filter matrices and $Mn^{2}$ test data matrices (under
plaintext). For simplicity, we note $M>m$ and the channel number of test data
is $1$. Herein, the requirements include (a) public verifiability and no need
of interaction, (b) privacy preservation of data and model and (c) batch
proving and verification, respectively. See concrete description in Section I.

Schemes | Requirement | Proving Time
---|---|---
(a) | (b) | (c)
SafetyNets[9] |  |  |  | $O(M\cdot Mn^{2}\cdot(n^{2}\cdot m^{2}))$
Keuffer’s[13] |  |  |  | $O(M\cdot Mn^{2}\cdot(n^{2}\cdot m^{2}))$
SafeTPU[10] |  |  |  | $O(M\cdot Mn^{2}\cdot(n^{2}\cdot m^{2}\cdot\frac{m^{2}}{n^{2}}))$
Madi’s[15] |  |  |  | $O(M\cdot Mn^{2}\cdot(n^{2}\cdot m^{2}))$
vCNN[11] |  |  |  | $O(M\cdot Mn^{2}\cdot(n^{2}+m^{2}))$
VeriML[14] |  |  |  | $O(M\cdot Mn^{2}\cdot(n^{2}\cdot m^{2}))$
ZEN[12] |  |  |  | $O(M\cdot Mn^{2}\cdot(n^{2}\cdot m^{2}\cdot\frac{1}{\textsf{fac}}))$
zkCNN[16] |  |  |  | $O(M\cdot Mn^{2}\cdot(n^{2}+m^{2}))$
Ours |  |  |  | $O(Mn^{2}\cdot Mn^{2})$

  * •

denotes the requirement is not satisfied;  denotes the scheme partially
supports the requirement;  denotes the scheme fully supports the requirement.
Besides, fac depends on the real size of filters. ZEN’s optimization method
may not be effective for small filters. See Table 4 in [12].

Verifiable CNN Prediction/Testing. Many prior schemes [9, 10, 11, 12, 13, 14,
15, 16] fail to fully satisfy our requirements, as summarized in TABLE I. The
previous schemes can be roughly classified into two major groups, according to
their underlying cryptographic proof techniques, such as Sum-Check like
protocols [17, 31, 32] and Groth16 zk-SNARK-based systems [18, 19, 20, 21,
22]. Based on the underlying techniques, some schemes clearly elaborate how
they support privately verifiable and interactive proofs[9, 10, 15]; some
schemes support partial privacy protection[15, 11, 12]. A few schemes [33, 34]
do not consider CNN. In addition, other promising directions are designing
efficient and memory-scalable proof protocol to support complicated neural
network inference [35], and using clever verification methods to convert any
semi-honest secure inference into a malicious secure one [36], when entities
are allowed to be simultaneously online.

We next differentiate this paper from previous schemes in terms of our
requirements.  _Regarding requirement (a)._ We adopt a class of zk-SNARK proof
systems that provide public delegatability and public verifiability, which is
suitable to our scenario. We depart from previous schemes like SafetyNets,
SafeTPU and Madi et al.’s work, since they generally need not the properties.
Compared to the line of Groth16 zk-SNARK-based schemes [11, 12, 13, 14], we
make new contributions considering the following requirements (b) and (c).
_Regarding requirement (b)._ We protect data and model privacy by enabling CNN
inference on encrypted test data while ensuring the correctness of the result.
Specifically, we protect the test data from the entity who runs the CNN
inference, preserve the model privacy from the entity who provides the test
data, and prevent any verifier who checks the result correctness from learning
private information either of the test data or of the model. Most existing
work protects the privacy either of model or of test data, which depends on
which one is treated as the witnesses on the side of a prover. For example,
Keuffer’s [13], vCNN [11] and zkCNN [16] treat model parameters as the
witnesses to be proven, while in ZEN [12], test data is witness and model
parameters should be shared between a prover and a verifier. Although Madi’s
[15] provides privacy protection on the both sides, by leveraging homomorphic
encryption and homomorphic message authenticator, the work requires a
designated verifier. As requirement (a) mentioned, our work considers a non-
designated verifier, since each user as a verifier is not designated in
advance. _Regarding requirement (c)._ We improve the proving time for handling
2-D convolutional operations on batches of filters and test data, as well as
aggregate multiple proofs for reducing verification cost. In terms of proving
time, Keuffer’s and VeriML directly apply the Groth16 zk-SNARK [18] to the 2-D
convolutional operation between each filter and each input, resulting in
$O(n^{2}\cdot m^{2})$ proving time. For such convolutional operation, vCNN
reduces the proving time to $O(n^{2}+m^{2})$ by firstly transforming the
original convolutional representations of a sum of products into a product of
sums representations, and then employing the quadratic polynomial program
(QPP) in the original QAP-based zk-SNARK. ZEN also makes effort to reduce the
proving time by reducing the number of constraints in the underlying zk-SNARK
system based on a new stranded encoding method. Essentially, ZEN’s encoding
method can be complementary to other zk-SNARK-based applications, including
ours, when encoding the original numbers into finite field elements. _Despite
the effort, they do not consider the batch case as we previously described.
When handling convolutional operations between $M$ filters and $Mn^{2}$ input
data, we have $O(Mn^{2}\cdot Mn^{2})$ proving complexity. It derives from our
two-step effort: first, we strategically represent the $M$ filters into a
matrix of $Mn^{2}\times Mn^{2}$ and meanwhile reshape the $Mn^{2}$ inputs into
another matrix; second, we employ a new quadratic matrix program (QMP) in the
QAP-based zk-SNARK, making proving time depend on the dimension of matrices,
_i.e._ , $Mn^{2}\times Mn^{2}$. Besides, the previous work does not consider
proof aggregation as our work._

Secure Outsourced ML Inference. Our work delegates partial computation of CNN
inference to a strong but untrusted server, which relates to a long line of
work about secure outsourced ML inference. One of most relevant work starts
from CryptoNets, enabling CNN inference on FHE-encrypted data. CryptoNets [37]
inspires many follow-up schemes [38, 39, 40, 41, 42, 36] that aim to improve
accuracy, communication or computational efficiency by carefully leveraging
cryptographic primitives, other than FHE [37, 43]. For example, Huang _et al._
[42] achieve efficient and accurate CNN feature extraction using a secret
sharing-based encryption technique, which avoids approximating the ReLU
function with a low-degree polynomial that is needed by CryptoNets, and
thereby ensures accuracy. However, the integrity of outsourced computation is
out of the consideration of the above schemes. Similarly targeted at the
scenario of privacy-preserving outsourced computation, another line of work
studies a group of toolkits, which may pave the way for achieving more complex
privacy-preserving ML. The toolkits support general operations of integer
numbers [44] and rational numbers [45], as well as enable large-scale
computation [46]; many ML-based applications usually contain such computation
characteristics.

##  III PRELIMINARIES

###  III-A CNN Prediction

We present here a prediction process of a CNN model on a step-by-step basis.
The CNN model basically contains two convolution (conv) layers and three full
connection (fc) layers in order; other layers between them include activation
(act) and max pooling or average pooling (pool) layers, and the output layer
is softmax layer. Notice, complex CNN models generally contain the above
layers. Specifically, taking as inputs a single-channel test data X which is a
$n\times n$ matrix, _e.g._ , gray-scale image, the layer-by-layer operations
are conducted sequentially:
$y_{o}=f^{o}(f^{fc}(f^{fc}(f^{pool}(f^{act}(f^{conv}(f^{pool}(f^{act}(f^{conv}(\textbf{X}))))))))),$
where $f^{o}$ is the output function which selects out the maximal value among
the values outputted by the last $f^{fc}$, determining the prediction output.

We proceed to elaborate the layer-by-layer operations in detail. Denote a
$m\times m$ weight matrix $\textbf{W}^{(k)}$ in the $k_{th}$ layer.

Convolutional Layer $f^{conv}$. Two dimensional (2-D) convolution operations
will be applied to input matrices and weight matrices (also called _filters_).
Here, we show a 2-D convolution operation applying to two matrices X and
$\textbf{W}^{(1)}$ with a $(n-m+1)\times(n-m+1)$ matrix $\textbf{Y}^{(1)}$ as
output:

$\textbf{Y}^{(1)}[i][j]=\sum_{l^{(1)}_{r}=0,l^{(1)}_{c}=0}^{m-1,m-1}\textbf{X}[i+l^{(1)}_{r}][j+l^{(1)}_{c}]\times\textbf{W}^{(1)}[l^{(1)}_{r}][l^{(1)}_{c}],$

where $i,j\in[0,n-m+1)$ and the row (resp. column) index of the weight is
$l^{(1)}_{r}$ (resp. $l^{(1)}_{c}$), and the stride size is $1$. The
subsequent $f^{conv}$ are done similarly, applying to the previous layer’s
output matrices and the weight matrices in the current layer.

Activation Layer $f^{act}$. There are two widely used activation functions,
applying to each element of the output matrices of $f^{conv}$ in layer $l$, in
order to catch non-linear relationships. Concretely, the two functions are
$f^{act}(\textbf{Y}^{(k)}[i][j])=max(\textbf{Y}^{(k)}[i][j],0)$ named ReLU
function, and
$f^{act}(\textbf{Y}^{(k)}[i][j])=\frac{1}{1+e^{-\textbf{Y}^{(k)}[i][j]}}$
named Sigmoid function.

Pooling Layer $f^{pool}$. Average pooling and max pooling are two common
pooling functions for reducing the dimension of the output matrices in certain
layer $k$. They are applied to each region covered by a $m\times m$ filter,
within each output matrix of the previous $f^{act}$ layer. Specifically,
average pooling function is done by
$(\textbf{Y}^{(k)}[0][0],...,\textbf{Y}^{(k)}[m-1][m-1])/m^{2}$, and max
pooling function is by
max($\textbf{Y}^{(k)}[0][0],...,\textbf{Y}^{(k)}[m-1][m-1]$).

Full Connection Layer $f^{fc}$. In this layer, each output matrix of the
previous layer multiplies by each weight matrix, and then add with a bias in
the current layer. We will omit the bias, for simplicity.

After executing the mentioned sequential operations, $f^{o}$ finally outputs a
label $l_{test}$ for X, which is the prediction output.

###  III-B Non-Interactive Zero-Knowledge Arguments

Non-interactive zero-knowledge (NIZK) arguments allow a prover to convince any
verifier of the validity of a statement without revealing other information.
Groth [18] proposed the most efficient zk-SNARK scheme, with small constant
size and low verification time. Our work leverages a CaP Groth16 variant to
prove arithmetic circuit satisfiability with committed inputs, parameters and
outputs. We here recall some essential preliminaries.

Bilinear Groups. We review Type-3 bilinear group ($p$, $\mathtt{G}_{1}$,
$\mathtt{G}_{2}$, $\mathtt{G}_{T}$, $e$), where $p$ is a prime, and
$\mathtt{G}_{1},\mathtt{G}_{2}$ are cyclic groups of prime order $p$. Note
that $g\in\mathtt{G}_{1}$, $h\in\mathtt{G}_{2}$ are the generators. Then,
$e:\mathtt{G}_{1}\times\mathtt{G}_{2}\rightarrow\mathtt{G}_{T}$ is a bilinear
map, that is, $e(g^{a},h^{b})=e(g,h)^{ab}$, where
$a,b\in\mathtt{Z}_{p},e(g,h)^{ab}\in\mathtt{G}_{T}$.

Arithmetic Circuits. Arithmetic circuits are the widely adopted computational
models for expressing the computation of polynomials over finite fields
$\mathtt{F}_{p}$. An arithmetic circuit is formed with a directed acyclic
graph, where each vertex of fan-in two called _gate_ is labelled by an
operation $+$ or $\times$, and each edge called _wire_ is labelled by an
operand in the finite field. Besides, there are usually two measures for the
complexity of a circuit, such as its size and depth. Specifically, the number
of wires of the circuit determines its size; the longest path from inputs to
the outputs determine its depth.

Quadratic Arithmetic Program (QAP) [47] For an arithmetic circuit with
$n_{in}$ input variables, $n_{ot}$ output variables in $\mathtt{F}_{p}$ ($p$
is a large prime) and $n_{*}$ multiplication gates, a QAP is consisting of
three sets of polynomials $\\{l_{i}(X),r_{i}(X),o_{i}(X)\\}_{i=0}^{m}$ and a
$n_{*}$-degree target polynomial $t(X)$. The QAP holds and
$(a_{0},...,a_{n_{in}},a_{m-n_{ot}+1},...,a_{m})\in\mathtt{F}_{p}^{n_{in}+n_{ot}}$
is a valid assignment for the input/output variables of the arithmetic circuit
_iff_ there is
$(a_{n_{in}+1},...,a_{m-n_{ot}})\in\mathtt{F}_{p}^{m-n_{in}-n_{ot}}$ such that
$\sum_{i=0}^{m}a_{i}l_{i}(X))\cdot\sum_{i=0}^{m}a_{i}r_{i}(X)\equiv\sum_{i=0}^{m}a_{i}o_{i}(X)\quad\text{mod}\quad
t(X).$ Herein, the size of the QAP is $m$ and the degree is $n_{*}$.

zk-SNARK. Groth16 [18] is a QAP-based zk-SNARK scheme, enabling proving the
satisifiability of QAP via conducting a divisibility check between
polynomials, which is equivalent to prove the satisifiability of the
corresponding circuits. We figure out some major notations which can pave the
way for presenting Groth16 and our design later. Concretely, we can specify
the mentioned assignment
$(a_{0},...,a_{n_{in}},a_{m-n_{ot}+1},...,a_{m})\in\mathtt{F}_{p}^{n_{in}+n_{ot}}$
as statement st to be proven, and specify ($a_{n_{in}+1},...,a_{m-n_{ot}}$)
$\in\mathtt{F}_{p}^{m-n_{in}-n_{ot}}$ as witness wt only known by a prover.
Then, we define the polynomial time computable binary relation $\mathtt{R}$
that comprises the pairs of (st, wt) satisfying the denoted QAP
$\\{\\{l_{i}(X),r_{i}(X),$ $o_{i}(X)\\}_{i\in[0,m]},t(X)\\}$. The degree of
$\\{l_{i}(X),r_{i}(X),o_{i}(X)\\}$ is lower than that of $t(X)$. If
$\mathtt{R}$ holds on (st, wt), $\mathtt{R}=1$; otherwise, $\mathtt{R}=0$.
Formally, the relation is denoted as
$\mathtt{R}=\\{(\textsf{st},\textsf{wt})\mid\textsf{st}:=(a_{0},...,a_{n_{in}},a_{m-n_{ot}+1},...,a_{m}),\textsf{wt}:=(a_{n_{in}+1},...,a_{m-n_{ot}}).$
Associated to the relation $\mathtt{R}$, we denote that language $\mathtt{L}$
contains the statements that the corresponding witnesses exist in
$\mathtt{R}$, that is,
$\mathtt{L}=\\{\textsf{st}\mid\exists\textsf{wt}~{}\text{s.t.}~{}\mathtt{R}(\textsf{st},\textsf{wt})=1\\}$.

Based on the above notations, we are proceeding to review the definition of a
zk-SNARK scheme for the relation $\mathtt{R}$. Specifically, a zk-SNARK scheme
is consisting of a quadruple of probabilistic polynomial time (PPT) algorithms
(Setup, Prove, Verify, Sim), which satisfies three properties:

$\underline{\textsf{Setup}(1^{\lambda},\mathtt{R})\rightarrow(\textsf{crs},\textsf{td})}$:
the Setup algorithm takes a security parameter $\lambda$ and a relation
$\mathtt{R}$ as inputs, which returns a common reference string crs and a
simulation trapdoor td.

$\underline{\textsf{Prove}(\textsf{crs},\textsf{st},\textsf{wt})\rightarrow\pi}$:
the Prove algorithm takes crs, statement st and witness wt as inputs, and
outputs an argument $\pi$.

$\underline{\textsf{Verify}(\mathtt{R},\textsf{crs},\textsf{st},\pi)\rightarrow
0/1}$: the Verify algorithm takes the relation $\mathtt{R}$, common reference
string crs, statement st and argument $\pi$ as inputs, and returns $0$ as
Reject or $1$ as Accept.

$\underline{\textsf{Sim}(\mathtt{R},\textsf{td},\textsf{st})\rightarrow\pi^{{}^{\prime}}}$:
the Sim algorithm takes the relation $\mathtt{R}$, simulation trapdoor td and
statement st as inputs, and returns an argument $\pi^{{}^{\prime}}$.

_$\cdot$ Completeness._ Given a security parameter $\lambda$,
$\forall(\textsf{st},\textsf{wt})\in\mathtt{R}$, a honest prover can convince
a honest verifier the validity of a correctly generated proof with an
overwhelming probability, that is,
$\textsf{Pr}\\{\textsf{Setup}(1^{\lambda},\mathtt{R})\rightarrow(\textsf{crs},\textsf{td}),\textsf{Prove}(\textsf{crs},\textsf{st},\textsf{wt})\rightarrow\pi|\\\
\textsf{Verify}(\mathtt{R},\textsf{crs},\textsf{st},\pi)\rightarrow
1\\}=1-\text{negl}(1^{\lambda}).$

_$\cdot$ Computational soundness._ For every computationally bounded adversary
$\mathcal{A}$, if an invalid proof is successfully verified by a honest
verifier, there exists a PPT extractor $\mathcal{E}$ who can extract wt with a
non-negligible probability, that is,
$\textsf{Pr}\\{\exists(\textsf{st},\textsf{wt})\notin\mathtt{R},\mathcal{A}(\textsf{crs},\textsf{st},\textsf{wt})\rightarrow\pi|\textsf{Verify}(\mathtt{R},\textsf{crs},\textsf{st},\pi)\rightarrow
1\\\
\wedge\mathcal{E}(\textsf{crs})\rightarrow\textsf{wt}\\}=1-\text{negl}(1^{\lambda}).$

_$\cdot$ Zero knowledge._ For every computationally bounded distinguisher
$\mathcal{D}$, there exists the Sim algorithm such that $\mathcal{D}$
successfully distinguishes a honestly generated proof from a simulation proof
with a negligible probability, that is,
$\textsf{Pr}\\{\textsf{Setup}(1^{\lambda},\mathtt{R})\rightarrow(\textsf{crs},\textsf{td}),\textsf{Prove}(\textsf{crs},\textsf{st},\textsf{wt})\rightarrow\pi,\\\
\textsf{Sim}(\mathtt{R},\textsf{td},\textsf{st})\rightarrow\pi^{{}^{\prime}}|\mathcal{D}(\pi,\pi^{{}^{\prime}})=1\\}\leq\text{negl}(1^{\lambda}).$

Commit-and-prove zk-SNARK. We particularly emphasize the capability of CaP zk-
SNARK that is useful for our scenario. The formal definition can be found in
Definition 3.1 of [20]. Essentially, the CaP capability allows a prover to
convince a verifier of ”$C_{y^{1}}$ commits to $y^{1}$ such that
$y^{1}=F_{1}(x)$ and meanwhile $y^{2}=F_{2}(y^{1})$”. Intuitively, we suppose
$C_{m}$ committed to an intermediate model $m$ of a computation and meanwhile
the model $m$ is taken as input for completing subsequent computation, that is
$m=F(x)\wedge y=G(m)$. We next explain how such capability matches the
expectation of our scenario features: (_a_) _Compression_. Before proving the
correctness of a CNN testing, the CNN developer (and testers) store
commitments to the CNN model (resp. test inputs), in which commitment is a
lightweight method to compress large-size CNN models and test inputs, and seal
them as well. (_b_) _Flexibility_. Committing to the CNN model in advance
provides the developer with certain flexibility that enables proving later-
defined statements on the previously committed CNN model, with regard to the
test inputs which are usually later-coming. (_c_) _Interoperability_. The
proofs corresponding to the process of CNN testing are generated separately
due to that a CNN model is partitioned into separate parts, so commitments to
the CNN model will provide the interoperability between the separately
generated proofs.

##  IV Problem Statement

This section firstly introduces a process of CNN collaborative inference, and
subsequently presents the scenario workflow, and lastly clarifies some
necessary threat assumptions.

###  IV-A Collaborative Inference

We take the CNN model described in Section III-A for image classification as
an example, and partition it into two parts. We choose the second convolution
layer as a split point, such that the model can be partitioned into a part
named PriorNet $F_{\textbf{M}_{1}}=f^{pool}(f^{act}(f^{conv}(\cdot)))$ and
another part named LaterNet
$F_{\textbf{M}_{2}}=f^{o}(f^{fc}(f^{fc}(f^{pool}(f^{act}(f^{conv}(\cdot))))))$.
Suppose that the chosen split point is sufficiently optimized [26] or the
model is pre-processed [27] for privacy protection, which makes the outputs of
the PriorNet not reveal private information of its input data. The choice of
the split point also depends on the model architecture. Besides, we note that
PriorNet $\textbf{M}_{1}$ will be locally evaluated and LaterNet
$\textbf{M}_{2}$ will be delegated.

Figure 2: Pipeline of PriorNet and LaterNet inference.

We now elaborate in Fig. 2 the pipeline of PriorNet and LaterNet inference
over a given test input encrypted under a tester’s public key of homomorphic
encryption. We note that the corresponding label of the test input is not
encrypted. Concretely, PriorNet is privately performed by the developer. It
takes as input an encrypted test $\textbf{X}_{et}\in\mathcal{R}_{q}$, and
produces an FHE-encrypted intermediate result
$\textbf{Y}^{(3)}_{et}\in\mathcal{R}_{q}$ as the output. Since the homomorphic
encryption cannot efficiently support the operations beyond additions and
multiplications [37, 28], the activation layer within the PriorNet is
approximated by a $2$-degree polynomial function.

Successively, $\textbf{Y}^{(3)}_{et}$’s plaintext $\textbf{Y}^{(3)}$ will be
fed into the LaterNet $F_{\textbf{M}_{2}}$ whose computations are delegated to
a service provider. We can leverage re-encryption technique to let the service
provider obtain the plaintext $\textbf{Y}^{(3)}$. Since the computations are
conducted in the clear, the later activation functions remain unchanged.
Finally, LaterNet outputs the prediction result $l_{\textsf{test}}$. The
service provider proceeds to compare the previously given true label
$l_{\textsf{truth}}$ with $l_{\textsf{test}}$, and returns an equality
indicator $0$ or $1$. For a batch of test data, he would count the number of
$1$ indicator, and return a proportion of correct prediction. For the case
using a posterior probability vector as a prediction output, we determine the
indicator value according to the distance between the prediction output and
the corresponding truth.

###  IV-B Basic Workflow

We consider four main entities— _public platform (PP)_ , _model tester (MT)_ ,
_model developer (MD)_ and _service provider (SP)_ as demonstrated in Fig. 3.

Figure 3: Scenario overview of pvCNN

Specifically, the _PP_ in real world may refer to a publicly accessible and
online platform, _e.g._ , OpenMined and DecentralizedML, which can be
maintained by a set of computational nodes. On the platform, an _MD_ is
allowed to advertise his/her pre-trained CNN model by announcing some usage
descriptions and model performance, so as to attract users of interest for
earning profits, while an _MT_ can provide test data for measuring the model
performance. In order to establish trust among the _MD_ , the _MT_ and future
users in the scenario, the pvCNN wants to enable verifiable announcements on
the public platform, that is, any future user is assured of the truthfulness
of model performance without learning any information of either model
parameters or test data. We note the _MD_ can delegate computation-consuming
tasks to the powerful _SP_.

The basic workflow around the entities is shown below: ➊  _MTs_ freely
participate in the platform and commit to the test data. They also store
encrypted test data by using a leveled FHE (L-FHE) scheme [48] on the publicly
accessible cloud. ➋ The _MD_ splits his CNN model into a private PriorNet
which is kept at local device, as well as, a public LaterNet which is sent to
the _SP_ ; After that, he generates two commitments to the PriorNet and
LaterNet, and sends them to the _PP_. ➌ The _MD_ downloads the ciphered test
data. ➍ The _MD_ evaluates the plaintext PriorNet on the encrypted test data
and generates a proof of executing the inference computation as promised. ➎
The _MD_ sends the encrypted output of the Step ➍. Note that the encrypted
output can be transformed into the ciphertext under the _SP_ ’s public key via
re-encryption. ➏ The _SP_ successively runs LaterNet inference in the clear by
taking the plaintext output of PriorNet inference as inputs, and proves that
LaterNet is executed correctly with the true inputs and meanwhile LaterNet is
consistent to the committed one. ➐ The service provider submits the final test
results (_e.g.,_ classification correctness rate) to the platform, and
distributes proofs to the decentralized nodes for proofs aggregation and
validation.

###  IV-C Threat Assumptions

Model Developers. We consider CNN developers are untrusted; they can provide
untruthful prediction results, _e.g._ , outputting meaningless predictions or
using arbitrary test data or CNN model. They can also be curious about test
data during a CNN testing. Note that our verifiable computing design does not
focus on poisoned or backdoored models[49], but it greatly relies on multi-
tester test data to probe the performance of CNN models in a black-box manner.
Recently, SecureDL[50] and VerIDeep[51] resort to sensitive samples to detect
model changes, which can be complementary to our work.

Service Providers. They can be computationally powerful entities, and accept
outsourced LaterNet from developers. Despite service providers’ powerful
capabilities on computation and storage, we do not trust them. They can try
their best to steal private information with regard to CNNs and test inputs.
They even incorrectly run LaterNet and produce untruthful or meaningless
results for saving computation and storage resources. Service providers can
also collude with a developer to fake correctness proofs, with respect to the
independent inference processes based on a splitting CNN, aiming to evade
verification by later-coming users.

Model Testers. Testers are organized via a crowdsourcing manner. We consider
that the testers are willing to contribute their test inputs for measuring the
quality of the CNNs. A tester’s test inputs concretely contain a batch of data
on an input-label basis. We assume the original inputs need protected but
their labels can be public (refer to encrypted inputs and plaintext labels in
Section IV-A). We also assume each label is consistent with the corresponding
input’s true label, considering currently popular crowdsourcing-empowered
label platforms.

Public Platform and Future Users. We assume both the public platform and
future users are honest. We note users have access to all of data uploaded to
the platform and the data on the platform cannot be tampered. But we do not
want them to obtain either model parameters or test data.

Finally, we assume that entities communicate via a secure authenticated
channel.

##  V CONCRETE DESIGN

This section will introduce how to generate publicly verifiable zk-SNARK
proofs for CNN testing based on L-FHE and collaborative inference. We will
present high-level ideas in the subsection V-A. We then illustrate the
optimization for 2-D convolutional relations in the subsection V-B. In the
subsequent subsection V-C, we generate zk-SNARK proofs for a whole CNN testing
process in a divide-and-conquer fashion, and aggregate multiple proofs in the
subsection V-D.

###  V-A High-level Ideas

On top of the scenario of testing PriorNet and LaterNet with encrypted test
data from testers, we want to generate zk-SNARK proofs for convincing any
future user that (1) the model developer correctly runs PriorNet on the
ciphered test data and returns the ciphered intermediate result as output; and
(2) the service provider exactly takes the intermediate result as input and
correctly accomplishes the successive computations of LaterNet, which produces
a correct result. Meanwhile, any future user does not learn any information
about the model parameters, the intermediate result and the test data.

Figure 4: Overview of proof generation. See the column of function, we use a
2-degree polynomial to approximate the ReLU function in the PriorNet
$F_{\textbf{M}_{1}}$.

Most importantly, we make two efforts to improve proving and verification
costs, by reducing the number of multiplication gates and compressing multiple
proofs, respectively. For ease of understanding, we firstly introduce a
roadmap of proof generation, and then particularly emphasize our two efforts
during proof generation. As shown in Fig. 4, the roadmap of generating QAP-
based zkSNARK proofs is: 1) compiling the _functions_ of the splitting CNN
testing into circuits, 2) expressing the _circuits_ as a set of QAPs, 3)
constructing the zk-SNARK proofs for the QAPs, and 4) generating _commitments_
for linking together the zk-SNARK proofs which are constructed separately.
Based on the roadmap, our main efforts include: (a) Optimizing convolutional
relations for 2) (see Section V-B). We allow matrices in constructing the QAP,
leading to quadratic matrix programs (QMP) [29], which is inspired by
vCNN[11]’s efforts of applying polynomials into QAP (QPPs, quadratic
polynomial programs [52]). Our QMP can optimize convolutional relations,
considering a convolution layer with multiple filters and inputs can be
strategically represented by a single matrix multiplication operation. The
operation of matrix multiplication then is complied into the arithmetic
circuits in QMP with only a single multiplication gate. As a consequence, the
number of multiplication gates dominating proving costs is greatly reduced,
compared to the previous case of using the original expression of QAP. (b)
Aggregating proofs for 3) (see Section V-D). We enable aggregating multiple
proofs for different statements respective to test datasets over the same
QAP/QMP for the same CNN model. The single proof after aggregation then is
validated by a secure committee and the validity result based on the majority
voting will be submitted and recorded on our public platform. In such way, any
future user only needs to check the validation result to determine whether or
not the statements over the CNN are valid.

###  V-B Optimizing Convolutional Relations

As demonstrated in Fig. 5, we consider 2-D convolution operations between
$Mn^{2}$ amount of $n\times n$ input matrices and $M$ amount of $m\times m$
convolution filters (herein, $M>n$), which produces $M^{2}n^{2}$ filtered
matrices of $(n-m+1)\times(n-m+1)$, by setting the stride $1$. Specifically,
by computing the inner products between each input matrix and each filter
matrix, $\forall i,j\in[0,n-m]$ and $k\in[0,M-1]$, it can be expressed as:
$\textbf{Y}^{k}[i][j]=\sum_{l_{r}=0,l_{c}=0}^{m-1,m-1}\textbf{X}[i+l_{r}][j+l_{c}]\times\textbf{W}^{k}[l_{r}][l_{c}].$
Obviously, the multiplication complexity of such inner product computation is
$O(n^{2}\cdot m^{2})$. Note that there are $M\cdot Mn^{2}$ amount of such set
of Y, with respect to $Mn^{2}$ inputs and $M$ filters. Thus, $O(M\cdot
Mn^{2}\cdot(n^{2}\cdot m^{2}))$ multiplication gates in QAP-based circuits are
needed for handling $Mn^{2}$ inputs and $M$ filters. Since the proving time
depends on the number of multiplication gates, a proof generation process for
2-D convolution operations becomes impractical.

Figure 5: Matrix multiplication for convolution operations. We transform the
convolution operations of $M$ weight matrices and $Mn^{2}$ input matrices
(demonstrated on the top) into the matrix multiplication operation between two
square matrices of $Mn^{2}\times Mn^{2}$ (demonstrated on the bottom).

Now, we seek for improving proving efficiency by reducing the number of
multiplication gates to $O(Mn^{2}\cdot Mn^{2})$. The very first step is to
represent the inner products between the $Mn^{2}$ inputs and $M$ filters with
_a single matrix multiplication_. Concretely, we show a concrete example of
the representation in Fig. 5. First, given $Mn^{2}$ amount of $n\times n$
input matrices $\\{\textbf{X}\\}$, they are reshaped into a square matrix
$\textbf{X}^{r}$ of $Mn^{2}\times Mn^{2}$. Second, another square matrix
$\textbf{W}^{r}$ of the same dimension can be constructed by packing the $M$
filter matrices in a moving and zero padding manner. As a result, the
multiplication between the two square matrices produces a square matrix
$\textbf{Y}^{r}$ of $Mn^{2}\times Mn^{2}$, which can also be regarded as a
reshaped matrix from the original $M\cdot Mn^{2}$ amount of output matrices.
Based on such representation, the two square matrices $\textbf{W}^{r}$ and
$\textbf{X}^{r}$ of the matrix multiplication can later be the left and right
inputs of an arithmetic circuit with only one multiplication gate. We proceed
to express the above circuit with our new QMP by using matrices in QAP, which
follows the similar principle of using polynomials in QAP [52].

QMP Definition [29]. For an arithmetic circuit with $n_{in}$ input variables,
$n_{ot}$ output variables in $\textbf{M}_{(\mathtt{F}_{p})}^{s\times s}$ and
$n_{*}$ multiplication gates, a QMP is consisting of three sets of polynomials
$\\{L_{i}(x),R_{i}(x),O_{i}(x)\\}_{i=0}^{m}$ with coefficients in
$\textbf{M}_{(\mathtt{F}_{p})}^{s\times s}$ and a $n_{*}$-degree target
polynomial $t(x)\in\mathtt{F}_{p}[x]$. $\mathtt{F}_{p}$ is a large finite
field, _e.g._ , $2^{254}$. The QMP computes the arithmetic circuit and
$(\textbf{A}_{0},...,\textbf{A}_{n_{in}},\textbf{A}_{m-n_{ot}+1},...,\textbf{A}_{m})\in\textbf{M}_{(\mathtt{F}_{p})}^{s\times
s}$ is valid assignment for the $n_{in}+n_{ot}$ input/output variables _iff_
there exists $m-n_{in}-n_{ot}$ coefficients
$(\textbf{A}_{n_{in}+1},...,\textbf{A}_{m-n_{ot}})\in\textbf{M}_{(\mathtt{F}_{p})}^{s\times
s}$ for arbitrary $\textbf{X}\in\textbf{M}_{(\mathtt{F}_{p})}^{s\times s}$
such that $t(x)$ divides
$p(x,\textbf{X})=\textsf{tr}\\{\textbf{X}^{T}\sum_{i=0}^{m}\textbf{A}_{i}L_{i}(x))\cdot\sum_{i=0}^{m}\textbf{A}_{i}R_{i}(x)\\}-\textsf{tr}\\{\textbf{X}^{T}\sum_{i=0}^{m}\textbf{A}_{i}O_{i}(x)\\}.$
Herein, tr means the trace of a square matrix, and the degree of the QMP is
$deg(t(x))$. We note that each wire of the arithmetic circuit is labeled by a
square matrix $\textbf{A}_{i}\in\textbf{M}_{(\mathtt{F}_{p})}^{s\times s}$.
Suppose that the arithmetic circuit contains $n_{*}$ multiplication gates, and
then $t(x)=\prod_{r=0}^{n_{*}-1}t(x-x_{r})$. With regard to a multiplication
gate $x_{r}$, its left input wire is labeled by
$\sum_{i=0}^{m}\textbf{A}_{i}L_{i}(x_{r}))$, right input wire is labeled by
$\sum_{i=0}^{m}\textbf{A}_{i}R_{i}(x_{r}))$, and the output wire is
$\sum_{i=0}^{m}\textbf{A}_{i}O_{i}(x_{r}))$. We note that the multiplication
gate is constrained by
$\textsf{tr}\\{\textbf{X}^{T}\sum_{i=0}^{m}\textbf{A}_{i}L_{i}(x_{r}))\cdot\sum_{i=0}^{m}\textbf{A}_{i}R_{i}(x_{r})\\}=\textsf{tr}\\{\textbf{X}^{T}\sum_{i=0}^{m}\textbf{A}_{i}O_{i}(x_{r})\\}.$

Part 1: Layer-wise prediction correctness for PriorNet. Step 1: to prove that
the prover knows the openings of the commitments in
$\textsf{st}_{\textsf{PN}}^{S1}$
$\mathtt{R}_{\textsf{PN}}^{S1}:=\big{\\{}(\textsf{st}_{\textsf{PN}}^{S1}=(C_{\textsf{L}_{1}},C_{\textbf{X}},C_{\textsf{PN}}^{inter},\underline{C_{\textsf{L}_{1},k},C_{\textsf{L}_{2},k},C_{\textsf{L}_{3},k}},k,{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{\textsf{S1}},ck_{\textsf{PN}}}),\textsf{wt}_{\textsf{PN}}^{S1}=(\textbf{W}_{ed}^{r(1)},\textbf{X}_{et}^{r(1)},\textbf{Y}_{et}^{r(1)},\textbf{Y}_{et}^{r(2)},\textbf{Y}_{et}^{r(3)},\underline{\textbf{W}_{ed,k}^{r(1)},\textbf{X}_{et,k}^{r(1)},\textbf{Y}_{et,k}^{r(1)},\textbf{Y}_{et,k}^{r(2)},\textbf{Y}_{et,k}^{r(3)}},\mathbf{r}_{\textsf{PN}})\mid$
$\textbf{W}_{ed,k}^{r(1)}=\textbf{W}_{ed}^{r(1)}(k)\wedge\textbf{X}_{et,k}^{r(1)}=\textbf{X}_{et}^{r(1)}(k)\wedge\textbf{Y}_{et,k}^{r(1)}=\textbf{Y}_{et}^{r(1)}(k)\wedge\textbf{Y}_{et,k}^{r(2)}=\textbf{Y}_{et}^{r(2)}(k)\wedge\textbf{Y}_{et,k}^{r(3)}=\textbf{Y}_{et}^{r(3)}(k)$
$\wedge
C_{\textsf{L}_{1}}=\textsf{MPoly.Com}(\textbf{W}_{ed}^{r(1)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{\textsf{S1}}},\mathbf{r}_{\textsf{PN}})\wedge
C_{\textbf{X}}=\textsf{MPoly.Com}(\textbf{X}_{et}^{r(1)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{\textsf{S1}}},\mathbf{r}_{\textsf{PN}})\wedge
C_{\textsf{PN}}^{inter}=\textsf{MPoly.Com}(\textbf{Y}_{et}^{r(1)},\textbf{Y}_{et}^{r(2)},\textbf{Y}_{et}^{r(3)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{PN}}},\mathbf{r}_{\textsf{PN}})$
$\wedge\underline{C_{\textsf{L}_{1},k}=\textsf{MPoly.Com}(\textbf{W}_{ed,k}^{r(1)},\textbf{X}_{et,k}^{r(1)},\textbf{Y}_{et,k}^{r(1)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{PN}}},\mathbf{r}_{\textsf{PN}})}$
$\wedge\underline{C_{\textsf{L}_{2},k}=\textsf{MPoly.Com}(\textbf{Y}_{et,k}^{r(2)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{PN}}},\mathbf{r}_{\textsf{PN}})}\wedge\underline{C_{\textsf{L}_{3},k}=\textsf{MPoly.Com}(\textbf{Y}_{et,k}^{r(3)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{PN}}},\mathbf{r}_{\textsf{PN}})}\big{\\}}.$
//$ck_{\textsf{PN}}$ is the commitment key used before the evaluation while
$ck^{\textsf{S1}}$ is used during the prediction //$C_{\textbf{X}}$ commits to
$\textbf{X}_{et}^{r(1)}$ whose compression version, _e.g._ , hash of it, is
submitted to the public platform before //$C_{\textsf{L}_{1}}$ commits to the
same $\textbf{W}_{ed}^{r(1)}$ that has been committed by model owner in
advance Step 2: to prove that the equations with respect to
$\textsf{L}_{1},\textsf{L}_{2},\textsf{L}_{3}$ hold
$\mathtt{R}_{\textsf{PN}}^{S2}[\textsf{L}_{1}]:=\big{\\{}(\textsf{st}_{\textsf{PN}}^{S2}=(C_{\textsf{L}_{1},k}^{{}^{\prime}},k,{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{1}}}),\textsf{wt}_{\textsf{PN}}^{S2}=(\textbf{W}_{ed,k}^{r(1)},\textbf{X}_{et,k}^{r(1)},\textbf{Y}_{et,k}^{r(1)},\textbf{r}_{\textsf{PN}}))\mid\textbf{Y}_{et,k}^{r(1)}=\textbf{W}_{ed,k}^{r(1)}\odot\textbf{X}_{et,k}^{r(1)}\wedge~{}C_{\textsf{L}_{1},k}^{{}^{\prime}}=\textsf{MPoly.Com}(\textbf{W}_{ed,k}^{r(1)}),\textbf{X}_{et,k}^{r(1)},\textbf{Y}_{et,k}^{r(1)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{1}}},\textbf{r}_{\textsf{PN}})\big{\\}}.$
//$ck_{\textsf{L}_{1}}$ is built depending on the relation;
$C_{\textsf{L}_{1},k}^{{}^{\prime}}$ commits to the consistent
$\textbf{W}_{ed,k}^{r(1)}),\textbf{X}_{et,k}^{r(1)},\textbf{Y}_{et,k}^{r(1)}$
with the above $C_{\textsf{L}_{1},k}$
$\mathtt{R}_{\textsf{PN}}^{S2}[\textsf{L}_{2},\textsf{L}_{3}]:=\big{\\{}(\textsf{st}_{\textsf{PN}}^{S2}=(C_{\textbf{L}_{2},k}^{{}^{\prime}},C_{\textbf{L}_{2}}[\textbf{Y}_{et,k}^{r(1)}],C_{\textbf{L}_{3},k}^{{}^{\prime}},C_{\textbf{L}_{3}}[\textbf{Y}_{et,k}^{r(2)}],k,{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{2}}},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{3}}}),\textsf{wt}_{\textsf{PN}}^{S2}=(\textbf{Y}_{et,k}^{r(2)},\textbf{Y}_{et,k}^{r(3)},\mathbf{r}_{\textsf{PN}})\mid$
$\\{\textbf{Y}^{r(2)}_{et,k}[i][j]=(\textbf{Y}^{r(1)}_{et,k}[i][j])^{2}+\textbf{Y}^{r(1)}_{et,k}[i][j]\\}_{i=0,j=0}^{Mn^{2}-1,Mn^{2}-1}\wedge\textbf{Y}^{r(3)}_{et,k}=f^{\text{avg}}(\textbf{Y}^{r(2)}_{et,k})\wedge~{}C_{\textbf{L}_{2},k}^{{}^{\prime}}=\textsf{MPoly.Com}(\textbf{Y}_{et,k}^{r(2)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{2}}},\mathbf{r}_{\textsf{PN}})$
$\wedge
C_{\textbf{L}_{2}}[\textbf{Y}_{et,k}^{r(1)}]=\textsf{MPoly.Com}(\textbf{Y}_{et,k}^{r(1)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{2}}},\mathbf{r}_{\textsf{PN}})\wedge
C_{\textbf{L}_{3},k}^{{}^{\prime}}=\textsf{MPoly.Com}(\textbf{Y}_{et,k}^{r(3)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{3}}},\mathbf{r}_{\textsf{PN}})\wedge
C_{\textbf{L}_{3}}[\textbf{Y}_{et,k}^{r(2)}]=\textsf{MPoly.Com}(\textbf{Y}_{et,k}^{r(2)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}3}},\mathbf{r}_{\textsf{PN}})\big{\\}}.$
//$C_{\textbf{L}_{2},k}^{{}^{\prime}}$ (and
$C_{\textbf{L}_{3},k}^{{}^{\prime}}$) commit to the same
$\textbf{Y}_{et,k}^{r(2)}$ (resp. $\textbf{Y}_{et,k}^{r(3)}$) with
$C_{\textbf{L}_{2},k}$ (resp. $C_{\textbf{L}_{3},k}$)
//$C_{\textbf{L}_{2}}[\textbf{Y}_{et,k}^{r(1)}]$ should commit to the same
$\textbf{Y}_{et,k}^{r(1)}$ that $C_{\textsf{L}_{1},k}^{{}^{\prime}}$ commits
to; similarly, $C_{\textbf{L}_{3}}[\textbf{Y}_{et,k}^{r(2)}]$ should commit to
the same $\textbf{Y}_{et,k}^{r(2)}$ that $C_{\textsf{L}_{2},k}^{{}^{\prime}}$
commits to Part 2: Layer-wise prediction correctness for LaterNet.
$\mathtt{R}_{\textsf{LN}}[\textsf{L}_{4}]:=\big{\\{}(\textsf{st}_{\textsf{LN}}=(C_{\textbf{Y}^{r(3)}},C_{\textsf{L}_{4}},C_{\textbf{Y}^{r(4)}},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{4}}}),~{}\textsf{wt}_{\textsf{LN}}=(\textbf{W}^{r(4)},\textbf{Y}^{r(3)},\textbf{Y}^{r(4)},\mathbf{r}_{\textsf{LN}}))\mid\textbf{Y}^{r(4)}=\textbf{W}^{r(4)}\times\textbf{Y}^{r(3)}$
$\wedge~{}C_{\textbf{Y}^{r(3)}}=\textsf{MPoly.Com}(\textbf{Y}^{r(3)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{4}}},\mathbf{r}_{\textsf{LN}})\wedge
C_{\textsf{L}_{4}}=\textsf{MPoly.Com}(\textbf{W}^{r(4)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{4}}},\mathbf{r}_{\textsf{LN}})\wedge
C_{\textbf{Y}^{r(4)}}=\textsf{MPoly.Com}(\textbf{Y}^{r(4)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{4}}},\mathbf{r}_{\textsf{LN}})\big{\\}}.$
//$C_{\textbf{Y}^{r(3)}}$ should commit to $\textbf{Y}^{r(3)}$ whose
encryption is committed in $C_{\textsf{PN}}^{inter}$
$\mathtt{R}_{\textsf{LN}}[\textsf{L}_{5},\textsf{L}_{6}]:=\big{\\{}(\textsf{st}_{\textsf{LN}}=(C_{\textsf{L}_{5}}[\textbf{Y}^{r(4)}],C_{\textbf{Y}^{r(5)}},C_{\textsf{L}_{6}}[\textbf{Y}^{r(5)}],C_{\textbf{Y}^{r(6)}},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{5}}},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{6}}}),~{}\textsf{wt}_{\textsf{LN}}=(\textbf{Y}^{r(4)},\textbf{Y}^{r(5)},\textbf{Y}^{r(6)},\mathbf{r}_{\textsf{LN}}))\mid$
$\\{\textbf{Y}^{r(5)}[i][j]=max(\textbf{Y}^{r(4)}[i][j],0)\\}_{i=0,j=0}^{Mn^{2}-1,Mn^{2}-1}\wedge\textbf{Y}^{r(6)}=f^{\text{avg}}(\textbf{Y}^{r(5)})$
$\wedge~{}C_{\textsf{L}_{5}}[\textbf{Y}^{r(4)}]=\textsf{MPoly.Com}(\textbf{Y}^{r(4)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{5}}},\mathbf{r}_{\textsf{LN}})\wedge
C_{\textbf{Y}^{r(5)}}=\textsf{MPoly.Com}(\textbf{Y}^{r(5)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{6}}},\mathbf{r}_{\textsf{LN}})$
$\wedge
C_{\textsf{L}_{6}}[\textbf{Y}^{r(5)}]=\textsf{MPoly.Com}(\textbf{Y}^{r(5)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{6}}},\mathbf{r}_{\textsf{LN}})\wedge
C_{\textbf{Y}^{r(6)}}=\textsf{MPoly.Com}(\textbf{Y}^{r(6)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{6}}},\mathbf{r}_{\textsf{LN}})\big{\\}}.$
//$C_{\textsf{L}_{5}}[\textbf{Y}^{r(4)}]$ should commit to $\textbf{Y}^{r(4)}$
that is committed in $C_{\textbf{Y}^{r(4)}}$ of $\textsf{L}_{4}$
//$C_{\textsf{L}_{6}}[\textbf{Y}^{r(5)}]$ should commit to $\textbf{Y}^{r(5)}$
that is committed in $C_{\textbf{Y}^{r(5)}}$ of $\textsf{L}_{5}$
$\mathtt{R}_{\textsf{LN}}[\textsf{L}_{7},\textsf{L}_{8}]:=\big{\\{}(\textsf{st}_{\textsf{LN}}=(C_{\textsf{L}_{7,8}},C_{\textsf{L}_{7}}[\textbf{Y}^{r(6)}],C_{\textsf{L}_{8}}[\textbf{Y}^{r(8)}],{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{7,8}}}),~{}\textsf{wt}_{\textsf{LN}}=(\textbf{W}^{r(7)},\textbf{W}^{r(8)},\textbf{Y}^{r(6)},\textbf{Y}^{r(7)},\textbf{Y}^{r(8)},\mathbf{r}_{\textsf{LN}}))\mid$
$\textbf{Y}^{r(7)}=\textbf{Y}^{r(6)}\times\textbf{W}^{r(7)}$ $\wedge
C_{\textsf{L}_{7,8}}=\textsf{MPoly.Com}(\textbf{W}^{r(7)},\textbf{W}^{r(8)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{7,8}}},\mathbf{r}_{\textsf{LN}})\wedge
C_{\textsf{L}_{7}}[\textbf{Y}^{r(6)}]=\textsf{MPoly.Com}(\textbf{Y}^{r(6)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{7,8}}},\mathbf{r}_{\textsf{LN}})\wedge
C_{\textsf{L}_{8}}[\textbf{Y}^{r(8)}]=\textsf{MPoly.Com}(\textbf{Y}^{r(8)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{7,8}}},\mathbf{r}_{\textsf{LN}})\big{\\}}.$
//$C_{\textsf{L}_{7}}[\textbf{Y}^{r(6)}]$ should commit to $\textbf{Y}^{r(6)}$
that is committed in $C_{\textbf{Y}^{r(6)}}$ of $\textsf{L}_{6}$
$\mathtt{R}_{\textsf{LN}}[\textsf{L}_{o}]:=\big{\\{}(\textsf{st}_{\textsf{LN}}=(C_{\textsf{L}_{o}}[\textbf{Y}^{r(8)}],\textbf{l}_{test},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{o}}}),\textsf{wt}_{\textsf{LN}}=(\textbf{Y}^{r(8)}))\mid\textbf{l}_{test}[j]=\textsf{argmax}(\textbf{Y}^{r(8)}[j])\wedge~{}C_{\textsf{L}_{o}}[\textbf{Y}^{r(8)}]=\textsf{MPoly.Com}(\textbf{Y}^{r(8)},{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck_{\textsf{L}_{o}}},\mathbf{r}_{\textsf{LN}})\big{\\}}.$
//$C_{\textsf{L}_{o}}[\textbf{Y}^{r(8)}]$ should commit to $\textbf{Y}^{r(8)}$
that is committed in $C_{\textbf{Y}^{r(8)}}$ of $\textsf{L}_{8}$

Figure 6: Layer-by-layer relation definition for our splitting CNN testing.

QMP for Matrix Multiplication Relations. As we introduced before, we can
represent convolutional operations as matrix multiplication
$\textbf{Y}^{r}=\textbf{W}^{r}\times\textbf{X}^{r}$, where
$\textbf{Y}^{r},\textbf{X}^{r}$ and
$\textbf{W}^{r}\in\textbf{M}_{(\mathtt{Z}_{p})}^{Mn^{2}\times Mn^{2}}$. It is
noteworthy that we can use advanced quantization techniques to transform
floating-point numbersm of 8-bit precision into unsigned integer numbers in
[$0,255$], which adapts to a large finite field. Now according to the QMP
definition, when the matrix multiplication computation is expressed by the
arithmetic circuit over matrices, the corresponding QMP is
$\\{L_{\textbf{W}}(x),R_{\textbf{X}}(x),O_{\textbf{Y}}(x),t(x)\\}$ of the
arithmetic circuit. Herein, there are three input/output variables, and the
degree of the QMP is one.

Similarly, we can apply our above idea into full connection operations, and
finally the operations can also be expressed with similarly low-degree QMP.

###  V-C Proof Generation for a Whole CNN Testing

This section elaborates how to generate proofs based on the CaP zk-SNARK for
ensuring result correctness of executing the PriorNet and LaterNet. The proofs
convince an arbitrary user that PriorNet is correctly evaluated on the
ciphered test inputs, and subsequently, LaterNet is correctly performed by
taking the clear outputs of PriorNet as inputs, yielding correct results. We
note that the processes of proof generation for the PriorNet and LaterNet are
slightly different. For PriorNet, the values, such as weights, test inputs and
outputs, are represented as polynomial ring elements, and we follow Fiore _et
al._ ’s work [21] to generate proofs for the computation over polynomial
rings. For LaterNet, we generate zk-SNARK proofs for the computation over
scalars. We will begin with relation definition, and then present concrete
realization for generating proofs. In light of the nature of layer-by-layer
computation of model inference, we will use a divide-and-conquer method to
generate zk-SNARK proofs for each separate layer, and combine them as a whole
via a commit-and-prove methodology.

Let us define some notations at the beginning. We let MPoly.Com be a
polynomial commitment scheme from [21]. We denote $ck_{\textsf{PN}}$ and
$ck_{\textsf{LN}}$ are the commitment keys used for committing to the PriorNet
and LaterNet; $\mathbf{r}_{\textsf{PN}}$, $\mathbf{r}_{\textsf{LN}}$ are non-
reused commitment randomnesses. $C_{\textbf{M}_{1,{ed}}}$ means the
commitments to the inputs, weights, intermediates of $\textbf{M}_{1}$ while
$C_{\textbf{M}_{2}}$ represents the commitments to the weights and
intermediates of $\textbf{M}_{2}$.

Relation Definition. We define the relations $\mathtt{R}_{\textsf{PN}}$ and
$\mathtt{R}_{\textsf{LN}}$ with regard to PriorNet and LaterNet execution
correctness:

$\displaystyle\mathtt{R}_{\textsf{PN}}:=\big{\\{}(\textsf{st}_{\textsf{PN}}$
$\displaystyle=(C_{\textbf{M}_{1,{ed}}},C_{\textbf{X}_{et}^{r(1)}},\textbf{Y}^{r(3)}_{et},ck_{\textsf{PN}}),$
$\displaystyle\textsf{wt}_{\textsf{PN}}$
$\displaystyle=(\textbf{M}_{1,{ed}},\textbf{X}_{et},\mathbf{r}_{\textsf{PN}}))\mid$
$\displaystyle\textbf{Y}^{r(1)}_{et}$
$\displaystyle=\textbf{W}^{r(1)}_{ed}\odot\textbf{X}^{r(1)}_{et}$
$\displaystyle\wedge\\{\textbf{Y}^{r(2)}_{et}[i][j]$
$\displaystyle=(\textbf{Y}^{r(1)}_{et}[i][j])^{2}+\textbf{Y}^{r(1)}_{et}[i][j]\\}_{i=0,j=0}^{Mn^{2}-1,Mn^{2}-1}$
$\displaystyle\wedge\textbf{Y}^{r(3)}_{et}$
$\displaystyle=f^{\text{avg}}(\textbf{Y}^{r(2)}_{et})$ $\displaystyle\wedge
C_{\textbf{M}_{1,{ed}}}$
$\displaystyle=\textsf{MPoly.Com}(\textbf{M}_{1,{ed}},ck_{\textsf{PN}},\mathbf{r}_{\textsf{PN}})$
$\displaystyle\wedge C_{\textbf{X}_{et}}$
$\displaystyle=\textsf{MPoly.Com}(\textbf{X}_{et}^{r(1)},ck_{\textsf{PN}},\mathbf{r}_{\textsf{PN}})\big{\\}},$
$\displaystyle\mathtt{R}_{\textsf{LN}}:=\\{(\textsf{st}_{\textsf{LN}}$
$\displaystyle=(C_{\textbf{Y}^{r(3)}},C_{\textbf{M}_{2}},l_{test},ck_{\textsf{LN}}),$
$\displaystyle\textsf{wt}_{\textsf{LN}}$
$\displaystyle=(\textbf{Y}^{r(3)},\textbf{M}_{2},\mathbf{r}_{\textsf{LN}}))\mid$
$\displaystyle\textbf{Y}^{r(4)}$
$\displaystyle=\textbf{W}^{r(4)}\times\textbf{Y}^{r(3)}$
$\displaystyle\wedge\\{\textbf{Y}^{r(5)}[i][j]$
$\displaystyle=max(\textbf{Y}^{r(4)}[i][j],0)\\}_{i=0,j=0}^{Mn^{2}-1,Mn^{2}-1}$
$\displaystyle\wedge\textbf{Y}^{r(6)}$
$\displaystyle=f^{\text{avg}}(\textbf{Y}^{r(5)})$
$\displaystyle\wedge\textbf{Y}^{r(7)}$
$\displaystyle=\textbf{Y}^{r(6)}\times\textbf{W}^{r(7)}$
$\displaystyle\wedge\textbf{Y}^{r(8)}$
$\displaystyle=\textbf{Y}^{r(7)}\times\textbf{W}^{r(8)}$
$\displaystyle\wedge~{}\textbf{l}_{test}[j]$
$\displaystyle=\textsf{argmax}(\textbf{Y}^{r(8)}[j])$
$\displaystyle\wedge~{}C_{\textbf{Y}^{r(3)}}$
$\displaystyle=\textsf{MPoly.Com}(\textbf{Y}^{r(3)},ck_{\textsf{LN}},\mathbf{r}_{\textsf{LN}})$
$\displaystyle\wedge~{}C_{\textbf{M}_{2}}$
$\displaystyle=\textsf{MPoly.Com}(\textbf{M}_{2},ck_{\textsf{LN}},\mathbf{r}_{\textsf{LN}})\big{\\}}.$

Besides the relations, we further define layer-by-layer relations for proving
the layer-wise computations of the $\mathtt{R}_{\textsf{PN}}$ and
$\mathtt{R}_{\textsf{LN}}$ in Fig. 6. In Part 1, the layer-wise computations
of the PriorNet performs in an encryption manner, so we define the relations
to be proven with Setp 1 and Setp 2, as guided by the work [21]. In Part 2,
the LaterrNet runs in a plaintext setting, so we define the corresponding
relations similar to the above Setp 2 (not needing Setp 1). Lastly, in order
to combine the layer-wise computations as a whole, we also denote the
relations for ensuring that starting from the second layer, each layer’s
inputs are consistent with the former layer’s outputs.

With the relations, we proceed to generate zk-SNARK proofs accordingly. At a
high level, the computations of the PriorNet and LaterNet are proved correct
_iff_ both of binary relations $\mathtt{R}_{\textsf{PN}}$ and
$\mathtt{R}_{\textsf{LN}}$ return $1$, which means $\mathtt{R}_{\textsf{PN}}$
and $\mathtt{R}_{\textsf{LN}}$ hold on the corresponding pairs of statement
and witness $(\textsf{st},\textsf{wt})$. For $\mathtt{R}_{\textsf{PN}}$, we
generate publicly verifiable proofs that $\textbf{Y}^{r(3)}_{et}$ is computed
correctly in an encryption manner, with the trained parameters of PriorNet
$\textbf{M}_{1,{ed}}$ and ciphered test inputs $\textbf{X}_{et}^{r(1)}$
through the sequential computations mentioned in the
$\mathtt{R}_{\textsf{PN}}$. In the relation, the witnesses
$\textbf{M}_{1,{ed}}$ and $\textbf{X}_{et}^{r(1)}$ are committed using the key
$ck_{\textsf{PN}}$, and the generated commitments plus
$\textbf{Y}^{r(3)}_{et}$ are treated as the public statement. For
$\mathtt{R}_{\textsf{LN}}$, we generate proofs that LaterNet takes the correct
plaintext $\textbf{Y}^{r(3)}$ and returns the correct inference result
$l_{test}$ by conducting the sequential operations included in the
$\mathtt{R}_{\textsf{LN}}$. Similarly, the witnesses $\textbf{M}_{2}$ and
$\textbf{Y}^{r(3)}$ are committed using the key $ck_{\textsf{LN}}$, and then
the commitments and the execution result are public statements. The processes
of proof generation for $\mathtt{R}_{\textsf{PN}}$ and
$\mathtt{R}_{\textsf{LN}}$ are conducted separately, since the two parts
PriorNet and LaterrNet are executed by different entities. After completing
the proofs for the two parts, we link the proofs together by additionally
proving that the output of the PriorNet is exactly equal to the input of the
LaterNet.

Step 1 CaP zk-SNARK Proofs of Knowledge of Commitments 1:
MUniEv-$\Pi$.Setup($\lambda,d_{c},n_{c})\rightarrow{\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}}:$
2: //$d_{c}$ refers to the degree of ciphers; $n_{c}$ is the number of ciphers
3: $g,h\overset{\$}{\leftarrow}\mathtt{G}$,
$g^{*}\overset{\$}{\leftarrow}\mathcal{G}$,
$\alpha,s,t\overset{\$}{\leftarrow}\mathtt{Z}_{p}$ 4:
$\hat{g}=g^{\alpha},\hat{h}=h^{\alpha},\hat{g^{*}}={g^{*}}^{\alpha}$,
$g^{*}_{1}={g^{*}}^{s}$, $h_{1}=h^{s}$, 5:
$\\{g_{i,j}=g^{s^{i}t^{j}},\hat{g}_{i,j}=\hat{g}^{s^{i}t^{j}}\\}_{i=0,j=0}^{d_{c},n_{c}}$,
HASH: ${\mathtt{G}}^{*}\times{\mathtt{Z}_{q}}^{*}\rightarrow\mathtt{Z}_{p}$ 6:
${\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}}:=(g,h,g^{*},\\{g_{i,j},\hat{g}_{i,j}\\}_{i=0,j=0}^{d_{c},n_{c}},\hat{g},\hat{h},\hat{g^{*}},g^{*}_{1},h_{1},\textsf{HASH})$
7:
MUniEv-$\Pi$.Prove(${\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}},\textbf{W}^{r(1)}_{ed},\textbf{X}^{r(1)}_{et})\rightarrow\pi^{S1}:$
8: //$\textbf{W}^{r(1)}_{ed},\textbf{X}^{r(1)}_{et}$ are square matrices of
$l_{\text{new}}=Mn^{2}$ 9: //$l_{\text{new}}^{2}$ is smaller that $n_{c}$ 10:
//call the commitment scheme MPoly.Com 11:
$\textsf{call~{}MPoly.Com}({\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}},\textbf{W}^{r(1)}_{ed})\rightarrow
C_{\textsf{W}_{1}}$:
$-~{}r_{\textsf{W}_{1}}\overset{\$}{\leftarrow}\mathtt{Z}_{p}$,
$-~{}C_{\textsf{W}_{1}}^{1}=h^{r_{\textsf{W}_{1}}}g_{i,j}^{\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}w_{i,j}}$,
$C_{\textsf{W}_{1}}^{2}=\hat{h}^{r_{\textsf{W}_{1}}}\hat{g}_{i,j}^{\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}w_{i,j}}$,
$-~{}C_{\textsf{W}_{1}}:=(C_{\textsf{W}_{1}}^{1},C_{\textsf{W}_{1}}^{2})$ 12:
$\textsf{call~{}MPoly.Com}({\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}},\textbf{X}^{r(1)}_{et})\rightarrow
C_{\textbf{X}}$: $-~{}r_{\textbf{X}}\overset{\$}{\leftarrow}\mathtt{Z}_{p}$,
$C_{\textbf{X}}^{1}=h^{r_{\textbf{X}}}g_{i,j}^{\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}\text{x}_{i,j}}$,
$C_{\textbf{X}}^{2}=\hat{h}^{r_{\textbf{X}}}\hat{g}_{i,j}^{\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}\text{x}_{i,j}}$,
$-~{}C_{\textbf{X}}:=(C_{\textbf{X}}^{1},C_{\textbf{X}}^{2})$ 13:
$\textsf{call~{}MPoly.Com}({\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}},\textbf{Y}^{r(1)}_{et})\rightarrow
C_{\textbf{Y}}$: $-~{}r_{\textbf{Y}}\overset{\$}{\leftarrow}\mathtt{Z}_{p}$,
$C_{\textbf{Y}}^{1}=h^{r_{\textbf{Y}}}g_{i,j}^{\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}\text{y}_{i,j}}$,
$C_{\textbf{Y}}^{2}=\hat{h}^{r_{\textbf{Y}}}\hat{g}_{i,j}^{\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}\text{y}_{i,j}}$,
$-~{}C_{\textbf{Y}}:=(C_{\textbf{Y}}^{1},C_{\textbf{Y}}^{2})$ 14:
$k=\textsf{HASH}(C_{\textsf{W}_{1}},C_{\textbf{X}},\textbf{W}^{r(1)}_{ed},\textbf{X}^{r(1)}_{et},\textbf{Y}^{r(1)}_{et})$
15:
//$\textbf{X}^{r(1)}_{et}\in\textbf{M}_{\mathtt{Z}_{q}[x](x^{d_{c}}+1)}^{l_{new}^{2}}$,
$\textbf{X}(x,y)=\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}\text{x}_{i,j}x^{i}y^{j}$
16:
//$\textbf{W}^{r(1)}_{et}\in\textbf{M}_{\mathtt{Z}_{q}[x](x^{d_{c}}+1)}^{l_{new}^{2}}$,
$\textbf{W}(x,y)=\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}\text{w}_{i,j}x^{i}y^{j}$
17:
//$\textbf{Y}^{r(1)}_{et}\in\textbf{M}_{\mathtt{Z}_{q}[x](x^{d_{c}}+1)}^{l_{new}^{2}}$,
$\textbf{Y}(x,y)=\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}\text{y}_{i,j}x^{i}y^{j}$
18:
$\textsf{L}_{1}:=\textsf{L}_{1}(x,y)=\textbf{W}(x,y)+\textbf{X}(x,y)+\textbf{Y}(x,y)=\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}l_{i,j}x^{i}y^{j}$
19:
$\textsf{call~{}MPoly.Com}({\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}},\textsf{L}_{1}(s,t))\rightarrow
C_{\textsf{L}_{1}}=(C_{\textsf{L}_{1}}^{1},C_{\textsf{L}_{1}}^{2})$ 20:
$\textsf{L}_{1,k}:=\textsf{L}_{1}(k,y)=\textbf{W}(k,y)+\textbf{X}(k,y)+\textbf{Y}(k,y)=\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}l_{i,j}k^{i}y^{j}$
21:
$\textsf{call~{}MPoly.Com}({\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}},\textbf{W}^{r(1)}_{ed,k})\rightarrow
C_{\textsf{w},k}=(C_{\textsf{w},k}^{1},C_{\textsf{w},k}^{2})$ 22:
$\textsf{call~{}MPoly.Com}({\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}},\textbf{X}^{r(1)}_{ed,k})\rightarrow
C_{\textsf{x},k}=(C_{\textsf{x},k}^{1},C_{\textsf{x},k}^{2})$ 23:
$\textsf{call~{}MPoly.Com}({\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}},\textbf{Y}^{r(1)}_{ed,k})\rightarrow
C_{\textsf{y},k}=(C_{\textsf{y},k}^{1},C_{\textsf{y},k}^{2})$ 24:
$C_{\textsf{L}_{1},k}^{1}=(C_{\textsf{w},k}^{1}\cdot C_{\textsf{x},k}^{1}\cdot
C_{\textsf{y},k}^{1});C_{\textsf{L}_{1},k}^{2}=(C_{\textsf{w},k}^{2}\cdot
C_{\textsf{x},k}^{2}\cdot C_{\textsf{y},k}^{2})$ 25:
$\textbf{T}(x,y)=\frac{\textsf{L}_{1}(x,y)-\textsf{L}_{1}(k,y)}{(x-k)}$ 26:
$\bar{g}=\frac{h_{1}}{h^{k}}$, $a,b\overset{\$}{\leftarrow}\mathtt{Z}_{p}$,
27:
$\textsf{call~{}MPoly.Com}({\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}},\textbf{T}(x,y))\rightarrow
C_{\textbf{T}}$: $-~{}r_{\textbf{T}}\overset{\$}{\leftarrow}\mathtt{Z}_{p}$,
$C_{\textbf{T}}^{1}=h^{r_{\textbf{T}}}\bar{g}^{\sum_{t=0,i=0,j=0}^{d_{c}-1,d_{c}-t,l_{\text{new}}^{2}-1}l_{i+t,j}k^{i-1}s^{i}t^{j}}$,
$C_{\textbf{T}}^{1}=h^{r_{\textbf{T}}}\hat{\bar{g}}^{\sum_{t=0,i=0,j=0}^{d_{c}-1,d_{c}-t,l_{\text{new}}^{2}-1}l_{i+t,j}k^{i-1}s^{i}t^{j}}$,
$-~{}C_{\textbf{T}}:=(C_{\textbf{T}}^{1},C_{\textbf{T}}^{2})$ 28:
$U=e(h^{a}\bar{g}^{b},g^{*})$,
$\mathtt{e}\leftarrow\textsf{HASH}(C_{\textsf{L}_{1}},C_{\textsf{L}_{1},k},C_{\textbf{T}},U,k)$,
29:
$\sigma=a-(r_{\textbf{L}_{1},k}-r_{\textbf{L}_{1}})\cdot\mathtt{e}~{}\text{mod}~{}q$,
$\tau=b-r_{\textbf{T}}\cdot\mathtt{e}~{}\text{mod}~{}q$,
$\pi^{S1}=(C_{\textbf{T}},\mathtt{e},\sigma,\tau)$ 30:
MUniEv-$\Pi$.Verify(${\color[rgb]{0.68,0.09,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0.09,0.13}ck^{S1}},C_{\textsf{L}_{1}},C_{\textbf{X}},C_{\textsf{L}_{1},k},C_{\textbf{T}},k,\pi^{\textsf{S1}})\rightarrow
0/1$: 31:
$b_{1}:=(e(C_{\textsf{L}_{1}}^{1},\hat{g^{*}})==e(C_{\textsf{L}_{1}}^{2},g^{*}))$;
$b_{2}:=(e(C_{\textbf{X}}^{1},\hat{g^{*}})==e(C_{\textbf{X}}^{2},g^{*}))$; 32:
$b_{3}:=(e(C_{\textbf{w},k}^{1},\hat{g^{*}})==e(C_{\textbf{w},k}^{2},g^{*})\wedge
e(C_{\textbf{x},k}^{1},\hat{g^{*}})==e(C_{\textbf{x},k}^{2},g^{*})$ $\wedge
e(C_{\textbf{y},k}^{1},\hat{g^{*}})==e(C_{\textbf{y},k}^{2},g^{*}))$; 33:
$b_{4}:=(e(C_{\textbf{T}}^{1},\hat{g^{*}})==e(C_{\textbf{T}}^{2},g^{*}))$; 34:
$H=e(C_{\textbf{T}}^{1},g^{*}_{1}/{g^{*}}^{k})\cdot
e(C_{\textbf{L}_{1}}^{1}/C_{\textbf{L}_{1},k}^{1},g^{*})^{-1}$,
$\bar{g}=h_{1}/h^{k}$, 35: $U=e(h^{\sigma}\bar{g}^{\tau},g^{*})\cdot
H^{\mathtt{e}}$, 36:
$b_{5}:=(\mathtt{e}==\textsf{HASH}(C_{\textbf{L}_{1}},C_{\textbf{L}_{1},k},C_{\textbf{T}},U,k))$;
37: $b=(b_{1}\wedge b_{2}\wedge b_{3}\wedge b_{4}\wedge b_{5})\rightarrow
0/1$.

Figure 7: Generating zk-SNARK proofs for relation
$\mathtt{R}_{\textsf{PN}}^{S1}$.

Step 2 CaP zk-SNARK Proofs over QMP //st=($\textbf{W}^{r(1)}_{ed,k}$,
$\textbf{X}^{r(1)}_{et,k}$, $\textbf{Y}^{r(1)}_{et,k}$); $io=m=3$;
QMP=($L(x)$,$R(x)$,$O(x)$,$t(x)$)
//$p(x,\textbf{Z})=\textsf{tr}\\{\textbf{Z}^{T}\cdot L(x)\cdot
R(x)\\}-\textsf{tr}\\{\textbf{Z}^{T}\cdot O(x)\\}=h(x,\textbf{Z})t(x)$,
$\forall~{}\textbf{Z}\in\textbf{M}_{(\mathtt{Z}_{p})}^{l_{new}^{2}}$ 1:
AC-$\Pi$.Setup($1^{\lambda}$, QMP)$\rightarrow\textsf{crs}$: 2:
$(\alpha,\beta,\gamma,\delta,\eta,z)\leftarrow\mathtt{Z}_{p}$,
$\textbf{Z}\leftarrow\textbf{M}_{(\mathtt{Z}_{p})}^{l_{new}^{2}}$,
$g,h\leftarrow\mathtt{G}$ 3:
$\textsf{crs}:=(g,h,g^{\alpha},g^{\beta},h^{\beta},h^{\gamma},g^{\delta},h^{\delta},g^{\frac{\eta}{\delta}},g^{\frac{\eta}{\gamma}},\\{\textsf{OP}_{i}=g^{\frac{\beta
L_{i}(z)}{\gamma}}\cdot g^{\frac{\alpha R_{i}(z)}{\gamma}}\cdot
g^{\frac{O_{i}(z)}{\gamma}}\\}_{i=0}^{t})$ 4: AC-$\Pi$.Prove(crs,
st,wt)$\rightarrow\pi^{S2}_{\textsf{L}_{1}}$: 5:
$L(x)=\cdot\textbf{W}^{r(1)}_{ed,k}\cdot L_{\textbf{W}}(z)$;
$R(x)=\textbf{X}^{r(1)}_{et,k}\cdot R_{\textbf{X}}(z)$;
$O(x)=\cdot\textbf{Y}^{r(1)}_{et,k}\cdot O_{\textbf{Y}}(z)$ 6:
$(t,s,v)\overset{\$}{\leftarrow}\mathtt{Z}_{p}$, $A:=g^{\alpha}\cdot
g^{\textbf{Z}^{T}L(z)}\cdot g^{\delta t}$, $B:=h^{\beta}\cdot h^{R(z)}\cdot
h^{\delta s}$, 7: $C:=g^{h(z,\textbf{Z})t(z)/\delta}\cdot
A^{s}\cdot(g^{\beta}\cdot g^{R(z)}\cdot g^{\delta s})^{t}\cdot
g^{-ts\delta}\cdot g^{-v\eta/\delta}$, 8:
$D:=g^{\frac{\beta\textbf{Z}^{T}L(z)}{\gamma}}\cdot g^{\frac{\alpha
R(z)}{\gamma}}\cdot g^{\frac{\textbf{Z}^{T}O(z)}{\gamma}}\cdot
g^{v\eta/\gamma}$, 9: $d_{1}=g^{\frac{\beta L(z)}{\gamma}}\cdot
g^{v\eta/\gamma},d_{2}=g^{\frac{\alpha R(z)}{\gamma}}\cdot
g^{v\eta/\gamma},d_{3}=g^{\frac{O(z)}{\gamma}}\cdot g^{v\eta/\gamma}$, 10:
$C_{\textsf{L}_{1},k}^{{}^{\prime}}:=(d_{1},d_{2},d_{3}),$
$~{}~{}\pi^{S2}_{\textsf{L}_{1}}:=(A,B,C,D,C_{\textsf{L}_{1},k}^{{}^{\prime}})$
11: AC-$\Pi$.Verify(crs, $\pi^{S2}_{\textsf{L}_{1}})\rightarrow 0/1$: 12:
$b:=(\textsf{tr}\\{e(A,B)\\}==\textsf{tr}\\{e(g^{\alpha},h^{\beta})\cdot
e(D,h^{\gamma})\cdot e(C,h^{\delta})\\})\rightarrow 0/1$.

Figure 8: Generating zk-SNARK proofs for relation
$\mathtt{R}_{\textsf{PN}}^{S2}[\textsf{L}_{1}]$.

Proof Generation for $\mathtt{R}_{\textsf{PN}}$. As described before, the
relation $\mathtt{R}_{\textsf{PN}}$ defines that PriorNet is performed in an
encryption manner, by taking the encrypted inputs $\textbf{X}_{et}^{r(1)}$ in
ring field $Z_{q}[x](x^{d_{c}}+1)$. To prove it, we adopt the methodology of
efficient verification computation on encrypted data by Fiore _et al._ [21].
We then integrate it with the aforementioned CaP zk-SNARk from Groth scheme
[20] for proving the satisifiability of QMP-based arithmetic circuits that are
used to express convolutional operations.

Following Fiore _et al._ , there are two steps for completing the proofs. With
respective to the relation $\textsf{R}^{S_{1}}_{\textsf{PN}}$, Step 1 is to
prove the knowledge of the commitments to test inputs, trained weights of
$\textsf{L}_{1}$, and intermediate outputs, by proving simultaneous evaluation
of multiple ring field polynomials on a same point, as demonstrated in Fig. 7.
With respective to the relation
$\textsf{R}^{S_{2}}_{\textsf{PN}}[\textsf{L}_{1}]$, Step 2 shown in Fig. 8 is
to prove the arithmetic correctness of the matrix multiplication computation
with our idea of using QMP. The proofs in Fig. 8 contains the commitments to
the QMP, and they are
$C_{\textsf{L}_{1},k}^{{}^{\prime}}=(d_{1},d_{2},d_{3})$. For another relation
$\textsf{R}^{S_{2}}_{\textsf{PN}}[\textsf{L}_{2},L_{3}]$, the computation
conducted in the two layers involves a 2-degree polynomial evaluated on
$\textbf{Y}^{r(1)}_{et}$ and subsequently an average pooling function. Hence,
we remain using the QAP-based circuit to express them, instead of QMP-based
one, and generate proofs by directly leveraging the CaP variant of the Groth
scheme [20].

Proof Generation for $\mathtt{R}_{\textsf{LN}}$. We previously describe in the
relation $\mathtt{R}_{\textsf{LN}}$ that LaterNet is executed over scalars
instead of polynomial rings, due to all of the data here are plaintext. Hence,
Step 1 is not needed and we directly adopt the above Step 2 to prove the
validity of the relations regarding the LaterNet. Notice, before proof
generation, we express matrix multiplication operations in
$\mathtt{R}_{\textsf{LN}}[\textsf{L}_{4}]$ and
$\mathtt{R}_{\textsf{LN}}[\textsf{L}_{7},\textsf{L}_{8}]$ using QMP-based
arithmetic circuits, while expressing non-linear operations in
$\mathtt{R}_{\textsf{LN}}[\textsf{L}_{5},\textsf{L}_{6}]$ and
$\mathtt{R}_{\textsf{LN}}[\textsf{L}_{o}]$ using QAP-based arithmetic
circuits.

$\textsf{CP}_{\textsf{link}}$ proof for
$\mathtt{R}_{\textsf{PN}}^{\textsf{link}}$ 1: build
$\mathtt{R}_{\textsf{PN}}^{\textsf{link}}:=\big{\\{}(\textsf{st}_{\textsf{PN}}^{\textsf{link}},\textsf{wt}_{\textsf{PN}}^{\textsf{link}})\mid\mathtt{R}_{\textbf{W}}\wedge\mathtt{R}_{\textbf{X}}\wedge\mathtt{R}_{\textbf{Y}}\big{\\}}$
2:
$\textsf{CP}_{\textsf{link}}$.Setup($1^{\lambda},ck_{\textsf{PN}}$,$\mathtt{R}_{\textsf{PN}}^{\textsf{link}}$)$\rightarrow\textsf{crs}^{\textsf{link}}$:
3: build ck from $ck_{\textsf{PN}}$, $ck_{\textsf{L}_{1}}$ 4: call
$\prod_{as}^{\prime}$.Setup(ck )$\rightarrow$ $\textsf{crs}^{\textsf{link}}$
5: $\textsf{CP}_{\textsf{link}}$.Prove($\textsf{crs}^{\textsf{link}}$,
$C_{\textsf{L}_{1},k}^{1}$,
$C_{\textsf{L}_{1},k}^{{}^{\prime}}$,$\textbf{r}_{\text{PN}}$,$\textbf{W}^{r(1)}_{ed,k}$,
$\textbf{X}^{r(1)}_{et,k}$,
$\textbf{Y}^{r(1)}_{et,k}$)$\rightarrow\pi^{\textsf{link}}$: 6: build C from
$C_{\textsf{L}_{1},k}^{1}$, $C_{\textsf{L}_{1},k}^{{}^{\prime}}$ 7: build wt
from $\textbf{r}_{\text{PN}}$,$\textbf{W}^{r(1)}_{ed,k}$,
$\textbf{X}^{r(1)}_{et,k}$, $\textbf{Y}^{r(1)}_{et,k}$ 8: call
$\prod_{as}^{\prime}$.Prove($\textsf{crs}^{\textsf{link}}$, C,
wt)$\rightarrow$ $\textsf{crs}^{\textsf{link}}$ 9:
$\textsf{CP}_{\textsf{link}}$.Verify($\textsf{crs}^{\textsf{link}}$,
$C_{\textsf{L}_{1},k}^{1}$,
$C_{\textsf{L}_{1},k}^{{}^{\prime}}$)$\rightarrow$$\pi^{\textsf{link}}$): 10:
call $\prod_{as}^{\prime}$.Verify($\textsf{crs}^{\textsf{link}}$,
C)$\rightarrow$$\pi^{\textsf{link}}$

Figure 9: Generating zk-SNARK proofs for relation
$\mathtt{R}_{\textsf{PN}}^{\textsf{link}}$.

Proofs Composition. We now need to combine the previous layer-wise proofs
together by following the commit-and-prove methodology. Concretely, we need to
prove two commitments of two successive layer proofs open to the same values.
One of the commitments may commit to the inputs of a current layer while
another one may commit to its previous layer’s outputs. Taking two separate
proofs $\pi^{\textsf{S1}}$ and $\pi^{\textsf{S2}}_{\textsf{L}_{1}}$ as an
example, we ensure the commitments $C_{\textsf{L}_{1},k}^{1}$ and
$C_{\textsf{L}_{1},k}^{{}^{\prime}}$ are opened to the same value, _i.e._ ,
$\mathtt{R}_{\textsf{PN}}^{\textsf{link}}:=\big{\\{}(\textsf{st}_{\textsf{PN}}^{\textsf{link}}=(C_{\textsf{L}_{1},k}^{1},C_{\textsf{L}_{1},k}^{{}^{\prime}},ck_{\textsf{PN}},ck_{\textsf{L}_{1}}),\textsf{wt}_{\textsf{PN}}^{\textsf{link}}=(\textbf{W}^{r(1)}_{et,k},\textbf{X}^{r(1)}_{et,k},\textbf{Y}^{r(1)}_{et,k},r_{\textsf{PN}},r^{\prime}_{\textsf{PN}}))\mid$
$C_{\textsf{L}_{1},k}^{1}=\textsf{MPoly.Com}(\textbf{W}^{r(1)}_{et,k},\textbf{X}^{r(1)}_{et,k},\textbf{Y}^{r(1)}_{et,k},r_{\textsf{PN}},ck_{\textsf{PN}})\wedge
C_{\textsf{L}_{1},k}^{{}^{\prime}}=\textsf{MPoly.Com}(\textbf{W}^{r(1)}_{et,k},\textbf{X}^{r(1)}_{et,k},\textbf{Y}^{r(1)}_{et,k},r^{\prime}_{\textsf{PN}},ck_{\textsf{L}_{1}})\big{\\}}.$
Note that they are Pedersen-like commitments. We make use of the previously
proposed CaP zk-SNARK $\textsf{CP}_{\textsf{link}}$ [20] to composite two
separate proofs by proving the validity of the relation
$\mathtt{R}_{\textsf{PN}}^{\textsf{link}}$. Also, the similar methodology can
be applied into other-layer relations for linking the proofs regarding any two
subsequent layers. The key idea of the methodology is to reshape the
computation of Pedersen commitment into the linear subspace computation.
Concretely, the relation of proving
$C_{\text{w},k}^{1}=h^{r_{w,k}}g_{0,i}^{\sum_{i=0}^{l^{2}_{\text{new}}-1}w_{i}}$
(line 21 of Fig. 7) and $d_{1}=g^{\frac{v\eta}{\gamma}}\cdot
g^{\frac{\beta}{\gamma}\sum_{i=0}^{l^{2}_{\text{new}}-1}w_{i}}$ (line 9 of
Fig. 8) committing to $\textbf{W}^{r(1)}_{ed,k}$ is transformed into the
linear subspace relation
$\mathtt{R}_{\textbf{W}}:\textbf{C}=\textbf{ck}\cdot\textbf{wt}=\overbrace{{\begin{bmatrix}g^{\frac{\beta}{\gamma}\text{w}_{0}}\cdot
g^{v\eta/\gamma}\\\ g^{\frac{\beta}{\gamma}\text{w}_{1}}\cdot
g^{v\eta/\gamma}\\\ ...\\\
h^{r_{\text{w},k}}g_{0,i}^{\sum_{i=0}^{l^{2}_{\text{new}}-1}w_{i}}\end{bmatrix}}}^{\textbf{C}\in\mathtt{G}^{l_{new}^{2}}}$

$=\overbrace{{\begin{bmatrix}0&g^{\frac{\eta}{\gamma}}&g^{\frac{\beta}{\gamma}}&0&...&0\\\
0&g^{\frac{\eta}{\gamma}}&0&g^{\frac{\beta}{\gamma}}&...&0\\\
...&...&...&...&...&...\\\
0&g^{\frac{\eta}{\gamma}}&0&0&...&g^{\frac{\beta}{\gamma}}\\\
h&0&g_{0,0}&...&...&g_{0,(l_{new}^{2}-1)}\end{bmatrix}}}^{\textbf{ck}\in\mathtt{G}^{(l_{new}^{2})\times(l_{new}^{2}+2)}}$
$\times\overbrace{{\begin{bmatrix}r_{\text{w},k}\\\ v\\\ \text{w}_{0}\\\
\text{w}_{1}\\\ ...\\\ \text{w}_{(l_{new}^{2}-1)}\\\
\end{bmatrix}_{.}}}^{\textbf{wt}\in\mathtt{Z}_{p}^{(l_{new}^{2}+2)}}$.

Similarly, we can deduce relations $\mathtt{R}_{\textbf{X}}$ and
$\mathtt{R}_{\textbf{Y}}$ for proving $C_{\text{x},k}^{1}$ and $d_{2}$
committing to $\textbf{X}^{r(1)}_{et,k}$, and $C_{\text{y},k}^{1}$ and $d_{3}$
committing to $\textbf{Y}^{r(1)}_{et,k}$, respectively. As a result, we
represent the former $\mathtt{R}_{\textsf{PN}}^{\textsf{link}}$ as
$\mathtt{R}_{\textsf{PN}}^{\textsf{link}}:=\big{\\{}(\textsf{st}_{\textsf{PN}}^{\textsf{link}},\textsf{wt}_{\textsf{PN}}^{\textsf{link}})\mid\mathtt{R}_{\textbf{W}}\wedge\mathtt{R}_{\textbf{X}}\wedge\mathtt{R}_{\textbf{Y}}\big{\\}}$.
Then, as demonstrated in Fig. 9, the proof $\pi^{\textsf{link}}$ for such a
relation is generated by leveraging $\textsf{CP}_{\textsf{link}}$ that calls a
scheme for proving linear subspace relations $\mathtt{R}_{\textbf{W}}$,
$\mathtt{R}_{\textbf{X}}$ and $\mathtt{R}_{\textbf{Y}}$.

###  V-D Aggregating multiple proofs

Due to that a CNN model is tested with the test data from multiple testers,
there are multiple proofs with respect to proving the correctness of each
inference process. For ease of storage overhead and verification cost, it is
desirable to aggregate multiple proofs into a single proof. Besides, ensuring
the verification computation as simple and low as possible can make our public
platform more easily accessible to a later-coming user. To the end, this
section proceeds to introduce the algorithm of aggregating multiple proofs.

Relation Definition. Suppose there are $n_{t}$ CaP proofs
$\\{\pi^{\textsf{m},i}=(A_{i},B_{i},C_{i},D_{i})\\}_{i\in[n_{t}]}$ w.r.t a CNN
m which is tested by $n_{t}$ testers. We define the aggregation relation that
the multiple generated proofs are valid at the same time:
$\mathtt{R}_{\text{agg}}=\\{(\textsf{st}_{\text{agg}},\textsf{wt}_{\text{agg}})\mid\\{\textsf{AC-}\prod.\textsf{Verify}(\textsf{vk}^{\textsf{m}},\pi^{\textsf{m},i},\textsf{st}^{\textsf{m},i})\rightarrow
1\\}_{i\in[n_{t}]}\\}.$ Here, $\textsf{vk}^{\textsf{m}}$ is the verification
key, extracted from the common randomness string in the Setup algorithm, and
$\textsf{vk}^{\textsf{m}}=(g^{\alpha},h^{\beta},\\{\textsf{OP}_{i}\\}_{i=0}^{t},h^{\gamma},h^{\delta})$.
We note that $\textsf{vk}^{\textsf{m}}$ is the same for the different
statements $\\{\textsf{st}^{\textsf{m},i}\\}_{i\in[n_{t}]}$, each of which
contains $\textsf{st}^{\textsf{m},i}=(a_{i,0},...,a_{i,t})$.
$\pi^{\textsf{m},i}$ is the proof for the statement
$\textsf{st}^{\textsf{m},i}$ based on the different test data and the
different intermediates during the computation of m.

Proof Aggregation. With the defined relation, we are ready to provide a proof
for it. A crucial tool to generate such a proof is recently proposed SnarkPack
[30]. The external effort for us is to extend this work targeted at the
original Groth16 scheme [18] without a commit-and-prove component to our case,
that is, the proofs based on the CaP Groth16 scheme [20] as well as our QMP-
based proofs (see Fig. 8). As shown in line $18$ of Fig. 10, we additionally
compute a multi-exponentiation inner product for $\\{D_{i}\\}_{i\in[n_{t}]}$
of the multiple proofs, which is similar to computing the original
$\\{C_{i}\\}_{i\in[n_{t}]}$. As a result, we enable a single verification on
the aggregated proof $\pi_{\textsf{agg}}$ for a later-coming user who is
interested in the model m that is tested by $n_{t}$ testers.

Aggregating multiple CaP proofs 1:
SnarkPack.Setup($1^{\lambda},\mathtt{R}_{\text{agg}})\rightarrow\textsf{crs}_{\textsf{agg}}$:
2: obtain $g$ and $h$ from crs; $a,b\overset{\$}{\leftarrow}\mathtt{Z}_{p}$ 3:
generate commitment keys $ck_{\textsf{two}}$ and $ck_{\textsf{one}}$: 4:
$\vec{v_{1}}=(h,h^{a},...,h^{a^{n-1}})$,
$\vec{w_{1}}=(g^{a^{n}},...,g^{a^{2n-1}})$, 5:
$\vec{v_{2}}=(h,h^{b},...,h^{b^{n-1}})$,
$\vec{w_{2}}=(g^{b^{n}},...,g^{b^{2n-1}})$ 6:
$ck_{\textsf{two}}=(\vec{v_{1}},\vec{v_{2}},\vec{w_{1}},\vec{w_{2}})$,
$ck_{\textsf{one}}=(\vec{v_{1}},\vec{v_{2}})$ //call a generalized inner
product argument MT_IPP (see Section 5.2 of [30]) 7:
MT_IPP.Setup($1^{\lambda}$,$\mathtt{R}_{\textsf{MT}}$)$\rightarrow\textsf{crs}_{\textsf{MT}}$
8:
$\textsf{crs}_{\textsf{agg}}=(vk^{\textsf{m}},ck_{\textsf{two}},ck_{\textsf{one}},\textsf{crs}_{\textsf{MT}})$
9:
$\textsf{SnarkPack}.\textsf{Prove}(\textsf{crs}_{\textsf{agg}},\\{\textsf{st}^{\textsf{m},i}\\}_{i\in[n_{t}]},\\{\pi^{\textsf{m},i}\\}_{i\in[n_{t}]})$:
10: //commit to $\\{A_{i}\\}_{i\in[n_{t}]}$ and $\\{B_{i}\\}_{i\in[n_{t}]}$
using $ck_{\textsf{two}}$ 11:
$C_{1-AB}=e(A_{0},h)...e(A_{n_{t}-1},h^{a^{n-1}})...e(g^{a^{n}},B_{0})...e(g^{a^{2n-1}},B_{n_{t}-1})$
12:
$C_{2-AB}=e(A_{0},h)...e(B_{n_{t}-1},h^{b^{n-1}})...e(g^{b^{n}},B_{0})...e(g^{b^{2n-1}},B_{n_{t}-1})$
13: //commit to $\\{C_{i}\\}_{i\in[n_{t}]}$ and $\\{D_{i}\\}_{i\in[n_{t}]}$
separately using $ck_{\textsf{one}}$ 14:
$C_{C}=e(C_{0},h)...e(C_{n_{t}-1},h^{a^{n-1}})$,
$C_{C}=e(C_{0},h)...e(C_{n_{t}-1},h^{b^{n-1}})$ 15:
$C_{D}=e(D_{0},h)...e(D_{n_{t}-1},h^{a^{n-1}})$,
$C_{D}=e(D_{0},h)...e(D_{n_{t}-1},h^{b^{n-1}})$ 16: //generate a challenge 17:
$r=\textsf{HASH}(\\{\textsf{st}^{\textsf{m},i}\\}_{i\in[n_{t}]},C_{1-AB},C_{2-AB},C_{C},C_{D})$,
$\vec{r}=(r^{0},...,r^{n_{t}-1})$ 18:
$I_{AB}=\prod_{i=0}^{n_{t}-1}e(A_{i},B_{i})^{r^{i}}$,
$I_{C}=\prod_{i=0}^{n_{t}-1}(C_{i})^{r^{i}}$,
$I_{D}=\prod_{i=0}^{n_{t}-1}(D_{i})^{r^{i}}$ 19:
MT_IPP.Prove($\textsf{crs}_{\textsf{MT}},C_{1-AB},C_{2-AB},C_{C},C_{D},I_{AB},I_{C},I_{D}$,
$(A_{i},B_{i},C_{i},D_{i})_{i\in[n_{t}]},\vec{r})\rightarrow\pi_{\textsf{MT}}$
21:
$\pi_{\textsf{agg}}=(C_{1-AB},C_{2-AB},C_{C},C_{D},I_{AB},I_{C},I_{D},\pi_{\textsf{MT}})$
22:
SnarkPack.Verify($vk^{\textsf{m}},\textsf{crs}_{\textsf{MT}},\\{\textsf{st}^{\textsf{m},i}\\}_{i\in[n_{t}]},\pi_{\textsf{agg}})\rightarrow
b_{1}\wedge b_{2}$
23:MT_IPP.Verify($\textsf{crs}_{\textsf{MT}},C_{1-AB},C_{2-AB},C_{C},C_{D},I_{AB},I_{C},I_{D},\vec{r},\pi_{\textsf{MT}})\rightarrow
b_{1}$ 24:
($I_{AB}\overset{?}{=}e(g^{\alpha\sum_{i=0}^{n_{t}-1}r^{i}},h^{\beta})e(I_{D}^{\sum_{i,j=0}^{n_{t}-1,t}a_{i,j}},h^{\gamma})e(I_{C},h^{\delta}))\rightarrow
b_{2}$

Figure 10: Generating zk-SNARK proofs for relation
$\mathtt{R}_{\textsf{agg}}$.

##  VI SECURITY ANALYSIS

######  Theorem 1.

If the underlying CaP zk-SNARK schemes are secure commit-and-prove arguments
of knowledge $\prod_{s}$, the used leveled FHE scheme L-FHE is semantically
secure and commitments Com are secure, and moreover a model is partitioned
into PriorNet and LaterNet with an optimal splitting strategy, then our
publicly verifiable model evaluation satisfies the following three properties:

Correctness. If PriorNet $F_{\textbf{M}_{1}}$ runs on correctly encrypted
inputs $\textbf{X}_{et}$ and outputs $\textbf{Y}_{et}^{(3)}$, and meanwhile,
LaterNet $F_{\textbf{M}_{2}}$ runs on the correctly decrypted
$\textbf{Y}^{(3)}$ and returns $l_{\textsf{test}}$, then
$l_{\textsf{test}}=F_{\textbf{M}_{2}}(\textbf{Y}^{(3)})$ and
$\textbf{Y}_{et}^{(3)}=F_{\textbf{M}_{1}}(\textbf{X}_{et})$ are verified;

Security. If a PPT $\mathcal{A}$ knows all public parameters and public
outputs of $\prod_{s}$, L-FHE and Com, as well as, the computation of
$F_{\textbf{M}_{1}}$ and $F_{\textbf{M}_{2}}$, but has no access to the model
parameters of $F_{\textbf{M}_{1}}$, it cannot generate $l_{\textsf{test}}^{*}$
which passes verification but $l_{\textsf{test}}^{*}\neq
F_{\textbf{M}_{2}}(\textbf{Y}^{(3)})$;

Privacy. If a PPT $\mathcal{A}$ knows all public parameters and public outputs
of $\prod_{s}$, L-FHE and Com, as well as, the computation of
$F_{\textbf{M}_{1}}$ and $F_{\textbf{M}_{2}}$, but has no access to the model
parameters of $F_{\textbf{M}_{1}}$, it cannot obtain any information about the
clear X.

We recall that a secure CaP zk-SNARK scheme should satisfy the properties of
completeness, knowledge soundness and zero-knowledge; a secure commitment
should be correct, hiding and binding, and a secure L-FHE scheme satisfies
semantic security and correctness. Now we are ready to analyze how the three
properties of correctness, security and privacy can be supported by the
underlying used cryptographic components of our publicly verifiable model
evaluation method. Notice, as we mentioned in Section III-A, the proof
generation for $\mathtt{R}_{\textsf{PN}}$ needs an additional step (namely
Step 1 in Fig. 7), since $\mathtt{R}_{\textsf{PN}}$ relates to encrypted
computation. $\mathtt{R}_{\textsf{LN}}$ only needs Step 2, relying on the
completeness, knowledge soundness and zero-knowledge of the underlying CaP zk-
SNARK scheme [20]. Our following analysis is exactly for
$\mathtt{R}_{\textsf{PN}}$.

The correctness property relies on the correctness of L-FHE and commitments,
and the completeness of the underlying CaP zk-SNARK schemes. We employ a
widely-adopted L-FHE scheme [48] which has been proved correct. For CaP zk-
SNARK schemes, our designs use (_a_) Fiore et al.’s CaP zk-SNARK for
simultaneous evaluation of multiple ciphertexts generated by the L-FHE scheme
[21] (see Fig. 7), (_b_) the CaP Groth16 scheme [18, 20], (_c_) our QMP-based
zk-SNARK derived from the CaP Groth16 (see Fig. 8), and (_d_) the CaP zk-SNARK
$\textsf{CP}_{\textsf{link}}$ for compositing separate proofs [20] (see Fig.
9).

Based on _Theorem 10_ of scheme (_a_) [21], we deduce the correctness of zk-
SNARK proofs for relation $\mathtt{R}_{\textsf{PN}}^{S1}$ by direct
verification (see Fig. 7). Specifically, if
$C_{\textsf{L}_{1}},C_{\textbf{X}}$ are correct commitments, and for
$\textsf{L}_{1}(x,y)=\textbf{W}(x,y)+\textbf{X}(x,y)+\textbf{Y}(x,y)=\sum_{i=0,j=0}^{d_{c},l_{\text{new}}^{2}-1}l_{i,j}x^{i}y^{j}$
and random point $k\in\mathtt{Z}_{p}$, $s,t\in\mathtt{Z}_{p}$, the following
formula holds,

$\displaystyle\textbf{T}(s,t)=\frac{\textsf{L}_{1}(s,t)-\textsf{L}_{1}(k,t)}{(s-k)}$
$\displaystyle=\underline{[(\textsf{L}_{1,0}(s)\cdot
t^{0}+...+\textsf{L}_{1,l_{\text{new}}^{2}-1}(s)\cdot
t^{l_{\text{new}}^{2}-1})-}$
$\displaystyle~{}~{}~{}~{}~{}\frac{(\textsf{L}_{1,0}(k)\cdot
t^{0}+...+\textsf{L}_{1,l_{\text{new}}^{2}-1}(k)\cdot
t^{l_{\text{new}}^{2}-1})]}{(s-k)}$
$\displaystyle=\underline{[(l_{0,0}(s-k)+...+l_{d_{c},0}(s^{d_{c}}-k^{d_{c}}))\cdot
t^{0}+...+}$
$\displaystyle~{}~{}~{}~{}~{}\frac{(l_{0,l_{\text{new}}^{2}-1}(s-k)+...+l_{d_{c},l_{\text{new}}^{2}-1}(s^{d_{c}}-k^{d_{c}}))\cdot
t^{l_{\text{new}}^{2}-1}]}{(s-k)}$
$\displaystyle=\sum_{j=0}^{l_{\text{new}}^{2}-1}\sum_{t=0}^{d_{c}-1}\sum_{i=0}^{d_{c}-t}l_{i+t,j}k^{i-1}s^{i}t^{j}.$

Note that $C_{\textbf{T}}$ correctly commits to $\textbf{T}(s,t)$, then given
$\pi^{S1}=(C_{\textbf{T}},\mathtt{e},\sigma,\tau)$, a verifier can compute $U$
which is equal to $e(h^{a}\bar{g}^{b},g^{*})$ (see line $28$ in Fig. 7) by

$\displaystyle U$ $\displaystyle=e(h^{\sigma}\bar{g}^{\tau},g^{*})\cdot
e(C_{\textbf{T}}^{1},g^{*}_{1}/{g^{*}}^{k})^{\textsf{e}}\cdot
e(C_{\textbf{L}}^{1}/C_{\textbf{L},k}^{1},g^{*})^{-\textsf{e}}$
$\displaystyle=e(h^{\sigma}\bar{g}^{\tau},g^{*})\cdot
e(h^{r_{\textsf{T}}}\bar{g}^{\textsf{T}(s,t)},{g^{*}}^{(s-k)})^{\textsf{e}}\cdot
e(\frac{h^{r_{\textsf{T}}}}{h^{r_{\textsf{T},k}}}\frac{g^{\textsf{L}_{1}(s,t)}}{g^{\textsf{L}_{1}(k,t)}},g^{*})^{-\textsf{e}}$
$\displaystyle=e(h^{\sigma}\bar{g}^{\tau},g^{*})\cdot
e(h,g^{*})^{\textsf{e}r_{\textsf{T}}(s-k)}\cdot
e(g,g^{*})^{\textsf{e}\textsf{T}(s,t)(s-k)}\cdot$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}e(h,g^{*})^{-\textsf{e}(r_{\textsf{T}}-r_{\textsf{T},k})}\cdot
e(g,g^{*})^{-\textsf{e}(\textsf{L}_{1}(s,t)-\textsf{L}_{1}(k,t))}$
$\displaystyle=e(h,g^{*})^{\sigma}\cdot
e(h,g^{*})^{\textsf{e}(r_{\textsf{T},k}-r_{\textsf{T}})}\cdot
e(\bar{g},g^{*})^{\tau+\textsf{e}r_{\textsf{T}}}\cdot$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}e(g,g^{*})^{\textsf{e}\textsf{T}(s,t)(s-k)}\cdot
e(g,g^{*})^{-\textsf{e}(\textsf{L}_{1}(s,t)-\textsf{L}_{1}(k,t))}$
$\displaystyle=e(h,g^{*})^{a}\cdot e(\bar{g},g^{*})^{b}\cdot 1$
$\displaystyle=e(h^{a}\bar{g}^{b},g^{*}).$

Based on _Theorem H.1._ of scheme (_b_) [20], we proceed to derive the
correctness of our QMP-based zk-SNARK proofs for relation
$\mathtt{R}_{\textsf{PN}}^{S2}[\textsf{L}_{1}]$ (_i.e._ , scheme (_c_)) by
verifying
$\pi^{S2}_{\textsf{L}_{1}}:=(A,B,C,D,C_{\textsf{L}_{1},k}^{{}^{\prime}})$,
where $C_{\textsf{L}_{1},k}^{{}^{\prime}}$ will be used in
$\textsf{CP}_{\textsf{Link}}$. Specifically, a verifier needs to verify that
($\star$)
$\textsf{tr}\\{e(A,B)\\}\overset{?}{==}\textsf{tr}\\{e(g^{\alpha},h^{\beta})\cdot
e(D,h^{\gamma})\cdot e(C,h^{\delta})\\}$, where

$\displaystyle\textsf{tr}\\{e(A,B)\\}=\textsf{tr}\\{e(g^{\alpha}\cdot
g^{Z^{T}L(z)}\cdot g^{\delta t},h^{\beta}\cdot h^{R(z)}\cdot h^{\delta
s})\\}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle=e(g,h)^{\textsf{tr}\\{(\alpha+Z^{T}L(z)+\delta
t)(\beta+R(z)+\delta s)\\}}$ $\displaystyle=e(g,h)^{(\alpha+\delta
t)(\beta+R(z)+\delta s)+\textsf{tr}\\{Z^{T}L(z)(\beta+R(z)+\delta s)\\}}$
$\displaystyle=e(g,h)^{(\alpha+\delta t)(\beta+R(z)+\delta s)+\beta
Z^{T}L(z)+\textsf{tr}\\{Z^{T}L(z)R(z)\\}+\delta sZ^{T}L(z)},$
$\displaystyle\textsf{tr}\\{e(g^{\alpha},h^{\beta})\cdot e(D,h^{\gamma})\cdot
e(C,h^{\delta})\\}$ $\displaystyle=\textsf{tr}\\{e(g,h)^{\alpha\beta}\cdot
e(g^{\frac{\beta Z^{T}L(z)+\alpha R(z)+Z^{T}O(z)+v\eta}{\gamma}},h^{\gamma})$
$\displaystyle\cdot e(g^{h(z,Z)t(z)/\delta+(\alpha+Z^{T}L(z)+\delta
t)s+(\beta+R(z)+\delta s)t-ts\delta-v\eta/\delta},h^{\delta})\\}$
$\displaystyle=e(g,h)^{\alpha\beta+\beta Z^{T}L(z)+\alpha
R(z)+\textsf{tr}\\{Z^{T}O(z)\\}+v\eta}$ $\displaystyle\cdot
e(g,h)^{h(z,Z)t(z)+(\alpha+Z^{T}L(z)+\delta t)s\gamma+(\beta+R(z)+\delta
s)t\gamma-ts\gamma^{2}-v\eta}.\vspace{-20pt}$

Due to $p(x,Z)=\textsf{tr}\\{Z^{T}\cdot L(x)\cdot
R(x)\\}-\textsf{tr}\\{Z^{T}\cdot O(x)\\}=h(x,Z)t(x)$, formula ($\star$) holds.

The presentation of the correctness of schemes (_b_) and (_d_) is omitted, as
they can be directly found in [20].

The security property relies on the correctness of L-FHE, and the knowledge
soundness of CaP zk-SNARK we leveraged. The correctness of L-FHE ensures that
$\textbf{Y}^{r(3)}_{et}=f^{\text{avg}}(f^{\textsf{act}}(f^{\text{conv}}(\textbf{X}_{et}^{r(1)})))$
decrypts to
$\textbf{Y}^{r(3)}=f^{\text{avg}}(f^{\textsf{act}}(f^{\text{conv}}(\textbf{X}^{r(1)})$.
For the knowledge soundness of our two-step zk-SNARK proofs (Fig. 7 and Fig.
8), we rely on the knowledge soundness of the two schemes (_a_) and (_c_), and
assume an adversary can black-box query a random oracle HASH. We next analyze
it specifically for the first layer $\textsf{L}_{1}$ from two aspects.

On the one hand, based on the knowledge soundness of schemes (_a_) and (_c_),
if any adversary $\mathcal{A}$ can provide valid proofs with regard to layer-
by-layer computations, _e.g.,_ $\pi^{\textsf{S1}}$ and $\pi^{\textsf{S2}}$ for
$\textsf{L}_{1}$, there exists an extractor who is able to output the
witnesses satisfying the corresponding defined relations
$\mathtt{R}_{\textsf{PN}}^{S_{1}},\mathtt{R}_{\textsf{PN}}^{S_{2}}[\textsf{L}_{1}]$,
with all but negligible probability. Particularly, the knowledge soundness of
scheme (_a_) gives us that
$\textbf{T}(s,t)=\sum_{j=0}^{l_{\text{new}}^{2}-1}\sum_{t=0}^{d_{c}-1}\sum_{i=0}^{d_{c}-t}l_{i+t,j}k^{i-1}s^{i}t^{j}$
is correct evaluation value in the random point $k$ of the polynomial
$\textsf{L}_{1}(x,t)$; the knowledge soundness of scheme (_c_) gives us that
$\textsf{tr}\\{Z^{T}\cdot L(z)\cdot R(z)\\}-\textsf{tr}\\{Z^{T}\cdot
O(z)\\}=h(z,Z)t(z)$.

On the other hand, the remaining probability $\mathcal{A}$ can cheat is that
$\textbf{W}(x,t)\odot\textbf{X}(x,t)-\textbf{Y}^{*}(x,t)$ is a non-zero
polynomial while $\textbf{W}(k,t)\odot\textbf{X}(k,t)-\textbf{Y}^{*}(k,t)=0$
(meaning
$\textbf{Y}^{*r(1)}_{et}=\textbf{W}^{r(1)}_{ed}\odot\textbf{X}^{r(1)}_{et}$),
which is negligible in $\textsf{L}_{1}$. This depends on that we ensure
parameters $q\gg d_{c}$ ($q=2^{109}$ and $d_{c}=4096$) and the point $k$ is
randomly generated by the random oracle HASH. The probability that $k$ is the
root of the non-zero polynomial
$\textbf{W}(x,t)\odot\textbf{X}(x,t)-\textbf{Y}^{*}(x,t)$ thus is negligible,
_i.e._ , $d_{c}$/$q$=$4096/2^{109}$. Last, to analyze the knowledge soundness
of the proofs for other layers of PriorNet is similar to the above two-aspect
analysis for $\textsf{L}_{1}$, due to the nature of layer-wise computation.

The privacy property relies on the semantic security of L-FHE, the hiding
property of comments and the zero-knowledge of the leveraged CaP zk-SNARK
schemes. In terms of semantic security, we derive from the security of a
previously proposed L-FHE (applied to PriorNet), such that for any PPT
adversary $\mathcal{A}$ who has acess to the resulting proofs, the probability
of the following experiment
$\textsf{Exp}_{\mathcal{A}}^{Privacy}[\textsf{L-FHE},f^{\text{avg}}(f^{\text{act}}(f^{\text{conv}}(\cdot),\lambda]$
outputting 1 is not larger than $1/2+\text{negl}(\lambda)$:

$\displaystyle\textsf{Exp}_{\mathcal{A}}^{Privacy}[\textsf{L-FHE},f^{\text{avg}}(f^{\text{act}}(f^{\text{conv}}(\cdot),\lambda]:$
$\displaystyle~{}~{}~{}b\leftarrow{0,1};$
$\displaystyle~{}~{}~{}(pk_{u},sk_{u})\leftarrow\textsf{L-FHE}.\textsf{KeyGen}(1^{\lambda});$
$\displaystyle~{}~{}~{}(\textbf{X}^{r(1)}_{0},\textbf{X}^{r(1)}_{1})\leftarrow\mathcal{A}(pk_{u});$
$\displaystyle~{}~{}~{}(\textbf{X}^{r(1)}_{et,b})\leftarrow\textsf{L-FHE}.\textsf{Enc}(\textbf{X}^{r(1)}_{b});$
$\displaystyle~{}~{}~{}b^{*}\leftarrow\mathcal{A}(pk_{u},\textbf{X}^{r(1)}_{et,b},\pi^{\textsf{S1}},\pi^{\textsf{S2}}),$
$\displaystyle~{}~{}~{}\text{If}~{}b^{*}=b,\text{output}~{}1,\text{else}~{}0.\vspace{-20pt}$

For commitments, we leverage the MPoly.Com scheme which is perfect hiding as
proven in _Theorem_ 8 of [21].

We now analyse zero-knowledge based on the zero-knowledge simulators of the
underlying zk-SNARKs, including
$(\textsf{Sim}^{\textsf{MUniEv}-\Pi.\textsf{Setup}},\textsf{Sim}^{\textsf{MUniEv}-\Pi.\textsf{Prove}})$
and
$(\textsf{Sim}^{\textsf{AC}-\Pi.\textsf{Setup}},\textsf{Sim}^{\textsf{AC}-\Pi.\textsf{Prove}})$,
respectively. $\textsf{Sim}^{\textsf{MUniEv}-\Pi.\textsf{Setup}}$ and
$\textsf{Sim}^{\textsf{AC}-\Pi.\textsf{Setup}}$ are the same as the algorithms
of $\textsf{MUniEv}-\Pi.\textsf{Setup}$ and $\textsf{AC}-\Pi.\textsf{Setup}$
respectively, and generate specific common random strings for the two zk-
SNARKs by running
$\textsf{Sim}^{\textsf{MUniEv}-\Pi.\textsf{Setup}}(1^{\lambda})\rightarrow(\textsf{crs}^{S1},\textsf{td}^{S1})$
and
$\textsf{Sim}^{\textsf{AC}-\Pi.\textsf{Setup}}(1^{\lambda})\rightarrow(\textsf{crs}^{S2},\textsf{td}^{S2})$.
Then, we use the simulations
$\textsf{Sim}^{\textsf{MUniEv}-\Pi.\textsf{Prove}}$ and
$\textsf{Sim}^{\textsf{AC}-\Pi.\textsf{Prove}}$ to generate simulated proofs
with the crs for the corresponding statements. With the simulators, we proceed
with the following games, in which any PPT distinguisher $\mathcal{D}$
successfully distinguishes the simulation with a negligible probability.

Hybrid 0. This starts with the real algorithms in Fig. 7 and Fig. 8, where the
proofs $\pi^{S1}$ and $\pi^{S2}$ are generated by
$\textsf{MUniEv}-\Pi.\textsf{Prove}$ and $\textsf{AC}-\Pi.\textsf{Prove}$,
respectively.

Hybrid 1. This remains unchanged in the usage of witnesses to be proven and we
generate commitments as the line 11-12, 19-23 and 27 presented of Fig. 7. But
we adopt the zero-knowledge simulators including
$(\textsf{Sim}^{\textsf{MUniEv}-\Pi.\textsf{Setup}},\textsf{Sim}^{\textsf{MUniEv}-\Pi.\textsf{Prove}})$
and
$(\textsf{Sim}^{\textsf{AC}-\Pi.\textsf{Setup}},\textsf{Sim}^{\textsf{AC}-\Pi.\textsf{Prove}})$
to generate proofs. Based on that the real
$\textsf{MUniEv}-\Pi.\textsf{Prove}$ and $\textsf{AC}-\Pi.\textsf{Prove}$ are
zero-knowledge algorithms, Hybrid 0 and Hybrid 1 are indistinguishable.

Hybrid 2. This runs the same algorithms as Hybrid 1 except that we replace the
values in the above commitments with zeros. Based on the hiding property of
the leveraged MPoly.Com scheme, Hybrid 1 and Hybrid 2 are indistinguishable.

##  VII Experiments

Implementation. The main components of our implementation include zk-SNARK
systems, FHE and polynomial commitment. We firstly use the libsnark library in
C++ to implement proving/verification based on Groth16 of QAP and QMP-based
circuits during the process of CNN prediction. We then use the Microsoft SEAL
library to encrypt test inputs and evaluate PriorNet on ciphered inputs, with
necessary parameters setting (_i.e._ , $d_{c}=4096,q=2^{109},t=1032193\approx
2^{20}$) as recommended. We proceed to implement the component of polynomial
commitment using the libff library of libsnark, for generating commitments to
encrypted/unencrypted data.

In the aspect of machine learning models, we use well-trained CNN models to
run the prediction process over the single-channel MNIST and three-channel
CIFAR-10 datasets. Specifically, we start from a toy CNN with a convolution
layer, a ReLU layer plus an average pooling layer, and generate proofs w.r.t
the toy CNN running on the MNIST dataset. We then extend it to LeNet-5 over
the MNIST dataset. We additionally run the model on the CIFAR-10 dataset. In
this part, we spend major efforts on approximately handling convolution
operations over the two datasets with different-scale matrix multiplication,
before generating proofs. Due to the parameters and pixel values of data are
floating-point numbers, not adapting to zk-SNARK systems, we use a generic
$8$-bit unsigned quantization technique to transform them into integers in
[$0,255$].

We conduct our MNIST experiments on a Ubuntu $18.04.6$ server with a 6-core
Ryzen5 processor, $7.8$ GB RAM and $97.2$ GB Disk space, and execute CIFAR-10
experiments on a docker container with Ubuntu18.04, Quad-core Intel i5-7500
processor running at 3.4 GHz and 48 GB RAM.

Evaluation. We compare QMP-based zk-SNARK and QAP-based zk-SNARK for matrix
multiplication in terms of the proving time, Setup time and CRS size, as shown
Fig.11 and TABLE II. Concretely, we simulate the operations of matrix
multiplication in increasing dimensions up to $200\times 200$ padding with
random integers in [$0,10$]. Then, we generate proofs for the matrix
multiplication operations using the QAP-based and QMP-based zk-SNARK. Fig.11
shows that the QMP-based zk-SNARK is efficient than the QAP-based one in
generating CRS and proof, as the matrix dimension increases. For the
$200\times 200$ matrix multiplication, the QMP-based zk-SNARK is $17.6\times$
and $13.9\times$ faster than the QAP-based one in Setup time and proving time,
respectively. Besides, the QMP-based zk-SNARK obviously produces smaller CRS
size than the QAP-based zk-SNARK, see TABLE II.

Figure 11: Comparison on Setup time and proving time. TABLE II: CRS size comparison (KB). Matrix dimension | $\mathbf{30\times 30}$ | $\mathbf{50\times 50}$ | $\mathbf{100\times 100}$ | $\mathbf{200\times 200}$
---|---|---|---|---
QAP | 2,911.22 | 12,445.73 | 97,230.09 | 768,503.09
QMP | 84.42 | 233.83 | 934.21 | 3,735.72
Matrix dimension | $\mathbf{500\times}$ | $\mathbf{1000\times}$ | $\mathbf{2000\times}$ | $\mathbf{3000\times}$
QMP | 23,346.32 | 93,384.16 | 373,535.53 | 840,454.47

Figure 12: Performance of our QMP-based zk-SNARK handling matrix
multiplication in dimensions greater than $220\times 220$.

Figure 13: Setup time and proving time for a conv. layer with 1000 images from MNIST and CIFAR-10. TABLE III: Other performance metrics. Datasets | #Filter | Verification time (s) | Size (KB)
---|---|---|---
CRS | Proof
MNIST | 1 | 54559 | 1,054,266.00 | 351,421.97
3 | 54002 | 1,054,266.00 | 351,421.97
5 | 56011 | 1,054,266.00 | 351,421.97
CIFAR-10 | 1 | 375942 | 15353859056 | 351,421.97
3 | 376144 | 15353859056 | 351,421.97
6 | 408911 | 16927629296 | 351,421.97

We can see in Fig. 12 that the QMP-based zk-SNARK can handle the matrix
multiplication in increasing dimensions up to $3360\times 3360$, which is its
merit, compared to the QAP-based zk-SNARK supporting the maximum number of
multiplication bound $10^{7}$ [13]. Also, the proving time almost increases
linearly by the dimension of matrices.

Figure 14: Time complexity of of experiment Exp ($\star$) on the MNIST
dataset.

Figure 15: Time complexity of of experiment Exp ($\star$) on the CIFAR-10
dataset.

We proceed to apply the QMP-based zk-SNARK in a convolution layer with stride
$(1,1)$, taking as inputs $1000$ single-channel images of $28\times 28$ from
MNIST and $1000$ three-channel images of $32\times 32$ from CIFAR-10. For the
former dataset, we use $5$ filters of $5\times 5$ while for the latter one, we
use $6$ filters. We transform the convolution operations into a matrix
multiplication between a weight matrix and an input matrix both in dimension
$3360\times 3360$ for MNIST (similarly, $4704\times 4704$ for CIFAR-10). We
note $3360=28\times(28-5+1)\times 5\approx mn^{2}$, where $m,n$ mean the
dimension of a filter and an image, respectively. Here, $m\geq M$ which is the
number of filters. Different from the aforementioned experiments where the
values of matrices are random integers, the weight matrix of $3360\times 3360$
here is strategically assigned with the weights of filters plus some zero
elements as padding, for ensuring computation correctness (recall it in
Fig.5), and similarly, the input matrix of $3360\times 3360$ is assigned with
the pixel values of $1000$ images, padding with $3360\times(3360-1000)$ zeros.
As a result, the average performance results of 5 runs are shown in Fig. 13.
We discover that compared to the aforementioned experiments as presented in
Fig.12, the Setup and proving time here are relatively smaller. The main
reason can be the padding zero elements inside the weight and input matrices
cancel a lot of multiplications. Besides the Setup and proving time, TABLE III
demonstrates the corresponding verification time, as well as constant CRS size
and proof size.

We further conduct additional experiments (named Exp ($\star$)) on different
number of filters and an increasing number of inputs from MNIST and CIFAR-10
datasets, as elaborated in Fig. 14 and Fig. 15. We can see from the figures
that the proving time basically stays stable regardless of the number of
filters, but the Setup time increases linearly by the number of filters $M$.
We note that the complexity of the proving time is $O(mn^{2}\cdot
mn^{2}),m\geq M$ (resp. $O(Mn^{2}\cdot Mn^{2})$ if $m<M$), where $mn^{2}$
(resp. $Mn^{2}$) is the number of inputs, and the proving time is independent
of the number of filters $M$.

We proceed to generate QAP-based proofs for the ReLU and average pooling
operations on the previous $3360\times 3360$ matrix, named Exp ($\star\star$).
Note that a ReLU operation needs $20$ constraints and an average pooling
operation needs $144$ constraints. The evaluated performance is elaborated in
TABLE IV.

TABLE IV: Performance for Exp ($\star\star$) (s). Layer | Setup Time | Proving Time | Ver. Time
---|---|---|---
ReLU | 5520.61 | 1448.83 | 14.78
Pooling | 196.43 | 49.93 | 14.78

##  VIII Conclusion

We study verifiable CNN testing over ciphered test data by leveraging the
state-of-the-art zk-SNARK systems. Following existing related works, we make
efforts to optimize matrix multiplication relations. Specifically, we
represent convolution operations applying to multiple filters and inputs with
a single MM computation. We then use a new QMP for expressing the MM
computation, so as to reduce the multiplication gate of the finally generated
circuit for the MM computation, and thereby reducing proof generation
overhead. We also aggregate multiple proofs with respect to a same CNN but
different test datasets into a single proof. Besides, we present a proof-of-
concept implementation and conduct experiments to demonstrate the validity of
our approach. For ease of following, we share our implementation code
publicly.

## Acknowledgment

We appreciate all reviewers for their constructive comments and suggestions.
Jian Weng was supported by National Natural Science Foundation of China under
Grant No. 61825203, National Key Research and Development Plan of China under
Grant No. 2020YFB1005600, Major Program of Guangdong Basic and Applied
Research Project under Grant No. 2019B030302008, Guangdong Provincial Science
and Technology Project under Grant No. 2021A0505030033, National Joint
Engineering Research Center of Network Security Detection and Protection
Technology, and Guangdong Key Laboratory of Data Security and Privacy
Preserving. Anjia Yang was supported by the Key-Area R&D Program of Guangdong
Province (No. 2020B0101090004, 2020B0101360001), the National Key R&D Program
of China (No. 2021ZD0112802), the National Natural Science Foundation of China
(No. 62072215). Jia-Nan Liu was supported by the National Natural Science
Foundation of China (No. 62102166), China Postdoctoral Science Foundation (No.
2022M711330).

## References

  * [1] Y. LeCun, B. Boser _et al._ , “Backpropagation applied to handwritten zip code recognition,” _Neural computation_ , vol. 1, no. 4, pp. 541–551, 1989\.
  * [2] R. Das, E. Piciucco _et al._ , “Convolutional neural network for finger-vein-based biometric identification,” _IEEE Transactions on Information Forensics and Security_ , vol. 14, no. 2, pp. 360–373, 2018.
  * [3] G. Accident, “A google self-driving car caused a crash for the first time.” https://www.theverge.com/2016/2/29/11134344/google-self-driving-car-crash-report, 2016.
  * [4] “The two-year fight to stop amazon from selling face recognition to the police.” https://www.technologyreview.com/2020/06/12/1003482/amazon-stopped-selling-police-face-recognition-fight/, 2020\.
  * [5] M. Wicker, X. Huang _et al._ , “Feature-guided black-box safety testing of deep neural networks,” in _Proc. of TACAS_ , 2018.
  * [6] A. Aggarwal, S. Shaikh, S. Hans, S. Haldar, R. Ananthanarayanan, and D. Saha, “Testing framework for black-box ai models,” in _Proc. of IEEE/ACM ICSE-Companion_ , 2021.
  * [7] L. Ma, F. Juefei-Xu _et al._ , “Deepgauge: Multi-granularity testing criteria for deep learning systems,” in _Proc. of ACM/IEEE ICASE_ , 2018\.
  * [8] D. Hendrycks and T. Dietterich, “Benchmarking neural network robustness to common corruptions and perturbations,” in _ICLR_ , 2018.
  * [9] Z. Ghodsi, T. Gu, and S. Garg, “Safetynets: Verifiable execution of deep neural networks on an untrusted cloud,” in _Proc. of NIPS_ , 2017.
  * [10] M. I. M. Collantes _et al._ , “Safetpu: A verifiably secure hardware accelerator for deep neural networks,” in _Proc. Of IEEE VTS_ , 2020.
  * [11] S. Lee, H. Ko, J. Kim, and H. Oh, “vcnn: Verifiable convolutional neural network.” https://eprint.iacr.org/2020/584.pdf, 2020.
  * [12] B. Feng, L. Qin, Z. Zhang, Y. Ding, and S. Chu, “Zen: An optimizing compiler for verifiable, zero-knowledge neural network inferences,” https://eprint.iacr.org/2021/087.pdf, 2021.
  * [13] J. Keuffer, R. Molva, and H. Chabanne, “Efficient proof composition for verifiable computation,” in _Proc. of ESORICS_ , 2018.
  * [14] L. Zhao, Q. Wang _et al._ , “Veriml: Enabling integrity assurances and fair payments for machine learning as a service,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 10, pp. 2524–2540, 2021.
  * [15] A. Madi, R. Sirdey _et al._ , “Computing neural networks with homomorphic encryption and verifiable computing,” in _ACNS Workshops_ , 2020.
  * [16] T. Liu, X. Xie _et al._ , “zkcnn: Zero knowledge proofs for convolutional neural network predictions and accuracy,” in _Proc. of ACM CCS_ , 2021.
  * [17] J. Thaler, “Time-optimal interactive proofs for circuit evaluation,” in _Annual Cryptology Conference_ , 2013, pp. 71–89.
  * [18] J. Groth, “On the size of pairing-based non-interactive arguments,” in _EUROCRYPT_ , 2016, pp. 305–326.
  * [19] S. Agrawal, C. Ganesh _et al._ , “Non-interactive zero-knowledge proofs for composite statements,” in _CRYPTO_ , 2018, pp. 643–673.
  * [20] M. Campanelli _et al._ , “Legosnark: Modular design and composition of succinct zero-knowledge proofs,” in _Proc. of ACM CCS_ , 2019.
  * [21] D. Fiore, A. Nitulescu, and D. Pointcheval, “Boosting verifiable computation on encrypted data,” in _PKC_ , no. 12111, 2020, pp. 124–154.
  * [22] D. Mouris and N. G. Tsoutsos, “Zilch: A framework for deploying transparent zero-knowledge proofs,” _IEEE Transactions on Information Forensics and Security_ , 2021.
  * [23] “Bvlc/caffe,” https://github.com/BVLC/caffe/wiki/Model-Zoo, 2019.
  * [24] Kaggle, “Data science competition platform.” https://www.kaggle.com/.
  * [25] G. Xu, H. Li _et al._ , “Verifynet: Secure and verifiable federated learning,” _IEEE Transactions on Information Forensics and Security_ , vol. 15, pp. 911–926, 2019.
  * [26] Z. He, T. Zhang, and R. B. Lee, “Model inversion attacks against collaborative inference,” in _Proc. of ACM ACSAC_ , 2019.
  * [27] T. Ryffel, E. Dufour-Sans _et al._ , “Partially encrypted machine learning using functional encryption,” in _NIPS_ , 2019.
  * [28] Y. Aono, T. Hayashi _et al._ , “Privacy-preserving deep learning via additively homomorphic encryption,” _IEEE Transactions on Information Forensics and Security_ , vol. 13, no. 5, pp. 1333–1345, 2017.
  * [29] S. G. Francesco Alesiani, “Method for verifying information,” https://patentimages.storage.googleapis.com/53/3c/62/0ed0b3f9bb163f/US20210091953A1.pdf, 2021\.
  * [30] N. Gailly, M. Maller, and A. Nitulescu, “Snarkpack: Practical snark aggregation.” in _Proc. of RWC_ , 2022.
  * [31] J. Zhang, T. Liu _et al._ , “Doubly efficient interactive proofs for general arithmetic circuits with linear prover time,” in _Proc. of ACM CCS_ , 2021.
  * [32] S. Goldwasser _et al._ , “Delegating computation: interactive proofs for muggles,” _Journal of the ACM_ , vol. 62, no. 4, pp. 1–64, 2015.
  * [33] C. Niu, F. Wu, S. Tang, S. Ma, and G. Chen, “Toward verifiable and privacy preserving machine learning prediction,” _IEEE Transactions on Dependable and Secure Computing_ , 2020.
  * [34] J. Zhang, Z. Fang _et al._ , “Zero knowledge proofs for decision tree predictions and accuracy,” in _Proc. of ACM CCS_ , 2020.
  * [35] C. Weng, K. Yang, X. Xie, J. Katz, and X. Wang, “Mystique: Efficient conversions for zero-knowledge proofs with applications to machine learning,” in _Proc. of USENIX Security_ , 2021, pp. 501–518.
  * [36] C. Dong, J. Weng _et al._ , “Fusion: Efficient and secure inference resilient to malicious server and curious clients,” in _Proc. of NDSS_ , 2023\.
  * [37] R. Gilad-Bachrach, N. Dowlin _et al._ , “Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy,” in _ICML_ , 2016, pp. 201–210.
  * [38] P. Mohassel and Y. Zhang, “Secureml: A system for scalable privacy-preserving machine learning,” in _Proc. Of IEEE S &P_, 2017.
  * [39] P. Mishra, R. Lehmkuhl _et al._ , “Delphi: A cryptographic inference service for neural networks,” in _USENIX Security_ , 2020, pp. 2505–2522.
  * [40] C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan, “$\\{$GAZELLE$\\}$: A low latency framework for secure neural network inference,” in _Proc. of USENIX Security_ , 2018.
  * [41] N. Kumar, M. Rathee _et al._ , “Cryptflow: Secure tensorflow inference,” in _IEEE S &P_, 2020, pp. 336–353.
  * [42] K. Huang, X. Liu _et al._ , “A lightweight privacy-preserving cnn feature extraction framework for mobile sensing,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 18, no. 3, pp. 1441–1455, 2019.
  * [43] E. Hesamifard, H. Takabi, and M. Ghasemi, “Cryptodl: Deep neural networks over encrypted data,” https://arxiv.org/abs/1711.05189, 2017.
  * [44] X. Liu, R. H. Deng _et al._ , “An efficient privacy-preserving outsourced calculation toolkit with multiple keys,” _IEEE Transactions on Information Forensics and Security_ , vol. 11, no. 11, pp. 2401–2414, 2016.
  * [45] X. Liu _et al._ , “Efficient and privacy-preserving outsourced calculation of rational numbers,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 15, no. 1, pp. 27–39, 2016.
  * [46] X. Liu, R. H. Deng _et al._ , “Privacy-preserving outsourced calculation toolkit in the cloud,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 17, no. 5, pp. 898–911, 2018.
  * [47] R. Gennaro, C. Gentry _et al._ , “Quadratic span programs and succinct nizks without pcps,” https://eprint.iacr.org/2012/215.pdf, 2012.
  * [48] J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption,” https://eprint.iacr.org/2012/144.pdf, 2012.
  * [49] X. Chen, C. Liu _et al._ , “Targeted backdoor attacks on deep learning systems using data poisoning,” https://arxiv.org/abs/1712.05526, 2017.
  * [50] G. Xu, H. Li _et al._ , “Secure and verifiable inference in deep neural networks,” in _Proc. of ACM ACSAC_ , 2020.
  * [51] Z. He, T. Zhang _et al._ , “Sensitive-sample fingerprinting of deep neural networks,” in _CVPR_ , 2019.
  * [52] A. E. Kosba, D. Papadopoulos _et al._ , “Trueset: Faster verifiable set computations,” in _Proc. of USENIX Security_ , 2014.

|  Jiasi Weng received the B.S. degree in software engineering from South
China Agriculture University, and the Ph.D. degree in the Colledge of
Information Science and Technology & College of Cyber Security at Jinan
University. She researches in the field of trustworthy machine learning. She
has published over ten papers in peer-reviewed venues and journals.
---|---
|  Jian Weng is a professor and the Executive Dean with College of Information
Science and Technology in Jinan University. He received B.S. degree and M.S.
degree from South China University of Technology in 2001 and 2004
respectively, and Ph.D. degree at Shanghai Jiao Tong University in 2008. His
research areas include public key cryptography, cloud security, blockchain,
etc. He has published 80 papers in international conferences and journals such
as CRYPTO, EUROCRYPT, ASIACRYPT, TCC, PKC, CT-RSA, IEEE TPAMI, IEEE TDSC, etc.
---|---
|  Gui Tang received the B.S. degree in electronics information science and
technology from Shandong Technology and Business University in 2020. He
currently works towards the M.S. degree at Jinan University. His research
interests include privacy-enhancing technologies and applications.
---|---
|  Anjia Yang received the B.S. degree from Jilin University in 2011 and the
Ph.D. degree from the City University of Hong Kong in 2015. He is currently an
associate professor in Jinan University, Guangzhou. His research interests
include security and privacy in vehicular networks, internet of things,
blockchain and cloud computing.
---|---
|  Ming Li received his B.S. in electronic information engineering from
University of South China in 2009, M.S. in information processing from
Northwestern Polytechnical University in 2012 and Ph.D. at Jinan University in
2020. His research interests include blockchain, crowdsourcing and its privacy
and security.
---|---
|  Jia-Nan Liu received the B.S. degree from Zhengzhou University in 2013, and
the M.S. degree from Jinan University in 2016, and the Ph.D. degree from Jinan
University in 2020. His research interests include cryptography and cloud
computing security.
---|---