FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks

1. Security proof of FicGCN

Thanks for your comments. FicGCN fully adopts CryptoGCN's[3] threat model and privacy assumptions which has been rigorously proved. We utilize the CKKS scheme, whose security is guaranteed by the hardness of the RLWE problem[1], ensuring polynomial-time indistinguishability. During inference, we employ only CKKS-supported secure homomorphic operations (PMult,CMult,Rot), and the ciphertext packings. Since CKKS inherently supports arbitrary message vector ordering in its plaintext polynomial encoding[2] and homomorphic operations, FicGCN preserves CKKS's original security guarantees. In the setup stage, we select homomorphic encryption parameters[2] to achieve 128-bit security—meaning any successful attack would require at least $2^{128}$ basic operations.

2. Analysis of the impact of supplementary references on FicGCN

The techniques from the referenced works are orthogonal to our research and do not directly contribute to it. However, they can be easily integrated with our approach in their intended applications to enhance overall end-to-end performance.

To illustrate, FedML-HE enables clients to strategically compromise certain node features' security via Selective Encryption, converting partial computations from ciphertext to plaintext for reduced latency. THE-X primarily optimizes nonlinear layers through polynomial approximation—an objective orthogonal to FicGCN's linear-layer optimizations. Similarly, BatchCrypt's quantization uniformly accelerates all layers, constituting another independent optimization dimension. While all 3 studies offer potential improvements for GCN inference, their techniques operate on distinct axes from our approach. We therefore incorporate them as valuable references while emphasizing FicGCN's unique contributions.

3. Key management in FicGCN

In FicGCN, we exclusively employ FHE to execute encrypted inference for ensuring data security. This framework requires three distinct keys: the public key (pk), private key (sk), and evaluation key (evk).

• Pk: Used for data encryption/decryption and enabling homomorphic operations, thus being publicly shared between both parties.
• Sk: Also involved in encryption/decryption, is strictly client-exclusive to prevent server-side privacy breaches. All decryption occurs solely on the client side to eliminate man-in-the-middle risks.
• Evk: Generated by the client and disclosed to the server, facilitates server-side HE computations (e.g. Rotation, CMult).

4. Analysis of collusion threat model in FicGCN

FicGCN's application scenario involves strictly one client and one server following the common FHE assumption[3], where the client possesses all node features and refuses to disclose any data to the server. This fundamentally contradicts the prerequisite for collusion models defined in [4]—which require at least three participating parties capable of covert coordination to violate protocol security. Under our key management framework, FHE inherently eliminates collusion threats because:

(1) Only two non-cooperating parties exist

(2) Even if a server supports multiple colluding clients, they cannot obtain honest clients' private keys

(3) Security reduces solely to RLWE hardness

Reference:

[1] Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC '05)

[2] Cheon, J.H., Kim, A., Kim, M., Song, Y. (2017). Homomorphic Encryption for Arithmetic of Approximate Numbers. In: Takagi, T., Peyrin, T. (eds) Advances in Cryptology – ASIACRYPT 2017.

[3] Ran Ran, Nuo Xu, Wei Wang, Gang Quan, Jieming Yin, and Wujie Wen. 2022. CryptoGCN: fast and scalable homomorphically encrypted graph convolutional network inference. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NIPS '22).

[4] Goldreich, O. (2004). Foundations of Cryptography II. Cambridge University Press.

1. Justification for the need to reorder nodes(Q1)

Thanks for your comments. Negotiating and determining the optimal packing method based on NOO prior to private inference indeed constitutes a key contribution of our work. We discussed it in Section 3.2.1 and Figure 8(b). However, only packing is insufficient due to the leak of utilization of sparsity of A in online inference(Table 4,6), we thus introduce three techniques and put them together to support efficient FHE-GCN inference:

• Latency-aware packing: Optimizes packing for XW to enable dense SIMD computations.
• SpIntra-CA: A novel approach leverages irregular sparsity patterns during AX, enabling arbitrary desire node order and supporting parallel and non-redundant node aggregation.
• NOO: A reordering algorithm that groups nodes to enhance SpIntra-CA's computational efficiency while preserving XW performance.

To illustrate, in Figure 8(b) both parties iteratively determine the node packing order, starting from the final layer and back-propagating to the client's input based on NOO and SpIntra-CA. This reverse derivation is then integrated with our latency-aware strategy to derive the optimal packing method, achieving simultaneous optimization of both AX and XW computation.

2. Proof of upper bound rotation counts in SpIntra-CA (Q2)

Due to space constraints, we present the key proof arguments and the complete formal proof with notation tables is at https://anonymous.4open.science/r/FicGCN-D208. In our paper, n denotes the sampled neighbor counts.

The rotation counts of each stage in SpIntra-CA can be calculated as $\sum\_{k=0}^{i-1}Con_{k,j+\sum\_{p=0}^{k-1}2^p} \cdot \frac{1}{2^k}\leq \sum\_{k=0}^{i-1}2^k \cdot \frac{1}{2^k}$, is less than $log(N)$. Thus the total counts is $O(log^2(N))$ rather than $O(N)$. This can be formally proved by the Lemma 1 and Conflict Bound Analysis.

Analysis: 1) $Con_{i,j}$, the number of conflicts in the $i^{th}$ rotation stage at the $j^{th}$ slot, is the summation of all conflicts during the prior stages in the corresponding slots which can be rotated to $j^{th}$. 2) $PR(ct[m]\rightarrow ct[q])$, the the probability of rotating an element in $m^{th}$ slot to $q^{th}$. The case "$ct[j+\sum^{k-1}\_{p=0}2^p]\rightarrow ct[j]$" means that the rotation step($rs$) bits of an element in $ct[j+\sum^{k-1}\_{p=0}2^p]$ should be all ``1'' among the corresponding k contiguous bits.

Lemma 1: Given any bit distribution($Pr[bit_p=1]=\frac{1}{2}-\epsilon$), $PR(ct[j+\sum\_{p=0}^{k-1}2^p]\rightarrow ct[j])\le \frac{1}{2^k}$

Proof: Based on Analysis 2), we have $PR(ct[j+\sum\_{p=0}^{k-1}2^p]\rightarrow ct[j])\le \frac{1}{2^k}$ when $\epsilon>0$. When $\epsilon\le0$, by replacing cyclic left shifts with cyclic right shifts, the $rs$ bits become the complement of the original: $PR(ct[j+\sum^{k-1}\_{p=0}2^p]\rightarrow ct[j])=(\frac{1}{2}+\epsilon)^k \leq \frac{1}{2^k}$ So we have $PR(ct[j+\sum\_{p=0}^{k-1}2^p]\rightarrow ct[j])< \frac{1}{2^k}$ when $\epsilon\neq 0$

Conflict Upper Bound Analysis: $Con_{i,j} \leq log(N)$ under the worst case(uniform distribution).

Proof: According to Analysis 1), $Con_{i,j}=\sum\_{k=0}^{i-1}Con_{k,j+\sum\_{p=0}^{k-1}2^p} \cdot PR(ct[j+\sum\_{p=0}^{k-1}2^p]\rightarrow ct[j])$ According to Lemma 1, it is $\sum\_{k=0}^{i-1}Con_{k,j+\sum\_{p=0}^{k-1}2^p} \cdot \frac{1}{2^k}\leq \sum\_{k=0}^{i-1}2^k \cdot \frac{1}{2^k}=i \leq log(N)$ Thus, the number of conflicts per stage is bounded by log(N). Given that SpIntra-CA comprises log(N) stages, it yields a total conflict counts of less than $log^2(N)$ between an aggregation of two nodes.

3. Crypto primitives in FicGCN (Q3)

We use only FHE in FicGCN framework, with no other crypto primitives such as MPC.

4. Impact of masking on multiplicative depth

In CKKS, the consumption of multiplicative depth primarily stems from ciphertext rescaling operations. However, the masking procedures described in our work do not require such rescaling and introduce no additional burden on the multiplicative depth budget.

During CKKS, each floating-point message $m$ is first scaled by a precision parameter $\Delta$ and quantized to an integer before encryption: $c=Enc(\Delta \cdot m)\$. Consequently, when multiplying two ciphertexts with identical initial scales ($\Delta$), the resulting ciphertext's scale becomes $\Delta^2$: $c_1*c_2=Enc(\Delta\cdot m_1)*Enc(\Delta\cdot m_2)=Enc(\Delta^2\cdot(m_1\*m_2))$

CKKS employs rescaling operations to restore the ciphertext's scale to $\Delta$. However during Masking, we multiply the ciphertexts by plaintexts encoding integer 0/1 with the scale=1: $Enc(\Delta \cdot m) * Encode(1 \cdot mask) = Enc(\Delta \cdot (m*mask))$ Therefore the scale of ciphertexts remains invariant. Also, the results of Masking bit-length remains constant because we multiply them by 0/1. Thus the multiplicative depth will not be consumed during Masking.

Time complexity of Node Order Optimization (NOO) on large-scale datasets

Thanks for your constructive comments. We have extended the application of NOO to large-scale datasets Pokec (1.6M nodes). The following table summarizes the experimental results across datasets, including:

• Graph Statistics: Node count ($|V(G)|$), edge count ($|E(G)|$), and average degree ($d_{avg}$).
• Time Overhead: NOO preprocessing time ($T_{NOO}$) and online stage FHE computation latency ($T_{FHE}$).
• Efficiency Ratio: $\rho=T_{NOO}/T_{FHE}$

As shown in this table, NOO exhibits low time overhead on smaller datasets. For large-scale graphs like Pokec, NOO's overhead remains negligible relative to FicGCN's online phase. Notably, on large graphs, the client-side encryption time alone eclipses NOO's latency, ensuring NOO does not bottleneck FicGCN's performance.