概要

この記事は

この続編になります。

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

LattiGo

を触ってみました。

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

今回解説するのは、

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

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

Exampleの中身
勉強したい方へ

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

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

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

bootstrap という手法を、CKKS形式の格子暗号で実行しています。
CKKS形式は暗号に対して掛け算を実行する回数に制限がある、「レベル型」の準同型暗号でした。
レベルが例えば３であれば、「３回のみ」暗号に対して掛け算を実行することが可能です。
３回掛け算を実行し、もう一度掛け算を実行するためには、一度ユーザに暗号を復号してもらい、
消費したレベルをリセットする必要がありました。
bootstrapを利用すると、このリセットを暗号状態のまま実行することができます。
従って、レベル形式でありながら、「実質的に暗号状態でできる掛け算回数が無限」
になるため、非常に強力な手法です。

しかしながら、ブートストラップをやろうとすると演算が非常に重い（遅い）
ということを認識する必要があります。

また、CKKS形式のブートストラップは近似式を利用して復号に必要な関数を暗号状態で実行するものであり、
それに伴ってブートストラップ後の誤差が発生します。
つまり、１を暗号化してブートストラップを実行すると、１から少しズレた値が出力されるということです。
この辺りの実行速度や、実行時の誤差を確認するのが、このチュートリアルで検証したい内容になります。

チュートリアルの解説

注意

このExmample はメモリが最低16GB必要になります（下記の --short を用いればもっと少なくても大丈夫です）。
お使いのPCスペックに注意してください。

プログラム実行方法

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

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

で実行可能です。

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

パラメータ設定

main.go

	// Bootstrapping parameters
	// Two sets of four parameters each, DefaultParametersSparse and DefaultParametersDense,
	// (each index 0 to 3) ensuring 128 bit of security are available in
	// github.com/tuneinsight/lattigo/v4/ckks/bootstrapping/default_params.go
	//
	// LogSlots is hardcoded to 15 in the parameters, but can be changed from 1 to 15.
	// When changing LogSlots make sure that the number of levels allocated to CtS and StC is
	// smaller or equal to LogSlots.

	paramSet := bootstrapping.DefaultParametersSparse[0] // bootstrapping.DefaultParametersDense[0]
	ckksParams := paramSet.SchemeParams

	if *flagShort {
		ckksParams.LogN = 13
		ckksParams.LogSlots = 12
	}

	btpParams := paramSet.BootstrappingParams

	params, err := ckks.NewParametersFromLiteral(ckksParams)
	if err != nil {
		panic(err)
	}

	fmt.Println()
	fmt.Printf("CKKS parameters: logN = %d, logSlots = %d, H(%d; %d), logQP = %d, levels = %d, scale= 2^%f, sigma = %f \n", params.LogN(), params.LogSlots(), params.HammingWeight(), btpParams.EphemeralSecretWeight, params.LogQP(), params.QCount(), math.Log2(params.DefaultScale().Float64()), params.Sigma())

ここでやっていることは、パラメータの設定です。
全てlattigoにあらかじめ設定されたセキュリティビット128に準じたパラメータを使用しています。

btpParams := paramSet.BootstrappingParams

の箇所で生成しているbootstrap用のパラメータもデフォルトのものです。

	params, err := ckks.NewParametersFromLiteral(ckksParams)
	if err != nil {
		panic(err)
	}

の箇所で、設定したパラメータが実行可能なものか検証されています。

鍵の生成

main.go


	// Scheme context and keys
	kgen = ckks.NewKeyGenerator(params)

	sk, pk = kgen.GenKeyPair()

	encoder = ckks.NewEncoder(params)
	decryptor = ckks.NewDecryptor(params, sk)
	encryptor = ckks.NewEncryptor(params, pk)

	fmt.Println()
	fmt.Println("Generating bootstrapping keys...")
	evk := bootstrapping.GenEvaluationKeys(btpParams, params, sk)
	fmt.Println("Done")

	if btp, err = bootstrapping.NewBootstrapper(params, btpParams, evk); err != nil {
		panic(err)
	}

の箇所で、

鍵の生成
Encryptor の生成
Decryptor の生成
Encoder の生成

を実行しています。
これらについては、前回の解説でも言及したので割愛します。

以前と違うのは、最後の

main.go


	if btp, err = bootstrapping.NewBootstrapper(params, btpParams, evk); err != nil {
		panic(err)
	}

の箇所です。

bootstrapping.NewBootstrapper により、
bootstrap を実行する時のUtil Class を生成しています。

暗号化

main.go

	// Generate a random plaintext
	valuesWant := make([]complex128, params.Slots())
	for i := range valuesWant {
		valuesWant[i] = utils.RandComplex128(-1, 1)
	}

	plaintext := encoder.EncodeNew(valuesWant, params.MaxLevel(), params.DefaultScale(), params.LogSlots())

	// Encrypt
	ciphertext1 := encryptor.EncryptNew(plaintext)

	// Decrypt, print and compare with the plaintext values
	fmt.Println()
	fmt.Println("Precision of values vs. ciphertext")
	valuesTest1 := printDebug(params, ciphertext1, valuesWant, decryptor, encoder)

ここでは、以下のことを実行しています。

入力となる平文をランダムに生成
Encoderにより、CKKS形式が暗号化する多項式へとマッピング
暗号化
デバッグのための復号、結果のプリント

これらについても前回のチュートリアルで解説をしたので、内容は割愛しますが、
やっていることは平文を作って暗号化し、次にbootstrap を利用する準備をしたということです。

bootstrap

main.go

	// Bootstrap the ciphertext (homomorphic re-encryption)
	// It takes a ciphertext at level 0 (if not at level 0, then it will reduce it to level 0)
	// and returns a ciphertext at level MaxLevel - k, where k is the depth of the bootstrapping circuit.
	// CAUTION: the scale of the ciphertext MUST be equal (or very close) to params.DefaultScale()
	// To equalize the scale, the function evaluator.SetScale(ciphertext, parameters.DefaultScale()) can be used at the expense of one level.
	fmt.Println()
	fmt.Println("Bootstrapping...")
	ciphertext2 := btp.Bootstrap(ciphertext1)
	fmt.Println("Done")

コメント箇所が言及しているのは、bootstrapを実行する時の注意点です。
bootstrapに入力する暗号文のスケールと呼ばれるもの（暗号空間の大きさになります）は、
デフォルトのスケール（params.DefaultScale()）と同じでなければならず、
もし違う時は
evaluator.SetScale(ciphertext, parameters.DefaultScale()) を利用しなければならない、
それをやるにはレベルを１消費する。
ということになります。

実際にbootstrapを実行しているのは

ciphertext2 := btp.Bootstrap(ciphertext1)
の箇所になります。

結果の確認

実行したブートストラップ後の暗号文には誤差が出るとお話ししましたが、
その誤差を最後に復号してどの程度か確かめています。

main.go

	// Decrypt, print and compare with the plaintext values
	fmt.Println()
	fmt.Println("Precision of ciphertext vs. Bootstrapp(ciphertext)")
	printDebug(params, ciphertext2, valuesTest1, decryptor, encoder)

実行

実行は

go run main.go

もしくは、検証用に小さいパラメータを使用するのであれば

go run main.go --short

で実行することができます。

結果として

ValuesTest: (0.0492218402-0.0485137536i) (-0.7822253275+0.1107204568i) (0.7450100138+0.8580748652i) (0.7988196376-0.5790897159i)...
ValuesWant: (0.0492218309-0.0485137523i) (-0.7822253477+0.1107204545i) (0.7450100392+0.8580748886i) (0.7988196623-0.5790897292i)...

というように誤差も小さく、ブートストラップを実行できることが検証できました。

最後に

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

bootstrap

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

euler
advanced/lut

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

今回はこの辺で

@kenmaro