FHE over the Integers and Modular Arithmetic Circuits

殆どのFHEは平文空間が
$\mathbb{Z}/2\mathbb{Z}$
, なのでboolean回路の準同型演算ができる.
some variantsはSIMD
$(\mathbb{Z}/2\mathbb{Z}{)}^m$
だったり拡大体
$\mathrm{GF}(2^m)$
だったりするがバイナリ
2を
$Q$
(奇素数)にすることはできないか? -> mod-Q arithmetic curcuitsを評価可能

$$c=pq+Qr+m,m\in \{0,\cdots ,Q-1\}$$

加算と乗算がmod Qでできるなら低次数=収まるの多項式をSHEで評価できる
FHE化はできるの？
復号の形:
$m=(c\mathrm{mod}p)\mathrm{mod}Q$
(squashing)をmod-Q算術回路で表さなければならない: ハードルは割り算
バイナリでは:

$$\frac{1}{p}\approx \sum s_i{y}_i$$

(
$y_i$
: 固定精度の実数)
$\sum s_i(c{y}_i)$
: 割り算は加算の繰り返しになる(なぜ?)