Faster Homomorphic Linear Transformations in HElib

1. Introduction

R_{p} = \mathbb{Z}_{p}[X]/\Phi_{n}(X) \cong \bigoplus_{i=1}^{h} \mathbb{Z}_{p}[X] /(f_{i}(X))$$ where $\Phi_{n}(X) = \prod_{i=1}^{h}f_{i}(X)$ ${}^{\forall} f_{i}$ 次数 $d = p \mod n$ 既約??? なので

R_{p} \cong (\mathrm{GF}(p^{d}))^{h}\quad (dh = \phi(n))

なので, 平文空間を $\mathrm{GF(p^{d})}$ ともみれて, $h$ 個のslotsを並列に計算できる. ### Some useful automorphisms ${}^{\forall} j \in \mathbb{Z}_{n}^{*}$ はauto $a: R_{p} \ni X \to X_{j}$ をもつ - key-switchingが必要, これを使って, slotsの移動が出来る(rotation) $p \equiv 1 \pmod{n} \Rightarrow \Phi_{n}(X)$ は $\mathbb{Z}_{p}$ を完全に分ける ので

R_{p} = \mathbb{Z}{p}[X]/(\Phi{n}(X)) \cong \mathrm{GF}(p)^{h}\quad (h = \phi(n))

i so

[f(X) \bmod \phi_{n}(X)] \mapsto [f(\omega^{i})]{i \in \mathbb{Z}{n

$a$ によって

[f(\omega^{i})] \mapsto [f(\omega

slotsでいうと $ij \mapsto i$ - 一般論: 巡回群構造 $\mathbb{Z}_{n}^{*}/\langle p \rangle$でrotationが出来る ex. - $\mathbb{Z}_{n}^{*}/\langle p \rangle \cong \mathbb{Z}_{3} \times \mathbb{Z}_{3}$ は9 slots(3 * 3行列) - rowとcol自由にroll出来る [[2022-10-18]] #todo 論文の方も読む ## 参考文献 - [Faster Homomorphic Linear Transformations in HElib - YouTube](https://www.youtube.com/watch?v=LXmGVPcCVag)