NTRU-based bootstrapping is a high-performance variant of FHEW-like bootstrapping schemes. Its main computational bottleneck lies in the blind rotation step, which involves numerous external products. In this work, we propose multiple techniques to reduce the number of these costly operations, including the use of block binary keys, block ternary keys, and the integration of block keys with the key unrolling method. Specifically, our approach reduces the number of external products to \(n/\ell \) for block keys \(\textbf{B}_{k,\ell }\) ( \(\textbf{T}_{k,\ell }\) ), compared to n in FINAL (ASIACRYPT 2021) and n/2 in the key unrolling approach (CHES 2024). When combining block keys with key unrolling, the number can further be reduced to \(n/2\ell \) . We implemented our algorithms using the CHIFHE library. Under 128-bit security settings, using block binary keys \(\textbf{B}_{k,\ell }\) ( \(\ell =4\) ), block ternary keys \(\textbf{T}_{k,\ell }\) ( \(\ell =4\) ) and key unrolling on \(\textbf{B}_{n/2,2}\) achieve a speedup of \(1.12\times \) over the key unrolling method (CHES 2024) and \(1.73\times \) over FINAL (ASIACRYPT 2021). Notably, the last 2 algorithms increase memory usage by less than 15MB compared to the key unrolling method (CHES 2024).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Accelerating NTRU-Based Bootstrapping with Block Key Distributions

  • Jingwei Feng,
  • Baofeng Wu,
  • Dongdai Lin,
  • Binwu Xiang

摘要

NTRU-based bootstrapping is a high-performance variant of FHEW-like bootstrapping schemes. Its main computational bottleneck lies in the blind rotation step, which involves numerous external products. In this work, we propose multiple techniques to reduce the number of these costly operations, including the use of block binary keys, block ternary keys, and the integration of block keys with the key unrolling method. Specifically, our approach reduces the number of external products to \(n/\ell \) for block keys \(\textbf{B}_{k,\ell }\) ( \(\textbf{T}_{k,\ell }\) ), compared to n in FINAL (ASIACRYPT 2021) and n/2 in the key unrolling approach (CHES 2024). When combining block keys with key unrolling, the number can further be reduced to \(n/2\ell \) . We implemented our algorithms using the CHIFHE library. Under 128-bit security settings, using block binary keys \(\textbf{B}_{k,\ell }\) ( \(\ell =4\) ), block ternary keys \(\textbf{T}_{k,\ell }\) ( \(\ell =4\) ) and key unrolling on \(\textbf{B}_{n/2,2}\) achieve a speedup of \(1.12\times \) over the key unrolling method (CHES 2024) and \(1.73\times \) over FINAL (ASIACRYPT 2021). Notably, the last 2 algorithms increase memory usage by less than 15MB compared to the key unrolling method (CHES 2024).