準同型暗号を用いた高速化の例

概要

次世代の暗号技術というニュアンスで量子耐性をもつ格子暗号まとめ①, 量子耐性をもつ格子暗号まとめ②
などに記事を書かせていただきましたが、その中でも我々は格子暗号を使ったプラットフォームの研究開発を行っています。
格子暗号を使う際に一番のネックになるのが計算量が増えることです。例えば $2+3、2 \times 3$ という演算を暗号文で行う時、それぞれの数を数千次元（時には一万以上の次元）で記述される多項式にエンコードして演算を行う必要があります。有名な格子暗号ライブラリの使用感をまとめてみた。でも書いたような準同型暗号のライブラリは、この多次元の多項式の演算をNTLなどのライブラリを使って高速化しているわけですが、やはりボトルネック感はかなりあります。また、これらの計算を機械学習などに応用しようとするときの線形代数的な演算には、乗算や加算が大量に含まれているため、これらの演算をいかにして少なくするか、もしくは効率的に行うかが、準同型暗号の実用化への鍵となるわけです。

そこで、格子暗号の特徴でもあるパッキング（バッチングとも呼ばれる）を用いてベクトルとベクトルの内積を格子暗号下でいかに高速化するか、というトピックについて書いていきます。

また、この記事は基本的にHElibを用いてこれを解説している Scalar Product Using HElibの解説になります。

内容

ここでは、$a = [1,2,3]$ と $b = [2,3,4]$の 内積を格子暗号を用いて計算するときの例について書いていきます。

平文だったら

ベクトルとベクトルの内積なんて、暗号関係なければ

inner.py

import numpy as np

a = [1,2,3]
b = [2,3,4]

print(np.dot(a,b))

>>> 20

でかけるわけですよね。暗号文を用いて内積を取ろうと考えると、このような書き方は一切できなくなります。

ケース①　要素ごとに暗号化、演算

これがScalar Product Using HElibでいうところのmethod1 になります。
まず、$a, b$の各要素を暗号化し、リストとして持たせます。そのあとにfor文で各要素ごとの掛け算をして、結果を最後に足し合わせます。HElibでのコードは以下のようになります。

element_wise.cpp

// Vectors to hold the ciphertexts created from the elements of u and v
std::vector<Ctxt> encU;
std::vector<Ctxt> encV;
 
// Each element is encrypted individually
for (int i = 0; i < VEC_SIZE; i++) {
    Ctxt tempU(pk);
    pk.Encrypt(tempU, to_ZZX(u[i]));
    encU.push_back(tempU);
    Ctxt tempV(pk);
    pk.Encrypt(tempV, to_ZZX(v[i]));
    encV.push_back(tempV);
}


// Multiply the corresponding positions of vectors
// Store the result in encU
for (int i = 0; i < VEC_SIZE; i++) {
    encU[i] *= encV[i];
}

// Sum all the elements in encU
// Save the result in the first position of the vector
for (int i = 1; i < VEC_SIZE; i++) {
    encU[0] += encU[i];
}

// Decrypt the first position, which holds the value of the scalar product
// ZZX is a class from the NTL library that represents polynomials
ZZX result;
sk.Decrypt(result, encU[0]);
 
return result[0];

これだと、ベクトルの長さを$N$とした時に、$O(N^2)$で計算オーダー（暗号文同士の乗算）が増加していきます。また、エレメントごとに暗号化を行う必要があるので、ベクトルの長さが大きくなればなるほどそれにかかる時間や、メモリ消費量が増大していきます。

これでは行列計算など、特に機械学習などの大きな次元のベクトルに対しては計算コストやメモリ使用量がスケールしません。
そこで、パッキングと呼ばれる手法を使います。

ケース②　係数パッキングによる手法

計算パッキングでは、ベクトルの要素をそのまま多項式の係数に埋め込みます。HElibでは、これはNTLの関数のSetCoeffを使って実現できます。
$a = [1,2,3], b = [2,3,4]$の時、$a = 1 + 2x + 3x^2, b = 4 + 3x + 2x^2$と多項式にエンコードします。この時片方を逆方向に（この場合ではbが$2 + 3x + 4x^2 $ とする代わりに$4+3+2x^2$としています。）こうすることで、この２つの多項式を掛け算することで、内積の結果（この場合は30）が$a\times b$の係数のうちの１つに入っています。この例では、$a\times b = 4 + 11x + 20x^2 + 30x^3 + 20x^4 + 11x^5 + 4x^6$　となります。したがって、$x^3$　の係数を復号後に抽出することで内積の結果を得ることができます。コードはこちら。

coeff_pack.cpp

// ZZX is a class for polynomials from the NTL library
ZZX U, V;
 
// Set the length of the polynomial u(x) and v(x)
U.SetLength(VEC_SIZE);
V.SetLength(VEC_SIZE);
 
// Set the coefficients of the polynomials u(x) and v(x)
// Note that the elements from v are "inverted" when encoded into the coefficients of v(x)
 
for (int i = 0; i < VEC_SIZE; i++) {
    SetCoeff(U, i, u[i]); // u(x) = 1 + 2x + 3x^2 + 4x^3
    SetCoeff(V, (VEC_SIZE - 1) - i, v[i]); // v(x) = 4 + 3x + 2x^2 + 1x^3
}

// Ciphertexts that will hold the polynomials encrypted using public key pk
Ctxt encU(pk);
Ctxt encV(pk);
 
// Encrypt the polynomials into the ciphertexts
pk.Encrypt(encU, U);
pk.Encrypt(encV, V);

// Multiply the ciphertexts and store the result in encU
encU *= encV;


// Decrypt the multiplied ciphertext into a polynomial using the secret key sk
ZZX result;
sk.Decrypt(result, encU); 
 
return result[VEC_SIZE - 1];

ケース③　CRTパッキングによる手法

CRTパッキングは、多項式の係数にパッキングをする係数パッキングとは違い、使用している多項式環の部分環に数字を入れ込む形になります。この時の背景ではCRT(Chinese Reminder Theorem)を使っているので、CRTパッキングと呼ばれています。
これを用いると、一つの暗号文の部分空間に数字を複数入れ込むことができ、足し算や掛け算などの演算も、その部分空間で行われるので、いつものベクトルのような感覚で演算が行えます。ただ、部分空間を使うことの制約も往々にして存在します。CRTパッキングした暗号文にユニークな演算としてローテーションというものが存在します。ローテーションは、部分空間に入れ込まれた数字の位置をずらすことができる演算です。例えば、$a=[1,2,3]$としてパッキングしたものを一回右にローテーションすると、$a=[3,1,2]$となります。これは実際実用上たくさん使います。例えばCRTパッキングをしたあとに、すべてのパッキングした要素を合計したい時は、ローテーションを1回ずつして、足し合わせることで、各要素の総和を得ることができます。これを利用してベクトルの内積を取るときのコードが以下になります。

crt_pack.cpp

// Create a helper object based on the context
EncryptedArray ea(context, context.alMod.getFactorsOverZZ()[0]);
 
// Create vectors from the values from the arrays
// The vectors should have the same size as the EncryptedArray (ea.size),
// so fill the other positions with 0. This won't affect the result.
std::vector<long int> U(u, u + VEC_SIZE);
std::vector<long int> V(v, v + VEC_SIZE);
for (int i = VEC_SIZE; i < ea.size(); i++) {
    U.push_back(0);
    V.push_back(0);
}

// Ciphertexts that will hold the encrypted vectors
Ctxt encU(pk);
Ctxt encV(pk);
 
// Encrypt the whole vector into one ciphertext using packing
ea.encrypt(encU, pk, U);
ea.encrypt(encV, pk, V);


// Multiply ciphertexts and store the result in encU
encU.multiplyBy(encV);
 
// Use the totalSums functions to sum all the elements
// The result will have the sum in all positions of the vector
totalSums(ea, encU);

// Decrypt the result (i.e., the scalar product value)
ZZX result;
sk.Decrypt(result, encU);
 
return result[0];

どれだけ高速化されるのか

以上の３つのメソッドを用いて内積計算を行った時の速度比較が以下になります。

メソッド1の要素ごとの暗号化、乗算を行なってしまうと大幅に計算量が増加してしまうため、高速化を考えるときにはパッキングが必須になることが容易に想像できます。CRTパッキングは暗号文がベクトルのように扱えるため、幾つもの演算を行いやすいことも多いですが、その分ローテーションなどの演算が大量に挟まってくるので結果として高速化が思った以上に望まないこともあります。係数パッキングは、係数のどこに結果が落ちてくるかをしっかりとおわなければならないので、複数の演算をするのには向きませんが、いくつかの場面ではCRTパッキングで行うようなローテーションが要らないので、計算量としては低く抑えられることもあります。

まとめ

このように、格子暗号を用いた演算では、内積を取る際、いろいろな制約を踏まえていろいろなメソッドを駆使して計算をおこなう必要があります。この操作を気をつけながら行うことはかなり難しいですし、骨の折れる作業ですが、これをすることで演算の高速化や、省メモリ化に取り組んで行くのは非常に重要です。
弊社では、このような高速化のアルゴリズム(この内積計算など)を駆使して、秘密計算の高速化を図っています。このように格子暗号を用いた秘密計算では、どのようにパッキングを駆使して計算を高速化するかが非常に大切になってくるので、これからも多くの工夫がひつようになってきますね。今回はこの辺で。

おわり。