Abstract:Homomorphic encryption (HE) enables computation over encrypted data but incurs a substantial overhead. For sparse matrix-vector multiplication, the widely used Halevi-Shoup scheme works over the non-empty diagonals, which may be many due to the irregular nonzero pattern of the matrix. Existing HE matrix-vector methods either use dense diagonal packing, which wastes rotations on empty diagonals, or sparse-coordinate compression, which can expose structural metadata. In this work, we instead keep the diagonal-method representation but reorder rows and columns to reduce the number of occupied cyclic diagonals. We formalize this problem as the 2D-diagonal packing problem and provide an integer programming formulation that yields optimal solutions for small instances. For large matrices, we propose practical ordering and iterative-improvement-based optimization heuristics. We also introduce a dense row/column elimination strategy. Experiments on 175 real-life matrices show that our ordering-optimization variants can reduce the diagonal count by $5.5\times$ on average ($45.6\times$ for one instance). In addition, the dense row/column elimination approach can be useful for cases where the proposed permutation techniques are not sufficient; for instance, in one case, the additional elimination helped to reduce the encrypted multiplication cost by $23.7\times$ whereas without elimination, the improvement was only $1.9\times$.
From: Deniz Elbek [view email]
[v1]
Mon, 6 Apr 2026 13:48:39 UTC (1,524 KB)
[v2]
Thu, 9 Jul 2026 11:19:40 UTC (824 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。