Go言語 + 準同型暗号 のライブラリ LattiGo のExample を解説 (advanced/lut)

概要

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

LattiGo

を触ってみました。

これの続編になります。

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

チュートリアルはこちら

今回解説するのは、

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

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

Exampleの中身
勉強したい方へ
の章で書いているので、まだ読んでいなければ読んでみてください。

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

プログラム実行方法

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

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

で実行可能です。

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

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

前提説明

以前のeuler のチュートリアルで

• xを暗号として e^x（イクスポネンシャル）の計算
  を実行した時や、

polyeval のチュートリアルで

• シグモイド関数

を暗号文に対して実行した時、どちらも多項式近似を用いて実行しました。

今回のLUTを使うと、任意の演算をルックアップテーブルのような感じで参照することで、
任意の関数に暗号を通すことができるようになります。

例えば、チュートリアルではsign関数（プラスの値だと＋１、マイナスの値だと−１を返す関数）
をCKKSに対して施しています。
sign関数はチュートリアル内に以下のように実装されています。

// ==============================
// Functions to evaluate with LUT
// ==============================
func sign(x float64) (y float64) {
	if x > 0 {
		return 1
	} else if x < 0 {
		return -1
	} else {
		return 0
	}
}

チュートリアル内の説明

main.go

// This example showcases how lookup tables can complement the CKKS scheme to compute non-linear functions
// such as sign. The example starts by homomorphically decoding the CKKS ciphertext from the canonical embeding
// to the coefficient embeding. It then evaluates the Look-Up-Table (LUT) on each coefficient and repacks the
// outputs of each LUT in a single RLWE ciphertext. Finally, it homomorphically encodes the RLWE ciphertext back
// to the canonical embeding of the CKKS scheme.

このように説明されています。少し私の言葉で翻訳します。

CKKS形式の暗号に対して、非線形関数を適用するために、ルックアップテーブルをどうやって使うかのチュートリアルである。CKKSを用いてルックアップテーブルを参照する時は、ステップは３つに分かれる。

• スロットパッキングから係数パッキングへのエンコーディング
• LUTをそれぞれの係数について計算し、結果はRLWE型の暗号になる
• そのRLWE型の暗号から、CKKS型かつスロット型の暗号形式に戻すでコーディング
  このステップにより、CKKS形式に対してLUTを実行することができる。

今回はadvanced と書いているだけあって、やっていることが結構ややこしいです。
踏み込みたくなければ、CKKS形式に対して非線形演算も実行可能であるとだけ理解してください。

それでは実際のチュートリアルプログラムの内容をできるだけ言葉で説明できるようにします。

チュートリアルの中身

パラメータの設定

main.go

	// Base ring degree
	LogN := 12

	// Q modulus Q
	Q := []uint64{0x800004001, 0x40002001} // 65.0000116961637 bits

	// P modulus P
	P := []uint64{0x4000026001} // 38.00000081692261 bits

	flagShort := flag.Bool("short", false, "runs the example with insecure parameters for fast testing")
	flag.Parse()

	if *flagShort {
		LogN = 6
	}

	// Starting RLWE params, size of these params
	// determine the complexity of the LUT:
	// each LUT takes N RGSW ciphertext-ciphetext mul.
	// LogN = 12 & LogQP = ~103 -> >128-bit secure.
	var paramsN12 ckks.Parameters
	if paramsN12, err = ckks.NewParametersFromLiteral(ckks.ParametersLiteral{
		LogN:     LogN,
		Q:        Q,
		P:        P,
		LogSlots: 4,
		LogScale: 32,
	}); err != nil {
		panic(err)
	}

	// LUT RLWE params, N of these params determine
	// the LUT poly and therefore precision.
	// LogN = 11 & LogQP = ~54 -> 128-bit secure.
	var paramsN11 ckks.Parameters
	if paramsN11, err = ckks.NewParametersFromLiteral(ckks.ParametersLiteral{
		LogN:     LogN - 1,
		Q:        Q[:1],
		P:        []uint64{0x42001},
		Pow2Base: 12,
	}); err != nil {
		panic(err)
	}

前回までのチュートリアルではパラメータは１種類の設定でしたが、
今回は２種類

• paramsN12
• paramsN11

が出てきます。

• paramsN12 はもともとの暗号化を実行する鍵のパラメータ
• paramsN11 はLUTを作って評価するための鍵のパラメータ

と考えてください。

リスケーリングの設定

main.go

	// Rescale inputs during Homomorphic Decoding by the normalization of the
	// LUT inputs and change of scale to ensure that upperbound on the homomorphic
	// decryption of LWE during the LUT evaluation X^{dec(lwe)} is smaller than N
	// to avoid negacyclic wrapping of X^{dec(lwe)}.
	diffScale := paramsN11.QiFloat64(0) / (4.0 * paramsN12.DefaultScale().Float64())
	normalization := 2.0 / (b - a) // all inputs are normalized before the LUT evaluation.

言っていることがややこしいですが、コメントの箇所を補足します。
もともとCKKS形式はスロットに平文をエンコーディングしたかたち（canonical embedding)ですが、
それを係数パッキングへとまず戻すことで、実質１個のRLWEとしての暗号を、N個のLWEの暗号へと置き換えることができます。そして、そのN個のLWEの暗号に対して、暗号状態のまま復号回路を計算します。
その復号回路は上ではdec(lwe)と書かれています。
このそれぞれの復号の結果が、N（こちらのNはLUTを作る時のパラメータのNであることに注意）より小さい値になるようにリスケーリングをそもそも行う必要があります。
そうしないと、LUTがNを超えて（ブラインド）ローテーションされた場合、LUTの係数の値が負の値になって位しまうからです。（これをto avoid negacyclicと表現していますね。）

したがって、diffScale を入力の暗号文に対してスケーリングの数として掛け算することになります。

エンコーディング、デコーディングの設定

main.go

	// SlotsToCoeffsParameters homomorphic encoding parameters
	var SlotsToCoeffsParameters = ckksAdvanced.HomomorphicDFTMatrixLiteral{
		Type:       ckksAdvanced.Decode,
		LogN:       paramsN12.LogN(),
		LogSlots:   paramsN12.LogSlots(),
		Scaling:    normalization * diffScale,
		LevelStart: 1,        // starting level
		Levels:     []int{1}, // Decomposition levels of the encoding matrix (this will use one one matrix in one level)
	}

	// CoeffsToSlotsParameters homomorphic decoding parameters
	var CoeffsToSlotsParameters = ckksAdvanced.HomomorphicDFTMatrixLiteral{
		Type:       ckksAdvanced.Encode,
		LogN:       paramsN12.LogN(),
		LogSlots:   paramsN12.LogSlots(),
		LevelStart: 1,        // starting level
		Levels:     []int{1}, // Decomposition levels of the encoding matrix (this will use one one matrix in one level)
	}

続いて先ほどの

• スロットから係数
• 係数からスロット

への変換のための

• エンコーダ（SlotsToCoeffsParameters)
• デコーダ（CoeffsToSlotsParameters)

のためのパラメータを設定しています。

LUT の生成

main.go

	fmt.Printf("Generating LUT... ")
	now := time.Now()
	// Generate LUT, provide function, outputscale, ring and interval.
	LUTPoly := lut.InitLUT(sign, paramsN12.DefaultScale(), paramsN12.RingQ(), a, b)
	fmt.Printf("Done (%s)\n", time.Since(now))

	// Index of the LUT poly and repacking after evaluating the LUT.
	lutPolyMap := make(map[int]*ring.Poly) // Which slot to evaluate on the LUT
	repackIndex := make(map[int]int)       // Where to repack slots after the LUT
	gapN11 := paramsN11.N() / (2 * paramsN12.Slots())
	gapN12 := paramsN12.N() / (2 * paramsN12.Slots())

	for i := 0; i < paramsN12.Slots(); i++ {
		lutPolyMap[i*gapN11] = LUTPoly
		repackIndex[i*gapN11] = i * gapN12
	}

LUTPoly := lut.InitLUT(sign, paramsN12.DefaultScale(), paramsN12.RingQ(), a, b)

の箇所でLUTを生成しています。
出力の型は(F *Poly)ですから、多項式になっています。
これがのちほどLUT参照の時に使われるLUT多項式です。

鍵の生成

main.go

	kgenN12 := ckks.NewKeyGenerator(paramsN12)
	skN12 := kgenN12.GenSecretKey()
	encoderN12 := ckks.NewEncoder(paramsN12)
	encryptorN12 := ckks.NewEncryptor(paramsN12, skN12)
	decryptorN12 := ckks.NewDecryptor(paramsN12, skN12)

	kgenN11 := ckks.NewKeyGenerator(paramsN11)
	skN11 := kgenN11.GenSecretKey()

	// Switchingkey RLWEN12 -> RLWEN11
	swkN12ToN11 := ckks.NewKeyGenerator(paramsN12).GenSwitchingKey(skN12, skN11)

今回はN12とN11の二つの鍵パラメータがありうます。
N12については

• 暗号化
• 復号
  が必要です。（N12のパラメータを持った暗号を作り、LUTの出力もN１２のものになるから）

N11については、LUTを計算するときに暗号がN11のパラメータのものであることから、
元々のN12の暗号をN11に変換するために、鍵交換と呼ばれる手法を使う必要があり、
そのときの鍵交換を行う鍵生成にN11の秘密鍵が必要なので、
skN11を生成しています。

さらに、鍵交換を行う鍵を

	// Switchingkey RLWEN12 -> RLWEN11
	swkN12ToN11 := ckks.NewKeyGenerator(paramsN12).GenSwitchingKey(skN12, skN11)

ここでswkN12ToN11として生成しています。

LUT の実行、後処理（デコード）

main.go

	fmt.Printf("Evaluating LUT... ")
	now = time.Now()
	// Extracts & EvalLUT(LWEs, indexLUT) on the fly -> Repack(LWEs, indexRepack) -> RLWE
	ctN12 = evalLUT.EvaluateAndRepack(ctN11, lutPolyMap, repackIndex, LUTKEY)
	fmt.Printf("Done (%s)\n", time.Since(now))

	fmt.Printf("Homomorphic Encoding... ")
	now = time.Now()
	// Homomorphic Encoding: [LUT(a), LUT(c), LUT(b), LUT(d)] -> [(LUT(a)+LUT(b)i), (LUT(c)+LUT(d)i)]
	ctN12, _ = evalCKKS.CoeffsToSlotsNew(ctN12, CoeffsToSlotsMatrix)

ここの

ctN12 = evalLUT.EvaluateAndRepack(ctN11, lutPolyMap, repackIndex, LUTKEY)

の箇所でLUTを参照するプログラムが走っています。
その後に、結果として出力されるRLWE型の暗号を、
スロットにパッキングさせるCKKS型の暗号に変換するデコードを

ctN12, _ = evalCKKS.CoeffsToSlotsNew(ctN12, CoeffsToSlotsMatrix)

ここで実行し、一連の作業がやっと終わることになります。

実行結果

--short を使って実際にチュートリアルを走らせてみます。
結果は

kmihara ~/Documents/lattigo $ go run examples/ckks/advanced/lut/main.go --short
Generating LUT... Done (62.676µs)
Gen SlotsToCoeffs Matrices... Done (511.524µs)
Encrypting bits of skLWE in RGSW... Done (6.089931ms)
Homomorphic Decoding... Done (659.9µs)
Evaluating LUT... Done (10.956626ms)
Homomorphic Encoding... Done (438.05µs)
-8.0000 -> (-1.0000-0.0000i)
-7.0000 -> (-1.0000-0.0000i)
-6.0000 -> (-1.0000+0.0000i)
-5.0000 -> (-1.0000-0.0000i)
-4.0000 -> (-1.0000-0.0000i)
-3.0000 -> (-1.0000+0.0000i)
-2.0000 -> (-1.0000-0.0000i)
-1.0000 -> (-1.0000+0.0000i)
 0.0000 -> ( 1.0000+0.0000i)
 1.0000 -> ( 1.0000-0.0000i)
 2.0000 -> ( 1.0000-0.0000i)
 3.0000 -> ( 1.0000+0.0000i)
 4.0000 -> ( 1.0000-0.0000i)
 5.0000 -> ( 1.0000-0.0000i)
 6.0000 -> ( 1.0000-0.0000i)
 7.0000 -> ( 1.0000-0.0000i)

となり、確かにsign関数を暗号文に対して実行できていることがわかりました。

まとめ

今回までで、LattigoのCKKSのチュートリアルを全てやってみましたが、
LUTをCKKS形式で実装がされていることは知らず、良い発見になりました。
実際のパラメータで運用できるかは工夫が要りそうですが、少なくともSEAL（マイクロソフトのライブラリ）
でできないことが実装してあり、チュートリアルも書いてあるのでどこかで使ってみようと思います。

余力があれば、Lattigo to WASM　もちょろっとやってみたいと思います。

今回はこの辺で。

@kenmaro