论文 2026/1023

更速之系数至槽与槽至系数于稀疏打包之密文应用CKKS自举

摘要

CKKS之自举，乃复恢近似密文可用模数预算之要器，遂使同态运算逾乎定阶电路。其要者，乃线性变换之对——CoeffToSlot与SlotToCoeff，用以移数据于槽表示，俾行同态模数约减，复返系数表示。于Cheon等（EUROCRYPT 2018）之稀疏打包设，有用数据据居短效槽向量，复现于全槽空间。今法于此，主用较小效维，而我法则利用其重复模式，得简且廉之变换。 是篇用重复槽模式，以增CoeffToSlot与SlotToCoeff之效率。每变换恒保乘积深\(1\)，而用同态算子较少。令\(N\)为环维，打包向量长\(n/2\)，书\(r=N/n\)为重复因子。每变换，当\(n\le r/2\)时，其费为一明文密文乘法及\(O(\log n)\)回转。当\(nr/2\),其成本为\(2n/r\)明文密文乘法，及\(O(\sqrt{2n/r}+\log r)\)回转。吾亦析新式\textsf{CoeffToSlot}布局所生辅格，证其合乎所求系数格之亚高斯界。是故\textsf{EvalMod}近似界仅需并集界之常量对数余量。 吾于OpenFHE中实此变换，并作为CKKS自举流程之一部而评之。设\(N=2^{16}\)，且所试稀疏维度\(n/2\le 1024\)，吾之变换较OpenFHE之深度1稀疏线性变换于稀疏密钥设置中速\(3.53\times\)至\(7.95\times\)。此使全自举流程速增\(1.71\times\)至\(5.28\times\)。均质密钥设置中亦见相似增益。增益最巨者，当\(n/2\le 512\)，吾法亦与深度3之OpenFHE基线竞，而减格四级。综观之，其示格重可减CKKS自举于稀疏打包设置中之实用成本。