<p>Homomorphic encryption (HE) is one of the mainstream cryptographic tools used to enable secure outsourced computation. A typical task is secure matrix computation, which is a fundamental operation used in various outsourced computing applications such as statistical analysis and machine learning. In this paper, we present a new framework for secure multiplication of two matrices with size <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1614_Article_IEq1.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">$r \times s$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>×</mo> <mi>s</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1614_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$s \times t$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo>×</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation> respectively, which requires only <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1614_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="61" /> </InlineMediaObject> <EquationSource Format="TEX">$O(\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> basic homomorphic operations if <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1614_Article_IEq4.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="59" /> </InlineMediaObject> <EquationSource Format="TEX">$rst \le n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mi>s</mi> <mi>t</mi> <mo>≤</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, where <i>n</i> is dimension of the polynomial ring used in RLWE encryption. Our method was implemented in HElib using the BGV scheme. Experimental results show that the new framework has significant advantage in efficiency when <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1614_Article_IEq4.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="59" /> </InlineMediaObject> <EquationSource Format="TEX">$rst \le n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mi>s</mi> <mi>t</mi> <mo>≤</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>. In this case, the new framework is 1.2 to 106.8 times faster than exiting algorithms in experiments.</p>

A new framework for fast homomorphic matrix multiplication

期刊论文
发表日期：

2025年3月15日

查看全文

Xiaopeng Zheng,
Hongbo Li,
Dingkang Wang

摘要

Homomorphic encryption (HE) is one of the mainstream cryptographic tools used to enable secure outsourced computation. A typical task is secure matrix computation, which is a fundamental operation used in various outsourced computing applications such as statistical analysis and machine learning. In this paper, we present a new framework for secure multiplication of two matrices with size $r \times s$ $r \times s$ and $s \times t$ $s \times t$ respectively, which requires only $O(\log n)$ $O (log n)$ basic homomorphic operations if $rst \le n$ $r s t \leq n$ , where n is dimension of the polynomial ring used in RLWE encryption. Our method was implemented in HElib using the BGV scheme. Experimental results show that the new framework has significant advantage in efficiency when $rst \le n$ $r s t \leq n$ . In this case, the new framework is 1.2 to 106.8 times faster than exiting algorithms in experiments.