概要

この記事は

この続編になります。

今まで触る機会はなかったのですが、
Go言語で実装された格子暗号のライブラリ

LattiGo

を触ってみました。

Exampleフォルダにあったテストプログラムの解説などを少し書き、
実際に何をやっているExampleなのかを解説してみたいと思います。

今回解説するのは、

ここにある、euler のチュートリアルです。

導入については polyeval の解説のところで、

Exampleの中身
勉強したい方へ

の章で書いているので、まだ読んでいなければ読んでみてください。

この記事では早速プログラムの中身に入ります。

プログラム実行方法

go がインストールされているのは仮定します。

git clone https://github.com/tuneinsight/lattigo.git
go run examples/ckks/euler/main.go

で実行可能です。

チュートリアルがやっていることの理解

まずは、このeuler チュートリアルが、何をやっているのかを言葉で説明します。
全体像や前提知識を持った上で、実際にチュートリアルプログラムを実行してみましょう。

チュートリアルプログラムの中身

このチュートリアルでは、

xを暗号としてi*x （iは複素数です）の計算
xを暗号としてx/r(rは複素数です）の割り算の計算
xを暗号として e^x（イクスポネンシャル）の計算
xを暗号として x^r(xのr乗）の計算

をやっています。

パラメータ設定

main.go

	// Schemes parameters are created from scratch
	params, err := ckks.NewParametersFromLiteral(
		ckks.ParametersLiteral{
			LogN:         14,
			LogQ:         []int{55, 40, 40, 40, 40, 40, 40, 40},
			LogP:         []int{45, 45},
			LogSlots:     13,
			DefaultScale: 1 << 40,
		})
	if err != nil {
		panic(err)
	}

CKKS形式の格子暗号を構成するためのパラメータを設定しています。
特筆すべきは

LogQ: []int{55, 40, 40, 40, 40, 40, 40, 40},
の箇所です。これは暗号空間を構成するビットだと考えてください。

最初の５５と最後の４０は特別なビットであり、その間に書かれている40 がいくつあるか、
が基本的にこのスキームは何回掛け算が可能かどうかを表しています。
今回は、40, 40, 40, 40, 40, 40となっており、６回４０が書かれているので、
６回掛け算ができるように設定された（レベル６の）暗号ということになります。

この辺りのパラメータについては、

この記事でも言及しているので、興味がある人はご覧ください。

また、レベルが大きくなればなるほど、暗号のサイズや、暗号に対する演算の実行時間が変化します。
この辺りは一度

や

で言及しています。

とりあえず、格子暗号を構成する時のパラメータは設定により、
実行可能な掛け算回数が変化する、ということをまず頭に入れれば大丈夫です。

鍵生成、Encryptor などの生成

main.go


	fmt.Println()
	fmt.Println("=========================================")
	fmt.Println("         INSTANTIATING SCHEME            ")
	fmt.Println("=========================================")
	fmt.Println()

	start = time.Now()

	kgen := ckks.NewKeyGenerator(params)

	sk := kgen.GenSecretKey()

	rlk := kgen.GenRelinearizationKey(sk, 1)

	encryptor := ckks.NewEncryptor(params, sk)

	decryptor := ckks.NewDecryptor(params, sk)

	encoder := ckks.NewEncoder(params)

	evaluator := ckks.NewEvaluator(params, rlwe.EvaluationKey{Rlk: rlk})

	fmt.Printf("Done in %s \n", time.Since(start))

	fmt.Println()
	fmt.Printf("CKKS parameters: logN = %d, logSlots = %d, logQP = %d, levels = %d, scale= %f, sigma = %f \n", params.LogN(), params.LogSlots(), params.LogQP(), params.MaxLevel()+1, params.DefaultScale().Float64(), params.Sigma())

チュートリアルの最初である　polyeval
の時に説明したので割愛しますが、暗号化や復号、計算に必要なクラス、および公開鍵と秘密鍵を生成しています。

xを暗号として`i*x` （iは複素数です）の計算

main.go

	evaluator.MultByi(ciphertext, ciphertext)

	fmt.Printf("Done in %s \n", time.Since(start))

	for i := range values {
		values[i] *= complex(0, 1)
	}

特に言及することもないかと思いますが、evaluator.MultByi という関数が用意されているので、
この関数を用いて計算します。

xを暗号として`x/r`(rは複素数です）の割り算の計算

main.go

	ciphertext.Scale = ciphertext.Mul(rlwe.NewScale(r))

	fmt.Printf("Done in %s \n", time.Since(start))

ちょっと特殊な書き方に見えますが、rで割り算をする時は上のように記述します。

xを暗号として `e^x`（イクスポネンシャル）の計算

main.go

	coeffs := []complex128{
		complex(1.0, 0),
		complex(1.0, 0),
		complex(1.0/2, 0),
		complex(1.0/6, 0),
		complex(1.0/24, 0),
		complex(1.0/120, 0),
		complex(1.0/720, 0),
		complex(1.0/5040, 0),
	}

	poly := ckks.NewPoly(coeffs)

	if ciphertext, err = evaluator.EvaluatePoly(ciphertext, poly, ciphertext.Scale); err != nil {
		panic(err)
	}

exponential の計算は、テイラー展開によって上記のように近似を用いて計算することになるのを気をつける必要があります。
近似に使う関数は自分で計算して、多項式の係数をハードコードする必要があります。

xを暗号として `x^r`(xのr乗）の計算

main.go

	monomialBasis := ckks.NewPolynomialBasis(ciphertext, ckks.Monomial)
	monomialBasis.GenPower(int(r), false, params.DefaultScale(), evaluator)
	ciphertext = monomialBasis.Value[int(r)]

この書き方も少しクセがありますが、xのr乗を計算する時はこのように計算するようです。

実行

実行時の出力は、抜粋すると以下のようになります。

=========================================
              ENCRYPTION
=========================================

Done in 10.205499ms

Level: 7 (logQ = 335)
Scale: 2^36.000000
ValuesTest: (6.2831853043-0.0000000041i) (6.2831853118+0.0000000001i) (6.2831853130+0.0000000014i) (6.2831853006+0.0000000060i)...
ValuesWant: (6.2831853072+0.0000000000i) (6.2831853072+0.0000000000i) (6.2831853072+0.0000000000i) (6.2831853072+0.0000000000i)...




===============================================
        EVALUATION OF i*x on 8192 values
===============================================

Done in 355.806µs

Level: 7 (logQ = 335)
Scale: 2^36.000000
ValuesTest: (0.0000000041+6.2831853043i) (-0.0000000001+6.2831853118i) (-0.0000000014+6.2831853130i) (-0.0000000060+6.2831853006i)...
ValuesWant: (0.0000000000+6.2831853072i) (0.0000000000+6.2831853072i) (0.0000000000+6.2831853072i) (0.0000000000+6.2831853072i)...




===============================================
       EVALUATION of x/r on 8192 values
===============================================

Done in 2.579µs

Level: 7 (logQ = 335)
Scale: 2^40.000000
ValuesTest: (0.0000000003+0.3926990815i) (-0.0000000000+0.3926990820i) (-0.0000000001+0.3926990821i) (-0.0000000004+0.3926990813i)...
ValuesWant: (0.0000000000+0.3926990817i) (0.0000000000+0.3926990817i) (0.0000000000+0.3926990817i) (0.0000000000+0.3926990817i)...




===============================================
       EVALUATION of e^x on 8192 values
===============================================

Done in 157.055783ms

Level: 4 (logQ = 216)
Scale: 2^40.000000
ValuesTest: (0.9238795529+0.3826833613i) (0.9238795300+0.3826834865i) (0.9238795377+0.3826834266i) (0.9238795197+0.3826834168i)...
ValuesWant: (0.9238795325+0.3826834324i) (0.9238795325+0.3826834324i) (0.9238795325+0.3826834324i) (0.9238795325+0.3826834324i)...



===============================================
       EVALUATION of x^r on 8192 values
===============================================

Done in 43.04939ms

Level: 0 (logQ = 56)
Scale: 2^39.999976
ValuesTest: (0.9999998616-0.0000011272i) (1.0000002912+0.0000008298i) (1.0000000582-0.0000001272i) (0.9999997480-0.0000001268i)...
ValuesWant: (1.0000000000+0.0000000000i) (1.0000000000+0.0000000000i) (1.0000000000+0.0000000000i) (1.0000000000+0.0000000000i)...



=========================================
         DECRYPTION & DECODING
=========================================

Done in 747.037µs

Level: 0 (logQ = 56)
Scale: 2^39.999976
ValuesTest: (0.9999998616-0.0000011272i) (1.0000002912+0.0000008298i) (1.0000000582-0.0000001272i) (0.9999997480-0.0000001268i)...
ValuesWant: (1.0000000000+0.0000000000i) (1.0000000000+0.0000000000i) (1.0000000000+0.0000000000i) (1.0000000000+0.0000000000i)...

どの関数も暗号状態での計算がうまく実行できていることがわかります。

最後に
今回は Lattigo のチュートリアルのうち

euler
を実際に実行、検証してみました。
CKKS形式のチュートリアルは残り1つ

advanced/lut
があるので、別記事でまた解説紹介します。

今回はこの辺で

@kenmaro