Homomorphic Encryption (HE)-enabled neural networks (NNs) [1,2,3] are designed for secure Machine Learning as a Service (MLaaS). In HE-enabled MLaaS, a client encrypts his/her data and uploads the encrypted data to a server in the cloud. The server computes inferences on the encrypted data and returns the encrypted output to the client. The server cannot decrypt the encrypted input or output during an inference. However, HE naturally supports only linear layers of a neural network. Some interactive HE-enabled NNs (HENNs) [4,5,6] take advantage of multi-party computation (MPC) to get the client involved in the computation of activation layers by exchanging several gigabyte data with the client during an inference, while other non-interactive HENNs [1, 2,3] approximate activations by a square function to perform secure inferences without involving the client. A non-interactive HE-enabled NN is a practical MLaaS solution with competitive accuracy for particular clients who have limited computing power and small network bandwidth. However, both interactive and non-interactive HE-enabled inferences are slow. An inference of state-of-the-art HENNs [5,3] on an encrypted CIFAR-10 image costs several hundred seconds. Their long inference latency is caused by expensive HE rotations. Modern HE cryptosystems, e.g., BFV [7], pack a vector consisting of small integers into a single large integer, so that they can allow concurrent HE arithmetic operations to happen on individual integers by performing a single operation on the large integer. The single instruction multiple data (SIMD) computing style of HE significantly reduces inference latency of HENNs from multiple hours to several hundred seconds. However, each accumulation in linear layers of a HE-enabled NN requires a rotation operation to shuffle small integers packed into a large integer. As a result, rotations consume > 90% of inference latency of a HE-enabled NN on an encrypted CIFAR-10 image.
Recent interactive HENNs [4,8] use frequency-domain convolutions [9,10] to perform only elementwise multiplications in their linear layers to eliminate expensive HE rotations. A plaintext image of a client is first converted to its frequency-domain representation by discrete Fourier transform (DFT), encrypted to a ciphertext, and then sent to a cloud server. Instead of HE multiply-accumulate (MAC) operations, only HE element-wise multiplications are required to perform frequency-domain convolutions on the server. After receiving the encrypted frequency-domain linear layer output, the client decrypts it and converts the plaintext frequency-domain output to a normal linear layer output by inverse DFT (IDFT). At last, the client performs activations on the normal linear layer output, and then moves to the next layer. The frequency-domain convolutions greatly reduce inference latency of interactive HENNs by 30% ∼ 40%.
However, naïvely using frequency-domain convolutions in non-interactive HENNs prolongs inference latency. Each HE operation introduces a certain amount of noise into the encrypted data. When the accumulated noise in the encrypted data is larger than the noise budget of a HENN, the encrypted data cannot be correctly decrypted. Therefore, the total number of HE operations along the critical path of a HENN decides the noise budget. A larger noise budget increases the latency of each HE operation. In interactive HENNs, the server sends the output to the client at the end of each linear layer. The client has to participate the computation of each activation layer. The client performs DFT and IDFT on plaintext data, and thus does not increase the number of HE operations at all. On the contrary, non-interactive HENNs homomorphically compute all linear and activation layers on the server without involving client. DFT and IDFT applied in non-interactive HENNs happen on the encrypted data, and thus should be homomorphic. Homomorphic DFT and IDFT greatly increase the noise budget of a non-interactive HENN by adding more HE operations to its critical path. Based on our estimation, the enlarged noise budget significantly prolongs inference latency of a frequency-domain non-interactive HENN by > 100%.
In this paper, we propose Falcon for fast non-interactive privacy-preserving inference. Our contributions can be summarized as follows.
• We propose a novel HE DFT algorithm to homomorphically and efficiently convert an encrypted input to its encrypted frequency-domain representation.
• We propose a fast HE-enable convolution technique and a fully-connected technique on spectral domain using block circulant weight matrices.
• We consider the improvements and overhead of proposed techniques on both HE noise growth and HE parameters selection. Our experiments prove that Falcon reduces the inference latency by 45.45% ∼ 85.34% over prior HENNs on MNIST and CIFAR-10.
Figure 2: A homomorphic dot-product.
Recent works [1, 2, 3, 4, 5, 6] use HE to implement linear layers of a HENN for MLaaS. However, HE cannot support non-linear activation layers. As Figure 1(a) shows, interactive HENNs [4,5,6] take advantage of MPC and secrete sharing to make the server to send the output to the client at the end of each linear layer, and get the client involved in the computation of each activation layer. In contrast, non-interactive HENNs [1, 2, 3] approximate activations by a square function to compute an entire secure inference without involving the client, as shown in Figure 1(b). Compared to interactive HENNs, non-interactive HENNs have a lower requirement on the computing power and network bandwidth of the client, thereby becoming more friendly to low-power mobile devices. A state-ofthe-art interactive HENN, Delphi [5], has to exchange 2GB data between the client and server for only a ResNet-32 inference on an encrypted CIFAR-10 image. In this paper, we focus on accelerating non-interactive HENNs. Particularly, we select LoLa [3] implemented by BFV [7] as our baseline, due to its state-of-the-art inference accuracy and latency. Compared to other HE cryptosystems such as CKKS [11], the BFV-based LoLa improves inference latency by 30%.
Homomorphic Encryption. HE allows operations on encrypted data without requiring access to the secret key [7]. Given a public key pk, a private key sk, an encryption function (), and a decryption function σ(), a HE operation ⊗ can be defined if there is another operation × such that σ( (x 1 , pk) ⊗ (x 2 , pk), sk) = σ( (x 1 × x 2 , pk), sk), where x 1 and x 2 are plaintexts. Each HE operation introduces a certain amount of noise into encrypted data. When the accumulated noise is larger than a noise budget, errors happen during HE decryption. A bootstrapping operation [12] is extremely expensive, although it can reduce the noise in encrypted data. Prior HENNs use leveled HE defining a noise budget to compute only a limited number of HE operations.
SIMD and Rotation. Modern HE cryptosystems, e.g., BFV [7], support single instruction multiple data (SIMD) vectors by encoding multiple integers into a larger integer based on Chinese Remainder Theorem. For instance, as Figure 2 shows, an encrypted input integer vector [x 0 , x 1 , x 2 , x 3 ] can be encrypted into m x , while another weight integer vector [w 0 , w 1 , w 2 , w 3 ] can be encrypted into m w . By computing a HE multiplication between m x and m w , four HE multiplications are simultaneously performed on individual integers, i.e., [
A HE cryptosystem also supports rotations to shuffle individual integers in a packed vector. For instance, rotating the vector [y 0 , y 1 , y 2 , y 3 ] by 2 results in the vector [y 2 , y 3 , y 0 , y 1 ]. A HE rotation is computationally expensive [4] and introduces non-trivial noise into the encrypted data.
Homomorphic Multiply-Accumulate. The major operation in linear layers of a HENN is homomorphic MAC, as shown in Figure 2. For a fully-connected (FC) layer, we assume the encrypted input vector x includes n elements, the encrypted output vector y has m elements, and the plaintext weight matrix w has a dimension of n × m. For instance, for each row of w j (0 ≤ j ≤ m -1) and [x], we have
where M ulP C indicates a HE SIMD multiplication between a packed plaintext and a packed ciphertext; and rot means a HE rotation. As Equation 1 describes, log 2 n HE rotations are required to accumulate an element of y. We summarized the HE operation number and noise of a FC layer of LoLa in Table 1. Among all HE operations, rotations dominate inference latency of LoLa. In this paper, we focus on eliminating HE rotate-and-accumulate operations.
Interactive HENNs. Prior interactive HENNs [4,8] use frequency-domain convolutions [9,10] to perform only element-wise multiplications in their HE linear layers to reduce rotation overhead, as shown in Figure 1(a). Based on Convolution Theorem, the convolutions in space domain are equivalent to element-wise products in frequency domain. Therefore, we have
. w 0,0 w 0,q-1 ... where IDFT means inverse DFT. Frequency-domain convolutions greatly reduce inference latency of interactive HENNs, since unencrypted DFT and IDFT performed by the client introduce small computing overhead.
: ciphertext numbers of LoLa and LoLa+DFT; n a = I c • f 2 and n a = I c • I w • I h : accumulation numbers of LoLa and LoLa+DFT, where x is for roundup x to the nearest integer. η 0 : initial noise; η m : MultPC noise; and η r : rotation noise).
Non-interactive HENNs. Unlike interactive HENNs, non-interactive HENNs shown in Figure 1(b) have to use homomorphic DFT (HDFT) and IDFT (HIDFT), since the entire inference occurs on the server. Though a CKKS-based homomorphic DFT function with bootstrapping [11] exists, there is no BFV-based DFT or IDFT function. Even if we have BFV-based DFT and IDFT functions, the total HE number and noise of a non-interactive HENN will be greatly increased by HDFT and HIDFT that also require HE rotate-and-accumulate operations. DFT and IDFT can be summarized as
where ω n = e 2πi/n . As Table 1 shows, if we naïvely apply HDFT and HIDFT on LoLa, LoLa+DFT increases more than 2× rotations since n a > n a and n c > n c , and thus introduces more noises. To maintain a larger noise budget for the noises, LoLa+DFT has to enlarge the HE encryption parameters, i.e., the ciphertext modulus q, and the polynomial degree N , which in turn prolong the latency of each M ulP C, AddCC, and rot operation.
Recent works [13] compresses a weight filter of a plaintext NN into multiple blocks-circulant matrices to reduce inference computing overhead. The n × m weight matrix is divided into p × q square blocks, each of which (w i,j ) contains k × k elements, where 0 ≤ i ≤ q -1 and 0 ≤ j ≤ p -1. We have p = m k and q = n k . The k × k elements in a block can be derived by only k elements with shift operations. The input vector is divided into q parts, while the output vector is divided into p parts. To compute each part of the output vector (y i ) as shown in Figure 3, we can use
The computational complexity of a FC layer is O(pqklogk). rotations. ENSEI and MPCHE are proposed to reduce homomorphic rotations of interactive HENNs using spectral-domain convolutions. Nevertheless, their methods based on convolution theorem can not be applied to fully-connected operations. In addition, both ENSEI and MPCHE focus on interactive HENNs and cannot perform DFT and IDFT homomorphically. They enforce clients to process DFT and IDFT on the unencrypted data. Directly applying their methods on non-interactive HENNs prolongs the inference latency, due to the huge overhead of homomorphic DFT. Our Falcon includes an efficient homommorphic DFT technique and supports both spectral convolutions and FC operations, which significantly reduces the inference latency of non-interactive HENNs.
3 Falcon
Algorithm 1: Homomorphic DFT (HDFT).
w 00 w 00 w 00 w 10 w 10 w 10 w 01 w 01 w 01 w 11 w 11 w 11 w 00 w 10 w 01 w 11 Re Re Re Re w 00 w 10 w 01 w 11 Re Re Re Re w 00 w 00 w 00 w 10 w 10 w 10 w 01 w 01 w 01 w 11 w 11 w 11 w 00 w 10 w 01 w 11 w00 w00 w10 w10
+ FC operations in LoLa FC operations in LoLa rot(y,1) rot(y,1) w01 w01 w11 w11 w01 w11 To support homomorphic DFT shown in Equation 3 using BFV scheme, we should firstly quantize and encode the complex numbers (w i,j ) of DFT conversion matrix.
Quantization. State-of-the-art non-interactive HENNs, e.g., LoLa, rely on the BFV protocol that supports only integer. The inputs, weights, activations, and outputs of the non-interactive HENNs are all integers. So x i of HDFT and HIDFT in Equation 3 is an integer. ω it n can be quantized as
where • is the rounding function converting a real number to an integer; and S 1 is an integer scaling factor. Through multiplying S 1 , the real inputs, weights, and ω it n of a HENN are scaled to keep more digits after their decimal point during the rounding process. We quantized the inputs, activations, weights, and ω it n of a HENN with 8-bit. We integrated the quantized HENN into the forward propagation of the training to minimize the accuracy loss.
Encoding Complex Numbers. Unlike HEAAN [11], the BFV protocol cannot naturally support complex number. We encode the real part (Re) S 1 cos( 2πt n ) and the imaginary part (Im) 5by two SIMD slots of a BFV ciphertext, so we have C = Re+jIm. For a HE complex addition (C 0 +C 1 ), we have (Re 0 +Re 1 )+j(Im 0 +Im 1 ). For a HE complex multiplication (C 0 ×C 1 ), we have ((Re 0 +Im 0 )Re 1 -(Re 1 +Im 1 )Im 0 )+j((Re 0 +Im 0 )Re 1 -(Re 1 +Im 1 )Re 0 ).
Homomorphic DFT and IDFT. We present a BFV-based homomorphic DFT in Algorithm 1 to homomorphically convert an encrypted integer vector [x] to its encrypted frequency-domain vector y=[x]. Here ω is the quantized DFT twiddle factors and its entries can be stacked and permuted in an offline phase. Table 3 shows a comparison of computational complexity between prior homomorphic DFT (FTHDFT) [17] and our Algorithm 1 when they both use the block circulant matrix technique. Algorithm 1 needs (log 2 k) rotations and additions, and 1 M ultP C operations for each real-part vector (Re) and imaginary-part vector (Im) of input vector x. Figure 4 shows an example of our algorithm 1 with k = 2, and this example requires 1 multiplication, rotation and addition for each real-part vector (Re) and imaginary-part vector (Im).
Table 3: The comparison of homomorphic DFT schemes with k points. Here η = η 0 η m k +η r (k-1).
Algorithm 2 shows our proposed homomorphic fully-connected (HFC) layer, which takes a spatial domain vector x as the input, and outputs the encrypted results 4 compares the computational overheads and noise growth between LoLa and our Falcon. Falcon requires 2log 2
Our experiments show that When k >= 2, Falcon costs less computations than LoLa. For noise growth, we set η = η 0 η m I + η r (I -1). When k > 1, Falcon reduces the noise accumulation, thereby potentially enabling more efficient HE parameters. Figure 5 shows an example why our Algorithm 2 is better than our baseline LoLa. In this example, k = 2, I = 2, O = 2 and N = 2, LoLa requires N c (O) = 2 ciphertexts and 2 × log 2 (I) = 2 additions, rotations and multiplications. Our Falcon only requires N c ( O k ) = 1 ciphertext and 1 × log 2 ( I 2 ) = 0 rotations. This is only a toy example and we should add the overhead of HDF T into our method. In practice, when I, O and N are very large, the overhead of HDF T is tiny compared to the other computations within a spectral FC, which is shown in section 5.
Table 4: The comparison of homomorphic FC operations with I inputs and O outputs. dot-products, where s is the stride size. Previous works use M c (O ) ciphertexts to pack O × stacked inputs, so that one homomorphic convolution operation is converted to O × homomorphic dot-product operations on each sliding window with size I . Table 5 shows that previous work requires log 2 I • M c (O ) rotations, and noise growth is η = η 0 η m I + η r (I -1). By using the block-circulant matrix technique, we only need M c ( O k ) ciphertexts as shown in Algorithim 3, which potentially reduces k× homomorphic rotations, multiplications and additions. In addition, the dot-product of each ciphertext in Algorithm 3 only needs to accumulate entries between blocks, which is implemented by setting k c • k w • k h = k. Thus, each dot-product with size I only requires I k additions and rotations to accumulate its partial results. Table 5 concludes the computational overheads and noise growth of LoLa and our Falcon. Falcon reduces ∼ k•log2(k) 2 rotations, additions and multiplications over LoLa. Flacon has k× less noise increase than LoLa.
Table 5: The comparison of homomorphic convolution schemes.
Dataset, Networks and Operation Details. Our datasets include MNIST [18] and CIFAR-10 [19].
The network architecture for MNIST dataset is same to LoLa [20], but we replace the spatial-domain middle layers into frequency domain. The network architecture and operations are summarized in Table 6. The block size k of circulant matrix is set as 8 so that accuracy is not decreased. We evaluated a 3-layer CNN same to LoLa [20] on CIFAR-10. To keep original accuracy, the block size k = 16 of circulant matrix is used.
Cryptosystems Settings. We use BFV scheme in SEAL [21] to implement Falcon. For MNIST and CIFAR-10, the plaintext modulus t = 2148728833 × 2148794369 × 2149810177, modulus degree N = 16384, coefficient modulus Q =∼ 440 bits. More specific encryption parameters settings are shown in Table 7 and Table 8. The security level is larger than 128 bits which is verified by lwe_estimator [22]. To have fair comparisons with baselines, We ran all experiments on the same Azure standard B8ms virtual machine with 8 vCPUs and 32GB DRAM.
We compared Falcon against the state-of-the-art works including CryptoNets [23], Faster CryptoNets (FCryptoNets) [24], nGraph-HE [25], CHET [15] and LoLa [20]. The homomorphic operation numbers (HOPs), encryption parameter bits, message size, latency and accuracy are summarized in Table 7. HOPs is the sum of all homomorphic operation number including M ultP C, M ultCC, AddCC and rot. Message size is the size of encrypted input and output that the client needs to transmit.
As
Table 8 shows the inference latency, accuracy and HOPs of existing works on CIFAR-10. nGraph-HE implements CIFAR-10 inference in 1628 seconds with 62.1% accuracy. FCryptoNets improves 14.6% accuracy compared to nGraph-HE with a deeper and more complex neural network architecture, but it suffers from huge latency with 39K seconds. EVA and LoLa support same vector representations and operations, but they are based on HEAAN and BFV respectively and encryption parameters, thereby they have different latency. LoLa introduces 53K expensive rotations, each of rotations has ∼ 10× latency of multiplication M ultP C. Our work Falcon removes 86% rotations and reduces the latency from 730 seconds to 107 seconds. Table 9 reports the batching representations and operations that Falcon applies in each layer. Since the second FC layer of LoLa occupies ∼ 97% of the total latency, we replace this layer by our homomorphic convolution and keep the other layers same to LoLa. Falcon uses 7674 rotations, reducing 86% rotation numbers in the second convolution layer compared to LoLa which consumes 52975 rotations. Our baseline LoLa can be improved by LoLa' using more proper encryption parameter Q.
In this paper, we propose Falcon, a low-latency deep neural network on encrypted data, which consists of a homomorphic DFT unit, a Homomorphic FC unit and a Homomorphic convolution unit based on block-circulant matrix. Our experimental results show Falcon reduces the inference latency by 45.45% ∼ 85.34% over prior HENNs on various datasets. Falcon is the first frequency-domain non-interactive HENNs.
Falcon enables a low-latency privacy-preserving neural network inference on encrypted data. With Falcon, users can enjoy low-latency secure inference services. In particular, users are able to receive low-latency and powerful machine learning inference services by uploading their sensitive data without concerning data privacy. Falcon has no negative impact on our society. If our proposed method fails, the latency of secure inferences will be prolonged.