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

概要

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

LattiGo

を触ってみました。

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

Exampleの中身

今回は、一番実用上使うであろうCKKS形式について解説しようかと思います。

フォルダの中には以下のような４つのフォルダがあり、それぞれチュートリアルプログラムが入っています。

取り組む順番

この中では難易度的に

• polyeval
• bootstrapping
• euler
• advanced/lut

の順にやってみるのがいいと思います。
それぞれのチュートリアルは、初めて準同型暗号について触るのであれば何をやっているのかわかりにくいかと思いますが、
一度理解してしまえば大丈夫なはずです。
実装だけを考えれば、プログラムが何をやっていて、自分がやりたいことがこれとこれを組み合わせればできそうだとか、
もしかすると足りない関数を実装しなければならないなど分かれば十分です。

勉強したい方へ

格子暗号やCKKS形式などの中身がどう動いているかに踏み込んでいくと、難易度は高くなります。
論文や解説記事などを読み込むことになると思います。

中身に興味がある方、もっと理論も交えながら最先端の格子暗号について勉強もしたいという方は

こちらのロードマップをお勧めします。

さらに、数学のレイヤまで研究レベルで勉強したいという方は、

こちらのロードマップもお勧めします。

プログラム実行方法

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

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

で実行可能です。

polyeval

さて、最初のチュートリアルについてみてみます。

main.go

	// This example packs random 8192 float64 values in the range [-8, 8]
	// and approximates the function f = 1/(exp(-x) + 1) over the range [-8, 8]
	// for the even slots and the function g = f * (1-f) over the range [-8, 8]
	// for the odd slots.
	// The result is then parsed and compared to the expected result.

ここに書いてあることは、このチュートリアルで実行することの説明です。
[-8, 8] の間にある数字をランダムに取ってきて、
それを平文とします。

平文を暗号化した後に、シグモイド関数を暗号状態で計算し、復号します。
平文で普通に計算したときの結果と比較して、暗号状態での計算がうまく行っていることを示します。

というようなプログラムになります。

	// Scheme params are taken directly from the proposed defaults
	params, err := ckks.NewParametersFromLiteral(ckks.PN14QP438)
	if err != nil {
		panic(err)
	}

セキュリティパラメータを設定している箇所です。
格子暗号は、セキュリティを担保する数学の問題として
LWE問題を使っていますが、そのLWE問題を構成するときにノイズの大きさや、格子空間の大きさなど
パラメータを設定する必要があります。
LWE問題は簡単に設定しすぎると暗号として弱いものになってしまいますし、
逆に難しく設定しすぎると暗号文が大きくなりすぎたり、計算がとても遅くなったりするため、
「いい感じの」パラメータを設定することが必要ですが、パラメータ設定は難しいテーマです。
研究者たちが今の所使用しているセキュリティパラメータが存在しているので、ここではそれを使っています。

main.go

	encoder := ckks.NewEncoder(params)

ここではエンコーダを定義しています。
CKKS形式では、数字をそのまま暗号化するのではなく、スケールと呼ばれる定数を掛け算し、
さらにヴァンデルモンデ行列という行列を掛け算してから、暗号化の入力となる多項式を作ります。
そのためのエンコーダはここで作っています。

main.go

	// Keys
	kgen := ckks.NewKeyGenerator(params)
	sk, pk := kgen.GenKeyPair()

	// Relinearization key
	rlk := kgen.GenRelinearizationKey(sk, 1)

ここでは鍵の生成を行っています。
sk, pk はそれぞれ秘密鍵、公開鍵です。

それではrlkはなんなのか、と思われると思いますが、
Relinearization Key (再線形化鍵）と呼ばれるもので、格子暗号特有のものです。
rlk は暗号同士を掛け算するときに使います。
詳細は省きますが、格子暗号では、暗号同士の掛け算は足し算に比べて複雑です。
掛け算した後の暗号は、大きさが増大するため、元々の大きさに戻す必要があります。
そのときに使う鍵がrlkであり、その時の操作を再線形化といいます。

また、掛け算を実行できる回数にも制限があります。
GenRelinearizationKey(sk, 1)　
となっていますが、この１は掛け算が１回のみできる鍵を生成しています。
回数制限は１回と設定しているので、x**3 （3乗）などは計算不可能です。
回数の設定回数を大きくすると汎用性が高まるように見えますが、この回数を大きくすると暗号としては重くなるため、ここの設定は実用性と汎用性のトレードオフになります。
この回数のことを「レベル」と呼びますが、詳しくは

この記事を読んでいただければと思います。

さて、

main.go

	// Encryptor
	encryptor := ckks.NewEncryptor(params, pk)

	// Decryptor
	decryptor := ckks.NewDecryptor(params, sk)

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

ここでは

• Encryptor
• Decryptor
• Evaluator

を生成していますが、名前の通りそれぞれ

• 暗号化
• 復号
• 計算

をするときに使うutilクラスです。
先ほどのrlkは掛け算するときに必要だと言いましたが、evaluator にrlkを持たせているところがポイントです。

main.go

	// Values to encrypt
	values := make([]float64, params.Slots())
	for i := range values {
		values[i] = utils.RandFloat64(-8, 8)
	}

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

	fmt.Println()
	fmt.Printf("Values     : %6f %6f %6f %6f...\n",
		round(values[0]), round(values[1]), round(values[2]), round(values[3]))
	fmt.Println()

	// Plaintext creation and encoding process
	plaintext := encoder.EncodeNew(values, params.MaxLevel(), params.DefaultScale(), params.LogSlots())

	// Encryption process
	var ciphertext *rlwe.Ciphertext
	ciphertext = encryptor.EncryptNew(plaintext)

ここでは平文として入力する数値をランダムで生成しています。
さらに、先ほど言及した通り、エンコードをして暗号化するための準備をしています。
最後に、先ほどのEncryptor を使って、暗号化を実行しています。

main.go

	a, b := -8.0, 8.0
	deg := 63

	fmt.Printf("Evaluation of the function f(x) for even slots and g(x) for odd slots in the range [%0.2f, %0.2f] (degree of approximation: %d)\n", a, b, deg)

	// Evaluation process
	// We approximate f(x) in the range [-8, 8] with a Chebyshev interpolant of 33 coefficients (degree 32).
	approxF := ckks.Approximate(f, a, b, deg)
	approxG := ckks.Approximate(g, a, b, deg)

ここでは、暗号状態でシグモイド関数を計算するためのパラメータを設定しています。
暗号状態でシグモイド関数のような非線形関数を計算するためには、テイラー展開による近似が必要です。
ここでは、チェビシェフ近似を使っており、そのためには近似する関数の定義域を設定する必要があります。
定義域は暗号の入力の領域であった[-8, 8] を設定し、
近似の精度については63を設定しています（何次の多項式で打ち切るか）。
f, g はそれぞれシグモイド関数と、シグモイド関数の微分として定義されています。

次に、

main.go

	// Map storing which polynomial has to be applied to which slot.
	slotsIndex := make(map[int][]int)

	idxF := make([]int, params.Slots()>>1)
	idxG := make([]int, params.Slots()>>1)
	for i := 0; i < params.Slots()>>1; i++ {
		idxF[i] = i * 2   // Index with all even slots
		idxG[i] = i*2 + 1 // Index with all odd slots
	}

	slotsIndex[0] = idxF // Assigns index of all even slots to poly[0] = f(x)
	slotsIndex[1] = idxG // Assigns index of all odd slots to poly[1] = g(x)

の記述で、あまり見慣れないですが二つの関数を暗号文に対して適用しています。
スロットと書かれているのは、平文のベクトルと同じだと考えてください。
例えば、１つの暗号にスロットが１００個ある時は、１００個の数字を１つの暗号にそのまま暗号化することができます。
これを使うと、ベクトルをそのまま暗号化することができるので、１つ１つ数字を暗号化するより効率的ですし、
１つの暗号に演算を加えることで、暗号状態でのベクトル演算のようなことを行うことができるので、実用上効率的です。

ここでは、スロットの偶数番目と奇数番目に対してそれぞれ異なる関数を適用する、
という例を行っています。
実用上このようなオペレーションを行うことがあるかは別として、このような使い方がLattigoだとできることを覚えておきましょう。

ここまで終わったら、次で実際に暗号に対してチェビシェフ多項式近似を実行しています。

main.go

	// Change of variable
	evaluator.MultByConst(ciphertext, 2/(b-a), ciphertext)
	evaluator.AddConst(ciphertext, (-a-b)/(b-a), ciphertext)
	if err := evaluator.Rescale(ciphertext, params.DefaultScale(), ciphertext); err != nil {
		panic(err)
	}

	// We evaluate the interpolated Chebyshev interpolant on the ciphertext
	if ciphertext, err = evaluator.EvaluatePolyVector(ciphertext, []*ckks.Polynomial{approxF, approxG}, encoder, slotsIndex, ciphertext.Scale); err != nil {
		panic(err)
	}

	fmt.Println("Done... Consumed levels:", params.MaxLevel()-ciphertext.Level())

まず、

main.go

	evaluator.MultByConst(ciphertext, 2/(b-a), ciphertext)
	evaluator.AddConst(ciphertext, (-a-b)/(b-a), ciphertext)

この2行については、なぜこんなことをしているのかと少し戸惑うかもしれませんが、
EvaluatePolyVectorに書かれているドキュメンテーションをみてみると、
以下のように書かれています。

EvaluatePolyVector evaluates a vector of Polynomials on the input Ciphertext in ceil(log2(deg+1)) levels. Returns an error if the input Ciphertext does not have enough level to carry out the full polynomial evaluation. Returns an error if something is wrong with the scale. Returns an error if polynomials are not all in the same basis. Returns an error if polynomials do not all have the same degree. If the polynomials are given in Chebyshev basis, then a change of basis ct' = (2/(b-a)) * (ct + (-a-b)/(b-a)) is necessary before the polynomial evaluation to ensure correctness. Coefficients of the polynomial with an absolute value smaller than "IsNegligibleThreshold" will automatically be set to zero if the polynomial is "even" or "odd" (to ensure that the even or odd property remains valid after the "splitCoeffs" polynomial decomposition). input: must be either *rlwe.Ciphertext or *PolynomialBasis. pols: a slice of up to 'n' *Polynomial ('n' being the maximum number of slots), indexed from 0 to n-1. encoder: an Encoder. slotsIndex: a map[int][]int indexing as key the polynomial to evaluate and as value the index of the slots on which to evaluate the polynomial indexed by the key. targetScale: the desired output scale. This value shouldn't differ too much from the original ciphertext scale. It can for example be used to correct small deviations in the ciphertext scale and reset it to the default scale.

Example: if pols = []*Polynomial{pol0, pol1} and slotsIndex = map[int][]int:{0:[1, 2, 4, 5, 7], 1:[0, 3]}, then pol0 will be applied to slots [1, 2, 4, 5, 7], pol1 to slots [0, 3] and the slot 6 will be zero-ed.

• チェビシェフ近似により、使用されるレベル（暗号文に対して使用される掛け算回数です）は、log2(deg+1)となる

この例では、deg = 63 でしたので、log2(64) となり、６回となります。
６のレベルが消費されますから、暗号は６回以上は掛け算ができるような設定で構成されている必要があります。（例えば５回しか掛け算できない設定だと、エラーとなります。）

• a change of basis ct' = (2/(b-a)) * (ct + (-a-b)/(b-a))

このようにチェビシェフ近似する前に暗号文をスケーリングする必要がある、と書かれています。
これが、先ほど

main.go

	evaluator.MultByConst(ciphertext, 2/(b-a), ciphertext)
	evaluator.AddConst(ciphertext, (-a-b)/(b-a), ciphertext)

このように記載されていた理由です。

このスケーリングは、MultByConst で掛け算を暗号に対して使用していることに注意です。
掛け算をしたのであれば、再線形化を行う必要がありました。したがって、

main.go

	if err := evaluator.Rescale(ciphertext, params.DefaultScale(), ciphertext); err != nil {
		panic(err)
	}

としてRescale(再線形化と読み替えて良い）が実行されているというわけです。

その後、

main.go

	// We evaluate the interpolated Chebyshev interpolant on the ciphertext
	if ciphertext, err = evaluator.EvaluatePolyVector(ciphertext, []*ckks.Polynomial{approxF, approxG}, encoder, slotsIndex, ciphertext.Scale); err != nil {
		panic(err)
	}

により、チェビシェフ近似が暗号文に対して実行されています。

最後に、どれだけのレベルが消費されたか（暗号文に対して何回の掛け算が実行されたか）を表示するために、

main.go

fmt.Println("Done... Consumed levels:", params.MaxLevel()-ciphertext.Level())

と記述されています。実行すると、

Done... Consumed levels: 7

と表示されるので、７回掛け算が暗号文に対して実行されたことがわかります。
このうち６回はチェビシェフ近似によるものであり、１回はスケーリングしたときの掛け算であることがわかりますね。

このあとの

main.go

	// Computation of the reference values
	for i := 0; i < params.Slots()>>1; i++ {
		values[i*2] = f(values[i*2])
		values[i*2+1] = g(values[i*2+1])
	}

	// Print results and comparison
	printDebug(params, ciphertext, values, decryptor, encoder)

では、（暗号関係なく）平文でシグモイド関数とシグモイド関数の微分を入力に対して計算して、
暗号文で計算したものと結果を比較している部分になります。

私が実行した際は、

ValuesTest: 0.9920008534 0.1563421734 0.9350766912 0.0044446872...
ValuesWant: 0.9919994167 0.1563411647 0.9350772942 0.0044445975...

と表示され、

• ValuesTestが暗号文での結果
• ValuesWantが平文での結果

となり、CKKS特有の「ノイズ」が少し入るものの、計算が暗号文状態でも実行できていることが確認できました。

以上でpolyevalのチュートリアルは終了となります。
お疲れ様でした。

続きます

コードを書いていると長くなってしまったので、

• bootstrapping
• euler
• advanced/lut

は次の記事に分けて書きます。

今回はこの辺で

@kenmaro