Quartz 5

modulus chain

Properties1
tagsfhe/ckks

3 min read

2022-10-15

  • leveled HEでは演算中のノイズ増加を防ぐために, ModSwitch を行う必要がある
  • level= なら前もって 個のmodulus chainを作成する必要がある
  • なら60bitの素数2つと40bitの素数1つ用意
    • [0] はprimary bit で復号時に影響する, 60が推奨値(uint_64_t なので)
    • [1..<-1] はscaling bit
    • [-1] はlast bit, scalingの際は関係ない

Microsoft SEAL の例

In this example we use a custom coeff_modulus, consisting of 5 primes of
sizes 50, 30, 30, 50, and 50 bits. Note that this is still OK according to
the explanation in `1_bfv_basics.cpp'. Indeed,
CoeffModulus::MaxBitCount(poly_modulus_degree)
returns 218 (greater than 50+30+30+50+50=210).
Due to the modulus switching chain, the order of the 5 primes is significant.
The last prime has a special meaning and we call it the `special prime'. Thus,
the first parameter set in the modulus switching chain is the only one that
involves the special prime. All key objects, such as SecretKey, are created
at this highest level. All data objects, such as Ciphertext, can be only at
lower levels. The special prime should be as large as the largest of the
other primes in the coeff_modulus, although this is not a strict requirement.

		 special prime +---------+
								 |
								 v
coeff_modulus: { 50, 30, 30, 50, 50 } +---+ Level 4 (all keys; `key level')
										  |
										  |
	coeff_modulus: { 50, 30, 30, 50 } +---+ Level 3 (highest `data level')
										  |
										  |
		coeff_modulus: { 50, 30, 30 } +---+ Level 2
										  |
										  |
			coeff_modulus: { 50, 30 } +---+ Level 1
										  |
										  |
				coeff_modulus: { 50 } +---+ Level 0 (lowest level)

暗号文の実数の精度について

  • scaling_bit を小さくすると整数部分の精度が大きくなる

  • ex. のとき

    • 暗号中の整数部分の精度は primary_bit - scaling_bit = 20 bit
    • 小数部分は scaling_bit - 20bit = 20bit

  • 計算中に値が整数部分 bit 以上になるとoverflowして値が壊れる

  • 小数部分はノイズが乗るため, 20 bit より少し小さくなる

ので

  • 計算に扱う値の範囲によってを予めパラメータを把握
  • level を予め決める

参考文献

Graph View

Backlinks